redis 에서 scan 명령 의 기본 구현 방법

머리말
하늘 이 맑 고 공기 가 맑 은 날,작은 회색 이 온라인 에 올 라 간 redis 는 데 이 터 를 조회 하려 고 한다.그러나 그 는 전체 키 가 얼마 인지 접두사 만 기억 하고 명령 행 에'keys xxx*'명령 을 입력 했다.
순간 서비스 카드 가 죽 고 경보 메 일이 메 일 로 가득 차 있 었 고,먼지 는 곧 다가 올 케이스 스 터 디 를 눈 을 부 릅 뜨 고 기다 릴 수 밖 에 없 었 다.
기본적으로 keys*명령 은 온라인 상에 서 운영 이 금지 되 어 있 습 니 다.
redis 키 는 hash-max-ziplist-value 보다 크 고 hash-max-ziplist-entries 보다 작 을 때 산 목록 데이터 구조 에 저 장 됩 니 다.keys 명령 을 실행 할 때 데이터베이스 키 공간 을 옮 겨 다 니 며 모든 키 를 꺼 낸 후 keys 뒤의 pattern 과 일치 합 니 다.
키 가 많은 상황 에서 redis 가 가능 한 카드 는 초 급 이상 이 고 모든 데이터 베 이 스 를 데이터베이스 에 연결 시 켜 데이터 베 이 스 를 눈사태 로 만 들 수 있 습 니 다.
그럼 우 리 는 어떻게 해야만 목표 버튼 을 찾 을 수 있 습 니까?redis 2.8.0 에 scan 명령 을 추가 하여 redis 키 를 여러 번 스 캔 할 수 있 습 니 다.응용 할 때 요구 에 부 합 된 키 를 모두 조회 하 는 시간 이 길 어 지지 만 redis 카드 가 걸 릴 확률 을 크게 줄 였 습 니 다.
여기 서 먼저 배경 을 보충 합 니 다.
redis 의 사전 rehash 는 점진 적 인 해시 입 니 다.즉,모든 키 를 한꺼번에 새로운 해시 표 로 옮 기 는 것 이 아니 라 다음 두 가지 상황 에서 데 이 터 를 옮 기 는 것 입 니 다.
해시 표 가 작 동 할 때마다 현재 rehash 에 있다 면 노드 를 옮 깁 니 다.
서비스 가 한가 할 때 rehash 100 개의 노드 가 있 습 니 다.
scan 명령 은 사전 이 rehash 에 있 는 과정 에서 다음 과 같은 두 가 지 를 보장 할 수 있 습 니 다.
중복 데이터 가 나타 나 지 않 습 니 다.
데이터 누락 없 음
그럼 scan 명령 은 어떻게 rehash 과정 에서 모든 노드 를 반복 하지 않 고 옮 겨 다 닐 수 있 습 니까?우리 함께 원본 코드 를 좀 읽 어 봅 시다.
Let's GO!
scan 명령 을 사용 할 때,우 리 는 매번 커서(0 부터)를 입력 한 다음,다음 라운드 에 서 는 이번 redis 가 돌아 오 는 커서 를 계속 사용 합 니 다.scan 사전 의 핵심 함 수 는 dictScan 이 고 dictScan 의 업데이트 커서 의 핵심 코드 는 다음 과 같 습 니 다.

v |= ~m0;//  m1
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);

그 중에서 m0,m1 은 현재 해시 표 의 크기 를 1 로 줄 이 고 rev 는 2 진 역순 이다.
여기 보시 면 여기 계 신 분 들 도 저 처럼 아래 표정 인지 모 르 겠 어 요.
우리 가 문 제 를 모 의 해 보면 알 수 있다.
우 리 는 현재 네 개의 노드 의 해시 표 에서 옮 겨 다 니 고 있다 고 가정 합 니 다.다음 그림 에서 커서 의 옮 겨 다 니 는 노드 는 0->2->1->3 입 니 다.

8 노드 의 상황 을 모 의 합 니 다:

여기 서 조금 알 겠 습 니까?위의 코드 는 현재 의 유효 자릿수(예 를 들 어 네 노드 는 유효 자릿수 2)범위 내 에서 왼쪽 에서 오른쪽으로 한 자리 들 어 가 는 것 입 니 다.
0 을 옮 겨 다 니 고 2 로 돌아 간 후에 사전 을 확대 했다 고 가정 하면 2->6->1->5->3->7 에 방문 해 야 합 니 다.
소 회:어,그 4 빠 뜨 린 거 아니 야?
4.이미 1 차 에서 0 을 옮 겨 다 닐 때 확 장 된 4 의 데이터 도 방문 했다.
따라서 확장 전의 유효 위 치 를 m 라 고 가정 합 니 다.redis 의 해시 표 확장 은 매번 현재 노드 가 가득 찼 을 때(use=size)크기 보다 큰 2^N 으로 확대 되 기 때문에 확장 후의 유효 위 치 는 m+1 입 니 다.
위의 그 코드 는 사실 낮은 m 비트 를 유지 하고 높 은 하 나 는 0 이 고 하 나 는 1 이다.이렇게 하면 용량 을 확대 한 후에 건 너 뛰 었 던 노드 는 이미 이전에 방문 되 었 다.건 너 뛰 었 던 노드 는 방문 한 노드 로 나 뉘 었 기 때문이다.

몸 을 움 츠 리 는 것 은 도리 와 같 으 니,스스로 밀어 도 된다.
여기 보니까 redis 의 scan 커서 가 교묘 하 게 디자인 된 것 같 지 않 아 요?
소 회:그 렇 군요.제 가 또 데 이 터 를 찾 아 볼 수 있 겠 네요!
마지막 으로 전체 rehash 과정 에서 scan 코드 를 첨부 합 니 다.

//        
t0 = &d->ht[0];
t1 = &d->ht[1];

/* Make sure t0 is the smaller and t1 is the bigger table */
//    t0   t1   
if (t0->size > t1->size) {
 t0 = &d->ht[1];
 t1 = &d->ht[0];
}

//     
m0 = t0->sizemask;
m1 = t1->sizemask;

/* Emit entries at cursor */
//    ，          
de = t0->table[v & m0];
while (de) {//      hash 
 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 {//      hash 
 /* 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;
 }

 //                 hash(key)&mask。       8，  mask   111，  ，                3 bit，
 //       abc。         16，  mask   1111，         ，      ?abc，   ?   0   1     ，
 //     ，        16      ，      0abc     1abc。    ，        32，
 //            00abc，01abc，10abc    11abc     。/* Increment the reverse cursor not covered by the smaller mask.*/
 v |= ~m1;//     v    n   ，       1
 //     ，       v，        1，        
 v = rev(v);//  v          ，  ，v   n       n   ，       
 v++;
 v = rev(v);//       

 /* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));//      v        1 ，        。

총결산
redis 에서 scan 명령 의 기본 적 인 실현 방법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 redis 에서 scan 명령 의 실현 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!