Redis HASH Table of  SETS

시작하기

SET은 내부적으로 두가지 데이터 구조를 사용한다.   데이터가 정수이고 멤버 개수가 512개 이하일 때는 정수 배열(intset)에 저장되고, 문자이거나 멤버 개수가 512개 보다 클때는 해시 테이블에 저장된다.   내부 데이터 구조를 정하는 파라미터는 redis.conf에 있는 set-max-intset-entries 이다.   기본 값은 512이다.  
자 그럼 이제, SET의 메인 데이터 구조인 해시 테이블에 대해서 알아보도록 합시다.

데이터 구조

아래는 해시 테이블 구조를 간단하게 표시한 것입니다.






해시 테이블 데이터 구조 명칭은 dict으로 시작하는데, 이는 dictionary의 줄임말입니다.  
• dict은 해시 테이블의 메인 데이터 구조로 dictht를 두 개 가지고 있고, 관련 펑션을 가지고 있는 dictType을 가리키는 포인터를 가지고 있습니다.
• dictht는 dictionary hash table의 약자로, bucket을 가리키는 포인터를 가지고 있으며, 배열로 0, 1 두 개가 있고, dict안에 포함되어 있습니다.
• dictType은 SET 관련 해시 테이블의 동작을 처리하기 위한 펑션을 가지고 있습니다.
• buckets은 dictEntry를 가리키는 포인터 배열입니다.
• dictEntry는 엔트리(값, value) 당 하나씩 할당되며, 값을 포함한 redisObject를 가리키는 포인터를 가지고 있습니다.
이제 하나씩 자세히 알아보도록 하겠습니다.

• dict(dictionary)는 해시 테이블의 앞에 있다.   dictht은 hash table 2개를 포함해서 96 bytes이다.   privdata는 null이 할당된다.





• DictType는 해시 테이블의 오퍼레이션이 가지고 있는 범용 구조이다.




setDictType은 SET에서 사용되는 펑션을 가지고 있는 DictType이다.   hash function, key compare, key destructor가 할당되고 나머지 필드는 null이다.






• dictht의 table 필드는 dictEntry를 가리키는 포인터 배열이고 버킷(buckets)이라고 한다.   size는 버킷의 크기를 나타낸다.   버킷 개수는 4부터 시작해서, 8, 16 이렇게 2의 제곱으로 증가한다.   sizemask는 버킷 인덱스를 얻기 위한 값으로 size-1이다.   used는 해시 테이블이 가지고 있는 엔트리 개수이다.





• dictEntry는 24 바이트로, 값(value) 하나당 하나씩 할당된다.   Key 필드가 값을 가지고 있는 redisObject를 가리킨다.   Val 필드는 SET에서는 null 이 할당된다.   Next 필드는 해시 값 충돌 시 다음 엔트리를 가리키는 포인터이다.

연결 관계

• 데이터 구조 처음에 단순한 그림으로 보여주었던 해시 테이블 구조를 자세하게 표시했다.







• redisObject의 type은 SET(REDIS_SET 0), encoding은 HT(REDIS_ENCODING_HT 2)이고, ptr은 SET의 dict를 가리킨다.
• dict에서 dictht[0]과 dictht[1]을 연결하는 선을 점선으로 한 것은 dict 안에 배열로 포함된 것임을 나타낸다.   포인터가 아니다.
• dictht[0]의 table 필드와 dictEntry 사이에 버킷(buckets)이 있어야 하나 여기서는 생략했다.


• 아래는 각 데이터 구조가 어느 펑션에서 생성되는지를 표시한 그림이다.







• redisObject는 robj  *createObject(int type, void *ptr)에서 생성된다.
• dictht를 포함한 dict은 dict *dictCreate(dictType *type, void *privDataPtr)에서 생성된다.   이때 privDataPtr은 null로 들어온다.
• dictType은 redis.c에 있는 setDictType에서 생성(할당) 된다.
• dictEntry는 dictAddRaw에서 생성된다.
• 값(value)는 이미 robj와 sds로 할당되어 넘어오고, 이것을 dictEntry의 val이 아닌, key가 가리키도록 한다.   Val에는 null로 채워진다.
각 펑션의 관계도는 저 아래에 있다.
• 아래는 버킷(buckets)과 sdshdr까지 포함하고, 그림에 맞는 값을 넣은 그림이다.


  그림 2-3   dict relation big picture

