Helium: Adding vector clock

blimp/net/helium/vector_clock.h

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BLIMP_NET_HELIUM_VECTOR_CLOCK_H_
+#define BLIMP_NET_HELIUM_VECTOR_CLOCK_H_
+
+#include <stdint.h>
+
+#include "blimp/net/blimp_net_export.h"
+
+namespace blimp {
+
+// From wikipedia:
+// A vector clock is an algorithm for generating a partial ordering of events
+// in a distributed system and detecting causality violations.
+// Just as in Lamport timestamps, interprocess messages contain the state of
+// the sending process's logical clock. A vector clock of a system of
+// N processes is an array/vector of N logical clocks, one clock per process

[Kevin M, 2016/09/27 21:36:09]

A summary description and a link to Wikipedia might be more effective than an
excerpt. We don't have N>2 processes, and the Lamport timestamp reference might
be too esoteric for a code comment.

[scf, 2016/09/27 23:23:10]

Done.

+//
+// In the particular case where N=2 (Client and Engine). So we can optimize to

[Kevin M, 2016/09/27 21:36:09]

Sentence doesn't parse.

[scf, 2016/09/27 23:23:11]

Done.

+// store the 2 fields directly.
+class BLIMP_NET_EXPORT VectorClock {
+ public:

[Kevin M, 2016/09/27 21:36:09]

Add a type alias for Revision (uint32_t) and use that consistently.

[scf, 2016/09/27 23:23:10]

Done.

+  enum class Comparison { LessThan, EqualTo, GreaterThan, Conflict };
+
+  VectorClock(int32_t local_revision, int32_t remote_revision);
+  VectorClock();
+
+  // Compares two vector clocks. There are 4 possibilities for the result:
+  // * LessThan: One revision is equal and for the other is smaller.
+  // (1,0).CompareTo((2, 0));
+  // * EqualTo: Both revisions are equals.

[Kevin M, 2016/09/27 21:36:09]

equals = equal

What about "the same", so we don't have a circular reference with the word
"equal"?

[scf, 2016/09/27 23:23:11]

Done.

+  // * GreaterThan: One revision is equal and for the other is greater.
+  // (2,0).CompareTo((1, 0));
+  // * Conflict: Both revisions are different. (1,0).CompareTo(0,1)
+  Comparison CompareTo(const VectorClock& other) const;
+
+  // Merges two vector clocks, this is useful/used after we merge the client

[Kevin M, 2016/09/27 21:36:09]

The "why" should be more generalized, so that we promote orthogonal design in
our foundation classes.

[scf, 2016/09/27 23:23:10]

Done.

+  // and server data and need to combine the clocks from both local and remote.
+  VectorClock MergeWith(const VectorClock& other) const;
+
+  // Increments one to the local_revision_. This is used when something changes

[Kevin M, 2016/09/27 21:36:09]

Active voice: "Increments local_revision_ by one."

[scf, 2016/09/27 23:23:10]

Done.

+  // in the local host like setting a property or applying a change set.

[Kevin M, 2016/09/27 21:36:09]

Does applying changesets modify the local revision? I thought it would only
modify the remote revision?

[Kevin M, 2016/09/27 21:36:09]

local state

[scf, 2016/09/27 23:23:11]

I think if we follow the vector clock definition yes: "Each time a process
receives a message, it increments its own logical clock in the vector by one and
updates each element in its vector by taking the maximum of the value in its own
vector clock and the value in the vector in the received message (for every
element)."


https://en.wikipedia.org/wiki/Vector_clock

[scf, 2016/09/27 23:23:11]

Done.

[Kevin M, 2016/09/28 01:23:15]

Wouldn't this necessarily be a conflicting state, then?

Maybe "process receives a message" is distributed system-ese for "a process'
state is mutated"?

+  void IncrementLocal();
+
+  int32_t local_revision() const { return local_revision_; }
+  void set_local_revision(int32_t local_revision) {

[Kevin M, 2016/09/27 21:36:09]

Why will we need to support a setter?

[scf, 2016/09/27 23:23:10]

Done.

+    local_revision_ = local_revision;
+  }
+  int32_t remote_revision() const { return remote_revision_; }
+
+ private:
+  int32_t local_revision_;
+  int32_t remote_revision_;
+};
+
+}  // namespace blimp
+
+#endif  // BLIMP_NET_HELIUM_VECTOR_CLOCK_H_