Redis ZIP List of LISTS

왜 WHY

레디스는 모든 데이터를 메모리(RAM)에 저장합니다.   업무에 따라서 수십 기가 또는 수백 기가 메모리를 가진 시스템들을 사용하지만, 메모리는 디스크에 비해 여전히 비싼 자원입니다.   그리고 레디스 서버는 데이터 타입에 따라 다르기는 합니다만, 실 데이터가 아주 작은 경우 메모리 오버헤드가 8 ~ 10 배에 이르는 경우도 있습니다.   사실 다른 DBMS 들도 마찬가지입니다만, 디스크에 저장하기 때문에 이 문제를 심각하게 따지지 않는 것뿐입니다.
레디스가 메모리를 절약하기 위해 어떤 노력을 하지는 알아봅시다.

자 그럼, 설명에 들어가기 전에 메모리를 절약하려면 어떤 데이터 구조를 가져야 하는지 생각해 봅시다.
조건은 아래와 같습니다.
1)   데이터는 특수문자를 포함할 수 있고,
2)   순방향 또는 역방향 탐색을 할 수 있어야 한다.

그래서 다음과 같은 구조를 생각해 보았습니다.   데이터(value)를 각각 관리하지 않고, 여러 데이터를 한 메모리 할당 영역에 관리하는 것입니다.   아래 그림처럼 문자열을 저장하고 마지막에 문자열 끝이라는 것을 표시할 수 있는 특수문자를 넣는 것입니다.   그러면, 메모리 절약에는 최적이지만, 데이터에 문자열 끝을 나타내는 특수문자를 포함할 수도 있기 때문에, 문자열을 구분할 수 없게 됩니다.   즉, 첫 번째 조건을 만족하지 못 합니다.

그럼, 이런 데이터 구조는 어떨까요?
데이터 길이를 저장하는 필드를 만들어서 특수문자 문제를 해결했습니다.   그리고 두 번째 조건인 순방향과 역방향 탐색을 위해서 다음과 이전 주소를 가지는 링크드 리스트 구조를 생각했습니다.

위 구조는 두 가지 조건을 만족했으므로, 이제 메모리가 얼마나 절약되는지 따져 봅시다.
첫 번째 항목은 데이터 사이즈 3 바이트, 데이터 길이 저장하는데 2 바이트, 다음 주소 저장하는데 8 바이트를 사용해서, 데이터 크기에 비해 오버헤드가 3.3배입니다.
두 번째 항목은 데이터 사이즈 10 바이트, 데이터 길이 저장하는데 2 바이트, 이전/다음 주소 저장하는데 8*2=16 바이트로 오버헤드 1.8배입니다.
조건은 만족했지만 메모리를 절약하는 목적을 달성했다고 하기는 어려워 보입니다.
일반적으로 메모리 주소(포인터)를 가지면 오버헤드가 커집니다.

그러면 레디스에서는 이 문제를 어떻게 해결하고 있는지 알아봅시다.

실수는 더블 형으로 바꾸어야 하는데, 그러면 문자열로 그대로 둘 때보다 메모리를 더 많이 사용할 경우가 많으므로 문자열 그대로 사용한다.

• itself len은 값이 문자열일 때는 1,2,5 바이트로 구분해서 길이를 저장하고, 숫자(정수) 일 때는 1 바이트만 사용한다.
• prevlen은 이전 엔트리의 길이를 저장하는 것이므로 문자, 숫자 구분 없이 1,5 바이트 두 종류를 사용한다.
• 값(value)은 문자열일 때는 그대로 저장하고, 숫자(정수) 일 때는 4,8,16,24,32,64 비트로 구분해서 저장한다.
• 값(value)이 실수일 때는 문자열로 취급한다.
• 레디스에서는 이렇게 데이터의 형태, 길이에 맞게 최대한 메모리를 절약할 수 있는 구조로 짚 리스트를 설계해서 사용하고 있다.

그림으로 보는 짚 리스트 오퍼레이션

다음은 짚 리스트에 엔트리 삽입, 삭제 시 값(value) 저장 위치와 각 필드들의 값이 어떻게 바뀌는지를 LIST 명령을 실행하는 것을 가정해서 그림으로 설명합니다.

prevlen은 왜 두 종류만 사용할까?

itself len을 저장하는데 1,2,5 바이트 세 종류를 사용하는데, prevlen을 저장하는데 왜 1,5 바이트 두 종류만 사용할까?   itself len처럼 세 종류를 사용하면 메모리가 더 절약될 텐데 말이다.   이유를 살펴보자.

