Giải thích về quét bảng băm Redis:Bên trong cơ chế

Bởi Ehud Tamir

Một trong những thách thức lớn đối với tôi với tư cách là nhà phát triển phần mềm là đọc mã của người khác. Đối với bài đăng này, tôi đã đọc một đoạn mã C thú vị mà trước đây tôi chưa biết và tôi sắp giới thiệu nó với bạn. Mã tôi sắp nói đến là một phần của Redis cơ sở dữ liệu và có thể tìm thấy nó ở đây.

Redis là một cơ sở dữ liệu khóa-giá trị. Mỗi mục trong cơ sở dữ liệu là một ánh xạ từ khóa tới giá trị. Các giá trị có thể có nhiều loại. Có số nguyên, danh sách, bảng băm và hơn thế nữa. Đằng sau, bản thân cơ sở dữ liệu cũng là một bảng băm. Trong bài đăng này, chúng ta sẽ khám phá lệnh SCAN trong Redis.

Giải thích về quét bảng băm Redis:Bên trong cơ chế _By © Người dùng: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=")

Quét Redis

QUÉT là lệnh lặp dựa trên con trỏ, cho phép máy khách duyệt qua tất cả các phần tử trong bảng. Máy quét dựa trên con trỏ này chấp nhận số nguyên con trỏ trên mỗi cuộc gọi và trả về một loạt mục và giá trị con trỏ được sử dụng trong cuộc gọi tới SCAN tiếp theo. Giá trị con trỏ ban đầu là 0 và khi SCAN trả về 0 làm giá trị con trỏ tiếp theo, điều đó có nghĩa là quá trình quét đã hoàn tất và tất cả các phần tử đã được khách hàng nhìn thấy.

Lệnh SCAN có một số thuộc tính thú vị:

Nó đảm bảo rằng tất cả các mục có trong bảng sẽ được trả về ít nhất một lần .
Đó là không quốc tịch . Bảng không lưu bất kỳ dữ liệu nào về máy quét đang hoạt động của nó. Điều này cũng có nghĩa là quá trình quét không khóa cơ sở dữ liệu.
Nó có khả năng thay đổi kích thước bảng rất linh hoạt. Để duy trì thời gian truy cập O(1), các bảng băm duy trì một hệ số tải nhất định. Hệ số tải đo lường mức độ “đầy” của bảng tại một thời điểm nhất định. Khi hệ số tải quá lớn hoặc quá nhỏ, bảng sẽ được thay đổi kích thước. SCAN sẽ duy trì sự đảm bảo của mình ngay cả khi được gọi trong khi bảng đang được thay đổi kích thước.

Triển khai

QUÉT được triển khai trong dict.c, trong hàm dictScan() . Đây là chữ ký của chức năng và công việc dọn phòng bổ sung:

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;
 // ...

Những điều đáng chú ý:

Hàm chấp nhận 5 tham số:dict *d , từ điển cần quét, unsigned long v , con trỏ và 3 tham số khác mà chúng ta sẽ đề cập sau.
Hàm trả về giá trị con trỏ sẽ được sử dụng trong lần gọi hàm tiếp theo. Nếu hàm trả về 0 thì có nghĩa là quá trình quét đã hoàn tất.
if (dictSize(d) == 0) return 0; . Khi từ điển trống, hàm trả về 0 để cho biết quá trình quét đã hoàn tất.

1. Quét bình thường

