Redis QUICK List of LISTS

트위터 Twitter

트위터는 데이터 센터 당 1만 개 이상의 레디스 서버를 사용하고 있고, 사용 메모리가 100TB 이상이라고 한다.   타임 라인을 관리하는데 레디스의 리스트(LIST)를 사용하고 있다.   리스트는 저장된 순서대로 보여주므로 타임 라인을 관리하는 데는 가장 적당하다고 할 수 있다.   그런데, 리스트는 노드 당 오버헤드가 50 바이트에 이른다.   이것은 listNode + redisObject + sdshdr를 합친 바이트이다.

문자 메시지의 사이즈는 매우 작은 것으로 알려져 있다.   평균 사이즈가 30 바이트라고 한다면, 단순하게 계산해도 오버헤드가 2배 나온다.   거기다 커널의 메모리 할당 방식도 고려해야 하므로 실제로 3배 이상이 될 것이다.   트위터에서 데이터 센터당 사용하는 메모리가 100TB 이상이라고 하니, 레디스를 그대로 사용하지 않고 메모리를 절약하는 방법을 찾았다.

레디스의 리스트는 내부적으로 두 가지 데이터 타입을 사용한다.   엔트리 개수가 적을 때는 짚 리스트에 저장하고, 많아지면 데이터 타입을 변환해서 더블 링크드 리스트에 저장한다.   더블 링크드 리스트는 엔트리 수에 거의 상관없이 주요 오퍼레이션이 매우 빠르게 처리된다. 반면, 메모리 오버헤드가 있다.   짚 리스트는 메모리 절약에 매우 효과이고, 엔트리 개수가 적으면 성능도 링크드 리스트에 비해서 많이 떨어지지 않는 반면, 짚 리스트가 차지하는 메모리가 클수록, 그리고 엔트리 수가 많을수록 오퍼레이션은 CPU를 많이 사용하고, 시간도 많이 걸린다.   즉, 부하가 심하다.

하이브리드 리스트 Hybrid List

트위터에서는 멋진 생각을 해냈다.   리스트가 노드 당 하나의 값(value)만 가지는 것이 아니라, 여러 개의 값을 가지게 한 것이다.   즉, 노드가 적당한 크기의 짚 리스트를 가지는 것이다.   트위터의 Core Infrastructure 팀에 있는 Yao Yu는 2014년 여름에 rackspace에서 Scaling Redis at Twitter로 이 내용을 발표했고, 이것을 Hybrid List라고 하고 A Linked List of ziplists라고 정의했다.

아래 그림은 Hybrid List 구성도이다.   Yao Yu가 말한 것처럼 simple idea 같아 보인다.   하지만 이 생각이 메모리 절약에 매우 효과적이다.


아래는 위 내용을 포함해서 트위터에서 레디스를 어떻게 사용하고 있는지 발표한 동영상이다.

퀵 리스트 Quick List

레디스에서 Linked List of ziplists 개념을 받아들여, 매트(Matt Stancliff)가 구현했고, 이름은 Quick List라고 했다.
위에 단순하게 표현했던 구성도를 좀 구체적으로 그려보았다.   더불어 짚 리스트도 같이 표현했다.


링크드 리스트(Linked List)와 짚 리스트(zip list) 의 동작 방식은 이전 글에서 설명했으므로 알 것이다.   혹시 보지 못했다면 큭릭해서 잠시 보고 돌아오세요.

압축 Compression

확실한 메모리 절약을 위해 짚 리스트를 압축하는 기법을 도입했다.   관련 파라미터는 다음과 같고 redis.conf에 있다.

• list-compress-depth : 압축 여부 또는 압축하지 않는 깊이를 나타낸다.   빠른 push/pop 처리를 위해 처음 노드와 마지막 노드는 항상 압축하지 않는다.  압축 깊이는 상황에 맞게 3 이상 더 크게 할 수 있다.

짚 리스트 사이즈

