Whatever happens to, all the zeros

As part of a recent refactor of repair, I looked through the chash, chashbin code and it raised a number of questions.

Firstly, Riak uses sha hashes which produce a 160-bit output which defined the Ring - and Chash has a RINGTOP defined as:

https://github.com/OpenRiak/riak_core/blob/1b01278e762b835c0777d5c7319fe7b22186560d/src/chash.erl#L55

I was curious as to why we calculate this as a float, and then truncate to an integer rather than use (1 bsl 160) - 1 for example. However, this ?RINGTOP is then used:

https://github.com/OpenRiak/riak_core/blob/1b01278e762b835c0777d5c7319fe7b22186560d/src/chash.erl#L89-L91

and

https://github.com/OpenRiak/riak_core/blob/1b01278e762b835c0777d5c7319fe7b22186560d/src/chash.erl#L167-L168

The clear implication is that ?RINGTOP is expected to be 2 ^ 160 not 2 ^ 160 - 1.

This was puzzling, how this all still worked. but the code is saved by the fact that ?RINGTOP is calculated using a truncated float and it is bigger than 2 ^ 53, so due to the limitations of large floats

trunc(math:pow(2,160)-1) == (1 bsl 160) - 1.
false
trunc(math:pow(2,160)-1) == 1 bsl 160.      
true

We're calculating an increment in the above ring code to add to a sequence of 160 bit integers, but with a ring size of 32 say this adding of an increment is in effect:

((X bsr 155) + 1) bsl 155

The point being that if we define RingBits as the power of 2 to create the RingSize - we're only ever interested in the first RingBits within the 160-bit space, and all the other bit sin the ring space are just making simple arithmetic harder for both the computer and developer.

With the hashes of keys - the position of a Key in the ring is:

<<KeyPosition:RingBits/integer, _NeverNeedThis/bitstring>> = crypto:hash(sha, BKey).

The only purpose of the hash is to give a position in the Ring, as I understand it - and we only need RingBits to identify that, all the other 150 or so bits are noise. Likewise with Partition IDs, they are RingBits worth of interesting information and (160 - RingBits) of zeros we will never be interested in.

Looking at the old repair code, here's the hoops we have to go through to identify a range of 20-byte binaries to check if a hash belongs to a target partition:

https://github.com/OpenRiak/riak_core/blob/1b01278e762b835c0777d5c7319fe7b22186560d/src/riak_core_repair.erl#L73-L97

With even seemingly innocuous things like statements like FirstIdx-1 requiring about 150 0s to be flipped to 1s.

The call to chash:predecessors/3 requires a RingSize length list (or 20-byte integers) to be split and copied not once

https://github.com/OpenRiak/riak_core/blob/1b01278e762b835c0777d5c7319fe7b22186560d/src/chash.erl#L161

but twice

https://github.com/OpenRiak/riak_core/blob/1b01278e762b835c0777d5c7319fe7b22186560d/src/chash.erl#L141-L145

But if we focus on just the RingBits that are interesting, I think the alternative is much more concise and also easier on the CPU and its cache. We just need to find the N positions of interest as RingBit size integers (noting that we mimic the circle of the ring using modulo arithmetic):

https://github.com/OpenRiak/riak_core/blob/664d93a1907957167c33db83320cc8b136741528/src/riak_core_repair.erl#L162-L167

Take the first RingBits from the key hash

https://github.com/OpenRiak/riak_core/blob/664d93a1907957167c33db83320cc8b136741528/src/riak_core_repair.erl#L105

Then check if that small integer is in the list of small integers we're interested in

https://github.com/OpenRiak/riak_core/blob/664d93a1907957167c33db83320cc8b136741528/src/riak_core_repair.erl#L144

Perhaps this is obvious (or perhaps it is obviously wrong and there is use for all the other bits), but I think as an operator of Riak it would make my life easier to see the base 10 representation of a Partition as just the interesting RingBits - not the noise generated by appending 150+ zeros to the base 2 representation.

With a ringSize of 1024, that's 20KB worth of zeros in the Partitions in the ring. How much space would there be on the ring for bucket type properties if we just removed all the zeros! After all we can just bsl to go from position to partition, and bsr to do the reverse.

Is it possible to have a much more concise set of functions for ring operations if we simply drop all the redundant zeros?

Start with the cited RINGTOP and predecessor logic in src/chash.erl, then trace partition and hash handling in src/riak_core_repair.erl at the referenced revisions. Compare the current and proposed representations, but the issue does not define compatibility, performance, or acceptance criteria for deciding that the redesign is done.