Redis 해시 테이블 스캔 설명:메커니즘 내부

작성자:에후드 타미르

소프트웨어 개발자로서 제가 겪는 가장 큰 과제 중 하나는 다른 사람의 코드를 읽는 것입니다. 이번 포스팅에서는 제가 그동안 몰랐던 흥미로운 C코드를 읽어서 여러분께 소개해드리려고 합니다. 제가 이야기할 코드는 Redis의 일부입니다. 데이터베이스이며 여기에서 찾을 수 있습니다.

Redis는 키-값 데이터베이스입니다. 데이터베이스의 모든 항목은 키에서 값으로의 매핑입니다. 값에는 여러 유형이 있을 수 있습니다. 정수, 목록, 해시 테이블 등이 있습니다. 이면에는 데이터베이스 자체도 해시 테이블입니다. 이번 게시물에서는 Redis의 SCAN 명령을 살펴보겠습니다.

Redis 해시 테이블 스캔 설명:메커니즘 내부 _By © 사용자: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=")

레디스 스캔

SCAN은 커서 기반 반복 명령으로, 클라이언트가 테이블의 모든 요소를 탐색할 수 있도록 해줍니다. 이 커서 기반 스캐너는 정수 커서를 허용합니다. 호출할 때마다 일괄 항목을 반환합니다. 및 커서 값 다음 SCAN 호출에 사용됩니다. 초기 커서 값은 0이며, SCAN이 다음 커서 값으로 0을 반환하면 스캔이 완료되어 모든 요소가 클라이언트에 표시되었음을 의미합니다.

SCAN 명령에는 몇 가지 흥미로운 속성이 있습니다:

테이블에 있는 모든 항목이 최소 한 번 반환되도록 보장합니다. .
무국적입니다. . 테이블은 활성 스캐너에 대한 데이터를 저장하지 않습니다. 이는 또한 스캔이 데이터베이스를 잠그지 않는다는 것을 의미합니다.
테이블 크기 조정에 탄력적입니다. O(1) 액세스 시간을 유지하기 위해 해시 테이블은 특정 로드 요소를 유지합니다. 로드 팩터는 특정 시간에 테이블이 얼마나 "가득 차 있는지"를 측정합니다. 부하율이 너무 크거나 작아지면 테이블 크기가 조정됩니다. SCAN은 테이블 크기가 조정되는 동안 호출되더라도 보장을 유지합니다.

구현

SCAN은 dict.c의 dictScan() 함수에서 구현됩니다. . 다음은 함수의 서명과 추가 관리입니다:

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

주목할 만한 사항:

이 함수는 5개의 매개변수를 허용합니다:dict *d , 스캔할 사전, unsigned long v , 커서 및 나중에 다루게 될 3개의 다른 매개변수입니다.
이 함수는 이 함수에 대한 다음 호출에 사용될 커서 값을 반환합니다. 함수가 0을 반환하면 스캔이 완료되었음을 의미합니다.
if (dictSize(d) == 0) return 0; . 사전이 비어 있으면 함수는 검색이 완료되었음을 나타내기 위해 0을 반환합니다.

1. 일반 스캔

다음 코드는 여러 요소를 검사합니다:

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

단계별로 살펴보겠습니다. 아래 첫 번째 줄부터 시작해 보겠습니다.

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

리해싱은 크기가 조정된 후 테이블 전체에 요소를 균등하게 분산시키는 프로세스입니다. dict.c 해시 테이블은 증분적으로 다시 해시됩니다. 즉, 전체 테이블을 한 번에 다시 해시하지 않고 조금씩 다시 해시한다는 의미입니다. 추가, 삭제, 찾기 등 테이블에서 수행되는 모든 작업은 다시 해시 단계도 수행합니다. 이를 통해 재해싱 중에 테이블을 작업에 사용할 수 있도록 유지할 수 있습니다. 재해싱이 구현되는 방식으로 인해 재해싱 중에 함수가 다르게 작동합니다. 먼저 테이블이 재해싱되지 않을 때 어떤 일이 일어나는지 살펴보겠습니다.

해시 테이블에 대한 포인터는 지역 변수 t0에 저장됩니다. 및 크기 마스크 m0에 저장됩니다 . 크기 마스크: dict.c 해시 테이블은 항상 2^n입니다. 크기가. 특정 테이블 크기에 대해 크기 마스크는 2^n-1입니다. , 이는 n를 갖는 이진수입니다. 최하위 비트는 1로 설정됩니다. 예를 들어 n=4; 2^n-1 = 00001111의 경우 . 특정 키에 대해 해시 테이블의 위치는 마지막 n이 됩니다. 해시의 일부 열쇠의. 잠시 후에 이 내용을 살펴보겠습니다.

dict.c 해시 테이블은 개방형 주소 지정을 사용합니다. 테이블의 모든 항목은 충돌하는 해시 값이 있는 요소의 연결된 목록입니다. 이를 버킷이라고 합니다. . 다음 부분에서는 버킷 개 요소가 스캔되었습니다:

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

크기 마스크 사용에 유의하세요. :t0->table[v & m0] . v가 테이블e. v &의 색인 생성 가능 범위를 벗어났을 수 있습니다. m0은 크기 마스크를 사용하여 las만 유지합니다. t n자리 o f v, 테이블에 유효한 인덱스를 생성합니다.