엔트리를 삽입할 때, 삽입되는 엔트리의 길이를 다음 엔트리의 prevlen 필드에 update 할 필요가 있다.   예를 들어, 다음 엔트리의 prevlen 필드의 길이가 1 바이트이고, 길이는 0을 가지고 있을 때, 삽입되는 엔트리의 길이가 10바이트라면, 0을 10으로 수정해주면 된다. 그런데, 삽입되는 엔트리의 길이가 254 바이트라면, 다음 엔트리 prevlen 필드의 길이를 1 바이트에서 5 바이트로 늘리고, 254를 저장해야 한다.   그럼, 다음 엔트리의 prevlen 필드가 늘어나면서 다음 엔트리 전체 바이트 수가 늘어서, 그다음 엔트리의 prevlen 필드를 수정해야 하는데, 이때 길이를 또 늘려 할 필요가 생길 수도 있다.   최악의 경우 이런 수정이 리스트 끝까지 발생한다면 성능에 매주 좋지 않은 영향을 미칠 것이다.

itself len처럼 세 종류를 사용했다면 1 바이트에서 2 바이트로 늘어날 때, 다시 5 바이트로 늘어날 때, 이런 현상이 두 번 발생할 것이다.   이것을 한 번만 발생하는 것으로 줄이기 위해서 두 종류만 사용한 것이다.

역으로 prevlen 필드 사이즈를 줄일 필요도 생긴다.   이전 엔트리의 길이가 254 바이트에서 10 바이트로 줄었다면, prevlen 길이를 5 바이트에서 1 바이트로 줄여야 할 것이다.   또 이와 같은 일이 연속해서 발생할 수 있다.   하지만 이때는 줄이지 않는다.   이것을 허용하면, 입력되는 필드의 사이즈에 따라 줄이고, 늘이는 일이 반복해서 발생할 수 있다.
이것을 "flapping(파닥거림)" 효과이라고 하는데, 이것은 매우 비효율적이다.   따라서 파닥거림 효과가 발생하지 않도록 한 번 늘린 것은 줄이지 않는다.

레디스는 여러 곳에서 파닥거림 효과를 방지하기 노력한다.   예를 들어, Sorted Set에서 처음에는 ziplist를 사용하지만 128 엔트리가 넘어가면 skiplist로 바꾼다.   하지만 엔트리 개수가 다시 128이하로 줄었다고 skiplist를 ziplist로 다시 바꾸지 않고, skiplist 그대로 둔다.

정리하면, 위와 같은 이유로 prevlen은 두 종류만 사용했고, 파닥거림 효과를 방지하기 위해서 한 번 늘인 것은 줄이지 않는다.   CascadeUpdate function에서 이 연속되는 수정을 처리하는데, 다음 엔트리의 prevlen 사이즈가 늘어나는 동안 계속되고, 변경이 없으면 멈춘다.

CascadeUpdate가 발생했을 때 성능

값(value) 사이즈를 250 바이트로 했다. 그러면 itself len은 2 바이트, prevlen은 1 바이트, 그래서 엔트리 사이즈는 253 바이트로 저장된다.   500 엔트리를 짚 리스트에 LPUSH 명령으로 저장했다.   그다음에 값(value) 사이즈를 251 바이트로 LPUSH 명령을 실행한다.   그러면 itself len 2 바이트, prevlen 1 바이트로 엔트리 사이즈가 254 바이트가 된다.   그럼 이미 저장된, 다음 엔트리의 prevlen 사이즈를 1 바이트에서 5 바이트로 늘려서 update 해야 한다.   이것이 500개 엔트리에 연속해서 발생하는 상황을 만들었다.


while i <= end_index:
      conn.lpush(key,'A'*250)
      i = i+1
...
3929:M 03 Jan 13:43:52.346 * Processing time(us):5, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):5, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):5, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):6, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):7, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):5, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):6, LPUSH key
3929:M 03 Jan 13:43:52.346 * Processing time(us):5, LPUSH key
...
>>> conn.lpush('key','B'*251)
501L
3929:M 03 Jan 13:49:10.598 * Processing time(us):2886, LPUSH key


앞 500개 엔트리 입력 평균 시간과 마지막 엔트리 입력 시간을 비교해 보자.
앞 500개 엔트리 입력 평균 시간: 5.6us(microsecond)
501번째 엔트리 입력 시간:      2,886us
약 500배 이상의 시간이 걸렸다.
절대 수치보다는 상대적인 비율을 보시기 바랍니다.

< listTypeOperation에서 엔트리 개수에 따라, Linked List operation과 zip list operation으로 나누어지는데, 여기서는 zip list를 설명하고 있으므로 Listed List operation은 제외했다. >