• 위에 SET의 dict를 가리키는 redisObject는 type이 SET이고, encoding은 HT이다.
• DictType은 hash function, key compare, key destuctor에 펑션이 할당된다.   나머지 필드는 null로 채워진다.
• dictht[0]에서 size는 가리키는 bucket의 개수이고, used는 엔트리 개수이다.   bucket에 1번이 비어있으나, 인덱스 0이 해시 값 충돌이 발생해 2개 엔트리가 연결되어 있다. 그래서 used가 4이다.
• 값(value)를 가지고 있는 redisObject의 type은 STRING이고 encoding은 EMBSTR이다.   저장된 값이 5자리이기 때문에 EMBSTR이다.   두 번째 표시한 엔트리는 값이 50자리이므로 encoding이 RAW이다.  
  이에 대한 자세한 내용은 스크링 데이터 구조 에 있으니 참고하길 바랍니다.
  그리고 각 값을 가리키는 robj의 type은 SET으로 바꾸지 않고 클라이언트로 받았을 때 설정된 STRING을 그대로 사용한다.

SET 해시 테이블(hashtable) 메모리 사용량

자, 그러면 이제 데이터를 하나씩 입력하면서 메모리 사용량을 확인해 보자.   명령 하나 실행할 때마다 info memory로 메모리 사용량을 확인했고, 명령은 테이터(값) 길이가 5 바이트인 'A1001', 'A1002'를 사용했다.
redis version 3.0.6
info memory : 815,072
명령 > sadd key A1001
info memory : 815,360   사용량 >> 288 bytes
명령 > sadd key A1002
info memory : 815,424   사용량 >>   64 bytes


첫 번째 명령 'sadd key A1001'은 288 바이트를 사용했고, 두 번째 명령 'sadd key A1002'는 64 바이트를 사용했다.

두 번째 명령이 사용한 64 바이트부터 분석해 보자.   dictEntry가 24 바이트, redisObject 16 바이트, sdshdr 8 바이트, 값(A1001) 5 바이트, 문자열 끝에 종료 문자(null term) 1바이트, 모두 더해보면 54 바이트이다.   그런데 어찌 64 바이트를 차지하고 있는가?   그것은 jemalloc()의 메모리 할당 단위를 따르기 때문이다.   jemalloc()는 16, 32, 64, 128 바이트 단위로 메모리를 할당한다.   따라서 dictEntry가 24 바이트만 필요해서 요청해도 32 바이트를 할당해 준다.   그리고 redisObject + sdshdr + value('A1001') + null term의 바이트를 합하면 30이다.   역시 30 바이트를 요청하면 32 바이트를 할당해 준다.   그래서 dictEntry 32 바이트와 합쳐서 64 바이트가 된것이다.   여기서 dictEntry를 가리키는 버킷(bucket) 하나에 8 바이트가 필요하지만, 버킷은 이미 할당되어 있으므로 여기서는 계산하지 않았다.

순수 데이터 길이는 5 바이트인데, 64 바이트를 사용했다.   위에서 계산에 넣지 않았던 버킷 8 바이트를 합하면 72 바이트이다.   메모리 오버헤드가 67 바이트나 된다.

이제 첫 번째 명령이 사용한 288 바이트를 분석해 보자.   위에서 계산하 64 바이트를 빼면 224 바이트가 된다.   새로운 키가 할당되는 것이므로 그림 2-3에서 보는 것처럼, redisObject 16 바이트 + DictType 48 바이트 + dict 96 바이트 + buckets 32 바이트를 합하면 192 바이트가 나온다.   224 - 192 = 32, 그럼 나머지 32 바이트는 실제 'key'가 저장될 redisObject + sds에 32 바이트가 할당된 것이다.   그래서 총 288 바이트가 사용되었다.

• 그럼, 테스트를 해보자.   키 하나에 sadd 명령으로 'A1001' ~ 'A2000'까지 1000개의 데이터를 넣어보자.   테스트는 파이썬(Python)으로 했다.
redis version 3.0.6
>>> conn.info('memory') 815,072
>>> test.saddstr(conn,'key',1001,2000)
>>> conn.info('memory') 886,432   사용량 >> 71,360 bytes


자, 71,360 바이트를 어디에 썼는지 알아봅시다.  
• 데이터 한 건당 64 바이트를 사용하므로 64 * 1,000 하면 64,000 바이트이다.
• 총 메모리 사용량 71,360 - 64,000 = 7,360 바이트가 남는다.
• 여기서 버킷 메모리 사용량이 8 * 1024 = 8,192 바이트이다.
• 논리적으로 계산한 사용량이 72,192 바이트로 실제 사용량 71,360 바이트와 약간의 차이는 있다.
• 정리하면, 실 데이터 크기 보다 약 14배의 메모리를 더 사용했고, 데이터 건당 66 바이트의 메모리 오버헤드가 발생한다.
• 이 테스트는 메모리 측면만 본 것이다.   값의 크기가 작은(5바이트) 것으로 해서 상대적으로 오버헤드가 커보인다.   빠른 속도와 값의 개수가 아주 많아도 성능이 거의 떨어지지 않는 것이 해시 테이블의 큰 장점이다.
• SET을 사용하면서 메모리를 절약할 수 있는 방법은 데이터(값)을 가능한 정수로 하는 것이다.   이렇게 해서 intset 을 사용하는 것이다.   redis.conf에 있는 파라미터 set-max-intset-entries의 기본값(defaul)이 512인데 이것을 1024로 수정해서 사용해도 성능이 거의 떨어지지 않는다.   메모리 부족이 문제라면 고려해 볼 것을 권합니다.

