basho/riak_core — pull request #319 by jtuple (2013-05-15 23:59:58+00:00)
Title: Optimize to better handle large rings/nodes

This pull-request consists of numerous changes that are all part of an effort to improve `riak_core` with respect to large rings and large clusters.

As a data point, consider this mailing list post:
http://lists.basho.com/pipermail/riak-users_lists.basho.com/2013-March/011331.html

That email shows that adding a node to a Riak cluster with a 2048-size ring takes about an hour. I have seen similar results in my own testing. With the changes in this pull-request, adding a node to a cluster with a **16384** size ring takes about 5 minutes.

In general, this was a continual round of whack-a-mole. Profile to find bottleneck A, fix it; profile to find bottleneck B. Rinse/repeat. I've tried to organize the pull-request into logical, self-contained commits. For code review, the best approach is to go through commit-by-commit, being sure to read the detailed commit messages provided.

---

As a whole, the primary changes are as follows.

First, it's been long known that using `mochiglobal` to read/write the ring has been a blessing and a curse. `mochiglobal` reads are very, very fast. They take advantage of the Erlang constant pool and allow multiple processes to read the same data without locks and without copying data into individual process heaps. Unfortunately, `mochiglobal` writes are very, very slow. And they get slower the larger the ring is. The majority of this time is not spent in the code loader but inside code that converts the bare term into the abstract syntax tree that is passed to the Erlang compiler.

These slow writes hurt Riak during periods of high gossip traffic (such as cluster transitions), where hundreds of ring events may be triggered per minute. The `riak_core_ring_manager` stalls, message queue backs up, etc. Bad news. Riak is now CPU bound, spinning it's wheels generating code at runtime.

Solution? A hybrid approach. When a ring is first written, it's written to a shared ETS table, and the atom `ets` is written to mochiglobal. If the ring doesn't change for 90 seconds, it is then promoted to mochiglobal. Thus, we get fast writes during high ring churn, and fast reads once things stabilize.

Of course, reading from ETS is slower than reading from mochiglobal. This is predominately due to the need to copy the data into the process heap, which for large rings is MBs of data.

To combat this, so that critical paths of Riak are not heavily affected during cluster transitions, the second change is to extract certain elements out of the ring and provide an alternate means to query them. Bucket properties are stored in the ETS table, and a binary version of the `chash` structure called `chashbin` is generated. Since the `chashbin` uses a binary for the bulk of it's data, the structure is quick to copy between processes due to off-heap binary sharing. The `chashbin` structure also provides nearly constant time operations for a variety of operations that the traditional `chash` structure did in `O(N)` time. So, it's a win/win.

Various other commit modify different aspects of Riak to use the `chashbin` structure: the preflist calculation in `riak_core_apl`, the coverage calculations, various parts of the vnode manager, etc. See the commits for more details.

The next set of changes optimizes various other things. This consist mostly of changing various algorithms that are `O(N^3)`, `O(N^2)`, or `O(N)` with large constant factors where N is either the ring size or number of nodes in the cluster to using different algorithms and/or data structures with reduced complexity. Again, see commits for details.

There is also a change to how ring events are triggered in the a few manager processes. The traditional ring event system triggers an event for every ring received. Most things in Riak only care if the ring has actually changed. Thus, a new approach that reduces the number of events generated / colacesing multiple events together was build. This change, along with some of the algorithmic changes, makes the `riak_core_ring_manager`, `riak_core_vnode_manager`, and `riak_core_capability_manager` much more lightweight, whereas before they were the three dominate processes with number reductions between them.

Finally, there are some other minor changes.

---

There's a lot of benchmarking / profiling I've done during this work, but most of it become outdated as I made further changes. Or I didn't keep good notes. Will add more details in the coming days, but wanted to get the code out for review.

One set of information I do have around is from a micro-benchmark that compares the cost of computing preference lists in Riak between `master`, this branch using non-`chashbin` approach, and this branch using `chashbin` approach. The results are as follows:

```
riak_core_apl:get_apl
--------------------------------------------------------
master chash chashbin
Ring Nodes Min Max Min Max Min Max
64 1 2 2 1 2 1 1
64 10 6 7 1 2 1 1
64 100 6 8 1 2 1 1
64 1000 6 8 1 2 1 1
128 1 2 4 1 3 1 1
128 10 11 13 1 3 1 1
128 100 14 15 1 3 1 1
128 1000 12 13 1 4 1 1
256 1 4 7 1 6 1 1
256 10 20 23 1 6 1 1
256 100 23 26 1 6 1 1
256 1000 25 26 1 7 1 2
512 1 6 12 3 11 1 1
512 10 39 45 3 11 1 1
512 100 48 50 3 10 1 1
512 1000 44 57 3 14 1 5
1024 1 15 27 8 19 1 1
1024 10 81 95 6 19 1 1
1024 100 87 103 6 20 1 1
1024 1000 116 121 6 18 1 1
2048 1 32 53 9 39 1 1
2048 10 153 181 10 39 1 1
2048 100 174 203 8 36 1 1
2048 1000 243 292 8 35 1 1
4096 1 57 96 20 68 1 1
4096 10 322 363 16 72 1 1
4096 100 360 419 17 75 1 2
4096 1000 477 548 18 71 1 1
8192 1 98 208 35 162 1 1
8192 10 596 701 45 133 1 1
8192 100 711 803 41 138 1 1
8192 1000 783 818 34 151 1 2
16384 1 196 380 81 295 1 1
16384 10 1242 1365 79 296 1 1
16384 100 1415 1512 97 296 1 1
16384 1000 1576 2003 83 276 1 2
```