Improving key expiration in Redis를 읽고

https://blog.twitter.com/engineering/en_us/topics/infrastructure/2019/improving-key-expiration-in-redis.html

Improving Key Expiration in Redis

얼마 전 Twitter 블로그에 Redis expire 기능을 개선했다는 글이 올라와 주말 동안 읽고 정리하고자 합니다.

블로그 요약(?)만 하려고 했는데 3.2 activeExpireCycle 함수에 재밌는 로직들이 추가되어 코드 얘기도 잠깐 하겠습니다.

먼저 Redis Expire 얘기를 하겠습니다.

Expire는 아래 3가지의 경우 실행이 됩니다.

1. 특정 키 조회 시 expire 여부 판단 및 expire 키라면 시간 계산하여 조건에 맞으면 삭제 (passively)
2. Redis 내부에 존재하는 cron이 activeExpireCycle(Slow) 함수를 주기적으로 실행 (actively)
3. redis event 명령어가 실행되기 전에 항상 beforesleep이 호출되는데 이때 activeExpireCycle(Fast) 함수를 실행 (actively)

※ redis event? time(cron)과 file event(aof, replica, client connection)

 

1번은 매우 직관적이라 패스하고, 2, 3에 대해 얘기하겠습니다.

redis expire

위 그림은 2, 3번이 어떤 흐름으로 activeExpireCycle 함수를 호출하는지 나타낸 것이고

실제 activeExpireCycle 동작은 다음과 같습니다.

void activeExpireCycle(int type) {
  if (type이 Fast인 경우) {
    if(직전 activeExpireCycle 실행이 time limit에 걸리지 않은 경우) return;
    if(마지막으로 activeExpireCycle(Fast) 실행한 시간이 일정 시간을 넘지 않은 경우) return;
  }
  
  if (redis의 db 개수보다 많은 횟수로 expire 검사하거나 
            직전 activeExpireCycle 실행이 time limit에 걸린 경우)
    expire 검사 횟수 = redis의 db 개수
    
  for(expire 검사 횟수만큼) {
    db = redisServer.db+(current_db % redis db 개수)
    current_db++;
    
    do {
      num = db->expires의 크기
      if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
        num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
        
      while(num--) {
        // random으로 db->expires에서 키를 가져와서
        // 설정한 시간이 현재 시간보다 과거라면 삭제, 그리고 expired++
      }
      
      // http://redisgate.jp/redis/server/latency.php#expire-cycle
      // 16번 돌때마다 expire->cycle 에 처리에 걸린 시간 기록, 16번 돌기전에 time limit으로 종료되면 안 남겨짐
      // 처리 시간이 일정 시간 넘어가면 종료, timelimit_exit = 1
    } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP / 4);
  }
}

재밌었던 건 Fast의 경우 초기에 분기 처리를 해서 많이 호출해도 부하를 주지 않도록 만든 점,

2.4에서는 server.db+j로 코드가 작성되어 매번 db 0번부터 검사를 했지만 
3.2에서는 redisServer.db+(current_db % redis db 개수)로 코드가 작성되어 마지막으로 expire 검사한 db
다음부터 expire 체크를 하도록 만든 점 입니다.

current_db 자료형을 unsigned int로 해서 계속 current_db++ 해도 문제없게 만든 antirez의 세심함도 보입니다.(당연한 건데
저만 이렇게 느낄 수도....ㅎㅎ)

 

Twitter 블로그 얘기 (요약, 편의상 존칭 생략)

2.4에서 3.2로 Redis 버전 업하는 프로젝트를 진행했는데 메모리 사용량과 레이턴시가 증가하는 문제를 발견하였다.
레이턴시 증가는 Key eviction과 연관 있음을 밝혔다. 결국 메모리 사용량의 원인을 찾아야 했다.

※ Key eviction: 쓰기 요청이 왔을 때 충분한 메모리가 없을 경우 다음을 만족할 때까지 현재 저장되어있는 키에서 임의로 선택하여 삭제

mem_tofree = mem_used - server.maxmemory;  // 메모리 할당 해제"할" 크기
mem_freed = 0;                             // 메모리 할당 해제"한" 크기
while (mem_freed < mem_tofree) {
  // EVICTION 알고리즘에 맞게 key를 선택해 삭제 처리
}

expire 세팅한 키가 제때 안 지워지는 건 아닐까 의심을 했고 Scan 명령어를 사용해보자는 의견이 있어 테스트 진행(passively expire)

효과는 좋았다. 하지만 이 방법은 클러스터를 증설해 사용 가능한 메모리를 늘려야 했다.
이번 버전업의 목적은 클러스터 크기와 비용을 줄이는 것이었으므로 적용하지 않았다.

※ Scan이랑 클러스터 증설이랑 어떤 관계인지 명확하게 모르겠다...

actively expire가 아닌 passively expire로 할 경우 버퍼가 필요한 건가? 정도의 생각을 해봅니다.

2.4와 3.2에 activeExpireCycle 함수에 어떤 변화가 있는지 살펴보았다.
Slow, Fast Option이 추가되었고, 기존에는 모든 database를 expire 체크했지만 3.2에서는 expire 체크할 db 개수를 정하는
로직이 추가되었다.
우리는 굉장히 많은 expire key가 있었는데 이걸 처리하기 위해 20개 샘플링은 충분치 않을 거라는 가설을 세우고 다음 작업을 진행했다.

1. ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP의 값을 수정

20(control), 200, 300, 500 총 4개로 테스트 진행.  효과는 괜찮았다.
더 나아가서 db[i]->expires의 크기에 비례해서 샘플링 개수도 동적으로 설정되도록 작업 했고 효과 있었다.
하지만 control instance 에는 발생하지 않았던 spike 레이턴시가 종종 발생했고 코드가 직관적이지 않고 복잡해서 적용하지 않았다.

※ control이라는 단어가 자주 나오는데 원본(?) 정도로 이해했습니다. 보다 정확한 표현을 아시는 분은 알려주세요.

 

 

2. expire 체크할 db 개수 검사하는 if 문 주석처리

//if (dbs_per_call > server.dbnum || timelimit_exit)
  dbs_per_call = server.dbnum;

if 문 주석 처리하니 굉장한 성능 향상이 있었다.
원인을 파악하기 위해 if 문의 어셈블리 명령어를 파악했고(mov, cmp, jg) 하나씩 검증을 하니 jg가 성능 저하의 원인임을 찾았다.

https://en.wikibooks.org/wiki/X86_Assembly/Control_Flow#Jump_if_Greater

jg를 사용하지 않고 jmp를 이용하였더니 원하는 성능이 나왔다.
그러나 CPU 메뉴얼도 보았지만 결정적인 원인을 찾지 못해 적용하지 않았다.

 

Finally. 샘플링 개수와 expire 체크하는 루프 종료 조건의 threshold 값을 config로 변경할 수 있도록 작업

적용!!!!   클러스터의 크기를 25% 줄이게 되었다.

P/R: https://github.com/antirez/redis/pull/5843 

 

 

배울 점: 원하는 결과에만 집중하는 것이 아니라 원인, 코드 가독성, 유지보수까지 고려해서 작업을 진행하는 모습

 

오늘의 영어

The code was also kind of convoluted, hard to explain, and not intuitive. We also would have had to adjust it for each cluster which wasn’t ideal because we would like to avoid adding operational complexity.

 

Nothing was conclusive about why the one instruction caused such a performance issue. We have some theories related to instruction cache buffers and cpu behavior when a jump is executed but ran out of time and decided to come back to this in future possibly.