home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Redis

Redis Hash Table Scan: กลไกภายในของคำสั่ง SCAN

Redis SCAN Command

SCAN เป็น cursor-based iterator วนลูปทุก elements ใน hash table คุณสมบัติ:

  1. รับประกันว่าจะคืนทุก item อย่างน้อย 1 ครั้ง
  2. Stateless — ไม่เก็บ state ของ scanner, ไม่ lock database
  3. ทนทานต่อ table resizing (rehashing)

Implementation ใน dict.c (dictScan())

1. Normal Scanning (ไม่ได้ rehashing)

  • Hash table size = 2^n, size mask m0 = 2^n - 1 (binary: n LSBs = 1)
  • Cursor v ใช้ index: v & m0 (bitwise AND → valid index)
  • Iterate bucket (linked list) ที่ index นั้น เรียก fn สำหรับแต่ละ entry
  • Cursor update: reverse → increment → reverse
v |= ~m0;        // set unmasked bits to 1
v = rev(v);      // reverse bits
v++;             // increment
v = rev(v);      // reverse back

ทำไมต้อง reverse?

เมื่อ table ขยาย (resize) size mask เพิ่ม bit ด้านซ้าย (MSB) Reverse cursor ทำให้ index เดิม map ไปยัง bucket เดิมและ bucket ใหม่ที่ขยายมา → cursor ยัง valid หลัง resize

ตัวอย่าง: size 16 (mask 00001111), cursor 00001000 → ขยายเป็น 32 (mask 00011111) → cursor เข้ากันได้ทั้ง 00001000 และ 00011000

2. Scanning ระหว่าง Rehashing (Incremental Rehashing)

Redis ใช้ 2 tables พร้อมกัน: ht[0] (เก่า), ht[1] (ใหม่) rehash ทีละนิด

  • Scan เริ่มจาก table เล็กกว่า (t0)
  • จากนั้น scan "complementing items" ใน table ใหญ่ (t1) ที่ขยายมาจาก index เดียวกัน
  • Loop increment reversed cursor จนครอบคลุมทุก expansion (while (v & (m0 ^ m1)))

สรุป

SCAN ใช้ bit-reversal cursor เพื่อรองรับ incremental rehashing และ stateless iteration โค้ด rev() ใช้ O(log n) bit operations โครงสร้าง dict.c ออกแบบได้อย่างชาญฉลาด