이제 bucketfn가 무엇인지 짐작하셨을 것입니다. 입니다. bucketfn 호출자가 제공하며 요소의 각 버킷에 적용됩니다. privdata도 전달됩니다. , 이는 dictScan()에 전달된 임의의 데이터입니다. 발신자에 의해. 비슷한 방식으로 fn 버킷의 모든 항목에 하나씩 적용됩니다. 버킷이 비어 있을 수 있으며, 이 경우 해당 값은 NULL입니다. .

좋아요, 그래서 우리는 요소 버킷을 반복했습니다. 다음은 무엇입니까? dictScan()에 대한 다음 호출을 위해 커서 값을 반환하겠습니다. . 이는 현재 커서 v를 증가시켜 수행됩니다. , 그러나 반전이 있습니다! 커서는 먼저 반전된 다음 증가하고 다시 반전됩니다.

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

먼저, v |= ~m0 v에 마스크되지 않은 모든 비트를 설정합니다. 1로. v를 반대로 하면 효과는 다음과 같습니다. 증가하면 이러한 비트는 사실상 무시됩니다. 그러면 v 반전되고, 증가하고, 다시 반전됩니다. 예를 살펴보겠습니다:

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

이 비트 매직 이후에는 v 반환됩니다.

커서가 증가하기 전에 반전되는 이유는 무엇인가요? 반복 사이에 테이블이 커질 수 있습니다. 이렇게 하면 커서가 유효한 상태로 유지됩니다. 테이블이 커지면 왼쪽에서 크기 마스크에 추가 비트가 추가됩니다. . 반전된 숫자를 증가시키면 작은 테이블의 인덱스를 더 큰 테이블로 확장할 수 있습니다.

예:이전 테이블의 크기가 16(크기 마스크 00001111)이었다고 가정해 보겠습니다. ) 및 커서는 00001000였습니다. . 테이블이 32개 요소로 커지면 크기 마스크는 00011111이 됩니다. . 이전에 00001000에 있었던 모든 요소 슬롯은 00001000 중 하나에 매핑됩니다. 또는 00011000 새 테이블에. 이 커서는 더 작은 테이블과 더 큰 테이블 모두와 호환됩니다!

2. 테이블 재해싱 중 스캔 중

우리가 이해해야 할 마지막 부분은 테이블이 다시 해싱되는 동안 스캔이 어떻게 작동하는지입니다. 증분적 재해싱 동시에 두 개의 활성 테이블을 가짐으로써 dict.c에서 구현됩니다. 해시 테이블의 크기가 조정되면 두 번째 테이블이 생성됩니다. 새 항목이 새 테이블에 추가됩니다. 모든 재해시 단계에서 이전 테이블의 요소가 새 테이블로 이동됩니다. 이전 테이블이 비게 되면 제거됩니다.

스캔을 수행할 때 이전 테이블과 새 테이블 모두에서 작은 요소부터 시작하여 요소를 검색합니다. 테이블 . 작은 테이블의 항목을 스캔한 후 보완 항목 더 큰 테이블에서 스캔됩니다. 따라서 커서 v에 포함된 모든 요소는 스캔됩니다. 이것이 어떻게 보이는지 봅시다. 이는 전체 코드 조각이며 아래에서 자세히 설명하겠습니다.

 } 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));
 }

우선 t0 및 t1 m0를 사용하여 더 작은 테이블과 더 큰 테이블을 각각 저장하는 데 사용됩니다. 그리고 m1 각각의 크기 마스크. 그런 다음 앞서 본 것처럼 더 작은 테이블이 스캔됩니다.

다음으로 커서는 더 큰 크기의 마스크 m1를 사용하여 더 큰 테이블에 대한 색인을 생성하는 데 사용됩니다. :de = t1->table[v & m1] . 내부 루프에서는 더 작은 테이블 인덱스의 모든 확장을 포함하도록 커서가 증가합니다.

예를 들어 작은 테이블의 버킷 인덱스가 0100인 경우 , 더 큰 테이블이 두 배 크기 때문에 이 루프에서 다루는 인덱스는 00100입니다. 및 10100 . do-while의 조건은 작은 테이블의 버킷이 포함하는 범위(while (v & (m0 ^ m1));)를 넘어 커서를 증가시키는 것을 방지합니다. . 이 마지막 부분을 이해하는 것은 여러분의 몫입니다 :)

그게 다야! 해시 테이블 스캔 기능 전체를 다루었습니다. 유일하게 누락된 부분은 rev(v) 구현입니다. , 이는 숫자의 비트를 반전시키는 일반적인 함수입니다. dict.c에 사용된 구현은 O(log n) 실행 시간을 달성하므로 특히 흥미롭습니다. 이 내용은 향후 게시물에서 다룰 수도 있습니다.

읽어주셔서 감사합니다! 영감과 지원을 주신 Dvir Volk에게 많은 감사를 드립니다! 게시물의 오류를 수정하는 데 도움을 준 Jason Li에게 감사드립니다.

무료로 코딩을 배우세요. freeCodeCamp의 오픈 소스 커리큘럼은 40,000명 이상의 사람들이 개발자로 취업하는 데 도움을 주었습니다. 시작하세요