g u t x .com.tr İpek yolu - Çin'i anlamaya götürürüm

Başlık mülakat soruları: Lütfen Redis'in 9 veri yapısı ve dahili kodlama uygulamaları hakkında konuşun

İnsanların% 90'ı Redis'in en temel 5 veri yapısını biliyor;

İnsanların% 10'undan azı 8 temel veri yapısı, 5 temel + bitmap + GeoHash + HyperLogLog;

İnsanların% 5'inden daha azı, 5.0 Streams'in en son sürümü olan 9 temel veri yapısını biliyor;

İnsanların% 1'inden daha azı 9 temel veri yapısının ve 8 dahili kodun tamamına hakim olmuştur;

Bu makalenin bilgi noktalarında ustalaşın. Röportaj yapanların gözünde Redis'in en güzel çocuğu olun !

Açıklama: Bu makale, Redis-3.2.11 Sürüm kaynak kodu analiz edilir.

5 ortak veri yapısı

Redis hakkında biraz bilgi sahibi olan herkes en temel 5 veri yapısını bilir: String, List, Hash, Set, Sorted Set. Bununla birlikte, hala birkaç yüksek frekanslı mülakat sorusu olduğu unutulmamalıdır.

Set ve Hash arasındaki ilişki

Cevap, Set'in değeri boş olan özel bir Hash olmasıdır. Set tipi işleminin kaynak kodu tset.c. Kodlama türü ise örnek olarak bir öğe eklemeyi alın (intsetTypeAdd (robj * subject, sds değeri)). OBJENCODING_HT , Daha sonra yeni kaynak kodun kaynak kodu aşağıdaki gibidir, aslında dict, Hash veri yapısı üzerinde işlem yapmaktır ve dictSetVal olduğunda değer NULL olur:

dictEntry * de = dictAddRaw (ht, değer, NULL); if (de) {dictSetKey (ht, de, sdsdup (değer)); dictSetVal (ht, de, NULL); dönüş 1;}

Benzer şekilde, thash.c'de Hash türünün yeni öğesini gördüğümüzde, kodlama türünü değerlendirdiğimizde OBJENCODING_HT Ne zaman, aynı zamanda dict: dictAdd (o- > ptr, f, v), dictAdd sonunda dictSetVal () yöntemini çağırır, ancak v, değer NULL değildir:

/ * Hedef hash tablosuna bir eleman ekleyin * / int dictAdd (dict * d, void * key, void * val) {dictEntry * entry = dictAddRaw (d, key, NULL); eğer (! giriş) DICT_ERR; dictSetVal (d, giriş, val); DICT_OK döndür}

Bu nedenle, Redis'te Set ve Hash arasındaki ilişki çok açıktır.Kod OBJENCODINGHT olduğunda, her ikisi de dict veri türleridir, ancak Set, değeri NULL olan özel bir diktedir.

Sıralanmış Set anlayışınız hakkında konuşun

Sıralı Kümenin veri yapısı bir atlama listesidir, yani AtlamaListesi.Aşağıdaki şekilde gösterildiği gibi, kırmızı çizgi 10'u bulma işlemidir:

Sorted set ile çok boyutlu sıralama nasıl gerçekleştirilir

Sıralı Küme, varsayılan olarak yalnızca faktör puanına göre sıralanabilir. Bu şekilde, sınırlama çok büyüktür, örneğin, popüler sıralama listesinin, veritabanındaki ORDER BY downloadcount ve updatetime DESC ile benzer şekilde, indirmelerin en son güncelleme zamanına göre sıralanması gerekir. Peki Redis Sorted Set ile böyle bir gereksinim gerçekleşirse?

Aslında, çok basit. Fikir, sınıflandırmada yer alan çok boyutlu bir sütunu belirli bir şekilde özel bir sütuna dönüştürmektir, yani sonuç = fonksiyon (x, y, z), yani x, y, z üç sıralama faktörüdür , Sonucu hesaplamak için özel işlev işlevi () aracılığıyla indirmeler, zaman vb. Gibi ve sonucu, herhangi bir boyutun sıralama gereksinimlerini elde etmek için Sıralı Kümedeki puanın değeri olarak kullanın.

Redis dahili kodlama

Sıklıkla String, List, Hash, Set, Sorted Set'in sadece harici kodlar olduğunu söyleriz.Aslında her veri yapısının kendi altta yatan dahili kodlama uygulaması vardır ve birden fazla uygulama vardır, böylece Redis doğru sahnede daha uygun olanı seçebilir. İç kodlama.

