From 78e594ef879f70f7e41b232c7720376f7c5eb0bf Mon Sep 17 00:00:00 2001 From: Nat Dempkowski Date: Sun, 15 Oct 2017 18:32:11 -0400 Subject: Move from inlined HTML to Markdown code blocks --- chapter/6/counters.md | 267 +++++++++++++++++++++++++------------------------- 1 file changed, 133 insertions(+), 134 deletions(-) (limited to 'chapter/6/counters.md') diff --git a/chapter/6/counters.md b/chapter/6/counters.md index 67e822a..23dccde 100644 --- a/chapter/6/counters.md +++ b/chapter/6/counters.md @@ -6,29 +6,28 @@ 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 +## 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 +### 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. -
class Counter(CmRDT):
+```python
+class Counter(CmRDT):
+    def __init__(self):
+        self._count = 0
 
-    def __init__(self):         # constructor function
-        self._count = 0
+    def value(self): 
+        return self._count
 
-    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 increment(self): + self._count += 1 + for replica in self.replicas(): + self.transmit("increment", replica) +``` 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. @@ -44,7 +43,7 @@ We can make the following observations: * **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t19*, c1 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 +### 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. @@ -52,24 +51,23 @@ Since the count always increases, modeling the state as count automatically make The code below provides the specification of this counter. -
class Counter(CvRDT):
-
-    def __init__(self, count = 0):  # constructor function
-        self._count = count
+```python
+class Counter(CvRDT):
+    def __init__(self, count = 0):  
+        self._count = count
 
-    def value(self):                # query function
-        return self._count
+    def value(self):                
+        return self._count
 
-    def increment(self):            # update function
-        self._count += 1
+    def increment(self):            
+        self._count += 1
 
-    def compare(self, other):       # comparison function
-        return self.value() <= other.value()
+    def compare(self, other):       
+        return self.value() <= other.value()
 
-    def merge(self, other):         # merge function
-        return Counter(max(self.value(), other.value()))
-
-
+ def merge(self, other): + return Counter(max(self.value(), other.value())) +``` 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. @@ -92,33 +90,33 @@ Let's observe the problem again. Our merge method only returns the state of that The specification below shows how this can be implemented. -
class Counter(CvRDT):
-
-    def __init__(self, counts = None):  # constructor function
-        if counts is None:
-            self._counts = [0] * length(self.replicas())
-        else:
-            self._counts = counts
+```python
+class Counter(CvRDT):
+    def __init__(self, counts = None):
+        if counts is None:
+            self._counts = [0] * length(self.replicas())
+        else:
+            self._counts = counts
 
-    def value(self):                    # query function
-        return sum(self._counts)
+    def value(self):
+        return sum(self._counts)
 
-    def counts(self):                   # query function
-        return list(self._counts)       # return a clone
+    def counts(self):
+		# return a copy of the counts
+        return list(self._counts)
 
-    def increment(self):                # update function
-        self._counts[self.replicaId()] += 1
+    def increment(self):
+        self._counts[self.replicaId()] += 1
 
-    def compare(self, other):           # comparison function
-        return all(v1 <= v2 for (v1, v2) in
-                   zip(self.counts(),
+    def compare(self, other):
+        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(),
+    def merge(self, other):
+        return Counter(map(max, zip(self.counts(),
                                     other.counts())))
-
-
+``` The figure below shows an execution trace of three replicas confirming to this specification. @@ -128,34 +126,32 @@ The figure below shows an execution trace of three replicas confirming to this s 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 +## 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 +### CmRDT: Operation based design The code below provides the specification of an operation based increment and decrement counter. -
-
-class Counter(CmRDT):
+```python
+class Counter(CmRDT):
+    def __init__(self):
+        self._count = 0
 
-    def __init__(self):         # constructor function
-        self._count = 0
+    def value(self):
+        return self._count
 
-    def value(self):            # query function
-        return self._count
+    def increment(self):
+        self._count += 1
+        for replica in self.replicas():
+            self.transmit("increment", replica)
 
-    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)
-
+ def decrement(self): + self._count -= 1 + for replica in self.replicas(): + self.transmit("decrement", replica) +``` 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. @@ -177,40 +173,41 @@ We can make the the following observations: 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 +### 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. -
class Counter(CvRDT):
+```python
+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 __init__(self, counts = None):
+        if counts is None:
+            self._counts = [0] * length(self.replicas())
+        else:
+            self._counts = counts
 
-    def value(self):                    # query function
-        return sum(self._counts)
+    def value(self):
+        return sum(self._counts)
 
-    def counts(self):                   # query function
-        return list(self._counts)       # return a clone
+    def counts(self):
+		# return a copy of the counts
+        return list(self._counts)
 
-    def increment(self):                # update function
-        self._counts[self.replicaId()] += 1
+    def increment(self):
+        self._counts[self.replicaId()] += 1
 
-    def decrement(self):                # update function
-        self._counts[self.replicaId()] -= 1
+    def decrement(self):
+        self._counts[self.replicaId()] -= 1
 
-    def compare(self, other):           # comparison function
-        return all(v1 <= v2 for (v1, v2) in
-                   zip(self.counts(),
+    def compare(self, other):
+        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(),
+    def merge(self, other):
+        return Counter(map(max, zip(self.counts(),
                                     other.counts())))
-
-
+``` 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. @@ -246,52 +243,54 @@ But we do gain two valuable insights from this design- 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. -
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(),
+```python
+class Counter(CvRDT):
+    def __init__(self,
+                 increments = None,
+                 decrements = None):
+        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):
+		# return a copy of the increments
+        return list(self._increments)
+
+    def decrements(self):
+		# return a copy of the decrements
+        return list(self._decrements)
+
+    def value(self):
+        return (sum(self.increments()) -
+                sum(self.decrements()))
+
+    def increment(self):
+        self._increments[self.replicaId()] += 1
+
+    def decrement(self):
+        self._decrements[self.replicaId()] += 1
+
+    def compare(self, other):
+        return (all(v1 <= v2 for (v1, v2) in
+                    zip(self.increments(),
                         other.increments()))
-                and
-                all(v1 <= v2 for (v1, v2) in
-                    zip(self.decrements(),
+                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())))
-
-
+ def merge(self, other): + return Counter( + increments = map(max, zip(self.increments(), + other.increments())), + decrements = map(max, zip(self.decrements(), + other.decrements()))) +``` The figure below shows an execution trace of three replicas confirming to this specification. @@ -305,7 +304,7 @@ This design converges to the correct value. This provides us an eventually consi State based increment and decrement counter(correct) lattice -## 3. References +## References {% bibliography --file counters %} -- cgit v1.2.3