PART #1, PART #2를 보면 결국 Redis Scan에서의 Cursor는 bucket 을 검색해야할 다음 index 값이라고 볼 수 있습니다. 그런데 실제로 실행시켜보면, 0, 1, 2 이렇게 증가하지 않고…
그 이유중에 하나는… 실제 Cursor 값이 다음 index의 reverse 값을 취하고 있기 때문입니다. 이걸 보기 전에 먼저 다시 한번 Scan의 핵심 함수인 distScan을 살펴보도록 하겠습니다.(젤 뒤만 보면 됩니다.)
unsigned long dictScan(dict *d,
unsigned long v,
dictScanFunction *fn,
void *privdata)
{
dictht *t0, *t1;
const dictEntry *de;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0;
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->sizemask;
/* Emit entries at cursor */
de = t0->table[v & m0];
while (de) {
fn(privdata, de);
de = de->next;
}
} else {
......
}
/* Set unmasked bits so incrementing the reversed cursor
* operates on the masked bits of the smaller table */
v |= ~m0;
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);
return v;
}
한 이터레이션이 끝나고 나면 m0 의 bitwise NOT을 or 하고 reverse를 취한 다음 1을 더하고 다시 reverse를 취합니다. 일단 bucket이 4개만 있다고 가정하고, rehashing은 빼고 생각해보도록 합니다. 먼저 여기서 reverse는 비트를 쭈욱 세워놓고, 그걸 거꾸로 뒤집는 것입니다.
그래서 0의 rev(0) 은 그대로 0이고, rev(1)은 8000000000000000(16진수), rev(2)는 4000000000000000(16진수) 가 됩니다.(아 이걸 출력을 64bit 라 64bit hex로 찍어야 하는데 32bit로 찍었다가… 잘못된 이해를 ㅋㅋㅋ)
처음에는 v(cursor) 가 0입니다. scan이 끝나고 (0 |= ~3) = -4, 그 뒤에 rev(-4)는 3fffffffffffffff(16진수) 가 됩니다. 여기에 1을 더하면 4000000000000000 여기서 다시 rev(4000000000000000)가 되면 2가 나오게 됩니다.
/* Function to reverse bits. Algorithm from:
* http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
unsigned long mask = ~0;
while ((s >>= 1) > 0) {
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
return v;
}
그런데 왜 reverse를 취하는 것일까요? 이것은 실제 적으로 1씩 증가하는 형태라면… cursor가 언제 끝나는지 알려주기가 애매해서 입니다. 즉 끝났다는 값을 다시 줘야 하는데, 그것보다는 0으로 시작해서 다시 0으로 끝날 수 있도록 reverse 형태를 취하는 것이죠.
PART #1, PART #2, PART #3 의 이유로 해서 SCAN은 다음과 같은 제약 사항을 가집니다.
1. count 값을 줄 수 있지만, 딱 그 개수를 보장하지 않는다.
2. 이미 scan 이 지나간 인덱스에 있는 index 에 나중에 추가된 아이템은 iteration 중에 데이터가 나오지 못한다.(Cursor가 이미 지나갔으므로…)
3. 해당 코드의 설명을 보면… 몇몇 데이터가 중복 될 수 있다는데… 이 부분은 저도 잘 이해가 안가는… 코멘트에 보면… hash table이 확장될때, 줄어들 때, rehashing 할 때 다시 스캔하지 않는다고 되어있는데… 이 부분은 잘 모르겠네요. ㅎㅎㅎ
그럼 Redis Scan 에 대한 부분은 마치도록 하겠습니다.
Charsyam's Blog 