漫画算法:什么是一致性哈希?
![](http://static.careerengine.us/api/aov2/https%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGp54n6Qu5eH49JmZuSZNgOqP8ugvhkxuTeH47m0RbgmeiaP4IOca1ucGyaUNvYVicx7tNb6Ejb5Q1cg_%7C_640%3Fwx_fmt%3Djpeg%5Cx26amp%3Btp%3Dwebp%5Cx26amp%3Bwxfrom%3D5%5Cx26amp%3Bwx_lazy%3D1.jpg)
(点击上方公众号,可快速关注)
来源:伯乐专栏作者/玻璃猫,微信公众号 - 梦见(dreamsee321)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGp54n6Qu5eH49JmZuSZNgOqP8ugvhkxuTeH47m0RbgmeiaP4IOca1ucGyaUNvYVicx7tNb6Ejb5Q1cg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGp54n6Qu5eH49JmZuSZNgOqygXiccxibJbocYjtAPJlRKasLqkeHTib3nibBAdqycHqmJnU7sZTTLibNXw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGp54n6Qu5eH49JmZuSZNgOqWvao0lficcJJ7tE38OMh76DOXJrumxarLq0DMJwxI3mJmKiceRdkPIyw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGp54n6Qu5eH49JmZuSZNgOqTJmicoUEghhSVJXIRPeIGSYia3miaWdCPmKS8vtSoyC7OyLpIhQe4WiaQQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
一年之前——
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGojVibLpIicSBOK4cTVL0Myu8yffEfcbav7e5Zgia1XOznL9KhjnzNibbyyvwmP9kRu8o82oNcALm0VXg_%7C_0%3F.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGojVibLpIicSBOK4cTVL0Myu8R8H8hic8LRwTPUOnVyic6qEBPdoKQyGhrKEg0STiclpbLPBk5ddXdyoyA_%7C_0%3F.jpg)
未来两年内,系统预估的总订单数量可达一亿条左右。
按Mysql单表存储500万条记录来算,暂时不必分库,单库30个分表是比较合适的水平分表方案。
于是小灰设计了这样的分表逻辑:
- 订单表创建单库30个分表
- 对用户ID和30进行取模,取模结果决定了记录存于第几个分表
- 查询时需要以用户ID作为条件,根据取模结果确定查询哪一个分表
分表方式如下图(为了便于描述,简化为5个分表):
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojaiakObA557U1Dgrx8GWKqr2eGeDbyPBh7K3tYXFjJOhPUWmlbQezvwg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
过了两个月——
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojpGxGSC6ic2SxfOqCZ7V8NoaMEUVjfJpQEMKMvhE1ObE2tib9yZc9uOAw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojwS2MlQP3lzE4GMAOqFUxibFEdlAUic6f98IicV1Gknr6kApjrfia3caKWA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
又过了半年多——
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLoj5sXnSVj2yxOEPnj4Wf3EGKgqfSxzlAKiakTicicloj05TDPeqWbodzqaQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojGywRGQib8dItg0qTDjTVetnHZKKJGtVgFD1szp60tia8G62a0Gle1Czg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojyMicdYdibuic6naYfBPTkiaNetuKiah90g4hr66ibDeUoJCl4CSqOeNR5I4A_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojqnZQUSX5prfCtczVI7df6BF87ON3icyMnmLRwI4HBmm5ZGuwGmeIUgA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojbXM2NyGLvSt6iceYwCjxWgkvN1KG9CMYoX5Tp77iaMiaTngtAF6Smb9qQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojAicDojA4rqU1KE16oVzXpdV7icI0mic2hrBkib4kT1ZaEoFogdiawxZg8pw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqibQgXlNgGEs1pcUhzCqLojC7Zp6FCkbiboj57ToDmww0m8iczaMgmcInI3ue1IjlphYDicialJbJS0jw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
小灰的回忆告一段落——
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORdCAW89zbyth2K3w8vzicF6nxgkTMab0J074WFpwLiaDMR0bj89ibKMJqg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8OR6ZMuyvoALxlCm3py17G8JQw4heqH2ThtMxAmtuww34dQ7CicZQq1zOA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORUibET7QUGnQpYoVibEUib0u8sZyia2iaHAnB4VFdJa9Dr49Mvq04Nd3Fiaow_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORwflZticpI9bEnGsZiaTicC1sLaiatYCaJzMptJGSojfIibMRjcPEQeRoREw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORjw4YqzeMgt75t118iaC9m6QybfCXdjW76hr7EDuuEaZI7pLVGrMOLoA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORhynK7AGW8w66ezhSTAtwJcpDTly5JYFib2OaicxcmYUWrIxgC83h7Q1A_%7C_0%3Fwx_fmt%3Djpeg.jpg)
1.首先,我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区,在Redis中则是把缓存key分配到16384个slot。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORwDJqbDQialrhXp7XdsvHvjKencoMuQToZEwId9JlWF19nibNia5QztHTg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
2.每一个缓存key都可以通过Hash算法转化为一个32位的二进制数,也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORXibuQBNMe9YUgfpGCk9GwASnclIpFcOJLUs9ibjgx5UbuptqGib3VR3ow_%7C_0%3Fwx_fmt%3Djpeg.jpg)
3.我们的每一个缓存节点(Shard)也遵循同样的Hash算法,比如利用IP做Hash,映射到环形空间当中。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORkGeK1oU3h8BRRWeicAtMP4tnGtllGkHEf5EZasNicvEUaAr2CC1ncegQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
4.如何让key和节点对应起来呢?很简单,每一个key的顺时针方向最近节点,就是key所归属的存储节点。所以图中key1存储于node1,key2,key3存储于node2,key4存储于node3。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORRia1C2Gngyh1YdqamhibVvuwUovqzwxGW0T6RW8moSicsCFbhqKJ0Lz4w_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORTqCVYibe2d6ptxwy03JxceoKGCjWZibibVic4qTdsqN0BxBIEx4kiatRqCw_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8OR7qfkLTnffwa2tXoibPRnqcGe4uPM2wpo8cblcSIl6gsluPOGCGufX6w_%7C_0%3Fwx_fmt%3Djpeg.jpg)
1.增加节点
当缓存集群的节点有所增加的时候,整个环形空间的映射仍然会保持一致性哈希的顺时针规则,所以有一小部分key的归属会受到影响。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORCwmzp1NA37b6qKA1oBSgqCOVqLDyTlgrdyYzvtiaC8XjDrkoNesmmrQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
有哪些key会受到影响呢?图中加入了新节点node4,处于node1和node2之间,按照顺时针规则,从node1到node4之间的缓存不再归属于node2,而是归属于新节点node4。因此受影响的key只有key2。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORUKFCpzJpQpnwTH3mpUx0BNTvYRcSyKLkR8cficicRgROIW1wXk7DykbQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
最终把key2的缓存数据从node2迁移到node4,就形成了新的符合一致性哈希规则的缓存结构。
2.删除节点
当缓存集群的节点需要删除的时候(比如节点挂掉),整个环形空间的映射同样会保持一致性哈希的顺时针规则,同样有一小部分key的归属会受到影响。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORYdDVehyfTf9icxujLiaDIGvCCC9k8pkKJIOIWNbxPgJZIP4Js3ricR56g_%7C_0%3Fwx_fmt%3Djpeg.jpg)
有哪些key会受到影响呢?图中删除了原节点node3,按照顺时针规则,原本node3所拥有的缓存数据就需要“托付”给
node3的顺时针后继节点node1。因此受影响的key只有key4。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORyHXOxlj2PvL6TxicS9IIjRkD7jHk3L8c6JUEzxBvRpeHoibqzEicIpduA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
最终把key4的缓存数据从node3迁移到node1,就形成了新的符合一致性哈希规则的缓存结构。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpmjkrYZ1664qOkxKRric8ORudYExogsnzLxoo7PHH9r06fMTwhhvyRWjAiarwBvnr5K0LhEds5I1UA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQdkcolnJWClrTBGMSQ4Idxicjs2nsoFPss9nDHeO8IzmiciaVRhSqqozag_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQ15iaib1sbxlDo3AHrEmbZ7gHX67ROyHQFq8L94cib3BibPaMfZ2kWwZjEg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQVss660xCakVNUrIrqCMHDpZZsTet4NZHBdsdKibz7v7rtN3FibQLauHQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQEPgAXmHIOdxRZtyG5BW2mBtqNQgVNiaBib2h8mKa1DIicH7P4kzCVCd8A_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQ9Fx4tvyUmH8oM40Xm0bah4DCYcHy5P5DKGJrbcCapImvUG6R1VTQibQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQgHRj5dUPkQkGj79NiaWia3hbVb9b4UCYN484sb84iaL9nNzkFKjq4icWIg_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQSWcIUVIctgEhThEyarBGtiavBgKdM2IREVQkyEH5dhoVOEJWYC04K2g_%7C_0%3Fwx_fmt%3Djpeg.jpg)
如上图所示,假如node1的ip是192.168.1.109,那么原node1节点在环形空间的位置就是hash(“192.168.1.109”)。
我们基于node1构建两个虚拟节点,node1-1 和 node1-2,虚拟节点在环形空间的位置可以利用(IP+后缀)计算,例如:
hash(“192.168.1.109#1”),hash(“192.168.1.109#2”)
此时,环形空间中不再有物理节点node1,node2,只有虚拟节点node1-1,node1-2,node2-1,node2-2。由于虚拟节点数量较多,缓存key与虚拟节点的映射关系也变得相对均衡了。
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQI5ZlnpPicSXQJ0JBuhgMQcfziaDq2QELzEvtLialHeLntfev6dyznkP9Q_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQXTEPWnZw5hIT3PU1gpDN3U3l1v5LSdN7Hke9xIqh7AlBG08K83f7eA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQWv7brQX7tSyQz6ahKh7YobSxqI9OTSrQIpGMemXNPBAgZNaI3cQZ8A_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGpo2UDvIPFHL9TNCgFspxHQJVn8U9uLQDmibufqd04lFp61ib2WlGAHVY2z9VcCH8RTC2icQibTBFUfCQ_%7C_0%3Fwx_fmt%3Djpeg.jpg)
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_jpg_%7C_NtO5sialJZGqMeYuX0RnbBJtiaSvy7JBgZV36kFaTIt5FrFhxF3KzCcUgJSFYd4s9bDxIyqxMVLI3fSCph73QlmA_%7C_0%3Fwx_fmt%3Djpeg.jpg)
漫画算法系列
觉得本文有帮助?请分享给更多人
关注「算法爱好者」,修炼编程内功
![](http://static.careerengine.us/api/aov2/http%3A_%7C__%7C_mmbiz.qpic.cn_%7C_mmbiz_%7C_QtPIxk7nOVcFcJfc3l7xpLl48d2YHYK16VobcpfoBx3z2ibBOS7sNeAumibnmK2zVwxLMibVZBqyL5j7u7TkTfPOA_%7C_640%3Fwx_fmt%3Dpng.jpg)
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。