Dağıtılmış Veri Önbelleğinde Tutarlı Hash Algoritması
Tutarlı hash algoritması, MemCached'de dağıtılmış önbellekleme alanında, Nginx'te yük dengeleme alanında ve çeşitli RPC çerçevelerinde yaygın olarak kullanılır.Genel hash fonksiyonuna hash tablosundaki slot sayısını ekleme problemini çözmek için kullanılır. Kelime yeniden eşleme sorunu.
Bu makale, tutarlı hash algoritmasının ilkesini ve uygulamasını tanıtacak ve farklı hash işlevlerinin performans verileri karşılaştırmasını verecek, Redis kümesinde veri parçalama uygulamasını tartışacak, vb. Uygulamanın spesifik github adresi makalenin sonunda verilecektir.
Memcached ve istemci dağıtımlı önbelleğe alma
Memcached yüksek performanslı dağıtılmış bir önbellek sistemidir, ancak sunucu dağıtılmış işlevlere sahip değildir ve sunucular birbirleriyle iletişim kurmayacaktır. Dağıtılmış uygulaması, aynı zamanda Memcached'in önemli bir özelliği olan istemci kitaplığına bağlıdır. Örneğin, üçüncü taraf spymemcached istemcisi, tutarlı bir karma algoritmaya dayalı olarak dağıtılmış önbellek işlevini uygular.
Spesifik adımlar aşağıdaki gibidir:
- Memcached'e veri eklemek için önce istemcinin algoritması, anahtar değerine göre anahtara karşılık gelen sunucuyu hesaplar.
- Sunucu seçildikten sonra, önbelleğe alınan verileri kaydedin.
- Aynı anahtar için veri alırken, istemcinin algoritması verileri elde etmek için aynı sunucuyu bulabilir.
Bu süreçte, istemcinin algoritması önce önbelleğe alınan verilerin mümkün olduğunca eşit bir şekilde her sunucuya dağıtılmasını sağlamalı ve ikinci olarak, tek tek sunucular çevrimdışı veya çevrimiçi olduğunda veri geçişi gerçekleşecek ve taşınması gereken veri miktarı en aza indirilmelidir.
İstemci tarafı algoritması, istemci tarafı dağıtılmış önbelleğin performansının anahtarıdır.
Sıradan karma tablo algoritmaları, genellikle anahtar değerini, karma değerini hesapladıktan sonra kalan işlemle farklı sunuculara eşler, ancak sunucu sayısı değiştiğinde, kalan işlemin bölenini değiştirir ve tüm anahtarlar eşlenir Hemen hemen tüm sunucular değişecek ve bu, dağıtılmış önbellek sistemi için kabul edilemez.
Tutarlı hash algoritması, sunucu sayısındaki değişikliklerin neden olduğu önbellek geçişini en aza indirebilir.
Hash algoritması
İlk olarak, tutarlı karma algoritma, sıradan karma algoritmalara dayanır. Çoğu öğrencinin hash algoritmasını anlaması, JDK'nın hashCode fonksiyonunda kalabilir. Aslında hash algoritmalarının birçok uygulaması vardır ve farklı yönlerden kendi avantajları ve dezavantajları vardır.Farklı senaryolar için farklı hash algoritmaları kullanılabilir.
Aşağıda, birkaç daha yaygın karma algoritma sunacağız ve bunların tekdüze dağılım, karma çarpışma olasılığı ve performans açısından artılarını ve eksilerini anlayacağız.
MD5 algoritması: Tam adı, eksiksiz ve tutarlı bilgi aktarımı sağlamak için kullanılan Message Digest Algorithm 5'tir. Bilgisayarlar tarafından yaygın olarak kullanılan karma algoritmalardan biridir ve MD5 genellikle ana programlama dillerinde uygulanmıştır. MD5'in işlevi, büyük kapasiteli bilgileri gizli bir biçime sıkıştırmaktır (yani, rastgele uzunluktaki bir bayt dizesini sabit uzunlukta onaltılık bir sayı dizesine dönüştürmektir). Yaygın bir dosya bütünlüğü denetimi, MD5 kullanmaktır.
CRC algoritması: Tam adı CyclicRedundancyCheck ve Çince adı Cyclic Redundancy Check'dir. Basit kodlama ve kod çözme yöntemleri ve güçlü hata algılama ve düzeltme yetenekleri ile önemli bir hash algoritması türüdür.Hata kontrolü sağlamak için iletişim alanında yaygın olarak kullanılmaktadır.
MurmurHash algoritması: 2008 yılında Austin Appleby tarafından kurulan yüksek hesaplama performansı, düşük çarpışma oranı, Hadoop, libstdc ++, nginx, libmemcached ve diğer açık kaynaklı sistemlere uygulanmıştır. Redis, Memcached, Cassandra, HBase, Lucene ve Guava Java dünyasında kullanılmaktadır.
FNV algoritması: Tam adı, üç mucit Glenn Fowler, Landon Curt Noll ve Phong Vo'nun adını taşıyan Fowler-Noll-Vo algoritmasıdır. İlk olarak 1991'de önerilmiştir. FNV, büyük miktarda veriyi hızlı bir şekilde hash edebilir ve küçük bir çakışma oranını koruyabilir.Yüksek dağılma derecesi, URL, ana bilgisayar adı, dosya adı, metin ve IP adresi gibi bazı çok benzer dizeleri hashing için uygun hale getirir.
Ketama algoritması: Tutarlı karma algoritmanın uygulamalarından biri.Diğer karma algoritmalar, genel tutarlı karma algoritma uygulamalarına sahiptir.Sadece karma eşleme işlevinin yerini alırlar.Ancak Ketama, tam bir süreçler kümesidir. Daha sonra tanıtıldı.
Tutarlı hash algoritması
Aşağıda, tutarlı karma algoritma döngüsü ilkesini analiz etmek için dağıtılmış önbelleğe alma senaryosunu bir örnek olarak alıyoruz.
Öncelikle, önbellek sunucusunu (ip + bağlantı noktası numarası) hashleyin ve halkadaki bir düğüme eşleyin, önbelleğe alınan verilerin anahtar değerinin karma anahtarını hesaplayın ve bunu halkayla da eşleyin ve önbellek olarak saat yönünde en yakın sunucu düğümünü seçin Depolanması gereken sunucu. Spesifik uygulama için aşağıdaki bölümlere bakın.
Örneğin, dört önbellek sunucusu A, B, C ve D olduğunda, tutarlı karma halkada bunların konumları ve anahtar değeri 1 olan önbelleğe alınmış verileri aşağıdaki şekilde gösterilir ve en yakın sunucu düğümü saat yönünde alınır. Kurallara göre, önbelleğe alınan veriler B sunucusunda saklanmalıdır.
Anahtar değeri 4 olan bir önbellek verisi depolanacağı zaman, tutarlı karma halkadaki konumu aşağıdaki gibidir, bu nedenle C sunucusunda depolanmalıdır.
Benzer şekilde, 5 ve 6 anahtar değerlerine sahip veriler, hizmet D'de depolanmalıdır ve anahtar değerleri 7 ve 8 olan veriler, hizmet A'da depolanmalıdır.
Şu anda, sunucu B kapalı ve çevrimdışıdır ve B sunucusunda depolanan önbellek verilerinin taşınması gerekir, ancak tutarlı karma halkanın varlığı nedeniyle yalnızca anahtar değeri 1 olan verilerin taşınması gerekir ve diğer veri depolama sunucuları gerçekleşmez. Çeşitlilik. Tutarlı hash algoritmasının kalan eşleme algoritmasından daha iyi olduğu yer burasıdır.
B sunucusu çevrimdışı olduğundan, 1 anahtar değerine sahip saat yönünde en yakın sunucu C'dir, bu nedenle veri depolama alanı C sunucusuna taşınır.
Gerçekte, tutarlı karma halkadaki sunucuların konumları o kadar eşit olarak dağıtılamaz ki bu, her düğümün aslında halka üzerinde işgal ettiği farklı boyutlarda aralıklara yol açar.
Bu durumda, çözmek için sanal bir düğüm ekleyebilirsiniz. Sanal düğümler eklenerek, halka üzerindeki her düğüm tarafından "yönetilen" alan daha eşittir. Bu, yalnızca düğüm değiştiğinde, veri dağıtımındaki değişikliğin mümkün olduğu kadar az olmasını ve aynı zamanda veri dağıtımının tekdüzeliğinin sağlanmasını sağlamakla kalmaz.
Uygulama
Aşağıda, Memcached dağıtılmış önbellek senaryosunda tutarlı hash algoritmasını uyguluyor ve belirli test performansı verilerini veriyoruz. Bu uygulama, kiritomoe blog gönderisindeki ve spymemcached istemci kodundaki uygulamaya dayanır. Lütfen özel uygulama için github'ıma bakın, adres https://github.com/ztelur/consistent-hash-algorithm'dir.
NodeLocator, dağıtılmış önbelleğe alma senaryolarında tutarlı bir karma algoritmanın bir soyutlamasıdır. Önbelleğe alınmış bir verinin anahtar değerini alan ve önbelleğe alınmış verileri depolayan sunucu örneğini çıkaran bir getPrimary işlevine sahiptir.
genel arayüz NodeLocator { MemcachedNode getPrimary (Dize k); }Aşağıda evrensel tutarlı hash algoritmasının uygulaması yer almaktadır: Tutarlı hashing halkasının veri yapısı olarak TreeMap'i kullanır. CeilingEntry işlevi halka üzerindeki en yakın düğümü alabilir. BuildConsistentHashRing işlevi, tutarlı bir karma halka oluşturma işlemini içerir ve varsayılan olarak 12 sanal düğüm eklenir.
public class ConsistentHashNodeLocator, NodeLocator { özel nihai statik int VIRTUAL_NODE_SIZE = 12; private final static String VIRTUAL_NODE_SUFFIX = "-"; özel geçici TreeMap < Uzun, MemcachedNode > hashRing; özel nihai HashAlgorithm hashAlg; public ConsistentHashNodeLocator (Liste < MemcachedNode > düğümler, HashAlgorithm hashAlg) { this.hashAlg = hashAlg; this.hashRing = buildConsistentHashRing (hashAlg, düğümler); } @Override public MemcachedNode getPrimary (Dize k) { uzun hash = hashAlg.hash (k); getNodeForKey (hashRing, hash); } özel MemcachedNode getNodeForKey (TreeMap < Uzun, MemcachedNode > hashRing, uzun hash) { / * Sağdaki ilk anahtarı bul * / Harita Giriş < Uzun, MemcachedNode > locatedNode = hashRing.ceilingEntry (hash); / * Bir yüzük olduğunuzu hayal edin, kuyruğun ötesindeki ilkini çıkarın * / eğer (locatedNode == null) { locatedNode = hashRing.firstEntry (); } locationNode.getValue () döndür; } özel TreeMap < Uzun, MemcachedNode > buildConsistentHashRing (HashAlgorithm hashAlgorithm, List < MemcachedNode > düğümler) { Ağaç Haritası < Uzun, MemcachedNode > virtualNodeRing = yeni TreeMap < > (); for (MemcachedNode düğümü: düğümler) { for (int i = 0; i < VIRTUAL_NODE_SIZE; i ++) { // Sanal düğüm ekleme yönteminin bir etkisi varsa, sanal düğümleri fiziksel düğümlerden genişleten bir sınıfı da soyutlayabilirsiniz virtualNodeRing.put (hashAlgorithm.hash (node.getSocketAddress (). toString () + VIRTUAL_NODE_SUFFIX + i), düğüm); } } virtualNodeRing döndür; } }GetPrimary işlevinde, anahtar değerine karşılık gelen karma değerini hesaplamak için önce HashAlgorithm'i kullanın ve ardından TreeMap'ten karşılık gelen en yakın sunucu düğümü örneğini elde etmek için getNodeForKey işlevini çağırın.
HashAlgorithm, hash algoritmasının bir soyutlamasıdır. Tutarlı hash algoritması, CRC, MurmurHash ve FNV gibi çeşitli yaygın hash algoritmalarını kullanabilir. Aşağıda, çeşitli hash algoritmalarının bu uygulamaya getirdiği performans farklılıklarını karşılaştıracağız.
Performans testi
Test verileri, bir algoritmanın kalitesini değerlendirmenin en doğru ve etkili yoludur.Kantitatif bir düşünme modu mevcut olmalıdır. Bu aynı zamanda programcıların ilerlemesi için sihirli silahlardan biridir. Farklı hash fonksiyonlarına dayalı tutarlı hash algoritmalarını değerlendirmek için aşağıdaki dört niceliksel göstergeyi kullanıyoruz.
- Her sunucu düğümünde depolanan önbellek sayısını sayın ve sapmayı ve standart sapmayı hesaplayın. Önbellek dağılımının tekdüzeliğini ölçmek için, 50.000 önbelleğe alınmış veriyi simüle edebilir, bunları 100 sunucuya dağıtabilir ve son düğümde depolanan önbelleğe alınmış veri miktarının varyansını ve standart sapmasını test edebiliriz.
- Sunucuların% 10'u rastgele çevrimdışı, önbelleği yeniden tahsis edin ve önbellek geçiş oranını sayın. Düğümlerin çevrimiçi ve çevrimdışı durumunu ölçmek için, 50.000 önbelleğe alınmış veriyi simüle edebilir ve bunları belirlenen 100 sunucuya tahsis edebilir, ardından rastgele 10 sunucudan çıkıp 50.000 veriyi yeniden dağıtabilir ve farklı sunuculara ayrılan önbellek oranını hesaplayabiliriz, bu geçiş oranıdır. .
- Farklı karma algoritmaların yürütme verimliliğini karşılaştırmak için JMH'yi kullanın.
Spesifik değerlendirme algoritması aşağıdaki gibidir.
public class NodeLocatorTest { / ** * Dağılımın dağılımını test edin * / @Ölçek public void testDistribution () { Liste < MemcachedNode > sunucular = new ArrayList < > (); for (String ip: ips) { server.add (yeni MemcachedNode (yeni InetSocketAddress (ip, 8080))); } // Test etmek ve farklı verileri almak için farklı DefaultHashAlgorithm kullanın NodeLocator nodeLocator = new ConsistentHashNodeLocator (sunucular, DefaultHashAlgorithm.NATIVE_HASH); // 50000 rastgele istek oluşturun Liste < Dize > anahtarlar = new ArrayList < > (); for (int i = 0; i < 50000; i ++) { keys.add (UUID.randomUUID (). toString ()); } // İstatistiksel dağılım AtomicLongMap < MemcachedNode > atomicLongMap = AtomicLongMap.create (); for (MemcachedNode sunucusu: sunucular) { atomicLongMap.put (sunucu, 0); } for (Dize anahtarı: anahtarlar) { MemcachedNode düğümü = nodeLocator.getPrimary (anahtar); atomicLongMap.getAndIncrement (düğüm); } System.out.println (StatisticsUtil.variance (atomicLongMap.asMap (). Values (). ToArray (yeni Long {}))); System.out.println (StatisticsUtil.standardDeviation (atomicLongMap.asMap (). Values (). ToArray (yeni Long {}))); } / ** * Test düğümü eklendikten ve silindikten sonraki değişim derecesi * / @Ölçek public void testNodeAddAndRemove () { Liste < MemcachedNode > sunucular = new ArrayList < > (); for (String ip: ips) { server.add (yeni MemcachedNode (yeni InetSocketAddress (ip, 8080))); } // Rastgele çevrimdışı 10 sunucu, önce karıştırın ve ardından 0'dan 90'a kadar seçin, rastgele hesaplamayı taklit edin. Collections.shuffle (sunucular); Liste < MemcachedNode > serverChanged = sunucular.subList (0, 90); NodeLocator loadBalance = new ConsistentHashNodeLocator (sunucular, DefaultHashAlgorithm.NATIVE_HASH); NodeLocator changeLoadBalance = new ConsistentHashNodeLocator (serverChanged, DefaultHashAlgorithm.NATIVE_HASH); // 50000 rastgele istek oluşturun Liste < Dize > anahtarlar = 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 (çağırma); MemcachedNode değişti = değiştirildiLoadBalance.getPrimary (çağırma); // Değiştirilen değeri say eğer (! origin.getSocketAddress (). equals (değiştirildi.getSocketAddress ())) count ++; } System.out.println (sayım / 50000D); } statik Dizge ips = {...}; }JMH'nin test komut dosyası aşağıda gösterilmektedir.
@BenchmarkMode (Mode.AverageTime) @OutputTimeUnit (TimeUnit.MICROSECONDS) @State (Scope.Thread) public class JMHBenchmark { özel NodeLocator nodeLocator; özel liste < Dize > anahtarlar; @BenimKahve public void testi () { for (Dize anahtarı: anahtarlar) { MemcachedNode düğümü = nodeLocator.getPrimary (anahtar); } } public static void main (String args) RunnerException { Seçenekler opt = new OptionsBuilder () .include (JMHBenchmark.class.getSimpleName ()) .forks (1) .warmupIterations (5) .measurementIterations (5) .inşa etmek(); new Runner (opt) .run (); } @Kurmak public void ready () { Liste < MemcachedNode > sunucular = new ArrayList < > (); for (String ip: ips) { server.add (yeni MemcachedNode (yeni InetSocketAddress (ip, 8080))); } nodeLocator = new ConsistentHashNodeLocator (sunucular, DefaultHashAlgorithm.MURMUR_HASH); // 50000 rastgele istek oluşturun anahtarlar = new ArrayList < > (); for (int i = 0; i < 50000; i ++) { keys.add (UUID.randomUUID (). toString ()); } } @Sökmek public void shutdown () { } statik Dizge ips = {...}; }DefaultHashAlgorithm'in NATIVE_HASH, FNV1_32_HASH, CRC_HASH, MURMUR_HASH ve KETAMA_HASH'a karşılık gelen sırasıyla JDK hash algoritması, FNV132 algoritması, CRC algoritması, MurmurHash algoritması ve Ketama algoritması test edilmiştir. Spesifik veriler aşağıda gösterilmiştir.
Sanal yuva bölümü
Bazı makaleler, Redis kümesinin tutarlı bir karma algoritma değil, sanal bir yuva bölümleme algoritması kullandığını söylüyor. Bununla birlikte, harici ağda (makalenin sonundaki adrese bakın), Redis tarafından kullanılan sanal slot bölümünün sadece tutarlı hash algoritmasının bir varyantı olduğu ve sanal alanın Redis'in dinamik olarak genişlemesine izin verebileceği söyleniyor.
Belki de yalnızca Redis'in kaynak kodunu anlayarak bu soruyu doğru yanıtlayabiliriz. Lütfen biliyorsanız cevaplamak için bir mesaj bırakın, teşekkür ederim.
Kişisel WeChat genel hesabı: remcarpediem, programcı Li Xiaobing
Kişisel blog adresi:
github adresi: https://github.com/ztelur/consistent-hash-algorithm
Redis dağıtılmış tartışmanın adresi: https://www.reddit.com/r/redis/comments/4yztxi/which_one_is_better_hash_slot_or_consistent/
referans
- https://jistol.github.io/software%20engineering/2018/07/07/consistent-hashing-sample/
- https://mp.weixin.qq.com/s/oe3EPu5DxB0bWheBImMsHg
