diff options
Diffstat (limited to 'chapter')
21 files changed, 532 insertions, 53 deletions
diff --git a/chapter/1/rpc.md b/chapter/1/rpc.md index ccc9739..36d195d 100644 --- a/chapter/1/rpc.md +++ b/chapter/1/rpc.md @@ -36,7 +36,7 @@ Originally, RPC was developed as a synchronous request-response mechanism, tied Modern RPC-based systems are language-agnostic, asynchronous, load-balanced systems. Authentication and authorization to these systems have been added as needed along with other security features. Most of these systems have fault-handling built into them as modules and the systems are generally spread all across the internet. -RPC programs have a network (or a communication channel), therefore, they need to handle remote errors and be able to communication information successfully. Error handling generally varies and is categorized as *remote-host* or *network* failure handling. Depending on the type of the system, and the error, the caller (or the callee) return an error and these errors can be handled accordingly. For asynchronous RPC calls, it's possible to specify events to ensure progress. +RPC programs have a network (or a communication channel), therefore, they need to handle remote errors and be able to communicate information successfully. Error handling generally varies and is categorized as *remote-host* or *network* failure handling. Depending on the type of the system, and the error, the caller (or the callee) return an error and these errors can be handled accordingly. For asynchronous RPC calls, it's possible to specify events to ensure progress. RPC implementations use a *serialization*(also referred to as *marshalling* or *pickling*) scheme on top of an underlying communication protocol (traditionally TCP over IP). These *serialization* schemes allow both the caller *caller* and *callee* to become language agnostic allowing both these systems to be developed in parallel without any language restrictions. Some examples of serialization schemes are JSON, XML, or Protocol Buffers {% cite grpc --file rpc %}. diff --git a/chapter/6/counters.md b/chapter/6/counters.md new file mode 100644 index 0000000..67e822a --- /dev/null +++ b/chapter/6/counters.md @@ -0,0 +1,319 @@ +--- +layout: page +title: "Counters" +by: "Aviral Goel" +--- + +Counters are replicated integers. They are the most basic distributed object. This chapter describes the different variations of counter CRDT in both state based and operation based form. + +## 1. G-counter - Increment only counter + +As the name suggests, these counters only support increment operation. They can be used to implement the `like` button functionality of social media websites. + +### 1.1. CmRDT: Operation based design + +In the operation based implementation, the increment operation is transmitted to all other replicas. +This is straightforward to implement as there is only one update operation. + +<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CmRDT): + + <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self): <span style="color:#919191"># constructor function</span> + self._count <span style="color:#ff5600">=</span> 0 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> self._count + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self): <span style="color:#919191"># update function</span> + self._count <span style="color:#ff5600">+=</span> 1 + <span style="color:#ff5600">for</span> replica <span style="color:#ff5600">in</span> self.replicas(): + self.transmit(<span style="color:#00a33f">"increment"</span>, replica) + +</pre> + +Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. In accordance with the specification, each increment request increments the counter locally by one unit and the operation is transmitted by the replica to all other replicas of the system. + +<figure class="fullwidth"> + <img style="margin: auto; display: block;" src="{{ site.baseurl }}/chapter/6/resources/images/counters/operation-based-increment-only-counter.png" alt="Operation based increment only counter"/> +</figure> + +We can make the following observations: + +* **Eventually consistent** - At *t<sub>16</sub>*, the replicas are inconsistent. Eventually, they all attain consistency. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent. + +* **Reliable broadcast** - The increment operation has to be transmitted to all replicas. If the network fails to deliver the operation, the system will never be able to achieve consistency. For example - if the increment operation on **c<sub>2</sub>** at *t<sub>11</sub>* is not transmitted reliably to **c<sub>1</sub>**, then its value will always be one unit less than the correct value. + +* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>19</sub>*, <b>c<sub>1</sub></b> encounters two increment operations. Since its the same operation, there is only one way to handle the situation. There is no conflict. + +### 1.2. CvRDT: State based design + +In the state based implementation, the counter state is transmitted to all other replicas. +But how do we model the state? Of course, the counter's count is its state. +Since the count always increases, modeling the state as count automatically makes it a join semilattice. + +The code below provides the specification of this counter. + +<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT): + + <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, count <span style="color:#ff5600">=</span> 0): <span style="color:#919191"># constructor function</span> + self._count <span style="color:#ff5600">=</span> count + + <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> self._count + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self): <span style="color:#919191"># update function</span> + self._count <span style="color:#ff5600">+=</span> 1 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other): <span style="color:#919191"># comparison function</span> + <span style="color:#ff5600">return</span> self.value() <span style="color:#ff5600"><=</span> other.value() + + <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other): <span style="color:#919191"># merge function</span> + <span style="color:#ff5600">return</span> Counter(<span style="color:#a535ae">max</span>(self.value(), other.value())) + +</pre> + +Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. The replicas keep transmitting their state at random times to other randomly chosen replicas. + +<figure class="fullwidth"> + <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png" alt="State based increment only counter (incorrect)"/> +</figure> + +We can make the following observations: + +* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the replicas transmit state at random times to randomly chosen replicas. Until their states are merged, the replicas may be inconsistent. + +* **Correctness** - The clients issue a total of four increment requests. But the eventually consistent value of replicas is 4. So, the design is **incorrect**. + +* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>28</sub>*, <b>c<sub>1</sub></b> receives states of the other two replicas. Since the merge operation is commutative, the order in which these operations are handled does not matter. + +* **Unreliable broadcast** - Messages may be lost during transmission. Message sent by <b>c<sub>2</sub></b> at *t<sub>9</sub>* is lost. But eventually, some messages from <b>c<sub>2</sub></b> reach other replicas. As long as messages eventually reach other replicas, directly or indirectly, the system will achieve consistency. A message can also be received out of order or duplicated. + +Let's figure out why our design is incorrect. We notice that the merge operation simply compares the state of the replicas and returns the bigger of the two counts. What we really need is to add the two counts as we need the total counts issued by all clients across all replicas. But this poses another problem. The merge operation is no longer idempotent, i.e. - repeated merging of same values will not return the same result. This means that if a message gets duplicated, then we will get incorrect count. What's more is that the merge operation will no longer compute the **least** upper bound. It will compute an upper bound but that will not be the least upper bound. This clearly violates the mathematical model we set out to implement. So we can't modify our merge method. This means that we need to change our representation of the state. +Let's observe the problem again. Our merge method only returns the state of that replica which handled the maximum number of counts. It loses counts of other replicas. Let's represent the state as a sequence of counts. Each value in the sequence corresponds to the count of a replica. So we have as many values in a state as the number of replicas. We also design the merge operation to compute the index-wise maximum of the state. + +The specification below shows how this can be implemented. + +<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT): + + <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, counts <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>): <span style="color:#919191"># constructor function</span> + <span style="color:#ff5600">if</span> counts <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>: + self._counts <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(self.replicas()) + <span style="color:#ff5600">else</span>: + self._counts <span style="color:#ff5600">=</span> counts + + <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">sum</span>(self._counts) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">counts</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._counts) <span style="color:#919191"># return a clone</span> + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self): <span style="color:#919191"># update function</span> + self._counts[self.replicaId()] <span style="color:#ff5600">+=</span> 1 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other): <span style="color:#919191"># comparison function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600"><=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span> + <span style="color:#a535ae">zip</span>(self.counts(), + other.counts())) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other): <span style="color:#919191"># merge function</span> + <span style="color:#ff5600">return</span> Counter(<span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.counts(), + other.counts()))) + +</pre> + +The figure below shows an execution trace of three replicas confirming to this specification. + +<figure class="fullwidth"> + <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png" alt="State based increment only counter (correct) lattice"/> +</figure> + +This design converges to the correct value. This provides us an eventually consistent state based increment only counter. + +## 2. PN-counter - Increment and Decrement counter + +A PN-counter can be incremented and decremented. These can serve as a general purpose counters, as they also provide a decrement operation. For example - counting the number of users active one a social media website at any point. Note that the users can go offline and the counter will have to decremented. This can't be done with an increment only counter. + +### 2.1. CmRDT: Operation based design + +The code below provides the specification of an operation based increment and decrement counter. + +<pre style="background:#fff;color:#000"> + +<span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CmRDT): + + <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self): <span style="color:#919191"># constructor function</span> + self._count <span style="color:#ff5600">=</span> 0 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> self._count + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self): <span style="color:#919191"># update function</span> + self._count <span style="color:#ff5600">+=</span> 1 + <span style="color:#ff5600">for</span> replica <span style="color:#ff5600">in</span> self.replicas(): + self.transmit(<span style="color:#00a33f">"increment"</span>, replica) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">decrement</span>(self): <span style="color:#919191"># update function</span> + self._count <span style="color:#ff5600">-=</span> 1 + <span style="color:#ff5600">for</span> replica <span style="color:#ff5600">in</span> self.replicas(): + self.transmit(<span style="color:#00a33f">"decrement"</span>, replica) +</pre> + +Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. In accordance with the specification, each increment request increments the counter locally by one unit and each decrement request decrements the counter locally by one unit. The corresponding operation is transmitted by the replica to all other replicas of the system. + +<figure class="fullwidth"> + <img style="margin: auto; display: block;" src="{{ site.baseurl }}/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png" alt="Operation based increment and decrement counter"/> +</figure> + +We can make the the following observations: + +* **Eventual Consistency** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all achieve consistency. This is because the operations happen immediately at one replica but take time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent. + +* **Reliable broadcast** - Each operation has to be transmitted to all replicas. If the network fails to deliver an operation, the system will never be able to achieve consistency. For example - if the decrement operation on **c<sub>2</sub>** at *t<sub>6</sub>* is not transmitted reliably to **c<sub>1</sub>**, then its value will always be one unit more than the correct value. + +* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>30</sub>*, <b>c<sub>1</sub></b> and <b>c<sub>2</sub></b> encounter increment and decrement operations concurrently. Let's take a look at the two choices: + +<figure class="fullwidth"> + <img style="margin: auto; display: block;" src="{{ site.baseurl }}/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png" alt="Increment and decrement operations commute"/> +</figure> + +In both cases the result is same because the two operations commute, i.e. - the order in which they are executed by the replicas does not matter. Both replicas perform them in different orders and still achieve consistency, eventually. + +### 2.2. CvRDT: State based design + +The code below provides the specification of a state based increment and decrement counter. We take inspiration from the design of state based increment only counter and model the state of this counter in the same way. + +<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT): + + <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, counts <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>): <span style="color:#919191"># constructor function</span> + <span style="color:#ff5600">if</span> counts <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>: + self._counts <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(self.replicas()) + <span style="color:#ff5600">else</span>: + self._counts <span style="color:#ff5600">=</span> counts + + <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">sum</span>(self._counts) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">counts</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._counts) <span style="color:#919191"># return a clone</span> + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self): <span style="color:#919191"># update function</span> + self._counts[self.replicaId()] <span style="color:#ff5600">+=</span> 1 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">decrement</span>(self): <span style="color:#919191"># update function</span> + self._counts[self.replicaId()] <span style="color:#ff5600">-=</span> 1 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other): <span style="color:#919191"># comparison function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600"><=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span> + <span style="color:#a535ae">zip</span>(self.counts(), + other.counts())) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other): <span style="color:#919191"># merge function</span> + <span style="color:#ff5600">return</span> Counter(<span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.counts(), + other.counts()))) + +</pre> + +Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. The replicas keep transmitting their state at random times to other randomly chosen replicas. + +<figure class="fullwidth"> + <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png" alt="State based increment and decrement counter (incorrect)"/> +</figure> + +We can make the the following observations: + +* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the replicas transmit state at random times to randomly chosen replicas. Until their states are merged, the replicas may be inconsistent. + +* **Correctness** - The clients issue a total of four increment requests and 2 decrement requests. But the eventually consistent value of replicas is 4. So, the design is **incorrect**. + +* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>27</sub>* <b>c<sub>1</sub></b> has to handle 2 merge operations concurrently. Since the state forms a partially ordered set and the merge operation computes its least upper bound, the order in which the merge operation happens does not affect the final outcome. Similarly, at *t<sub>21</sub>* and *t<sub>29</sub>*, two operations arrive concurrently at <b>c<sub>3</sub></b> and <b>c<sub>2</sub></b> respectively. + +* **Unreliable broadcast** - Messages may be lost during transmission. Message sent by <b>c<sub>3</sub></b> at *t<sub>12</sub>* is lost. But eventually, message at *t<sub>25</sub>* reaches another replica. As long as messages eventually reach other replicas, directly or indirectly, the system will achieve consistency. A message can also be received out of order or duplicated. + +Though we modeled the state after the increment only state based counter, this design doesn't work. Let's try to figure out what went wrong. At *t<sub>12</sub>*, <b>c<sub>1</sub></b> merges the state from <b>c<sub>2</sub></b>. The merge operation computes the index wise maximum in accordance with the specification. In doing so, the *-1* value of *c<sub>2</sub>* due to the decrement operation at *t<sub>6</sub>* is lost. +To make matters clearer, let's look at a section of the lattice formed by the state of this counter - + +<figure class="fullwidth"> + <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png" alt="State based increment and decrement counter(incorrect) lattice"/> +</figure> + +Its clear that we have violated the basic constraint, the decrement operation does not take the state higher up in the lattice. In other words, the decrement operation is non monotonic. So, when the results of increment and decrement operations are merged together, then the result of the increment operation is returned, as it is always higher up in the lattice. So the replicas only count the total number of increments. + +But we do gain two valuable insights from this design- + +> Eventual convergence does not guarantee correctness. + +> Incorrect designs may still converge eventually. + + +Let's try to correct this problem. We need a way to count the decrement operations without losing monotonicity. One solution is to model this counter using two increment only counters. The first counter counts the increment operations and the second one counts the decrement operations. The value of the actual counter is the difference between the two corresponding counters. The specification below shows how this can be implemented. + +<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT): + + <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, + increments <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>, + decrements <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>): <span style="color:#919191"># constructor function</span> + <span style="color:#ff5600">if</span> increments <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>: + self._increments <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(replicas()) + <span style="color:#ff5600">else</span>: + self._increments <span style="color:#ff5600">=</span> increments + <span style="color:#ff5600">if</span> decrements <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>: + self._decrements <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(replicas()) + <span style="color:#ff5600">else</span>: + self._decrements <span style="color:#ff5600">=</span> decrements + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increments</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._increments) <span style="color:#919191"># return a clone</span> + + <span style="color:#ff5600">def</span> <span style="color:#21439c">decrements</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._decrements) <span style="color:#919191"># return a clone</span> + + <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self): <span style="color:#919191"># query function</span> + <span style="color:#ff5600">return</span> (<span style="color:#a535ae">sum</span>(self.increments()) <span style="color:#ff5600">-</span> + <span style="color:#a535ae">sum</span>(self.decrements())) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self): <span style="color:#919191"># update function</span> + self._increments[self.replicaId()] <span style="color:#ff5600">+=</span> 1 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">decrement</span>(self): <span style="color:#919191"># update function</span> + self._decrements[self.replicaId()] <span style="color:#ff5600">+=</span> 1 + + <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other): <span style="color:#919191"># comparison function</span> + <span style="color:#ff5600">return</span> (<span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600"><=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span> + <span style="color:#a535ae">zip</span>(self.increments(), + other.increments())) + <span style="color:#ff5600">and</span> + <span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600"><=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span> + <span style="color:#a535ae">zip</span>(self.decrements(), + other.decrements()))) + + <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other): <span style="color:#919191"># merge function</span> + <span style="color:#ff5600">return</span> Counter(increments <span style="color:#ff5600">=</span> <span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.increments(), + other.increments())), + decrements <span style="color:#ff5600">=</span> <span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.decrements(), + other.decrements()))) + +</pre> + +The figure below shows an execution trace of three replicas confirming to this specification. + +<figure class="fullwidth"> + <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png" alt="State based increment and decrement counter (correct)"/> +</figure> + +This design converges to the correct value. This provides us an eventually consistent state based increment and decrement counter. We can take a look at the lattice formed by the state to convince ourselves. + +<figure class="fullwidth"> + <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png" alt="State based increment and decrement counter(correct) lattice"/> +</figure> + +## 3. References + +{% bibliography --file counters %} + +[increment-operation]: resources/images/counters/increment-operation.png +[decrement-operation]: resources/images/counters/decrement-operation.png +[operation-based-increment-only-counter]: resources/images/counters/operation-based-increment-only-counter.png +[state-based-increment-only-counter-incorrect]: resources/images/counters/state-based-increment-only-counter-incorrect.png +[state-based-increment-only-counter-correct]: resources/images/counters/state-based-increment-only-counter-correct.png +[operation-based-increment-and-decrement-counter]: resources/images/counters/operation-based-increment-and-decrement-counter.png +[state-based-increment-and-decrement-counter-incorrect]: resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png +[state-based-increment-and-decrement-counter-correct]: resources/images/counters/state-based-increment-and-decrement-counter-correct.png diff --git a/chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py b/chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py new file mode 100644 index 0000000..5182ab1 --- /dev/null +++ b/chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py @@ -0,0 +1,20 @@ +class CmRDT: + pass + +class Counter(CmRDT): + + def __init__(self): # constructor function + self._count = 0 + + def value(self): # query function + return self._count + + def increment(self): # update function + self._count += 1 + for replica in self.replicas(): + self.transmit("increment", replica) + + def decrement(self): # update function + self._count -= 1 + for replica in self.replicas(): + self.transmit("decrement", replica) diff --git a/chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py b/chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py new file mode 100644 index 0000000..b10cd98 --- /dev/null +++ b/chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py @@ -0,0 +1,15 @@ +class CmRDT: + pass + +class Counter(CmRDT): + + def __init__(self): # constructor function + self._count = 0 + + def value(self): # query function + return self._count + + def increment(self): # update function + self._count += 1 + for replica in self.replicas(): + self.transmit("increment", replica) diff --git a/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py new file mode 100644 index 0000000..1ea726d --- /dev/null +++ b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py @@ -0,0 +1,47 @@ +class CvRDT: + pass + +class Counter(CvRDT): + + def __init__(self, + increments = None, + decrements = None): # constructor function + if increments is None: + self._increments = [0] * length(replicas()) + else: + self._increments = increments + if decrements is None: + self._decrements = [0] * length(replicas()) + else: + self._decrements = decrements + + def increments(self): # query function + return list(self._increments) # return a clone + + def decrements(self): # query function + return list(self._decrements) # return a clone + + def value(self): # query function + return (sum(self.increments()) - + sum(self.decrements())) + + def increment(self): # update function + self._increments[self.replicaId()] += 1 + + def decrement(self): # update function + self._decrements[self.replicaId()] += 1 + + def compare(self, other): # comparison function + return (all(v1 <= v2 for (v1, v2) in + zip(self.increments(), + other.increments())) + and + all(v1 <= v2 for (v1, v2) in + zip(self.decrements(), + other.decrements()))) + + def merge(self, other): # merge function + return Counter(increments = map(max, zip(self.increments(), + other.increments())), + decrements = map(max, zip(self.decrements(), + other.decrements()))) diff --git a/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py new file mode 100644 index 0000000..6f0cbde --- /dev/null +++ b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py @@ -0,0 +1,31 @@ +class CvRDT: + pass + +class Counter(CvRDT): + + def __init__(self, counts = None): # constructor function + if counts is None: + self._counts = [0] * length(self.replicas()) + else: + self._counts = counts + + def value(self): # query function + return sum(self._counts) + + def counts(self): # query function + return list(self._counts) # return a clone + + def increment(self): # update function + self._counts[self.replicaId()] += 1 + + def decrement(self): # update function + self._counts[self.replicaId()] -= 1 + + def compare(self, other): # comparison function + return all(v1 <= v2 for (v1, v2) in + zip(self.counts(), + other.counts())) + + def merge(self, other): # merge function + return Counter(map(max, zip(self.counts(), + other.counts()))) diff --git a/chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py new file mode 100644 index 0000000..a3d9069 --- /dev/null +++ b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py @@ -0,0 +1,28 @@ +class CvRDT: + pass + +class Counter(CvRDT): + + def __init__(self, counts = None): # constructor function + if counts is None: + self._counts = [0] * length(self.replicas()) + else: + self._counts = counts + + def value(self): # query function + return sum(self._counts) + + def counts(self): # query function + return list(self._counts) # return a clone + + def increment(self): # update function + self._counts[self.replicaId()] += 1 + + def compare(self, other): # comparison function + return all(v1 <= v2 for (v1, v2) in + zip(self.counts(), + other.counts())) + + def merge(self, other): # merge function + return Counter(map(max, zip(self.counts(), + other.counts()))) diff --git a/chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py new file mode 100644 index 0000000..9971c65 --- /dev/null +++ b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py @@ -0,0 +1,19 @@ +class CvRDT: + pass + +class Counter(CvRDT): + + def __init__(self, count = 0): # constructor function + self._count = count + + def value(self): # query function + return self._count + + def increment(self): # update function + self._count += 1 + + def compare(self, other): # comparison function + return self.value() <= other.value() + + def merge(self, other): # merge function + return Counter(max(self.value(), other.value())) diff --git a/chapter/6/resources/images/counters/decrement-operation.png b/chapter/6/resources/images/counters/decrement-operation.png Binary files differnew file mode 100644 index 0000000..a2d3f1a --- /dev/null +++ b/chapter/6/resources/images/counters/decrement-operation.png diff --git a/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png b/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png Binary files differnew file mode 100644 index 0000000..93b52bf --- /dev/null +++ b/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png diff --git a/chapter/6/resources/images/counters/increment-operation.png b/chapter/6/resources/images/counters/increment-operation.png Binary files differnew file mode 100644 index 0000000..f016c23 --- /dev/null +++ b/chapter/6/resources/images/counters/increment-operation.png diff --git a/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png b/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png Binary files differnew file mode 100644 index 0000000..ddbc789 --- /dev/null +++ b/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png diff --git a/chapter/6/resources/images/counters/operation-based-increment-only-counter.png b/chapter/6/resources/images/counters/operation-based-increment-only-counter.png Binary files differnew file mode 100644 index 0000000..1231b92 --- /dev/null +++ b/chapter/6/resources/images/counters/operation-based-increment-only-counter.png diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png Binary files differnew file mode 100644 index 0000000..2bbcf6b --- /dev/null +++ b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png Binary files differnew file mode 100644 index 0000000..880aee0 --- /dev/null +++ b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png Binary files differnew file mode 100644 index 0000000..d13dfaa --- /dev/null +++ b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png Binary files differnew file mode 100644 index 0000000..7981767 --- /dev/null +++ b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png diff --git a/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png b/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png Binary files differnew file mode 100644 index 0000000..c382f8b --- /dev/null +++ b/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png diff --git a/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png b/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png Binary files differnew file mode 100644 index 0000000..3e79e42 --- /dev/null +++ b/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png diff --git a/chapter/6/resources/partitioned-network.jpg b/chapter/6/resources/images/partitioned-network.jpg Binary files differindex 513fc13..513fc13 100644 --- a/chapter/6/resources/partitioned-network.jpg +++ b/chapter/6/resources/images/partitioned-network.jpg diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index b19ba23..023c8c8 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -8,7 +8,7 @@ by: "James Larisch" ## What's the problem? In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination between computers is required. - As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network is simply not as reliable as, say, memory - and waiting for responses can result in untimeliness for the application's userbase. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the necessary and unnecessary properties of our systems. As stated, we can't perfectly emulate a single computer using multiple machines, but once we accept that fact and learn to work with it, there are plenty of things we *can* do! + As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network is simply not as reliable as, say, memory - and waiting for responses can result in untimeliness for the application's user base. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can drill down into the CAP pyramid and choose the necessary and unnecessary properties of our systems. As stated, we can't perfectly emulate a single computer using multiple machines, but once we accept that fact and learn to work with it, there are plenty of things we *can* do! ## The Shopping Cart Let's bring all these theorem talk back to reality. Let's say you're working at a new e-commerce startup, and you'd like to revolutionize the electronic shopping cart. You'd like to give the customer the ability to do the following: @@ -26,7 +26,7 @@ If you only had one user of your website, this wouldn't be too hard. You could m But as Section 6 has already explained, this is not so trivial. Messages between your servers in Beijing and Paris could be dropped, corrupted, reordered, duplicated, or delayed. Servers can crash. Sharks can cut the network cables between countries. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which country she's in (which server she asks). -It's possible to implement "consensus" protocols such as Paxos and 3-Phase-Commit that provide coordination between your machines. When failure happens, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable* - at least until it is consistent once more. For applications in which inconsistent state is dangerous, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart system experienced a failure and became unavailable, users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? +It's possible to implement "consensus" protocols such as Paxos and Raft that provide coordination between your machines. When more failures than the system can tolerate occur, such as a network shark-attack, the protocol detects a lack of consistency and becomes *unavailable* - at least until it is consistent once more. For applications in which inconsistent state is dangerous, this is appropriate. For a shopping cart, this seems like overkill. If our shopping cart system experienced a failure and became unavailable, users would not be able to add or remove things from the cart. They also couldn't check out. This means our startup would lose money! Perhaps it's not so important that our clients' shopping carts be completely synchronized across the entire world at all times. After all, how often are people going to be doing such wanderlust shopping? This is an important moment. By thinking about our specific problem, we've realized a compromise we're willing to make: our users always need to be able to add things, remove things, and checkout. In other words, our service needs to be as *available* as possible. Servers don't necessarily need to agree all the time. We'd like them to, but the system shouldn't shut down if they don't. We'll find a way to deal with it. @@ -56,10 +56,10 @@ Blue Skateboard Green Umbrella ``` -It's important to understand that Amazon has multiple machines storing the contents of your cart. These machines are asynchronously communicating in order to tell each other about updates they've received. Conflicts like this can happen when you try to read before the nodes have had time to gossip about your cart. More likely, however, is the situation in which one of the machines holding your cart goes offline and missing some updates. When it comes back online, you try to read, and this resolution process must occur. +Dynamo has multiple machines in charge of storing the contents of your cart. When you add something to your cart, Dynamo specifies a minimum number of nodes that must receive the new data before the write is considered complete. The same thing goes for reading the contents of your cart: Dynamo requires a minimum number of healthy, responsive nodes to return cart data before relaying this data to the user. Nodes periodically gossip their local state to their neighbors to ensure that any updates, which occurred while the node may have been offline, are eventually delivered. However, Dynamo sends updates to your carts asynchronously to all replicas. This means when you read the contents of your cart, it's possible to receive different results from different replicas. ### Good & Bad -What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures & conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. Given a conflict, there isn't a one-size-fits-all solution for resolving them. In the case of the shopping cart, it's relatively trivial. But as a programmer, every time you use DynamoDB for a different purpose you need to consider your resolution strategy. The database doesn't provide a general solution. +What do we love about Dynamo? It's a highly available key-value store. It replicates data well, and according to the paper, has high uptime and low latency. We love that it's *eventually consistent*. Nodes are constantly gossiping and `put`s are asynchronously propagated, so given enough time (and assuming failures are resolved), nodes' states will eventually converge. However, this property is *weak*. It's weak because when failures & conflicts occur, and [and they will occur](https://www.youtube.com/watch?v=JG2ESDGwHHY), it's up to the application developer to figure out how to handle it. Given a conflict, there isn't a one-size-fits-all solution for resolving them. In the case of the shopping cart, it's relatively trivial: our resolution strategy errs on the side of inclusion. But as a programmer, every time you use DynamoDB for a different purpose you need to consider your resolution strategy. The database doesn't provide a general solution. Instead of constructing an all-purpose database and forcing the burden of resolution on programmers, what if we constructed multi-purpose (read: multi, not *all*) data structures that required no manual resolution? These data structures would resolve conflicts inherently, themselves, and depending on your application you could choose which data structure works best for you. @@ -71,11 +71,11 @@ Let's try this transfiguration on the shopping cart. Let's strip it down: how do Using this knowledge, let's try to construct our own shopping cart that automatically resolves conflicts. -(Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at LWW-Sets.) +(Unfortunately Amazon has a leg up on our startup. Their programmers have figured out a way to add multiple instances of a single item into the cart. Users on our website can only add one "Red Candle"" to their shopping cart. This is due to a fundamental limitation in the type of CRDT I chose to exemplify. It's quite possible to have a fully functional cart. Take a look at OR-Sets.) ### Example -Let's take a look at the following Javascript. For simplicity's sake, let's pretend users can only add things to their shopping cart. +Let's take a look at the following JavaScript. For simplicity's sake, let's pretend users can only add things to their shopping cart. ```javascript class Cart { @@ -131,7 +131,7 @@ Here is an (almost) fully functional shopping cart program. You can imagine this 6. Sleep for 10 seconds. 7. Repeat! -Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. This should remind you of Dynamo's gossiping: nodes are constantly attempting to converge. +Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped, delayed, or reordered. But no worries! Beijing is `synchronizing` again in another 10 seconds. This should remind you of Dynamo's gossip and propagation: nodes are constantly attempting to converge. Both systems are eventually consistent - the difference here is our Javascript shopping cart displays *strong* eventual consistency. It's strong because it requires no specialized resolution. When a node transmits its state to another node, there's absolutely no question about how to integrate that state into the current one. There's no conflict. @@ -246,30 +246,30 @@ Wouldn't it be great if tools like this existed? Before talking about such tools, I'd like you to forget almost everything you know about programming for a second (unless of course you've never programmed in a Von Neumann-based language in which you sequentially update pieces of memory; which, by the way, you have). Imagine the following scenario: you are "programming" a node in a cluster of computers. All of the other computers work as expected. When you receive a message (all messages will include an integer), your task is to save the message, increment the integer, and resend the message back to its originator. You must also send messages you've received from `stdin`. Unfortunately, the programming environment is a little strange. -You have access to five buffers: +You have access to five sets: * Messages you have received in the last 5 seconds * Inputs you've received from `stdin` in the last 5 seconds -* An outgoing messages buffer: flushed & sent every 5 seconds +* An outgoing messages set: flushed & sent every 5 seconds * A bucket of saved messages: *never* flushed -However, you only have access to these buffers *every 5 seconds*. If messages are formatted as such: `(SOURCE, INTEGER, T)`, your buffers might look like when `t = 0`. (`t` is the number of seconds elapsed) +However, you only have access to these sets *every 5 seconds*. If messages are formatted as such: `(SOURCE, INTEGER, T)`, your sets might look like when `t = 0`. (`t` is the number of seconds elapsed) ``` <T = 0> -RECV-BUFFER: [(A, 1, 0), (B, 2, 0)] -RSTDIN-INPUTS: [(A, 5, 0), (C, 10, 0)] -SEND-BUFFER: [] -SAVED: [(D, -1, 0), (E, -100, 0)] +RECV-BUFFER: {(A, 1, 0), (B, 2, 0)} +RSTDIN-INPUTS: {(A, 5, 0), (C, 10, 0)} +SEND-BUFFER: {} +SAVED: {(D, -1, 0), (E, -100, 0)} ``` -If you don't write any code to manipulate these buffers, when `t = 5`, your buffers might look like: +If you don't write any code to manipulate these sets, when `t = 5`, your sets might look like: ``` <T = 5> -RECV-BUFFER: [(C, 10, 5)] -STDIN-INPUTS: [(X, 1, 5)] -SEND-BUFFER: [] -SAVED: [(D, -1, 0), (E, -100, 0)] +RECV-BUFFER: {(C, 10, 5)} +STDIN-INPUTS: {(X, 1, 5)} +SEND-BUFFER: {} +SAVED: {(D, -1, 0), (E, -100, 0)} ``` You can see that from `t = 0` to `t = 5`, you received one message from `C` and someone typed a message to `X` via `stdin`. @@ -301,51 +301,51 @@ or Ruby: ```ruby on_five_second_interval do - recv_buffer.each do |msg| - saved_buffer << msg + recv_set.each do |msg| + saved_set << msg new_msg = msg.clone new_msg.integer += 1 new_msg.flip_source_destination - send_buffer << new_msg + send_set << new_msg end - stdin_input_buffer.each do |msg| - send_buffer << msg + stdin_input_set.each do |msg| + send_set << msg end end ``` -We have expressed this model using an event-driven programming style: the callbacks are triggered when `t % 5 = 0`: when the buffers populate & flush. +We have expressed this model using an event-driven programming style: the callbacks are triggered when `t % 5 = 0`: when the sets populate & flush. -Notice we perform a few "copies". We read something from one buffer and place it into another one, perhaps after applying some modification. Perhaps we place a message from a given buffer into two buffers (`recv_buffer` to `saved_buffer` & `send_buffer`). +Notice we perform a few "copies". We read something from one set and place it into another one, perhaps after applying some modification. Perhaps we place a message from a given set into two sets (`recv_set` to `saved_set` & `send_set`). This situation screams for a more functional approach: ```ruby on_five_second_interval do - saved_buffer += recv_buffer # add everything in recv_buffer to saved_buffer + saved_set += recv_set # add everything in recv_set to saved_set - send_buffer += recv_buffer.map do |msg| # map over the recv_buffer, increment integers, add to send_buffer + send_set += recv_set.map do |msg| # map over the recv_set, increment integers, add to send_set new_msg = msg.clone new_msg.integer += 1 new_msg.flip_source_destination # send to originator new_msg # this block returns new_msg end - send_buffer += stdin_input_buffer # add stdin messages to the send buffer + send_set += stdin_input_set # add stdin messages to the send set end ``` After this block/callback is called, the system automatically flushes & routes messages as described above. -Bloom {% cite Bloom --file langs-consistency %}, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates certain buffers before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. +Bloom {% cite Bloom --file langs-consistency %}, a research language developed at UC Berkeley, has a similar programming model to the one described above. Execution is broken up into a series of "timesteps". In the above example, one "timestemp" would be the execution of one `on_five_second_interval` function. Bloom, like the theoretical system above, automatically flushes and populates certain sets before and after each timestep. In the above example, 5 seconds was an arbitrary amount of time. In Bloom, timesteps (rounds of evaluation) are logical tools - they may happen every second, 10 seconds, etc. Logically, it shouldn't affect how your program executes. In reality, Bud's timesteps correspond to evaluation iterations. Your code is evaluated, executed, and the process repeats. So what does a Bloom program look like? Bloom's prototypal implementation is called Bud and is implemented in Ruby. There are two main parts to a Bloom program: -1. User defined buffers: rather than the four buffers I gave you above, Bloom users can define their own buffers. There are different types of buffers depending on the behavior you desire: - * `channel`: Above, `recv_buffer` and `send_buffer` would be considered channels. They facilitate sending network messages to and from other nodes. Like the messages above, messages sent into these channels contain a "location-specifier", which tells Bloom where the message should be sent. If you wanted to send a message to `A`, you could push the message `(@A, 10)` into your send buffer (in Ruby, `["@A", 10]`). The `@` denotes the location-specifier. At the end of the timestep (or callback execution in the above example), these buffers are flushed. - * `table`: Above, `saved_buffer` would be considered a table. The contents of tables persist across timesteps, which means tables are never flushed. +1. User defined sets: rather than the four sets I gave you above, Bloom users can define their own sets. There are different types of sets depending on the behavior you desire. Bloom refers to these sets as 'collections': + * `channel`: Above, `recv_set` and `send_set` would be considered channels. They facilitate sending network messages to and from other nodes. Like the messages above, messages sent into these channels contain a "location-specifier", which tells Bloom where the message should be sent. If you wanted to send a message to `A`, you could push the message `(@A, 10)` into your send set (in Ruby, `["@A", 10]`). The `@` denotes the location-specifier. At the end of the timestep (or callback execution in the above example), these set are flushed. + * `table`: Above, `saved_set` would be considered a table. The contents of tables persist across timesteps, which means tables are never flushed. 2. Code to be executed at each timestep. A Bloom (Bud) program can be seen as the inside of the block passed to `on_five_second_interval`. In fact, it looks very similar, as we'll see. -For the purposes of this chapter, let's assume `stdin_input_buffer` is a special kind of channel in which are sent in via `stdin`. Let's also assume this channel exists in all Bloom programs. +For the purposes of this chapter, let's assume `stdin_input_set` is a special kind of channel in which are sent in via `stdin`. Let's also assume this channel exists in all Bloom programs. Let's take a look at an example Bud program. @@ -355,19 +355,19 @@ First, let's declare our state. module Incrementer def state channel :network_channel ['@dst', 'src', 'integer'] - table :saved_buffer ['dst', 'src', 'integer'] - # implied channel :stdin_input_buffer ['@dst', 'src', 'integer'] + table :saved_set ['dst', 'src', 'integer'] + # implied channel :stdin_input_set ['@dst', 'src', 'integer'] end end ``` The first line of `state` means: declare a channel called `network_channel` in which messages are 3-tuples. The first field of the message is called `dst`, the second `src`, and the third is called `integer`. `@` is our location-specifier, so if a program wants to send a message to a node at a given identifier, they will place it in the first `dst` field. For example, a message destined for `A` would look like `['A', 'me', 10]`. The `@` denotes the location-specifier within the collection's "schema". -The second line means: declare a table (persists) called `saved_buffer` in which messages follow the same format as `network_channel`. There's no location specifier since this collection is not network-connected. +The second line means: declare a table (persists) called `saved_set` in which messages follow the same format as `network_channel`. There's no location specifier since this collection is not network-connected. You can think of the Ruby array after the channel name as the "schema" of that collection. -Notice how we only have one network channel for both receiving and sending. Before, we had two buffers, one for sending and one for receiving. When we place items *into* `network_channel`, Bud will automatically send messages to the appropriate `@dst`. +Notice how we only have one network channel for both receiving and sending. Before, we had two sets, one for sending and one for receiving. When we place items *into* `network_channel`, Bud will automatically send messages to the appropriate `@dst`. Next, let's write our code. This code will be executed at every timestamp. In fact, you can think of a Bud program as the code inside of a timestamp callback. Let's model the raw Ruby code we saw above. @@ -375,8 +375,8 @@ Next, let's write our code. This code will be executed at every timestamp. In fa module Incrementer def state channel :network_channel ['@dst', 'src', 'integer'] - table :saved_buffer ['dst', 'src', 'integer'] - # implied channel :stdin_input_buffer ['@dst', 'src', 'integer'] + table :saved_set ['dst', 'src', 'integer'] + # implied channel :stdin_input_set ['@dst', 'src', 'integer'] end declare @@ -386,12 +386,12 @@ module Incrementer declare def save_messages - saved_buffer <= network_channel + saved_set <= network_channel end declare def send_messages - network_channel <~ stdin_input_buffer + network_channel <~ stdin_input_set end end ``` @@ -408,21 +408,21 @@ Here, we take messages we've received from the network channel and send them bac ``` declare def save_messages - saved_buffer <= network_channel + saved_set <= network_channel end ``` -In `save_messages`, we use the `<=` operator. `<=` says "copy all of the elements in the right-hand-side and add them to the table on the left-hand-side." It's important to note that this movement occurs *within the current timestep*. This means if `saved_buffer` is referenced elsewhere in the code, it will include the contents of `network_channel`. If we had used the `<+` operator instead, the contents of `network_channel` would show up in `saved_buffer` in the *next* timestep. The latter is useful if you'd like to operate on the current contents of `saved_buffer` in the current timestep but want to specify how `saved_buffer` should be updated for the next timestep. +In `save_messages`, we use the `<=` operator. `<=` says "copy all of the elements in the right-hand-side and add them to the table on the left-hand-side." It's important to note that this movement occurs *within the current timestep*. This means if `saved_set` is referenced elsewhere in the code, it will include the contents of `network_channel`. If we had used the `<+` operator instead, the contents of `network_channel` would show up in `saved_set` in the *next* timestep. The latter is useful if you'd like to operate on the current contents of `saved_set` in the current timestep but want to specify how `saved_set` should be updated for the next timestep. Remember, all of this code is executed in *each* timestep - the separation of code into separate methods is merely for readability. ``` declare def send_messages - network_channel <~ stdin_input_buffer + network_channel <~ stdin_input_set end ``` -`send_messages` operates very much like `increment_messages`, except it reads the contents of `stdin_input_buffer` and places them into the network channel to be sent off at an indeterminite time. +`send_messages` operates very much like `increment_messages`, except it reads the contents of `stdin_input_set` and places them into the network channel to be sent off at an indeterminite time. #### Details @@ -457,13 +457,13 @@ module ShoppingCart def state table :cart ['item'] channel :recv_channel ['@src', 'dst', 'item'] - # implied channel :stdin_input_buffer ['item'] + # implied channel :stdin_input_set ['item'] periodic :timer 10 end declare def add_items - cart <= stdin_input_buffer + cart <= stdin_input_set end declare @@ -544,15 +544,15 @@ All in all, Bloom provides programmers with a new model for writing distributed ### Lasp Lasp {% cite Lasp --file langs-consistency %}is an Erlang library which aims to facilitate this type of "disorderly" programming. -Lasp provides access to myriad of CRDTs. It does not allows user-defined CRDTs (lattices), but the programmer can have confidence that the CRDTs obey the lattice formal requirements. +Lasp provides access to myriad of CRDTs. The programmer can have confidence that the CRDTs obey the lattice formal requirements. Like Bloom<sup>L</sup>, if the user desires a new lattice he or she may implement it using an interface. A Simple Lasp Program is defined as either a: * Single CRDT instance * A "Lasp process" with *m* inputs, all Simple Lasp Programs, and one output CRDT instance -For those of you unfamiliar with Erlang: a *process* can be thought of as an independent piece of code executing asynchronously. Processes can receive messages and send messages to other processes. Process can also subscribe (I think) to other processes' messages. +For those of you unfamiliar with Erlang: a *process* can be thought of as an independent piece of code executing asynchronously. Processes in Erlang are actors that act sequentially and exchange messages through asynchronous message passing. -Programming in Erlang is unique in comparison to programming in Ruby or Javascript. Erlang processes are spun off for just about everything - and they are independent "nodes" of code acting independently while communicating with other processes. Naturally, distributed systems programming fits well here. Processes can be distributed within a single computer or distributed across a cluster of computers. So communication between processes may move over the network. +Programming in Erlang is unique in comparison to programming in Ruby or Javascript. Erlang processes are spun off for just about everything - and they are independent actors of code acting independently while communicating with other processes. Naturally, distributed systems programming fits well here. Processes can be distributed within a single computer or distributed across a cluster of computers. So communication between processes may move over the network. Distribution of a data structure, then, means the transmission of a data structure across network-distributed processes. If a client asks for the state of the shopping cart in Beijing, the processes located on the computer in Beijing will respond. However, the processes in New York may disagree. Thus, our task is to distribute our data structures (CRDTs, right?) across distributed processes. @@ -588,7 +588,7 @@ Compare Lasp and Bloom: Lasp * An Erlang library, meant to be used in every-day Erlang programs. -* Built-in CRDTs. Does not allow user-defined CRDTs (for now). +* Built-in CRDTs. * All data structures are CRDTs and all operations are logically monotonic. * Thus, it's essentially impossible to construct a non-monotonic program *using only the Lasp library*. * It is possible to use Lasp in a non-monotonic way with disrupting outer Erlang code. |