버킷 확장(Expand)

자, 이제 메모리 사용량은 잠시 잊고, 버킷(buckets) 확장에 대해서 알아봅시다.   내부적으로 확장(expand)이란 용어를 사용해서 여기서도 확장이라고 하지만, 사실 포인터 배열 메모리 할당(zcalloc)이다.   버킷(buckets, 배열크기)의 크기는 4부터 시작한다.

• 아래 그림은 버킷 4개에 모두 dictEntry가 할당된 상태이다.



• 확장 조건은 dictht[0].used가 size보다 같거나 크고, background로 AOF rewrite나 RDB save가 진행 중이 아니면 expand를 수행한다.   특별한 경우로 background로 AOF rewrite나 RDB save가 수행 중 이어도 used가 size의 5 배 보다 많으면 expand를 수행한다.
  확장은 현재 사용중인 버킷을 확장하는 것이 아니고, 새로운 버킷크기로 메모리를 할당하는 것이다.   dictht[1]은 새로 할당된 버킷을 가리키고, size = 8, used = 0이다.



• 새로운 키가 입력될 때는 saddCommand()에서 시각 해서 dbAdd()를 거쳐, dictAddRaw()에서 4개짜리 버킷이 할당되지만, 일반적으로는 값이 입력되는 (연한 주황색 function을 따라가자)  
  setTypeAdd() -> dictAdd() -> dictAddRaw() -> _dictKeyIndex() -> _dictExpandIfNeed() -> dictExpand()에서 메모리가 할당된다.

Rehash

버킷이 새로 할당되고 난 후 rehash가 시작되는데, 한 번에 모두 수행하는 것이 아니고, 몇 가지 오퍼레이션을 수행할 때마다 한 버킷(bucket) 씩 새 해시 테이블에 재 할당(rehash) 한다.   그러므로 한꺼번에 rehashing이 수행되어 다른 명령어 처리가 늦어질 것은 염려하지 않아도 된다.






• 앞에서 간단히 설명한 몇 가지 오퍼레이션을 아래 그림으로 표시했다.   해당 오퍼레이션은 dictAddRaw(), dictGenericDelete(), dictFind(), dictGetRandomKey(), dictGetSomeKeys() 이다.   Add나 Delete뿐만 아니라, Find에서도 rehash를 수행한다.
• 한 버킷 씩 수행되므로 펑션 명도 dictRehashStep이다.



• 위에 redis.c에 있는 databaseCron() 에서 부터 시작하는 rehash 가 있다.   대상은 키를 관리하는 레디스 메인 해시 테이블이다.   일반 SET, HASH의 해시 테이블은 대상이 아니다.  
  • databaseCron()은 100 millisecond마다 수행되는데, redis.conf에 있는 activerehashing이 yes 이면 rehash function 호출한다.
  • dictRehashMilliseconds(100)은 한 번 호출 시 100개의 버킷(buckets)을 rehash 한다.
  • 100 buckets을 rehash 후 1ms를 초과했으면 멈추고, 초과하지 않았으면 다시 100 buckets에 대해서 rehash를 수행하는 작업을 반복한다.


• 아래는 Rehashing이 완료된 상태이다.   완료된 버킷(buckets)이 dicht[0]에 연결되고, dicht[1] table 필드에 null이 할당되고 나머지 필드도 초기화된다.

해시 값 충돌, Changing

해시값으로 dictEntry를 버킷에 할당하는데, 다른 값(value)이지만, 같은 해시값을 가질 수 있다.   그러면 같은 버킷에 할당된다.   이때 새로운 엔트리가 버킷에 할당되고 새 엔트리의 next 필드에 기존 엔트리 포인터가 할당된다.
Rehash는 버킷 단위로 수행되므로, Changing이 발생해서 해당 버킷에 여러 개의 엔트리가 연결되어 있으면 한 번에 모두 Rehash 된다.

SET HashTable functions 흐름도

아래 그림 3개는 SET operation에서 HashTable operation으로 이어지는 function 흐름도이다.   약간 주의해서 봐야 할 부분만 간단히 설명하겠습니다.

• smoveCommand는 받은 값으로 setTypeRemove를 수행해서 값을 지우고, setTypeAdd로 넣는다.

정리

• 해시 테이블(dictionary) 기본 데이터 구조와
• dict data structure가 어느 dict function에서 생성되는지
• dict data structure간 연결관계
• 해시 테이블 메모리 사용량
• 버킷 확장(Expand)와 Rehashing
• SET 명령과 dict functions 간의 연결 관계를 알아보았습니다.