「Designing Data-Intensive Applications」Chapter 7
The Slippery Concept of a Transaction The Meaning of ACID The safety guarantees provided by transactions are often described by the well-known acronym ACID, which stands for Atomicity, Consistency, Isolation, and Durability. However, in practice, one database’s implementation of ACID does not equal another’s implementation. Atomicity Atomicity describes what happens if a client wants to make … Continue reading "「Designing Data-Intensive Applications」Chapter 7"
Read MorePolynomial Multiplication
Given two polynomials and of degree-bound : Multiply and , we get the product with coefficients: Here is also called the Convolution of and (denoted ). If we calculate by multiplying each term in by each term in and then combining terms with equal powers (exactly the old way we learnt in the junior high school), the time complexity would … Continue reading "Polynomial Multiplication"
Read More[Algorithm 101] Shortest Path Problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Dijkstra’s algorithm For a given vertex called the source in a weighted connected graph, Dijkstra’s Algorithm can find the shortest paths to all the graph’s other vertices. This algorithm is applicable to both undirected … Continue reading "[Algorithm 101] Shortest Path Problem"
Read MoreOperational Transformation
Back to I was in a startup company two years ago, we were going to develop an online video chatroom over WebRTC with a collaborative real-time editor to share codes or thoughts for online interviews. Starting to build the editor from scratch seemed quite challenging for us at that time, so we chose etherpad-lite, an … Continue reading "Operational Transformation"
Read More「Designing Data-Intensive Applications」Chapter 6
Partitioning Normally, partitions are defined in such a way that each piece of data belongs to exactly one partition. Partitioning and Replication Partitioning is usually combined with replication so that copies of each partition are stored on multiple nodes. A node may store more than one partition. If a leader–follower replication model is used, the combination … Continue reading "「Designing Data-Intensive Applications」Chapter 6"
Read More[Algorithm 101] Topological Sorting
A directed acyclic graph (DAG) is not only necessary but also sufficient for topological sorting to be possible. DFS Perform a DFS traversal and note the order in which vertices become dead-ends (i.e., popped off the traversal stack). Reversing this order yields a solution to the topological sorting problem, provided, of course, no back edge has been encountered … Continue reading "[Algorithm 101] Topological Sorting"
Read MoreMatrix Multiplication: A Programmer’s Perspective
The problem find the nth fibonacci number(A000045) has an optimal solution: matrix multiplication. Similarly, the matrix representation of sequence An = An-1 + An-2 + An-3 (A000073) is: By using matrix multiplication, we can reduce the time complexity from O(n) to O(logn). In linear algebra textbooks, matrix multiplication is the composition of two linear functions. Suppose: Represent … Continue reading "Matrix Multiplication: A Programmer’s Perspective"
Read More「Designing Data-Intensive Applications」Chapter 5
Replication Leaders and Followers Synchronous Versus Asynchronous Replication An important detail of a replicated system is whether the replication happens synchronously or asynchronously. It is impractical for all followers to be synchronous: any one node outage would cause the whole system to grind to a halt. In practice, if you enable synchronous replication on … Continue reading "「Designing Data-Intensive Applications」Chapter 5"
Read More「Designing Data-Intensive Applications」Chapter 4
Encoding and Evolution In order for the system to continue running smoothly, we need to maintain compatibility in both directions: Backward compatibility: newer code can read data that was written by older code. Forward compatibility: older code can read data that was written by newer code. Formats for Encoding Data Programs usually work with … Continue reading "「Designing Data-Intensive Applications」Chapter 4"
Read MoreOnline Judge from Scratch(3) – Sandbox
This article consists of two parts: the sandbox for GCC and the sandbox for the compiled binary. the sandbox for GCC Essentially, our sandbox for GCC is a wrapper of GCC with a watchdog, just like the sandbox we designed for the Java compiler. However, there are more situations need to be considered carefully for GCC. In … Continue reading "Online Judge from Scratch(3) – Sandbox"
Read More