Đoạn mã sau quét một loạt phần tử:

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 {
 // ...

Chúng ta hãy đi qua nó từng bước một. Hãy bắt đầu với dòng đầu tiên bên dưới:

if (!dictIsRehashing(d)) {
 t0 = &(d->ht[0]);
 m0 = t0->sizemask;

Phục hồi là quá trình trải đều các phần tử trên một bảng sau khi được thay đổi kích thước. Bảng băm dict.c sẽ băm lại tăng dần , có nghĩa là nó không thử lại toàn bộ bảng cùng một lúc mà từng chút một. Mọi thao tác được thực hiện trên bảng, như thêm, xóa, tìm, cũng thực hiện bước thử lại. Điều này cho phép giữ bảng sẵn sàng cho các hoạt động trong quá trình thử lại. Do cách thực hiện việc băm lại, hàm này hoạt động khác nhau trong quá trình băm lại. Chúng ta sẽ bắt đầu bằng cách xem điều gì sẽ xảy ra khi bảng không được băm lại.

Con trỏ tới bảng băm được lưu trong biến cục bộ t0 và mặt nạ kích thước của nó được lưu trong m0 . Kích thước mặt nạ: bảng băm dict.c luôn là 2^n về kích thước. Đối với kích thước bảng nhất định, mặt nạ kích thước là 2^n-1 , là số nhị phân có n các bit có trọng số nhỏ nhất được đặt thành 1. Ví dụ:đối với n=4; 2^n-1 = 00001111 . Đối với một khóa nhất định, vị trí của nó trong bảng băm sẽ là n cuối cùng bit của băm của chìa khóa. Chúng ta sẽ thấy điều này hoạt động sau một lát nữa.

Bảng băm dict.c sử dụng địa chỉ mở. Mỗi mục trong bảng là một danh sách liên kết các phần tử có giá trị băm xung đột nhau. Đây được gọi là nhóm . Trong phần tiếp theo này, một nhóm của các phần tử được quét:

/* 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;
}

Lưu ý việc sử dụng mặt nạ kích thước :t0->table[v & m0] . v có thể nằm ngoài phạm vi có thể lập chỉ mục của table. v & m0 sử dụng mặt nạ kích thước để chỉ giữ lại las t n chữ số o f v và mang lại một chỉ mục hợp lệ cho bảng.

Có thể bây giờ bạn đã đoán được bucketfn là gì là dành cho. bucketfn được cung cấp bởi người gọi và được áp dụng cho từng nhóm phần tử. Nó cũng được thông qua privdata , là dữ liệu tùy ý được truyền tới dictScan() bởi người gọi. Theo cách tương tự, fn được áp dụng cho tất cả các mục trong nhóm từng cái một. Lưu ý rằng một nhóm có thể trống, trong trường hợp đó giá trị của nó là NULL .

Được rồi, vậy là chúng ta đã lặp lại một nhóm phần tử. Tiếp theo là gì? Chúng tôi sẽ trả về giá trị con trỏ cho lệnh gọi tiếp theo tới dictScan() . Điều này được thực hiện bằng cách tăng con trỏ hiện tại v , nhưng có một sự thay đổi! Con trỏ đầu tiên được đảo ngược, sau đó tăng dần, rồi lại đảo ngược:

 /* 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 đặt tất cả các bit không bị che trong v thành 1. Hiệu quả là khi đảo chiều v và tăng dần, những bit này sẽ bị bỏ qua một cách hiệu quả. Sau đó, v được đảo ngược, tăng lên và đảo ngược một lần nữa. Hãy xem một 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 phép thuật bit này, v được trả về.

Tại sao con trỏ bị đảo ngược trước khi tăng lên? Bảng có thể phát triển giữa các lần lặp. Điều này đảm bảo rằng con trỏ vẫn hợp lệ. Khi bảng phát triển, các bit bổ sung sẽ được thêm vào mặt nạ kích thước của nó từ bên trái . Bằng cách tăng số đảo ngược, chúng ta có thể mở rộng chỉ mục của bảng nhỏ hơn thành chỉ mục lớn hơn.

Ví dụ:Giả sử kích thước của bảng cũ là 16 (mặt nạ kích thước 00001111 ) và con trỏ là 00001000 . Khi bảng tăng lên 32 phần tử, mặt nạ kích thước của nó sẽ là 00011111 . Tất cả các phần tử trước đó trong 00001000 vị trí sẽ ánh xạ tới 00001000 hoặc 00011000 trong bảng mới. Những con trỏ này tương thích với cả bảng nhỏ hơn và lớn hơn!

2. Quét trong khi đang băm lại bảng

Phần cuối cùng chúng ta cần hiểu là quá trình quét hoạt động như thế nào trong khi bảng đang được băm lại. Tập luyện lại dần dần được triển khai trong dict.c bằng cách có hai bảng hoạt động cùng một lúc. Bảng thứ hai được tạo khi bảng băm được thay đổi kích thước. Các mục mới được thêm vào bảng mới. Ở mỗi bước thử lại, các phần tử từ bảng cũ sẽ được chuyển sang bảng mới. Khi bảng cũ trở nên trống, nó sẽ bị xóa.

Khi thực hiện quét, cả bảng cũ và bảng mới đều được quét để tìm các phần tử, bắt đầu từ nhỏ hơn bảng . Sau khi quét các mục trong bảng nhỏ hơn, các mục bổ sung từ bảng lớn hơn sẽ được quét. Do đó, tất cả các phần tử được bao phủ bởi con trỏ v được quét. Hãy xem nó trông như thế nào. Đây là toàn bộ đoạn mã, chúng tôi sẽ chia nhỏ nó ra 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));
 }

Trước hết, t0 và t1 được sử dụng để lưu trữ các bảng nhỏ hơn và lớn hơn tương ứng, với m0 và m1 kích thước mặt nạ cho mỗi loại. Sau đó, bảng nhỏ hơn sẽ được quét, giống như chúng ta đã thấy trước đó.

Tiếp theo, con trỏ được sử dụng để lập chỉ mục vào bảng lớn hơn, sử dụng mặt nạ kích thước lớn hơn m1 :de = t1->table[v & m1] . Ở vòng lặp bên trong, con trỏ được tăng lên để bao phủ tất cả các phần mở rộng của chỉ mục của bảng nhỏ hơn.

Ví dụ:nếu chỉ mục của nhóm trong bảng nhỏ hơn là 0100 và bảng lớn hơn có kích thước gấp đôi, các chỉ mục trong vòng lặp này sẽ là 00100 và 10100 . Điều kiện do-while ngăn việc tăng con trỏ vượt quá phạm vi được bao phủ bởi nhóm của bảng nhỏ:while (v & (m0 ^ m1)); . Tôi sẽ để bạn hiểu điều cuối cùng này :)

Thế thôi! Chúng tôi đã đề cập đến toàn bộ chức năng quét bảng băm. Phần còn thiếu duy nhất là việc triển khai rev(v) , đây là một hàm tổng quát để đảo ngược các bit trong một số. Việc triển khai được sử dụng trong dict.c đặc biệt thú vị vì nó đạt được thời gian chạy O(log n). Tôi có thể đề cập đến nó trong một bài viết sau.

Cảm ơn đã đọc! Rất cám ơn Dvir Volk vì nguồn cảm hứng và sự hỗ trợ của anh ấy! Cảm ơn Jason Li vì phản hồi của anh ấy đã giúp tôi sửa lỗi trong bài viết.

Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu