Redis HASH Table of KEYS

기본 데이터 구조

아래는 해시 테이블에 사용되는 몇 가지 중요한 struct입니다.

dict (dictionary) struct : 96 bytes

Data Type	Name	Size	Description
dictType	*type	8 bytes	DictType 포인터
void	*privdata	8 bytes
dictht	ht[2]	64 bytes	해시 테이블 배열, 크기 2
long	rehashidx	8 bytes	Rehash 중 인지 표시, 초기값 -1, 0 이상 Rehash 중
int	iterators	8 bytes	number of iterators currently running

dictht (dictionary hash table) struct : 32 bytes

Data Type	Name	Size	Description
dictEntry	**table	8 bytes	Buckets 포인터 배열을 가리킨다.
unsigned long	size	8 bytes	Buckets(포인터 배열)의 크기
unsigned long	sizemask	8 bytes	몇 번째 배열인지 얻기 위한 mask, 3,7,15,etc
unsigned long	used	8 bytes	해시 테이블이 가지고 있는 엔트리 개수

dictEntry (dictionary entry) struct : 24 bytes

Data Type	Name	Size	Description
void	*key	8 bytes	키
union ---------- void uint64_t int64_t double	v ---------- *val u64 s64 d	8 bytes	값
dictEntry	*next	8 bytes	Chaining, Hash 값 충돌 시 다음 엔트리 포인터

redisObject struct : 16 bytes

Data Type	Name	Size	Description
unsigned	type:4	4 bits	외부 데이터 타입
unsigned	encoding:4	4 bits	내부 데이터 타입
unsigned	lru:REDIS_LRU_BITS	24 bits	time : LRU_CLOCK()
int	refcount	4 bytes	참조 횟수
void	*ptr	8 bytes	sdshdr의 buf를 가리키는 포인터

DictType struct : 48 bytes

Data Type	Name	Size	Description
unsigned int	(*hashFunction)(const void *key)	8 bytes	hash function
void	*(*keyDup)(void *privdata, const void *key)	8 bytes	key dup (키 복사)
void	*(*valDup)(void *privdata, const void *obj)	8 bytes	val dup (값 복사)
int	(*keyCompare)(void *privdata, const void *key1, const void *key2)	8 bytes	key compare (비교)
void	(*keyDestructor)(void *privdata, void *key)	8 bytes	key destructor (zfree)
void	(*valDestructor)(void *privdata, void *obj)	8 bytes	val destructor (zfree)

키 관리 data structure 요약도

redisDb 구조체의 1번째 필드가 dict 포인터이다.
dict은 hast table 2개를 가지고 있고, buckets을 거쳐서 dictEntry에 도달한다.
dictEntry의 key 필드는 키를 가지고 있는 sds를, value 필드는 값을 가지고 있는 redisObject를 가리키고 있다.     관련 명령: debug structsize, debug htstats 0

다음 diagram은 위 요약도에 필드를 추가해서 좀 자세히 표시했고, 값은 STRING type을 가지는 것으로 표현했다.

키 관리 data structure 상세도

dictEntry의 key와 val 필드는 redisObject를 가리키고 있는데, 키를 가지고 있는 redisObject의 type이 STRING이고 encoding은 RAW로 저장된다.
값을 가지고 있는 redisObject의 type과 encoding은 여러 가지지만, 이 그림에서는 대표적인 STRING type을 표시했다.   그러므로 encoding은 RAW, EMBSTR, INT 중 한 가지로 저장된다.
이에 대한 자세한 내용은 스트링 데이터 구조 STRING Data Structure에 있으니 참고하시기 바랍니다.

클라이언트에서 명령을 가져오는 것과 결과를 보내는 것은 networking.c에 있다.
클라이언트에서 입력한 명령(키, 값 등을 포함한 문자열)을 받아서 토큰 분리한 다음 redisObject에 넣는데 이때는 무조건 encoding을 RAW로 넣는다.
왜냐하면 이때까지는 아직 명령을 해석한 단계가 아니므로 각 토큰의 의미를 알지 못한다.   일반적으로 1번째 토큰은 명령, 2번째 토큰은 키지만 3번째 토큰부터는 명령에 따라 다양한 인수가 오므로 encoding은 명령 해석 후에 알 수 있다.
키의 encoding은 RAW로 그대로 둔다.

다음은 키 관리 data structure가 어느 function에서 사용되는지 알아보기 위해 레디스에서 대표적이면서 비교적 간단한 GET 명령의 function 흐름도를 소개하고, 그다음에 data structure와의 관계를 설명한다.

GET 명령 functions 흐름도

Function 바로 밑에는 흰 박스에 주요 argument 하나를 표시했다.

다음은 각 소스 파일별로 속해 있는 function 들이다.
• t_string.c : getCommand(), getGenericCommand()
• db.c : lookupKeyReadOrReply(), lookupKeyRead(), lookupKey()
• dict.c : dictFind()
• dict.h : dictHashKey(), dictCompareKeys(), dictGetVal()
• networking.c : addReplyBulk(), addReply()

networking.c는 클라이언트로부터 명령을 받고, 결과를 리턴하는 function들로 구성되어 있다.   addReplyBulk, addReply는 값을 받아 결과를 리턴하는 역할을 한다.

각 function의 arguments와 리턴 값을 표시했고, 간단한 설명을 달았다.
1. void getCommand(redisClient *c)
2. int getGenericCommand(redisClient *c)
3. robj *lookupKeyReadOrReply(redisClient *c, robj *key, robj *reply) : key를 받아 robj value를 리턴한다.
4. robj *lookupKeyRead(redisDb *db, robj *key)
   1. expireIfNeeded(db,key)를 호출하여 키가 이미 expire되었으면 키를 삭제한다.
   2. lookupKey(db,key)를 호출하여 키가 있어서 값을 리턴하면 server stat 에서 hits를 1증가시키고, 키가 없어서 null을 리턴하면 misses를 1증가시킨다.
   3. robj로 value를 리턴한다.
5. robj *lookupKey(redisDb *db, robj *key)
   1. dictFind()를 호출하여 키가 있으면 dictEntry를 리턴한다.
   2. 받은 dictEntry로 dictGetVal(de)를 호출하여 robj value를 리턴하다.
   3. 키가 없으면 null을 리턴한다.
6. dictEntry *dictFind(dict *d, const void *key) : 키를 찾는다.
7. dictHashKey(dict d, robj key)는 dict.h에 정의되어 있다. (d)->type->hashFunction(key)
   dictType의 hashFunction으로 index를 구한다. 이 index로 bucket를 찾아간다.
8. dictCompareKeys(d, key, he->key)는 dict.h에 정의되어 있다. (d)->type->keyCompare
   dictType의 KeyCompare로 키를 비교한다.
9. dictGetVal(de)는 dict.h에 정의되어 있다. robj value를 리턴한다.

Hash table data structure와 GET 명령 function 연결

여기서는 Data structure diagram 위에 GET 명령의 각 Function을 관계된 data structure 옆에 표시했다.
③번 lookupKeyReadOrReply 부터는 조회 명령에서 일반적으로 사용되는 키 찾기 흐름이다.

Dict struct 자체는 레디스가 시작할 때 생성된다.   그러나 dictEntry struct는 새로운 키가 입력될 때마다 생성된다.   이 과정을 알아보기 위해 SET 명령의 function 들의 흐름을 알아보고, 그다음에 키 관리 data structure와의 관계를 알아본다.

SET 명령 functions 흐름도

Function 바로 밑에는 흰 박스에 주요 argument 하나를 표시했다.

다음은 각 소스 파일별로 속해 있는 function 들이다.
• t_string.c : setCommand(), setGenericCommand()
• db.c : setKey(), lookupKeyWrite(), dbAdd(), dbOverwrite()
• dict.c : dictAdd(), dictAddRaw(), _dictKeyIndex()
• dict.h : dictSetKey(), dictSetVal()
• zmalloc.c : zmalloc()

