摘要:一致性哈希算法能盡可能減少了服務(wù)器數(shù)量變化所導(dǎo)致的緩存遷移。哈希算法首先,一致性哈希算法依賴于普通的哈希算法。我們以下面四個(gè)量化的指標(biāo)對(duì)基于不同哈希函數(shù)的一致性哈希算法進(jìn)行評(píng)測。
一致性哈希算法在分布式緩存領(lǐng)域的 MemCached,負(fù)載均衡領(lǐng)域的 Nginx 以及各類 RPC 框架中都有廣泛的應(yīng)用,它主要是為了解決傳統(tǒng)哈希函數(shù)添加哈希表槽位數(shù)后要將關(guān)鍵字重新映射的問題。
本文會(huì)介紹一致性哈希算法的原理及其實(shí)現(xiàn),并給出其不同哈希函數(shù)實(shí)現(xiàn)的性能數(shù)據(jù)對(duì)比,探討Redis 集群的數(shù)據(jù)分片實(shí)現(xiàn)等,文末會(huì)給出實(shí)現(xiàn)的具體 github 地址。
Memcached 與客戶端分布式緩存Memcached 是一個(gè)高性能的分布式緩存系統(tǒng),然而服務(wù)端沒有分布式功能,各個(gè)服務(wù)器不會(huì)相互通信。它的分布式實(shí)現(xiàn)依賴于客戶端的程序庫,這也是 Memcached 的一大特點(diǎn)。比如第三方的 spymemcached 客戶端就基于一致性哈希算法實(shí)現(xiàn)了其分布式緩存的功能。
其具體步驟如下:
向 Memcached 添加數(shù)據(jù),首先客戶端的算法根據(jù) key 值計(jì)算出該 key 對(duì)應(yīng)的服務(wù)器。
服務(wù)器選定后,保存緩存數(shù)據(jù)。
獲取數(shù)據(jù)時(shí),對(duì)于相同的 key ,客戶端的算法可以定位到相同的服務(wù)器,從而獲取數(shù)據(jù)。
在這個(gè)過程中,客戶端的算法首先要保證緩存的數(shù)據(jù)盡量均勻地分布在各個(gè)服務(wù)器上,其次是當(dāng)個(gè)別服務(wù)器下線或者上線時(shí),會(huì)出現(xiàn)數(shù)據(jù)遷移,應(yīng)該盡量減少需要遷移的數(shù)據(jù)量。
客戶端算法是客戶端分布式緩存性能優(yōu)劣的關(guān)鍵。
普通的哈希表算法一般都是計(jì)算出哈希值后,通過取余操作將 key 值映射到不同的服務(wù)器上,但是當(dāng)服務(wù)器數(shù)量發(fā)生變化時(shí),取余操作的除數(shù)發(fā)生變化,所有 key 所映射的服務(wù)器幾乎都會(huì)改變,這對(duì)分布式緩存系統(tǒng)來說是不可以接收的。
一致性哈希算法能盡可能減少了服務(wù)器數(shù)量變化所導(dǎo)致的緩存遷移。
哈希算法首先,一致性哈希算法依賴于普通的哈希算法。大多數(shù)同學(xué)對(duì)哈希算法的理解可能都停留在 JDK 的 hashCode 函數(shù)上。其實(shí)哈希算法有很多種實(shí)現(xiàn),它們?cè)诓煌矫娑几饔袃?yōu)劣,針對(duì)不同的場景可以使用不同的哈希算法實(shí)現(xiàn)。
下面,我們會(huì)介紹一下幾款比較常見的哈希算法,并且了解一下它們?cè)诜植季鶆虺潭龋E鲎哺怕屎托阅艿确矫娴膬?yōu)劣。
MD5 算法:全稱為 Message-Digest Algorithm 5,用于確保信息傳輸完整一致。是計(jì)算機(jī)廣泛使用的雜湊算法之一,主流編程語言普遍已有 MD5 實(shí)現(xiàn)。MD5 的作用是把大容量信息壓縮成一種保密的格式(就是把一個(gè)任意長度的字節(jié)串變換成定長的16進(jìn)制數(shù)字串)。常見的文件完整性校驗(yàn)就是使用 MD5。
CRC 算法:全稱為 CyclicRedundancyCheck,中文名稱為循環(huán)冗余校驗(yàn)。它是一類重要的,編碼和解碼方法簡單,檢錯(cuò)和糾錯(cuò)能力強(qiáng)的哈希算法,在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。
MurmurHash 算法:高運(yùn)算性能,低碰撞率,由 Austin Appleby 創(chuàng)建于 2008 年,現(xiàn)已應(yīng)用到 Hadoop、libstdc++、nginx、libmemcached 等開源系統(tǒng)。Java 界中 Redis,Memcached,Cassandra,HBase,Lucene和Guava 都在使用它。
FNV 算法:全稱為 Fowler-Noll-Vo 算法,是以三位發(fā)明人 Glenn Fowler,Landon Curt Noll,Phong Vo 的名字來命名的,最早在 1991 年提出。 FNV 能快速 hash 大量數(shù)據(jù)并保持較小的沖突率,它的高度分散使它適用于 hash 一些非常相近的字符串,比如 URL,hostname,文件名,text 和 IP 地址等。
Ketama 算法:一致性哈希算法的實(shí)現(xiàn)之一,其他的哈希算法有通用的一致性哈希算法實(shí)現(xiàn),只不過是替換了哈希映射函數(shù)而已,但 Ketama 是一整套的流程,我們將在后面介紹。
一致性哈希算法下面,我們以分布式緩存場景為例,分析一下一致性哈希算法環(huán)的原理。
首先將緩存服務(wù)器( ip + 端口號(hào))進(jìn)行哈希,映射成環(huán)上的一個(gè)節(jié)點(diǎn),計(jì)算出緩存數(shù)據(jù) key 值的 hash key,同樣映射到環(huán)上,并順時(shí)針選取最近的一個(gè)服務(wù)器節(jié)點(diǎn)作為該緩存應(yīng)該存儲(chǔ)的服務(wù)器。具體實(shí)現(xiàn)見后續(xù)的章節(jié)。
比如說,當(dāng)存在 A,B,C,D 四個(gè)緩存服務(wù)器時(shí),它們及其 key 值為1的緩存數(shù)據(jù)在一致性哈希環(huán)上的位置如下圖所示,根據(jù)順時(shí)針取最近一個(gè)服務(wù)器節(jié)點(diǎn)的規(guī)則,該緩存數(shù)據(jù)應(yīng)該存儲(chǔ)在服務(wù)器 B 上。
當(dāng)要存儲(chǔ)一個(gè) key 值為4的緩存數(shù)據(jù)時(shí),它在一致性哈希環(huán)上的位置如下所示,所以它應(yīng)該存儲(chǔ)在服務(wù)器 C 上。
類似的,key 值為5,6的數(shù)據(jù)應(yīng)該存在服務(wù) D 上,key 值為7,8的數(shù)據(jù)應(yīng)該存儲(chǔ)在服務(wù) A 上。
此時(shí),服務(wù)器 B 宕機(jī)下線,服務(wù)器 B 中存儲(chǔ)的緩存數(shù)據(jù)要進(jìn)行遷移,但由于一致性哈希環(huán)的存在,只需要遷移key 值為1的數(shù)據(jù),其他的數(shù)據(jù)的存儲(chǔ)服務(wù)器不會(huì)發(fā)生變化。這也是一致性哈希算法比取余映射算法出色的地方。
由于服務(wù)器 B 下線,key 值為1的數(shù)據(jù)順時(shí)針最近的服務(wù)器是 C ,所以數(shù)據(jù)存遷移到服務(wù)器 C 上。
現(xiàn)實(shí)情況下,服務(wù)器在一致性哈希環(huán)上的位置不可能分布的這么均勻,導(dǎo)致了每個(gè)節(jié)點(diǎn)實(shí)際占據(jù)環(huán)上的區(qū)間大小不一。
這種情況下,可以增加虛節(jié)點(diǎn)來解決。通過增加虛節(jié)點(diǎn),使得每個(gè)節(jié)點(diǎn)在環(huán)上所“管轄”的區(qū)域更加均勻。這樣就既保證了在節(jié)點(diǎn)變化時(shí),盡可能小的影響數(shù)據(jù)分布的變化,而同時(shí)又保證了數(shù)據(jù)分布的均勻。
具體實(shí)現(xiàn)下面我們實(shí)現(xiàn) Memcached 分布式緩存場景下的一致性哈希算法,并給出具體的測試性能數(shù)據(jù)。該實(shí)現(xiàn)借鑒了 kiritomoe 博文中的實(shí)現(xiàn)和 spymemcached 客戶端代碼。具體實(shí)現(xiàn)請(qǐng)看我的github,地址為 https://github.com/ztelur/con...。
NodeLocator 是分布式緩存場景下一致性哈希算法的抽象,它有一個(gè) getPrimary 函數(shù),接收一個(gè)緩存數(shù)據(jù)的 key 值,輸出存儲(chǔ)該緩存數(shù)據(jù)的服務(wù)器實(shí)例。
public interface NodeLocator { MemcachedNode getPrimary(String k); }
下面是通用的一致性哈希算法的實(shí)現(xiàn),它使用 TreeMap 作為一致性哈希環(huán)的數(shù)據(jù)結(jié)構(gòu),其 ceilingEntry 函數(shù)可以獲取環(huán)上最近的一個(gè)節(jié)點(diǎn)。buildConsistentHashRing 函數(shù)中包含了構(gòu)建一致性哈希環(huán)的過程,默認(rèn)加入了 12 個(gè)虛擬節(jié)點(diǎn)。
public class ConsistentHashNodeLocator implements NodeLocator { private final static int VIRTUAL_NODE_SIZE = 12; private final static String VIRTUAL_NODE_SUFFIX = "-"; private volatile TreeMaphashRing; private final HashAlgorithm hashAlg; public ConsistentHashNodeLocator(List nodes, HashAlgorithm hashAlg) { this.hashAlg = hashAlg; this.hashRing = buildConsistentHashRing(hashAlg, nodes); } @Override public MemcachedNode getPrimary(String k) { long hash = hashAlg.hash(k); return getNodeForKey(hashRing, hash); } private MemcachedNode getNodeForKey(TreeMap hashRing, long hash) { /* 向右找到第一個(gè)key */ Map.Entry locatedNode = hashRing.ceilingEntry(hash); /* 想象成為一個(gè)環(huán),超出尾部取出第一個(gè) */ if (locatedNode == null) { locatedNode = hashRing.firstEntry(); } return locatedNode.getValue(); } private TreeMap buildConsistentHashRing(HashAlgorithm hashAlgorithm, List nodes) { TreeMap virtualNodeRing = new TreeMap<>(); for (MemcachedNode node : nodes) { for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) { // 新增虛擬節(jié)點(diǎn)的方式如果有影響,也可以抽象出一個(gè)由物理節(jié)點(diǎn)擴(kuò)展虛擬節(jié)點(diǎn)的類 virtualNodeRing.put(hashAlgorithm.hash(node.getSocketAddress().toString() + VIRTUAL_NODE_SUFFIX + i), node); } } return virtualNodeRing; } }
在 getPrimary 函數(shù)中,首先使用 HashAlgorithm 計(jì)算出 key 值對(duì)應(yīng)的哈希值,然后調(diào)用 getNodeForKey 函數(shù)從 TreeMap 中獲取對(duì)應(yīng)的最近的服務(wù)器節(jié)點(diǎn)實(shí)例。
HashAlgorithm 是對(duì)哈希算法的抽象,一致性哈希算法可以使用各種普通的哈希算法,比如說 CRC ,MurmurHash 和 FNV 等。下面,我們將會(huì)對(duì)比各種哈希算法給該實(shí)現(xiàn)帶來的性能差異性。
性能測試測試數(shù)據(jù)是評(píng)價(jià)一個(gè)算法好壞的最為真實(shí)有效的方法,量化的思維模式一定要有,這也是程序員進(jìn)階的法寶之一。我們以下面四個(gè)量化的指標(biāo)對(duì)基于不同哈希函數(shù)的一致性哈希算法進(jìn)行評(píng)測。
統(tǒng)計(jì)每個(gè)服務(wù)器節(jié)點(diǎn)存儲(chǔ)的緩存數(shù)量,計(jì)算方差和標(biāo)準(zhǔn)差。測量緩存分布均勻情況,我們可以模擬 50000個(gè)緩存數(shù)據(jù),分配到100 個(gè)服務(wù)器,測試最后個(gè)節(jié)點(diǎn)存儲(chǔ)緩存數(shù)據(jù)量的方差和標(biāo)準(zhǔn)差。
隨機(jī)下線10%的服務(wù)器,重新分配緩存,統(tǒng)計(jì)緩存遷移比率。測量節(jié)點(diǎn)上下線的情況,我們可以模擬 50000 個(gè)緩存數(shù)據(jù),分配到100 個(gè)指定服務(wù)器,之后隨機(jī)下線 10 個(gè)服務(wù)器并重新分配這50000個(gè)數(shù)據(jù),統(tǒng)計(jì)緩存分配到不同服務(wù)器的比例,也就是遷移比率。
使用JMH對(duì)不同哈希算法的執(zhí)行效率進(jìn)行對(duì)比。
具體評(píng)測算法如下。
public class NodeLocatorTest { /** * 測試分布的離散情況 */ @Test public void testDistribution() { Listservers = new ArrayList<>(); for (String ip : ips) { servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080))); } // 使用不同的DefaultHashAlgorithm進(jìn)行測試,得出不同的數(shù)據(jù) NodeLocator nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH); // 構(gòu)造 50000 隨機(jī)請(qǐng)求 List keys = new ArrayList<>(); for (int i = 0; i < 50000; i++) { keys.add(UUID.randomUUID().toString()); } // 統(tǒng)計(jì)分布 AtomicLongMap atomicLongMap = AtomicLongMap.create(); for (MemcachedNode server : servers) { atomicLongMap.put(server, 0); } for (String key : keys) { MemcachedNode node = nodeLocator.getPrimary(key); atomicLongMap.getAndIncrement(node); } System.out.println(StatisticsUtil.variance(atomicLongMap.asMap().values().toArray(new Long[]{}))); System.out.println(StatisticsUtil.standardDeviation(atomicLongMap.asMap().values().toArray(new Long[]{}))); } /** * 測試節(jié)點(diǎn)新增刪除后的變化程度 */ @Test public void testNodeAddAndRemove() { List servers = new ArrayList<>(); for (String ip : ips) { servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080))); } //隨機(jī)下線10個(gè)服務(wù)器, 先shuffle,然后選擇0到90,簡單模仿隨機(jī)計(jì)算。 Collections.shuffle(servers); List serverChanged = servers.subList(0, 90); NodeLocator loadBalance = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH); NodeLocator changedLoadBalance = new ConsistentHashNodeLocator(serverChanged, DefaultHashAlgorithm.NATIVE_HASH); // 構(gòu)造 50000 隨機(jī)請(qǐng)求 List keys = new ArrayList<>(); for (int i = 0; i < 50000; i++) { keys.add(UUID.randomUUID().toString()); } int count = 0; for (String invocation : keys) { MemcachedNode origin = loadBalance.getPrimary(invocation); MemcachedNode changed = changedLoadBalance.getPrimary(invocation); // 統(tǒng)計(jì)發(fā)生變化的數(shù)值 if (!origin.getSocketAddress().equals(changed.getSocketAddress())) count++; } System.out.println(count / 50000D); } static String[] ips = {...}; }
JMH的測試腳本如下所示。
@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) @State(Scope.Thread) public class JMHBenchmark { private NodeLocator nodeLocator; private Listkeys; @Benchmark public void test() { for (String key : keys) { MemcachedNode node = nodeLocator.getPrimary(key); } } public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder() .include(JMHBenchmark.class.getSimpleName()) .forks(1) .warmupIterations(5) .measurementIterations(5) .build(); new Runner(opt).run(); } @Setup public void prepare() { List servers = new ArrayList<>(); for (String ip : ips) { servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080))); } nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.MURMUR_HASH); // 構(gòu)造 50000 隨機(jī)請(qǐng)求 keys = new ArrayList<>(); for (int i = 0; i < 50000; i++) { keys.add(UUID.randomUUID().toString()); } } @TearDown public void shutdown() { } static String[] ips = {...}; }
分別測試了 JDK 哈希算法,F(xiàn)NV132 算法,CRC 算法,MurmurHash 算法和Ketama 算法,分別對(duì)應(yīng) DefaultHashAlgorithm 的 NATIVE_HASH,FNV1_32_HASH,CRC_HASH,MURMUR_HASH 和 KETAMA_HASH 。具體數(shù)據(jù)如下所示。
虛擬槽分區(qū)有些文章說,Redis 集群并沒有使用一致性哈希算法,而是使用虛擬槽分區(qū)算法。但是外網(wǎng)(地址見文末)上都說 Redis 使用的虛擬槽分區(qū)只是一致性哈希算法的變種,虛擬槽可以允許 Redis 動(dòng)態(tài)擴(kuò)容。
或許只有去了解一下Redis的源碼才能對(duì)這個(gè)問題作出準(zhǔn)確的回答。請(qǐng)了解的同學(xué)積極留言解答,謝謝。
github 地址: https://github.com/ztelur/con...
redis分布式討論的地址: https://www.reddit.com/r/redi...
https://jistol.github.io/soft...
https://mp.weixin.qq.com/s/oe...
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/62104.html
摘要:五一致性算法的容錯(cuò)性和可擴(kuò)展性現(xiàn)假設(shè)不幸宕機(jī),可以看到此時(shí)對(duì)象不會(huì)受到影響,只有對(duì)象被重定位到。綜上所述,一致性算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù),具有較好的容錯(cuò)性和可擴(kuò)展性。 最近有小伙伴跑過來問什么是Hash一致性算法,說面試的時(shí)候被問到了,因?yàn)椴涣私猓跃蜎]有回答上,問我有沒有相應(yīng)的學(xué)習(xí)資料推薦,當(dāng)時(shí)上班,沒時(shí)間回復(fù),晚上回去了就忘了這件事,今天突然看到這個(gè),...
摘要:面試官聊下的分片集群,先聊好咯面試官是才有的官方集群方案,這塊你了解多少候選者嗯,要不還是從基礎(chǔ)講起唄候選者在前面聊的時(shí)候,提到的都是單實(shí)例存儲(chǔ)所有的數(shù)據(jù)。面試官:聊下Redis的分片集群,先聊 Redis Cluster好咯? 面試官:Redis Cluser是Redis 3.x才有的官方集群方案,這塊你了解多少? 候選者:嗯,要不還是從基礎(chǔ)講起唄? 候選者:在前面聊Re...
摘要:哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去,而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。平衡性平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去,這樣可以使得所有的緩沖空間都得到利用。 memcached分布式原理與實(shí)現(xiàn) 標(biāo)簽(空格分隔): nosql 0x01 概況 1.1 什么是memcached memcached是一個(gè)分布式,開源的數(shù)據(jù)存儲(chǔ)引擎。memcach...
摘要:哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去,而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。平衡性平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去,這樣可以使得所有的緩沖空間都得到利用。 memcached分布式原理與實(shí)現(xiàn) 標(biāo)簽(空格分隔): nosql 0x01 概況 1.1 什么是memcached memcached是一個(gè)分布式,開源的數(shù)據(jù)存儲(chǔ)引擎。memcach...
閱讀 2574·2021-10-19 11:41
閱讀 2415·2021-09-01 10:32
閱讀 3377·2019-08-29 15:21
閱讀 1755·2019-08-29 12:20
閱讀 1161·2019-08-29 12:13
閱讀 599·2019-08-26 12:24
閱讀 2520·2019-08-26 10:26
閱讀 827·2019-08-23 18:40