Tác giả: Ehud Tamir
Một trong những thách thức lớn cho tôi như software developer là đọc code của người khác. Cho bài viết này, tôi đọc một đoạn C code thú vị mà tôi chưa biết trước, và tôi sắp trình bày nó cho bạn. Code tôi sẽ nói về là phần của database Redis, và có thể tìm thấy ở đây.
Redis là key-value database. Mọi entry trong database là mapping từ key đến value. Values có thể có vài types. Có integers, lists, hash tables và hơn thế nữa. Behind the scenes, database chính nó cũng là hash table. Trong bài này, chúng ta sẽ khám phá command SCAN trong Redis.
_By © User:Colin / Wikimedia Commons, CC BY-SA 4.0, [https://commons.wikimedia.org/w/index.php?curid=30343877](https://commons.wikimedia.org/w/index.php?curid=30343877" rel="noopener" target="blank" title=")
Redis SCAN
SCAN là cursor-based iteration command, cho phép client duyệt qua tất cả elements trong table. Cursor-based scanner này chấp nhận integer cursor trên mỗi call, và trả về một batch items và giá trị cursor để dùng trong call tiếp theo đến SCAN. Giá trị cursor ban đầu là 0, và khi SCAN trả về 0 làm next cursor value, có nghĩa là scan xong và tất cả elements đã được client thấy.
Lệnh SCAN có vài properties thú vị:
- Nó đảm bảo tất cả items có mặt trong table sẽ được trả về ít nhất một lần.
- Nó stateless. Table không lưu bất kỳ data nào về active scanners của nó. Điều này cũng có nghĩa là scans không lock database.
- Nó resilient (kiên nhẫn) với table resizing. Để duy trì O(1) access time, hash tables duy trì load factor nhất định. Load factor đo lường table "đầy" đến đâu tại thời điểm cho trước. Khi load factor quá lớn hoặc quá nhỏ, table bị resize. SCAN sẽ giữ guarantees của nó ngay cả khi được gọi trong khi table đang được resize.
Triển khai (Implementation)
SCAN được triển khai trong dict.c, trong function dictScan(). Đây là signature của function và housekeeping thêm:
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction* bucketfn, void *privdata) {
dictht *t0, *t1;
const dictEntry *de, *next;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0;
// ...
Điều đáng chú ý:
- Function chấp nhận 5 tham số:
dict *d, dictionary để scan,unsigned long v, cursor, và 3 tham số khác chúng ta sẽ đi vào sau. - Function trả về cursor value để dùng trong call tiếp theo đến function này. Nếu function trả về 0, nghĩa là scan xong.
if (dictSize(d) == 0) return 0;. Khi dictionary rỗng function trả về 0 để chỉ ra scan xong.
1. Normal scanning (Quét bình thường)
Mã sau quét một nhóm elements:
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->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;
}
/* 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);
} else {
// ...
Hãy xem từng bước. Hãy bắt đầu với dòng đầu tiên dưới đây:
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->sizemask;
Rehashing là quá trình phân bố elements đều qua table sau khi nó bị resize. Hash table dict.c rehash incrementally (tăng dần), nghĩa là nó không rehash toàn bộ table cùng lúc, mà little-by-little (mỗi chút một). Mọi operation làm trên table, như add, delete, find, cũng thực hiện một rehash step. Điều này cho phép giữ table available cho operations trong lúc rehashing. Do cách rehashing được triển khai, function hoạt động khác trong lúc rehashing. Chúng ta sẽ bắt đầu xem gì xảy ra khi table không rehashing.
Con trỏ đến hash table được lưu trong local variable t0, và size mask của nó được lưu trong m0. Size mask: dict.c hash tables luôn có size 2^n. Với table size cho trước, size mask là 2^n-1, là binary number với n least-significant bits set thành 1. Ví dụ, với n=4; 2^n-1 = 00001111. Với key cho trước, vị trí của nó trong hash table sẽ là n bits cuối của hash của key. Chúng ta sẽ thấy điều này hoạt động sau chút.
Dict.c hash table dùng open addressing. Mọi entry trong table là linked-list của elements với conflicting hash value. Điều này gọi là bucket. Trong phần tiếp theo, một bucket elements được scan:
/* 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;
}
Chú ý dùng size mask: t0->table[v & m0]. v có thể ngoài indexable range của table. v & m0 dùng size mask để giữ chỉ last n digits of v, và yield valid index vào table.
Bạn có thể đã đoán bucketfn là làm gì. bucketfn được cung cấp bởi caller và áp dụng cho mỗi bucket elements. Nó cũng được truyền privdata, là arbitrary data truyền cho dictScan() bởi caller. Tương tự, fn được áp dụng cho tất cả entries trong bucket one-by-one. Lưu ý bucket có thể rỗng, trong trường hợp value là NULL.
OK, chúng ta lặp qua bucket elements. Tiếp theo gì? Chúng ta sẽ trả về cursor value cho call tiếp theo đến dictScan(). Điều này làm bằng cách increment cursor hiện tại v, nhưng có twist! Cursor đầu tiên bị reversed, sau đó incremented, và sau đó reversed lại:
/* 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);
Đầu tiên, v |= ~m0 set tất cả non-masked bits trong v thành 1. Hiệu ứng là khi reversing v và incrementing, các bits này sẽ bị effectively ignored. Sau đó, v bị reversed, incremented và reversed lại. Hãy xem ví dụ:
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
Sau bit-magic này, v được trả về.
Tại sao cursor bị reversed trước khi increment? Table có thể grow giữa các iterations. Điều này đảm bảo cursor vẫn valid. Khi table grow, bits thêm được thêm vào size mask của nó từ bên trái. Bằng cách increment reversed number, chúng ta có thể expand indices của table nhỏ hơn vào table lớn hơn.
Ví dụ: Giả sử old table size là 16 (size mask 00001111) và cursor là 00001000. Khi table grow đến 32 elements size mask sẽ là 00011111. Tất cả elements trước đó trong slot 00001000 sẽ map đến hoặc 00001000 hoặc 00011000 trong table mới. Các cursors này compatible với cả table nhỏ và lớn!
2. Scanning trong lúc table rehashing
Phần cuối chúng ta cần hiểu là scan hoạt động như thế nào trong lúc table rehashing. Incremental rehashing được triển khai trong dict.c bằng cách có hai active tables cùng lúc. Second table được tạo khi hash table bị resize. New items được thêm vào new table. Trên mọi rehash step, elements từ old table được move đến new table. Khi old table trở thành empty nó bị removed.
Khi thực hiện scan, cả old và new tables được scan cho elements, bắt đầu từ smaller table. Sau khi items trong smaller table được scanned, complementing items từ larger table được scanned. Do đó tất cả elements được cover bởi cursor v được scanned. Hãy xem nó trông như thế nào. Đây là toàn bộ code snippet, chúng ta sẽ break down bên dưới:
} 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));
}
Đầu tiên, t0 và t1 dùng để lưu smaller và larger tables tương ứng, với m0 và m1 size masks cho mỗi cái. Sau đó smaller table được scanned, giống như chúng ta thấy trước.
Tiếp theo, cursor được dùng để index vào larger table, dùng larger size mask m1: de = t1->table[v & m1]. Trong inner loop, cursor được incremented để cover tất cả expansions của smaller table's index.
Ví dụ, nếu index của bucket trong smaller table là 0100, và larger table gấp đôi lớn, indices covered trong loop này sẽ là 00100 và 10100. Điều kiện do-while ngăn không cho increment cursor vượt quá range covered bởi small table's bucket: while (v & (m0 ^ m1));. Tôi sẽ để bạn hiểu phần cuối này :)
Đó là xong! Chúng ta đã cover toàn bộ hash table scan function. Mảnh ghép còn thiếu là triển khai của rev(v), là function chung để reverse bits trong number. Triển khai dùng trong dict.c đặc biệt thú vị vì đạt O(log n) running time. Tôi có thể cover nó trong bài viết tương lai.
Cảm ơn đã đọc! Nhiều cảm ơn Dvir Volk cho inspiration và support! Cảm ơn Jason Li cho feedback giúp tôi sửa lỗi trong bài.
Học lập trình miễn phí. Chương trình mở của freeCodeCamp đã giúp hơn 40.000 người tìm được việc làm với tư cách là lập trình viên. Bắt đầu ngay hôm nay.