각 function의 arguments와 리턴 값을 표시했고, 간단한 설명을 달았다.
1. void setCommand(redisClient *c)
2. void setGenericCommand(redisClient *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply)
3. void setKey(redisDb *db, robj *key, robj *val) : lookupKeyWrite()로 키가 있는지 확인해서 없으면 dictAdd()를 실행해서 키와 값을 넣고, 있으면 dbOverwrite()를 실행해서 값을 덮어쓴다.
4. void dbAdd(redisDb *db, robj *key, robj *val)
5. int dictAdd(dict *d, void *key, void *val) : 여기서부터 dict을 argument로 받고, robj로 넘어오던 key와 val이 void로 바뀐다.
6. dictEntry *dictAddRaw(dict *d, void *key) : _dictKeyIndex()로 hash index(bucket index)를 얻은 다음 zmalloc()로 dictEntry를 생성하고, dictSetKey()로 키를 넣은 다음 dictEntry 포인터를 리턴한다.
7. static int _dictKeyIndex(dict *d, const void *key) : Hash index를 얻는다.
8. void *zmalloc(size_t size) : dictEntry struct 메모리를 할당한다.
9. dictSetKey(d, entry, _key_) : dictEntry의 key 필드에 robj key를 할당한다.
10. dictSetVal(d, entry, _val_) : dictEntry의 val 필드에 robj value를 할당한다.

lookupKeyWrite()와 dbOverwrite()는 번호를 붙이지 않아서 따로 설명한다.
• robj *lookupKeyWrite(redisDb *db, robj *key) : expireIfNeeded()로 키가 expire되었는지 확인하고 그러면 키를 삭제한다. 다음에 lookupKey()로 키를 찾고 값을 리턴한다.
• void dbOverwrite(redisDb *db, robj *key, robj *val) : dictFind()로 키를 찾고, dictReplace()로 덮어쓴다.

Hash table data structure와 SET 명령 function 연결

여기서는 Data structure diagram 위에 SET 명령의 각 Function을 관계된 data structure 옆에 표시했다.
dictAddRaw()에서 새로운 dictEntry를 만든다.
이제까지 dictEntry의 value 필드에 STRING data type을 위주로 설명했다.   Value 필드에는 STRING뿐만 아니라 레디스에서 사용하는 모든 data type이 들어간다. 이를 설명하는 요약 diagram을 보자.

키 관리 data structure 확장 요약도

DictEntry의 val 필드는 redisObject(robj)를 가리키고 redisObject의 type은 사용자에게 알려진 data type(STRING, LIST, SET, ZSET, HASH)을 관리하고, encoding은 내부 data structure를 관리한다.
레디스는 encoding 필드의 값을 보고 data structure에 맞는 function을 사용한다.

각 encoding data structure에 대한 자세한 설명은 아래 링크를 참조하세요.
• STRING Data Structure : RAW, EMBSTR, INT
• LIST : Linked List,   Ziplist 그리고 버전 3.2부터 사용되는 Quick List
• SET : Hash Table과 Intset
• ZSET : Skip list와 Ziplist
• HASH : Hash Table과 Ziplist

다음은 이 확장 요약도에 각 struct의 필드와, redisObject의 type와 encoding을 표시해서 좀 자세히 표현했습니다.

키 관리 data structure 상세도

좀 복잡해 보이지만, 레디스 데이터 구조의 핵심이라고 볼 수 있습니다.   레디스를 데이터 구조를 이해하는데 도움이 되길 바랍니다.

5개 Data Type과 Data Structure(encoding)의 관계

아래 그림은 5개의 data type과 내부 data structure와 관계를 나타내는데 위의 그림들과는 좀 다른 형태의 그림(표현)이다.

• Ziplist는 Lists, Sorted Sets(Zset), Hashes에서 사용된다.
• Hash table은 Sets과 Hashes에서 사용되고, 키 관리에서도 사용된다.
• Quick List는 버전 3.2부터 적용되고 linked list와 ziplist로 구성된다.

Lookupkey functions 흐름도

아래 그림은 키를 찾는 lookupkey functions의 일반적인 흐름도이다.

• 조회 명령들은 대게 lookupKeyReadOrReply function을 호출하고, 입력/수정/삭제 명령은 lookupKeyWriteOrReply function을 호출한다.
• lookupKeyReadOrReply는 lookupKeyRead를 호출하고, lookupKeyWriteOrReply는 lookupKeyWrite를 호출한 후 결과를 받아 addReply(networking.c)를 호출해서 클라이언트에 리턴한다.
• Key 찾기는 결과 lookupKey를 호출해서 키를 찾고 dictGetVal를 호출해서 값을 가져온다.

정리

• 키를 관리하는 data structure인 dictionary(dict)과 Hash table 구조를 살펴보았다.
• Hash table 구조와 GET, SET function이 어느 부분에서 작동하는지 살펴보았다.
• Data type과 내부 data structure와의 관계를 살펴보았다.
• 마지막으로 키 찾기 function 흐름을 살펴보았다.