짚 리스트의 크기를 정하는 파라미터가 도입되었다.   음수는 바이트를 나타내고, 양수는 짚 리스트에 들어갈 엔트리 개수를 나타낸다.   즉, 1로 하면 짚 리스트에 엔트리 하나만 들어가는 것이다.   일반적으로 8kb나 4kb를 권장한다.  

• list-max-ziplist-size
  • -5 : max size 64 kb
  • -4 : max size 32 kb
  • -3 : max size 16 kb
  • -2 : max size  8 kb     default
  • -1 : max size   4 kb
  • 1 : entry 1
  • 2 : entries 2
  • n : entries n

짚 리스트 정보 조회

debug object key : key의 데이터 타입이 quick list 일 때 좀 자세한 정보를 보여준다.
아래 예는 9바이트 데이터 10만건을 입력한 것이다.
encoding:quicklist
serializedlength:489652
ql_nodes:134
ql_avg_node:746.27
ql_ziplist_max:-2
ql_compressed:0
ql_uncompressed_size:1090369
• serializedlength: 압축해서 RDB 파일로 저장할 때 사이즈이다.   RDB 파일 압축은 데이터 사이즈 기준으로 20바이트 초과일 때 압축하는데, Ziplist, Intset은 포인터를 포함하고 있지 않으므로 Ziplist, Intset 단위로 압축한다.   이 예에서 값 크기는 5바이트이지만, Ziplist 크기가 8kb이므로 압축한다.
• ql_nodes: 퀵 리스트 노드 수
• ql_avg_node: 퀵 리스트 한 노드(짚 리스트) 안에 포함된 값의 수,   ql_nodes * ql_avg_node 하면 전체 값의 수가 나온다.
• ql_ziplist_max: 이것은 list-max-ziplist-size 값으로 노드 크기이다.
• ql_compressed: 이것은 list-compress-depth 값으로 압축 깊이이다.
• ql_uncompressed_size : 압축하지 않았을 때의 크기이다.

테스트 방법

• 테스트 값은 4 종류 크기(31, 39, 115, 495 바이트)의 문자열을 사용했습니다.   redis.io의 메인 페이지에 있는 내용입니다.
  • 케이스 1 (길이  31 바이트) : "in-memory data structure store."
  • 케이스 2 (길이  39 바이트) : "Redis is in-memory data structure store"
  • 케이스 3 (길이 115 바이트) : "Redis is an open source (BSD licensed), in-memory data structure store, used as database, cache and message broker."
  • 케이스 4 (길이 495 바이트) : "Redis is an open source (BSD licensed), in-memory data structure store, used as database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs and geospatial indexes with radius queries. Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via Redis Sentinel and automatic partitioning with Redis Cluster."


• 테스트 코드는 파이썬(Python)을 사용했고, Loop를 돌면서 LPUSH를 10만번 수행했다.   메모리 사용량 체크를 위해 테스트 전, 후에 info memory로 확인했다.
  def lpush31(conn,key,start_index,end_index):
        start_time=time.time()
        print 'Start time:',start_time
        msg = "in-memory data structure store."
        i = start_index
        while i <= end_index:
              conn.lpush(key,msg)
              i = i+1
        end_time = time.time()
        print 'End time:', end_time
        print 'Elapsed time(sec):', end_time-start_time
  


• 테스트는 아래 조건에서 위 네 가지 길이 데이터를 했다.  

레디스 서버 버전	짚 리스트 사이즈 (list-max-ziplist-size)	압축 여부 (list-compress-depth)
3.0.6	해당 사항 없음	No(압축 기능 없음)
3.2-rc1	8kb(-2)	No(0)
3.2-rc1	8kb(-2)	Yes(2)


링크드 리스트를 사용하는 3.0.6 버전과 퀵 리스트를 사용하는 3.2 버전을 수행했고, 3.2 버전에서는 압축에 따른 메모리 절약 효과를 알아보기 위해 압축하지 않은 것, 압축한 것 이렇게 수행했다.

테스트 서버는 아래와 같다.

