Continuum generation

Follows libmemcached’s KETAMA algorithm.

For better performance, we use dynamic_compile to generate mcache_continuum module on the fly. Several continuum:find() modes are provided.

1. case_when

find(Pool, Hash) →
case Hash of
H when H < 1111 → {Addr1, Port};
H when H < 2222 → {Addr2, Port};
….
end.

1. gb_trees

servers(Pool) → { {Addr1,Port1}, {Addr2,Port2}, … }.
continuums(Pool) → … % A Balanced Binary Tree in the form of {Key, Value, Smaller, Larger}. This is gb_trees’ internal data format.

find(Pool, Hash) →
Index = mcache_util:gb_trees_find(Hash, continums(Pool), Min, Max),
element(Index, servers(Pool)).

==
Find() benchmark: (single process, each checks 100 different test keys provided by libmemcached for 50 times)

The first column is the number of servers in the continuum.
The results are loops per second. so actual find ratio is 100*loops/sec.

case_when

1 – 6876,7168,6592,8012,7956
2 – 1216,1228,1227,1209,1172
3 – 843,859,862,860,866
5 – 557,562,555,558,562
10 – 280,288,289,288,283
20 – 145,145,146,145,145

gb_trees

1 – 3810,3918,4006,3912,3905
2 – 3924,3816,3935,3652,3816
3 – 3734,3733,3722,3708,3688
5 – 3595,3236,3340,3338,3351
10 – 3318,3331,3291,3623,3367
20 – 3085,3374,3484,3479,3265

====
case_when is linear, gb_trees is very stable on the contrary.