Perbincangan ringkas tentang kamus, algoritma cincang dan prinsip ReHash dalam Redis

Artikel ini akan memperkenalkan anda kepada kamus, algoritma cincang dan prinsip ReHash dalam Redis saya harap ia akan membantu anda!

Kamus dalam Redis digunakan secara meluas untuk melaksanakan pelbagai fungsi Redis, termasuk pangkalan data dan kekunci cincang.

Pelaksanaan asas kamus ialah jadual cincang Setiap kamus mempunyai dua jadual cincang, satu digunakan seperti biasa dan satu lagi digunakan apabila cincang digunakan untuk mengembangkan ruang. [Cadangan berkaitan: Tutorial video Redis]

Takrif struktur kamus

typedef struct dict {
	
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;
	
	// 哈希表，两个元素
	dictht ht[2]
	
	// rehash时记录的索引下标，当没有rehash时，值为-1
	int rehashidx;

} dict;

== Apabila melakukan rehash, rehashidx memindahkan satu Entri diindeks data akan menjadi 1; ==

Di mana, struktur jadual hash dicttht ditakrifkan sebagai:

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;
	
	// 哈希表大小
	unsigned long size;
	
	// 哈希表大小掩码，用于计算索引值
	unsigned long sizenask;
	
	// 该哈希表已有节点的数量
	unsigned long uesd;

} dictht;

di mana, jadual ialah tatasusunan, dan setiap elemen tatasusunan menghala ke Penunjuk Jenis dictEntry, jenis dictEntry menyimpan pasangan nilai kunci.

Ia juga boleh dilihat di sini bahawa nod jadual cincang disambungkan dengan senarai terpaut untuk menyelesaikan masalah konflik cincang, iaitu kaedah alamat rantai.

Konflik cincang dan algoritma cincang

Untuk mencapai akses pantas daripada kunci kepada nilai, Redis menggunakan jadual cincang untuk menyimpan semua pasangan nilai kunci. Kekunci sepadan dengan Kunci yang ditetapkan oleh Redis, dan nilai bukan sepadan dengan nilai itu sendiri, tetapi dengan penunjuk yang menunjuk kepada nilai khusus . Kelebihan terbesar menggunakan jadual cincang ialah anda boleh mencari pasangan nilai kunci dengan cepat dengan kerumitan masa O(1). Tetapi kerana ia adalah jadual cincang, sudah pasti akan ada masalah konflik cincang.

Konflik cincang bermakna apabila nilai cincang dua kekunci dan baldi cincang dikira, ia berlaku pada baldi cincang yang sama.

Cara Redis menyelesaikan konflik cincang adalah dengan menggunakan pencincangan rantai, iaitu kaedah zip. Apabila berbilang elemen menghala ke baldi cincang yang sama, senarai terpaut digunakan untuk menyimpan data yang sepadan dalam baldi cincang yang sama, dan ia disambungkan secara bergilir menggunakan penunjuk.

Algoritma cincang

Apabila menambahkan pasangan nilai kunci baharu pada kamus, atur cara perlu terlebih dahulu mengira nilai cincang dan indeks berdasarkan pasangan nilai kunci nilai, dan kemudian letakkan nod jadual cincang yang mengandungi pasangan nilai kunci baharu pada indeks yang ditentukan tatasusunan jadual cincang berdasarkan nilai indeks.

proses reHash

Terdapat faktor beban dalam jadual cincang untuk mengawal bilangan pasangan nilai kunci yang disimpan dalam jadual cincang. Ini memerlukan operasi rehash untuk diselesaikan. Antaranya, formula pengiraan faktor beban ialah:

// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

Syarat untuk pengembangan dan pengecutan jadual hash adalah seperti berikut:

• Pelayan tidak melaksanakan BGSAVE pada masa ini arahan atau arahan BGREWRITEAOF, dan ha Faktor beban jadual cincang adalah lebih besar daripada atau sama dengan 1;
• Pelayan sedang melaksanakan perintah BGSAVE atau arahan BGREWRITEAOF dan faktor muatan jadual cincang adalah lebih besar daripada atau sama dengan 5;

Salah satu syarat di atas Jika berpuas hati, proses rehash akan dilaksanakan.

Jika pelayan melaksanakan BGSAVE atau BGREWRITEAOF, Redis akan mencipta proses anak bagi proses pelayan semasa

Proses rehash secara kasar dibahagikan kepada tiga langkah:

• Peruntukkan ruang yang lebih besar kepada jadual cincang 2, contohnya dua kali saiz semasa jadual cincang 1; 2;

• mengeluarkan ruang jadual hash 1; rehash semasa Ditentukan oleh jenis operasi dan bilangan pasangan nilai kunci dalam jadual cincang semasa.

• Apabila operasi pengembangan dilakukan, saiz ruang yang diperuntukkan ialah nilai 2^n pertama yang lebih besar daripada atau sama dengan (bilangan pasangan nilai kunci dalam jadual cincang * 2);

Anggapkan bahawa bilangan pasangan nilai kunci semasa ialah 4, maka 4 * 2 = 8, kerana 8 betul-betul sama dengan 2^3, yang betul-betul sama dengan nilai pertama bersamaan dengan 2 ^n, jadi ruang pengembangan ialah 8;

Jika operasi pengecutan dilakukan, saiz ruang yang diperuntukkan ialah nilai 2^n pertama lebih besar daripada atau sama dengan (bilangan kunci -pasangan nilai dalam jadual cincang);

• Progressive ReHash

• Apabila terdapat sejumlah besar jadual cincang, jika semua data adalah disalin sekali gus, ia berkemungkinan menjejaskan pelayan. Oleh itu, Redis melakukan rehash dalam beberapa kali, iaitu rehash progresif.

Ringkasnya, dalam langkah kedua, Redis masih memproses permintaan pelanggan secara normal Apabila memproses permintaan, ia bermula dari kedudukan indeks pertama dalam jadual cincang 1, dan kemudian menukar indeks ini Semua elemen entri di bahagian. kedudukan disalin ke jadual cincang 2; apabila permintaan seterusnya dibuat, entri pada kedudukan indeks seterusnya disalin.

Dengan cara ini, overhed sejumlah besar salinan pada satu masa diagihkan dengan sangat bijak ke dalam proses memproses berbilang permintaan, mengelakkan operasi yang memakan masa dan memastikan akses pantas kepada data.

Operasi jadual cincang semasa cincang semula

Apabila melakukan operasi cincang semula progresif, pemadaman kamus, carian, kemas kini dan operasi lain akan dilakukan dalam dua jadual cincang. Sebagai contoh, jika anda ingin mencari kunci dalam kamus, anda akan menanyakannya terlebih dahulu dalam jadual asal Jika ia tidak menemuinya, anda akan menanyakannya dalam jadual baharu.

Dan operasi penambahan kamus hanya akan disimpan dalam jadual baharu.

Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati: Pengenalan kepada Pengaturcaraan! !

Atas ialah kandungan terperinci Perbincangan ringkas tentang kamus, algoritma cincang dan prinsip ReHash dalam Redis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!