OS : CentOS 7
H/W Model: HP DL320e Gen8 v2
Processor : Intel(R) Xeon(R) CPU E3-1231 v3 @3.4GHz, 8 Cores
Main Memory: DDR3 8GB RAM

테스트 결과

• 메모리 : 단위는 kb이다.

데이터 사이즈	순수 데이터 사이즈	버전 3.0.6 Linked List 압축 기능 없음 (건당 오버헤드)	버전 3.2 Quick List 압축하지 않음 (건당 오버헤드)	버전 3.2 Quick List 압축함 (비율)
31 바이트	3,100	9,374 (65)	3,251  (2.3)	105 (3.5%)
39 바이트	3,900	9,374 (57)	4,036  (2.3)	137 (3.6%)
115 바이트	11,500	17,187 (61)	11,639  (4.2)	432 (3.9%)
495 바이트	49,500	54,687 (65)	50,194(19.0)	4,130 (8.5%)
평균		62 바이트	7 바이트	7.2%



• 버전 3.0.6에서는 데이터 건당 오버헤드가 평균 62 바이트이다.
• 버전 3.2에서 압축하지 않으면 건당 오버헤드가 2 ~ 19로 평균 7 바이트이다.
• 버전 3.2에서 압축했을 때는 원래 사이즈보다 줄기 때문에 오버헤드를 따질 수 없고, 원래 크기에 비해서 얼마나 줄었는지를 계산했다.   3 ~ 8%로 평균 7%로 줄었다.   다르게 표현하면 원래 크기에 비해서 1/30 ~ 1/10으로 줄었다.   압축했을 때 메모리 절약은 획기적이라고 할 수 있다.

아래는 그래프로 표현했다.   압축했을 때 크기가 너무 줄어서 세로축을 다 표시하지 못했고, 압축했을 때를 표시하는 막대그래프가 너무 작어서 녹색 화살표로 표시했다.




• 성능(처리 속도) : LPUSH 실행(건당)이고 단위는 us(microsecond)이다.   즉, us per call이다.

데이터 사이즈	버전 3.0.6 링크드 리스트	버전 3.2 퀵 리스트	버전 3.2 퀵 리스트(압축)
31 바이트	0.35	0.42	0.45
39 바이트	0.36	0.48	0.45
115 바이트	0.35	0.49	0.54
495 바이트	0.35	0.79	1.86



• 링크드 리스트는 데이터 크기에 관계없이 처리 속도가 일정하다.
• 퀵 리스트는 데이터가 커질수록 처리 속도가 느려진다.   이유는 짚 리스트를 사용하므로 입력할 때마다 기존 데이터의 이동(복사)이 수행되기 때문이다.
• 압축한 퀵 리스트는 데이터가 커질수록 처리 속도가 비 압축보다 느리다.   이유는 위에 설명한 이유에 더해서, 데이터가 커질수록 한 짚 리스트 노드에 들어가는 엔트리 개수가 적어져서 압축을 더 자주 해야 하기 때문이다.

아래는 그래프로 표현했다.   링크드 리스트는 데이터 크기에 상관없이 일정하다.   압축했을 경우 데이터 크기가 커질수록 압축이 더 자주 발생하므로 처리 속도는 떨어진다.   예를 들면, 31 바이트는 8192 바이트 한 노드에 약 260개가 들어가므로 260 번 입력마다 압축이 수행되지만, 495 바이트는 한 노드에 16개가 들어가므로 16 번 입력마다 압축이 수행된다.   10만 번 입력하면 31 바이트는 약 370번 압축이 수행되고, 495 바이트는 약 6000 번 수행된다.   그러므로 전체적으로 처리 속도는 떨어지는 것이다.

정리

어디서 퀵 리스트를 처음 시작했는지, 데이터 구조, 메모리를 얼마나 절약하는지 알아보았다.   하이브리드 리스트를 발표해준 트위터와 Yao Yu에 감사하고, 레디스에 구현한 매트(Matt Stancliff)에게 고맙다는 인사를 전한다.