Dict

Dict는 다양한 자료구조를 담는 기본적인 redis의 자료구조입니다.  

key, value형식으로 되어있고 value에 사용자가 입력한 자료구조(?)들이 들어가게 되죠

출처 : http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_1_LL.svg

사용자가 입력한 John Smith, Lisa Smith같은 key값들이 hash function을 통해서 나름 고유한 숫자로 바뀌고
그 숫자들이 키가되고 키마다 value를 가리키고 있습니다.

주목할건 John Smith, Sandra Dee입니다. hash function을 통해 나온값이 동일한 값이 나오는 경우가 있는데(hash collision) 해결 방법중에 하나가 리스트 형식으로 동일한 hash value에 대해 처리를 해줍니다.

하지만 리스트가 길어지면 성능의 문제가 발생하기 때문에 
결국엔 bucket 크기를 늘려줘야 하는데 Redis 에서는 어떻게 동작하는지 밑에서 알아보도록 하죠 : )

dict의 구조

dictht, dictEntry 에서는 앞서 말한 구조를 구현해 놨고, 

dict 에서는 rehash를 위해서 두개의 dictht 와 hashfuction, key, value 비교/복사/삭제를 위한 dictType을 가지고 있습니다.

 
dictCreate를 하면 dict *d = zmalloc(sizeof(*d)); 를 수행합니다.
자~ 지금부터 재밌습니다. : )


dict에 데이터를 저장하는 순서입니다. (rehash라는 부분이 있는데 이건 뒷부분에 설명하기로 하고, 여기서는 데이타 삽입에 대해서만 알아보겠습니다.)

처음에는 아래의 코드로 인해 4개의 bucket으로 시작합니다.

데이타를 삽입을 계속 진행하다보면, 하나의 bucket에 많은 dictEntry가 이어져서
탐색하는데 상당한 시간이 걸리게 됩니다.
이때 아래와 같은 조건이 될때  Expand를 수행하고 Rehash를 수행합니다.

rehash되는 도중에 데이타 삽입이나, 삭제, 검색이 수행되면 문제 생기는거 아니냐? 라는 생각이 들었지만
소스를 보니 그 걱정은 뚝~!! ht[0]에서 없으면 ht[1]에서 검사합니다.

한번에 ht[0]의 모든 bucket을 Rehash 했으면 좋겠지만, 여기에서는 아래의 경우 하나씩하나씩 Rehash를 수행합니다.(여러개를 할수도 있습니다.)

dictAddRaw, dictGenericDelete, dictFind, dictGetRandomKey 함수 호출할때~!!

rehash 중일때는 ht[1]에 데이타 추가합니다.

rehash가 모두 끝나면, 즉 ht[0]에 used가 0이 되면, ht[0]은 ht[1]이 가리키고 있는
 table을 가리키고 ht[1]은 reset됩니다.

 검색의 색인구조에 사용해도 될것 같네요.  : )  key는 키워드, 데이타에는 출현한 문서번호들...
이상 dict 설명을 마치겠습니다. 

다음에는 value에 저장되는 자료구조들에 대해서 알아보겠습니다.(String, Hash, List, Set, SortedSet)

아래는 Redis의 자료구조를 정말 잘 표현한 그림 한장입니다.
예~~전에 좋다고 그냥 다운받아서 출처를 모르겠네요;; 혹시나 구글 이미지검색했는데....ㅋㅋ
문제가 된다면 지우겠습니다.