Make faster

[sargun]

@russelldb I worked on making the vclock faster. Old:

old:
  riak_dt_vclock: bench_test_.../Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:279:<0.540.0>: Increment Time (1): 20

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:280:<0.540.0>: Increment Time (2): 18

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:281:<0.540.0>: Merge Time (1): 1719

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:282:<0.540.0>: Merge Time (2): 1087

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:283:<0.540.0>: Merge Time (3): 1793

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:284:<0.540.0>: Merge Time (4): 1151

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:285:<0.540.0>: Merge Time (5): 2375

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:286:<0.540.0>: Merge Time (6): 1188

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:287:<0.540.0>: Descends Time (1): 7

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:288:<0.540.0>: Descends Time (2): 1

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:289:<0.540.0>: Descends Time (2): 11

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:290:<0.540.0>: Descends Time (3): 3

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:291:<0.540.0>: Descends Time (4): 11

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:292:<0.540.0>: Descends Time (5): 1

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:293:<0.540.0>: Descends Time (6): 6308

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:294:<0.540.0>: Descends Time (7): 6488

New:

  riak_dt_vclock: bench_test_.../Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:340:<0.426.0>: Increment Time (1): 534

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:341:<0.426.0>: Increment Time (2): 25

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:342:<0.426.0>: Merge Time (1): 1389

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:343:<0.426.0>: Merge Time (2): 320

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:344:<0.426.0>: Merge Time (3): 1747

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:345:<0.426.0>: Merge Time (4): 821

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:346:<0.426.0>: Merge Time (5): 1401

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:347:<0.426.0>: Merge Time (6): 294

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:348:<0.426.0>: Merge Time (7): 7

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:349:<0.426.0>: Merge Time (8): 6

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:351:<0.426.0>: Descends Time (1): 1067

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:352:<0.426.0>: Descends Time (2): 5

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:353:<0.426.0>: Descends Time (2): 1417

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:354:<0.426.0>: Descends Time (3): 3

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:355:<0.426.0>: Descends Time (4): 1429

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:356:<0.426.0>: Descends Time (5): 3

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:357:<0.426.0>: Descends Time (6): 2252

/Users/sdhillon/repos/riak_dt/_build/test/lib/riak_dt/src/riak_dt_vclock.erl:358:<0.426.0>: Descends Time (7): 423

[131.451 s] ok
  [done in 131.477 s]
=======================================================
  All 7 tests passed.

A lot of our clocks have replica counts in the 1-5000 number. We'll probably make a NIF soon unless you have any suggestions.

[sargun]

Talked to @zeeshanlakhani a bit:

• This work can't really easily handle an upgrade in place. It works (in-place) if you do a stop-the-world, global upgrade (Erlang hot code deploy anyone?)
• Our anti-entropy, as it stands today simply folds over a few thousand keys and compares their vector clocks. Therefore a fast dominates and descends is key to success

Other notes:

• Most of our keys are immutable - 99% of our keys, 1% of our keys are our biggest keys (80-100K), and they probably see 99% of our write traffic.
• Most of these "hot keys" would greatly benefit from the delta work
• Ideally, we can pair the delta work with the PVE work. The nicety with PVEs is that AAE is reasonably fast, it's much simpler than server wide clocks / global logical clocks, and you can still do incremental update (albeit you generate exceptions)

[russelldb]

@sargun do you update the vector clock on set /map removal?

[russelldb]

@sargun I'd love to know more about this "PVE" work. Deltas require version vectors with dots/gaps, is that what you mean?

[sargun]

@russelldb what do you think now?