{"id":696,"date":"2009-10-23T00:33:18","date_gmt":"2009-10-23T07:33:18","guid":{"rendered":"http:\/\/xiehang.com\/blog\/?p=696"},"modified":"2009-10-23T00:47:08","modified_gmt":"2009-10-23T07:47:08","slug":"nosql-start-with-consistent-hashing","status":"publish","type":"post","link":"https:\/\/xiehang.com\/blog\/2009\/10\/23\/nosql-start-with-consistent-hashing\/","title":{"rendered":"NoSQL – start with consistent hashing"},"content":{"rendered":"

Most NoSQL solutions are kind of caching, with persistent data store, with or without replication support. One of the key issue in production environment is using consistent hashing to avoid cache failure.<\/p>\n

I talked to a friend days ago about memcached deployment problem, he asked question about what to do with adding new memcached node to expand capacity, to avoid loading bunch of data from database to cache nodes. I told him I don’t have any experience, but if I encounter this problem, I will try to restart memcached client machines one by one, to use new configuration, so to avoid put massive load to database, also I will think about changing hashing function of memcached client, try to maximize entries that can keep partition unchanged.<\/p>\n

It turned out my second idea is correct (I should have read all those articles before talking to him :P). There are couple of articles discussing about this issue, and the good start point, of course, is wikipedia<\/a>.<\/p>\n

I tried libketama<\/a>, seems pretty good in term of retention rate. I did some tests that could be (sort of) real world use case. Say, we have 4 weak (512M) nodes and want to replace them with all new nodes with double capacity (1G), I’m going to add new nodes to the cluster one by one, and then remove old nodes one by one, and here are what I got:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
cluster<\/th>\ncapacity<\/th>\ncapacity
\nchanged<\/th>\n		key moved<\/th>\n<\/tr>\n
4x512M<\/td>\n2G<\/td>\n0%<\/td>\n0%<\/td>\n<\/tr>\n
4x512M
\n1x1G<\/td>\n		3G<\/td>\n50%<\/td>\n40%<\/td>\n<\/tr>\n
4x512M
\n2x1G<\/td>\n		4G<\/td>\n33%<\/td>\n30%<\/td>\n<\/tr>\n
4x512M
\n3x1G<\/td>\n		5G<\/td>\n25%<\/td>\n25%<\/td>\n<\/tr>\n
4x512M
\n4x1G<\/td>\n		6G<\/td>\n20%<\/td>\n20%<\/td>\n<\/tr>\n
3x512M
\n4x1G<\/td>\n		5.5G<\/td>\n8%<\/td>\n12%<\/td>\n<\/tr>\n
2x512M
\n4x1G<\/td>\n		5G<\/td>\n9%<\/td>\n13%<\/td>\n<\/tr>\n
1x512M
\n4x1G<\/td>\n		4.5G<\/td>\n10%<\/td>\n18%<\/td>\n<\/tr>\n
4x1G<\/td>\n4G<\/td>\n11%<\/td>\n19%<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

relatively, percentage of keys got moved to other partitions is close to capacity changes, which means it is close to the best number.<\/p>\n

And key distribution is pretty even (capacity\/utilization, node #1~#4 are 512M, #5~38 are 1G):<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
node #1<\/th>\nnode #2<\/th>\nnode #3<\/th>\nnode #4<\/th>\nnode #5<\/th>\nnode #6<\/th>\nnode #7<\/th>\nnode #8<\/th>\n<\/tr>\n
25.0%<\/p>\n

25.6%<\/td>\n

25.0%<\/p>\n

21.7%<\/td>\n

25.0%<\/p>\n

24.7%<\/td>\n

25.0%<\/p>\n

28.0%<\/td>\n

–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
16.7%<\/p>\n

16.9%<\/td>\n

16.7%<\/p>\n

15.2%<\/td>\n

16.7%<\/p>\n

19.0%<\/td>\n

16.7%<\/p>\n

17.7%<\/td>\n

33.3%<\/p>\n

31.1%<\/td>\n

–<\/td>\n–<\/td>\n–<\/td>\n<\/tr>\n
12.5%<\/p>\n

13.5%<\/td>\n

12.5%<\/p>\n

10.8%<\/td>\n

12.5%<\/p>\n

13.7%<\/td>\n

12.5%<\/p>\n

12.7%<\/td>\n

25.0%<\/p>\n

24.5%<\/td>\n

25.0%<\/p>\n

24.8%<\/td>\n

–<\/td>\n–<\/td>\n<\/tr>\n
10.0%<\/p>\n

10.9%<\/td>\n

10.0%<\/p>\n

9.4%<\/td>\n

10.0%<\/p>\n

11.0%<\/td>\n

10.0%<\/p>\n

8.3%<\/td>\n

20.0%<\/p>\n

19.6%<\/td>\n

20.0%<\/p>\n

20.0%<\/td>\n

20.0%<\/p>\n

20.9%<\/td>\n

–<\/td>\n<\/tr>\n
8.3%<\/p>\n

8.9%<\/td>\n

8.3%<\/p>\n

8.3%<\/td>\n

8.3%<\/p>\n

8.1%<\/td>\n

8.3%<\/p>\n

7.0%<\/td>\n

16.7%<\/p>\n

16.7%<\/td>\n

16.7%<\/p>\n

17.1%<\/td>\n

16.7%<\/p>\n

17.9%<\/td>\n

16.7%<\/p>\n

16.1%<\/td>\n<\/tr>\n

–<\/td>\n9.1%<\/p>\n

9.0%<\/td>\n

9.1%<\/p>\n

9.6%<\/td>\n

9.1%<\/p>\n

8.2%<\/td>\n

18.2%<\/p>\n

17.5%<\/td>\n

18.2%<\/p>\n

18.3%<\/td>\n

18.2%<\/p>\n

19.8%<\/td>\n

18.2%<\/p>\n

17.6%<\/td>\n<\/tr>\n

–<\/td>\n–<\/td>\n10.0%<\/p>\n

9.7%<\/td>\n

10.0%<\/p>\n

8.9%<\/td>\n

20.0%<\/p>\n

20.3%<\/td>\n

20.0%<\/p>\n

20.5%<\/td>\n

20.0%<\/p>\n

21.9%<\/td>\n

20.0%<\/p>\n

18.6%<\/td>\n<\/tr>\n

–<\/td>\n–<\/td>\n–<\/td>\n11.1%<\/p>\n

9.2%<\/td>\n

22.2%<\/p>\n

22.3%<\/td>\n

22.2%<\/p>\n

22.2%<\/td>\n

22.2%<\/p>\n

25.2%<\/td>\n

22.2%<\/p>\n

21.1%<\/td>\n<\/tr>\n

–<\/td>\n–<\/td>\n–<\/td>\n–<\/td>\n25.0%<\/p>\n

24.2%<\/td>\n

25.0%<\/p>\n

24.5%<\/td>\n

25.0%<\/p>\n

27.2%<\/td>\n

25.0%<\/p>\n

24.1%<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

I still need to try out fnv to see if it has better distribution and\/or less key shakiness, from the article above it was said at least it has better performance.<\/p>\n","protected":false},"excerpt":{"rendered":"

Most NoSQL solutions are kind of caching, with persistent data store, with or without replication support. One of the key issue in production environment is using consistent hashing to avoid cache failure. I talked to a friend days ago about memcached deployment problem, he asked question about what to do with adding new memcached node […]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[47,13,133,28],"_links":{"self":[{"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/posts\/696"}],"collection":[{"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/comments?post=696"}],"version-history":[{"count":6,"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/posts\/696\/revisions"}],"predecessor-version":[{"id":698,"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/posts\/696\/revisions\/698"}],"wp:attachment":[{"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/media?parent=696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/categories?post=696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xiehang.com\/blog\/wp-json\/wp\/v2\/tags?post=696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}