Aşağıdaki şekilde gösterildiği gibi (resim düzeltme: intset İç kodlama değil kodlama), her veri yapısının ikiden fazla dahili kodlama uygulaması olduğunu görebilirsiniz.Örneğin, String veri yapısı üç dahili kodlama içerir: raw, int ve embstr. Aynı zamanda, bazı dahili kodlar birden fazla harici veri yapısının dahili uygulamaları olarak kullanılabilir.Örneğin, ziplist, hash, list ve zset tarafından paylaşılan dahili koddur, oysa kümenin dahili kodu hashtable veya intset olabilir:

Bu şekilde tasarlanan Redis'in iki avantajı vardır:

Dış veri yapısını ve komutları etkilemeden dahili kodu gizlice geliştirmek mümkündür, böylece daha iyi bir dahili kod geliştirildiğinde, harici veri yapısını ve komutları değiştirmeye gerek kalmaz.
Çeşitli dahili kodlama uygulamaları, farklı senaryolarda kendi avantajlarını oynayabilir. Örneğin, ziplist hafızadan tasarruf sağlar, ancak listede daha fazla öğe olduğunda performans düşecektir. Şu anda Redis, yapılandırma seçeneklerine göre liste türünün dahili uygulamasını bağlantılı listeye dönüştürecektir.

String'in üç dahili kodlaması

