อธิบายการสแกนตาราง Redis Hash:ภายในกลไก

โอเค ดังนั้นเราจึงทำซ้ำกลุ่มองค์ประกอบต่างๆ อะไรต่อไป? เราจะคืนค่าเคอร์เซอร์สำหรับการโทรครั้งถัดไปไปที่ 228 . ซึ่งทำได้โดยการเพิ่มเคอร์เซอร์ปัจจุบัน 230 แต่พลิกสถานการณ์! เคอร์เซอร์จะย้อนกลับในขั้นแรก จากนั้นเพิ่มขึ้น จากนั้นจึงย้อนกลับอีกครั้ง:

 /* Set unmasked bits so incrementing the reversed cursor
 * operates on the masked bits */
 v |= ~m0;
 /* Increment the reverse cursor */
 v = rev(v);
 v++;
 v = rev(v);

อันดับแรก 240 ตั้งค่าบิตที่ไม่ปกปิดทั้งหมดใน 253 ถึง 1. ผลที่ได้คือเมื่อถอยหลัง 267 และเพิ่มขึ้นบิตเหล่านี้จะถูกละเว้นอย่างมีประสิทธิภาพ จากนั้น 278 กลับด้าน เพิ่มขึ้น และกลับด้านอีกครั้ง ลองดูตัวอย่าง:

Table size = 16 (n = 4, m0 = 16-1 = 00001111)
v = 00001000 (Current cursor)
v |= ~m0; // v == 11111000 (~m0 = 11110000)
v = rev(v); // v == 00011111
v++; // v == 00100000
v = rev(v); // v == 00000100

หลังจากบิตมหัศจรรย์นี้ 280 ถูกส่งกลับ

เหตุใดเคอร์เซอร์จึงกลับด้านก่อนที่จะเพิ่มขึ้น ตารางอาจเพิ่มขึ้นระหว่างการวนซ้ำ สิ่งนี้รับประกันได้ว่าเคอร์เซอร์จะยังคงใช้งานได้ เมื่อตารางขยายใหญ่ขึ้น บิตเพิ่มเติมจะถูกเพิ่มลงในมาสก์ขนาด จากด้านซ้าย . ด้วยการเพิ่มจำนวนที่กลับกัน เราสามารถขยายดัชนีของตารางที่เล็กลงให้เป็นดัชนีที่ใหญ่กว่าได้

ตัวอย่างเช่น สมมติว่าโต๊ะเก่ามีขนาด 16 (มาสก์ขนาด 291 ) และเคอร์เซอร์คือ 300 . เมื่อตารางขยายเป็น 32 องค์ประกอบ ขนาดมาสก์จะเป็น 316 . องค์ประกอบทั้งหมดก่อนหน้านี้ใน 329 slot จะแมปกับ 333 หรือ 347 ในตารางใหม่ เคอร์เซอร์เหล่านี้เข้ากันได้กับตารางทั้งเล็กและใหญ่!

2. กำลังสแกนระหว่างการปรับปรุงตาราง

ส่วนสุดท้ายที่เราต้องเข้าใจคือวิธีการทำงานของการสแกนในขณะที่ตารางกำลังทำการปรับปรุงใหม่ การปรับปรุงใหม่แบบค่อยเป็นค่อยไป ถูกนำไปใช้ใน dict.c โดยมีตารางที่ใช้งานอยู่สองตารางพร้อมกัน ตารางที่สองจะถูกสร้างขึ้นเมื่อมีการปรับขนาดตารางแฮช รายการใหม่จะถูกเพิ่มลงในตารางใหม่ ในทุกขั้นตอนการปรับปรุงองค์ประกอบจากตารางเก่าจะถูกย้ายไปยังตารางใหม่ เมื่อตารางเก่าว่างเปล่า ตารางนั้นจะถูกลบออก

เมื่อทำการสแกน ตารางทั้งเก่าและใหม่จะถูกสแกนหาองค์ประกอบ โดยเริ่มจากเล็กลง ตาราง . หลังจากสแกนรายการในตารางเล็กแล้ว รายการเสริม จากตารางที่ใหญ่กว่าจะถูกสแกน ดังนั้นองค์ประกอบทั้งหมดที่ครอบคลุมโดยเคอร์เซอร์ 350 ถูกสแกน เรามาดูกันว่าสิ่งนี้มีลักษณะอย่างไร นี่คือข้อมูลโค้ดทั้งหมด เราจะแจกแจงรายละเอียดด้านล่าง:

 } else { // dictIsRehashing(d)
 t0 = &d->ht[0];
 t1 = &d->ht[1];
 /* Make sure t0 is the smaller and t1 is the bigger table */
 if (t0->size > t1->size) {
 t0 = &d->ht[1];
 t1 = &d->ht[0];
 }
 m0 = t0->sizemask;
 m1 = t1->sizemask;
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
 de = t0->table[v & m0];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Iterate over indices in larger table that are the expansion
 * of the index pointed to by the cursor in the smaller table */
 do {
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
 de = t1->table[v & m1];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Increment the reverse cursor not covered by the smaller mask.*/
 v |= ~m1;
 v = rev(v);
 v++;
 v = rev(v);
 /* Continue while bits covered by mask difference is non-zero */
 } while (v & (m0 ^ m1));
 }

ก่อนอื่น 369 และ 377 ใช้เพื่อจัดเก็บตารางเล็กและใหญ่ตามลำดับด้วย 383 และ 395 ขนาดมาส์กสำหรับแต่ละอัน จากนั้นสแกนตารางเล็กๆ เหมือนกับที่เราเห็นก่อนหน้านี้

จากนั้น เคอร์เซอร์จะถูกใช้เพื่อสร้างดัชนีลงในตารางที่ใหญ่กว่า โดยใช้มาสก์ขนาดที่ใหญ่กว่า 405 :415 . ในวงใน เคอร์เซอร์จะเพิ่มขึ้นเพื่อครอบคลุมการขยายทั้งหมดของดัชนีของตารางที่เล็กลง