Yukarıdaki şekilde görülebileceği gibi, String'in üç dahili kodu şunlardır: int, embstr ve raw. İnt tipinin anlaşılması kolaydır.Bir anahtarın değeri bir tamsayı olduğunda, Redis onu int tipi olarak kodlayacaktır (başka bir koşul vardır: değeri bir dizge olarak ele alın ve uzunluğu 20'yi geçemez). Aşağıdaki gibi. Bu tür bir kodlama hafızadan tasarruf etmek içindir. Redis, varsayılan olarak 10000 tamsayı değerini önbelleğe alacaktır (#define OBJSHAREDINTEGERS 10000), bu, 10 farklı KEY varsa, değerlerinin tümü 10000 içinde olduğu anlamına gelir, aslında hepsi aynı nesneyi paylaşır:

127.0.0.1:6379 > "7890" numarası ayarla OK 127.0.0.1: 6379 > nesne kodlama numarası "int"

Sonraki iki dahili ebmstr ve raw kodunun uzunluk sınırıdır. Lütfen aşağıdaki kaynak koduna bakın:

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44robj * createStringObject (const char * ptr, size_t len) {if (len < = OBJ_ENCODING_EMBSTR_SIZE_LIMIT) return createEmbeddedStringObject (ptr, len); aksi takdirde createRawStringObject (ptr, len);}

Yani embstr ve ham kodlamanın uzunluk limiti 44'tür, aşağıdaki doğrulamayı yapabiliriz. Uzunluk 44'ü aştıktan sonra ham kodlama türüdür ve optimizasyon yapılmayacaktır. Ne kadar uzun, ne kadar bellek tüketilecek:

127.0.0.1:6379 > set adı "a1234567890123456789012345678901234567890123" OK127.0.0.1: 6379 > nesne kodlama adı "embstr" 127.0.0.1:6379 > set adı "a12345678901234567890123456789012345678901234" OK127.0.0.1: 6379 > nesne kodlama adı "ham"

Öyleyse neden embstr kodlaması var? Çiğe göre avantajları nelerdir? Embstr kodlaması, ham kodlama için bir dize nesnesi oluşturmak için gereken alan ayırma sayısını ikiden bire indirir. Embstr ile kodlanmış dizgi nesnelerinin tüm verileri bitişik bir bellekte depolandığından, bu tür kodlanmış dizgi nesneleri önbellekten ham kodlanmış dizge nesnelerinden daha iyi yararlanabilir. Ve embstr ile kodlanmış dizi nesnesinin serbest bırakılması için bellek serbest bırakma işlevinin yalnızca bir kez çağrılması gerekirken, ham kodlanmış dizgi nesnesinin serbest bırakılması bellek serbest bırakma işlevini iki kez çağırmalıdır. Aşağıdaki şekilde gösterildiği gibi, sol embstr kodlamadır ve sağda ham kodlamadır:

ziplist

Önceki şekilden, List, Hash ve Sorted Set'in üç dış yapısı olduğunu görebiliriz.Özel durumlarda, iç kod ziplisttir.Peki bu ziplistin büyüsü nedir?

Hash'i örnek olarak ele alırsak, önce dahili kodunun hangi koşullarda ziplist olduğuna bakalım:

Karma türü öğelerin sayısı, hash-max-ziplist-entry yapılandırmasından az olduğunda (varsayılan 512);
Tüm değerler, hash-max-ziplist-value yapılandırmasından daha azdır (varsayılan olarak 64 bayt);

Sıralı bir kümeyse, iki koşul da karşılanmalıdır:

Eleman sayısı zset-max-ziplist-entry konfigürasyonundan daha azdır, varsayılan 128'dir;
Tüm değerler zset-max-ziplist-değeri yapılandırmasından küçüktür, varsayılan değer 64'tür.

Aslında ziplist, Redis'in depolama verimliliği arayışını tam olarak yansıtıyor. Sıradan çift bağlantılı bir listede, bağlantılı listedeki her öğe bağımsız bir bellek parçasını kaplar ve öğeler adres işaretçileri (veya referanslar) ile bağlanır. Bu yaklaşım, çok fazla bellek parçalanması getirecek ve adres işaretçisi ayrıca ek bellek kullanacaktır. Ziplist tablodur Her öğe ardışık adres alanlarında saklanır , Zippist, bir bütün olarak büyük bir bellek bloğunu kaplar. Bu bir listedir, ancak bağlantılı bir liste değildir.

Ziplist'in kaynak kodu ziplist.c dosyasındadır, bu dosyada şöyle bir açıklama vardır - Ziplist'in genel düzeni aşağıdaki gibidir:

< zlbyte > < zltail > < zllen > < giriş > < giriş > ... < giriş > < zlend >

zlbyte : Bu ziplistin ne kadar yer kapladığını veya kaç bayt kapladığını gösterir; zlbyte'ın kendisi tarafından işgal edilen 4 baytı içerir;
zltail : Ziplistteki son öğeye olan ofseti temsil eder.Bu değerle, pop işleminin zaman karmaşıklığı O (1) 'dir, yani tüm ziplist'i geçmeye gerek yoktur;
zllen : Ziplist'te kaç girdi olduğunu, yani kaç öğenin kaydedildiğini gösterir. Bu alan 16 bayt kapladığından, maksimum değer 2 ^ 16-1'dir; bu, girişlerin sayısı 2 ^ 16-1'i aşarsa, girişlerin sayısını bilmek için tüm ziplist'i geçmeniz gerektiği anlamına gelir;
giriş : Gerçekte kaydedilen verilerin kendi kodu vardır;
zlend : Ziplist'in sonundaki özel karakterleri temsil etmek için özel olarak kullanılır, 8 bayt tutar ve değer 255'te sabittir, yani 8 baytlık her bit 1'dir.

Aşağıdakiler, 2 ve 5 numaralı iki öğeyi içeren gerçek bir ziplist kodlamasıdır:

bağlantılı liste

Bu, Java'daki LinkedList'e karşılık gelen, çok aşina olduğumuz çift bağlantılı bir liste olan List'in çok basit bir kodlama veri yapısıdır.

kaptan

Klasik atlama tablosu veri yapısı olan bundan daha önce de bahsedilmişti.

hashtable

Bu, Java'daki HashMap'e karşılık gelen çok kolaydır.

intset

Özel dahili kodlama ayarlayın, aşağıdaki koşullar karşılandığında Set'in dahili kodlaması hashtable yerine intset olur:

Küme 64 bitlik işaretli bir ondalık tam sayı olmalıdır;
Eleman sayısı set-max-intset-input konfigürasyonunu aşamaz, varsayılan 512'dir;

Doğrulama aşağıdaki gibidir:

127.0.0.1:6379 > sadd puanları 135 (tam sayı) 0127.0.0.1:6379 > sadd puanları 128 (tam sayı) 1127.0.0.1:6379 > nesne kodlama puanları "intset"

Peki, intset kodlaması tam olarak nedir? Kaynak kod tanımına aşağıdaki gibi bakıldığında, bir tamsayı dizisi olduğu ve bir Sıralı tamsayı dizisi . Bellek ayırmada bir şekilde ziplist'e benzer, sürekli bir bellek alanı bloğudur ve büyük tamsayılar ve küçük tamsayılar için farklı kodlamalar kullanır ve bellek kullanımını mümkün olduğunca optimize eder. Böyle bir veri yapısı için, eğer SISMEMBER komutu bir elemanın kümede olup olmadığını kontrol etmek için çalıştırılırsa, aslında ikili arama yöntemi kullanılır:

typedef struct intset {uint32_t kodlaması; uint32_t uzunluk; int8_t içerikleri;} intset; // Intset kodu arama yönteminin kaynak kodu (manuel olarak basitleştirilmiş), standart ikili arama yöntemi: statik uint8_t intsetSearch (intset * is, int64_t value, uint32_t * pos) {int min = 0, max = intrev32ifbe (is- > uzunluk) -1, orta = -1; int64_t cur = -1; while (max > = min) {mid = ((unsigned int) min + (unsigned int) max) > > 1; cur = _intsetGet (is, mid); if (değer > cur) {min = orta + 1;} else if (değer < cur) {max = mid-1;} else {break;}} eğer (değer == kur) {if (konum) * konum = orta; dönüş 1;} değilse {if (konum) * konum = min; dönüş 0;}} # tanımla INTSET_ENC_INT16 (sizeof (int16_t)) # define INTSET_ENC_INT32 (sizeof (int32_t)) # tanımla INTSET_ENC_INT64 (sizeof (int64_t))

3 gelişmiş veri yapısı

Redis'teki üç yüksek seviyeli veri yapısı bitmap, GEO ve HyperLogLog'dur.Bu üç veri yapısı için yazar bunları önceki makalelerde tanıtmıştır. Bunların arasında en önemlisi bit eşlem .

bit eşlem

Bu, Redis tarafından uygulanan BloomFilter'dir. BloomFilter çok basittir. Aşağıdaki şekilde gösterildiği gibi, halihazırda 3 öğenin a, b ve c olduğunu varsayarsak, üç karma algoritma h1 (), h2 () ve h2 () ve ardından biraz Atama için, daha sonra, d'nin zaten var olup olmadığını belirlemeniz gerektiğini varsayın, o zaman d'yi hesaplamak için 3 karma algoritması h1 (), h2 () ve h2 () kullanmanız ve ardından 3 bitin değerini, tam olarak bu 3 biti almanız gerekir. Değeri 1'dir ve bu açıklayabilir: d koleksiyonda mevcut olabilir . Sonra h1 (e) tarafından hesaplanan bitten önceki değer 0 olduğu için e'yi yargılayın, sonra açıklayın: e koleksiyonda bulunmamalıdır :

Bitmap'in gerçek bir veri yapısı olmadığı, esasen bir String veri yapısı olduğu unutulmamalıdır, ancak işlemin ayrıntı düzeyi biraz, yani bit olur. Dize türünün maksimum uzunluğu 512MB olduğu için, bitmap en fazla 2 ^ 32 bit depolayabilir.

GEO

GEO veri yapısı, coğrafi koordinatları Redis'te saklayabilir ve koordinatlar, EPSG: 900913 / EPSG: 3785 / OSGEO: 41001 tarafından aşağıdaki şekilde belirtildiği gibi sınırlandırılmıştır:

Etkili boylam -180 derece ile 180 derece arasındadır.
Etkili enlem, -85.05112878 derece ile 85.05112878 derece arasında değişir.

Koordinat konumu yukarıda belirtilen aralığı aştığında, komut bir hata döndürür. Coğrafi konum komutunu aşağıdaki gibi ekleyin:

Redis > GEOADD city 114.03104022.324386 "shenzhen" 112.57215422.267832 "guangzhou" (tam sayı) 2redis > GEODIST şehri shenzhen guangzhou "150265.8106"

Ancak, Geo'nun kendisinin bir veri yapısı olmadığı unutulmamalıdır. Temelde, hala Sıralı Küme'ye (ZSET) başvurur Ve kullan GeoHash Doldurma teknolojisi. Redis'te, enlem ve boylam 52 bitlik tamsayılar kullanılarak kodlanır ve zset'e yerleştirilir Puan, GeoHash'ın 52 bitlik tam sayı değeridir. Redis for Geo sorgusu kullanılırken, dahili karşılık gelen işlemi aslında zset (skiplist) işlemidir. Zset puanına göre sıralayarak koordinatların yakınındaki diğer elemanları elde edebilir ve puanı koordinat değerine geri yükleyerek elemanların orijinal koordinatlarını elde edebilirsiniz.

Kısacası, Redis'te bu coğrafi koordinat noktalarını işleme fikri şudur: iki boyutlu düzlem koordinat noktaları - > Tek boyutlu tamsayı kod değeri - > zset (puan kodlanmış değerdir) - > zrangebyrank (benzer puana sahip öğeleri al), zrangebyscore - > Koordinat noktasını puana göre tersine çözün (tamsayı kod değeri) - > Yakındaki noktaların coğrafi koordinatları.

GEOHASH prensibi

Wiki'deki örneği kullanarak, enlemi 42.6 ve boylamı -5.6 olan bir noktayı base32'ye nasıl dönüştürebilirim? Önce açıklamak için enlemi alın, enlem aralığı -90 ila 90'dır, bu aralığı iki bölüme ayırın, sonra böyledir ve ardından verilen enlemin hangi aralıkta olduğunu görün. Önceki aralıktaysa, mevcut konumu 0 olarak ayarlayın. , Değer 1 olacaktır. Ardından belirlenen aralık 1'i 2'ye bölmeye devam edin ve bit değerini belirlemek için değerin önde mi yoksa arkada mı olduğunu belirlemeye devam edin. Bu şekilde, aralığı yavaşça, genellikle en fazla 13 kez azaltın (enlem ve boylamın ikili rakamları toplamı 25 bit, boylam 13 bit ve enlem 12 bittir). Bu andaki medyan değer, verilen değere en yakın olanı olacaktır. Aşağıda gösterildiği gibi:

İlk satırda, 42.6 enlemi ortadadır, bu yüzden bit = 1; ikinci satırda, enlem 42.6 ortadadır, yani bit = 0; üçüncü satırda, 42.6 enlemi ortada, yani bit = 1 vb. Bu şekilde, şekildeki biti çıkarın: 101111001001, aynı yöntem, boylamı (-180 ila 180 aralığı) şu şekilde hesaplayın: 0111110000000. Sonuçlar aşağıdaki gibidir:

# 0111110000000 # Latitude 101111001001

Enlem ve boylamın ikili rakamlarını elde ettikten sonra, aşağıdakilerin birleştirilmesi gerekir: enlem ve boylam döngüsünden, her seferinde ikili bitlerinden birini alın (rakamlardan küçük olanlar 0 olarak alınır) ve bunları yeni bir ikili sayı ile birleştirin: 0110111111110000010000010. Her 5 basamak bir ondalık sayıdır ve base32 yazışma tablosu ile birlikte base32 değeri: ezs42'dir. Bu, kodlama işlemini tamamlar.

Canlı Yayınlar

Bu, Redis 5.0 tarafından sunulan yeni bir veri yapısıdır. Akımlar, Redis tarafından uygulanan Kafka'nın bellek sürümüdür. Dahası, Akışlarda ayrıca Tüketici Grupları kavramı. Redis kaynak kodundaki akış tanımından, akışların temel veri yapısının kök ağacı :

typedef struct stream {rax * rax; / * Akışı tutan taban ağacı. * / uint64_t uzunluk; / * Bu akış içindeki öğelerin sayısı. * / streamID last_id; / * Henüz hiç öğe yoksa sıfır. * / rax * cgroups; / * Tüketici grupları sözlüğü: isim- > streamCG * /} akışı;

Peki bu radix ağacı neye benziyor? Redis kaynak kodunun rax.h dosyasında buna benzer bir paragraf var, bu yüzden daha sezgisel görünüyor:

* (f) "" * / * (io) "f" * / \ * "ilk" ("rst") (o) "fo" * / \ * "ilk" "foo" * / \ * "ayak" ("er") ("ar") "foob" * / \ * "altbilgi" "foobar"

Radix Tree (radix tree) aslında neredeyse geleneksel bir ikili ağaçla aynı . Sadece yolu arıyorum, örnek olarak işaretsiz bir int tipi numarası alın, bu sayının her bitini ağaç düğümünün bir çıkarımı olarak kullanın. Örneğin 10001010101010110101010 numaralı bir sayı ise, Radix ağacına göre ekleme kök düğümde, 0 ile karşılaşırsa sol düğümü, 1 ile karşılaşırsa sağ düğümü işaret ettiği söylenebilir.Ağaç düğüm, ekleme işlemi sırasında ve silme işlemi sırasında oluşturulur. Ağaç düğümünü silin. Aşağıdaki 7 kelimelik bir Temel Ağaçtır: