Redis Dictionary(Hash Tables)

주요 struct

• dictEntry struct dictEntry { void *key; union { void *val; // value uint64_t u64; // unsigned integer int64_t s64; // signed integer double d; // double } v; struct dictEntry *next; // Chaining: Next entry in the same hash bucket. void *metadata[]; };
• dict
  struct dict { dictType *type; dictEntry **ht_table[2]; unsigned long ht_used[2]; long rehashidx; // -1: Not rehashing int16_t pauserehash; // If >0 rehashing is paused (<0 indicates coding error) signed char ht_size_exp[2]; // exponent of size. (size = 1<<exp) void *metadata[]; };
• dictIterator typedef struct dictIterator { dict *d; long index; int table, safe; dictEntry *entry, *nextEntry; unsigned long long fingerprint; } dictIterator; 'safe'가 '1'로 설정되면 안전한 반복자입니다. 즉, 반복하는 동안에도 사전에 대해 dictAdd, dictFind 및 기타 함수를 호출할 수 있습니다. 그렇지 않으면 '0' 안전하지 않은 반복자이며, 반복하는 동안에는 dictNext()만 호출해야 합니다.

주요 define

• #define dictFreeVal(d, entry) do {
  if ((d)->type->valDestructor) (d)->type->valDestructor((d), dictGetVal(entry)); } while(0)
• #define dictFreeKey(d, entry)
  if ((d)->type->keyDestructor) (d)->type->keyDestructor((d), dictGetKey(entry))
• #define dictCompareKeys(d, key1, key2)
  (((d)->type->keyCompare) ? (d)->type->keyCompare((d), key1, key2) : (key1) == (key2))
• #define dictEntryMetadataSize(d)
  ((d)->type->dictEntryMetadataBytes ? (d)->type->dictEntryMetadataBytes(d) : 0)
• #define dictMetadataSize(d) ((d)->type->dictMetadataBytes ? (d)->type->dictMetadataBytes() : 0)
• #define dictHashKey(d, key) ((d)->type->hashFunction(key))
• #define dictSlots(d) (DICTHT_SIZE((d)->ht_size_exp[0])+DICTHT_SIZE((d)->ht_size_exp[1]))
• #define dictSize(d) ((d)->ht_used[0]+(d)->ht_used[1])
• #define dictIsRehashing(d) ((d)->rehashidx != -1)
• #define dictPauseRehashing(d) ((d)->pauserehash++)
• #define dictResumeRehashing(d) ((d)->pauserehash--)

◼️ dict 생성(create)과 확장(expand)

• 1) static void _dictReset(dict *d, int htidx)
• 2) dict *dictCreate(dictType *type) // 해시 테이블 생성 Create a new hash table
  -> _dictInit(d,type); return d;
• 3) int _dictInit(dict *d, dictType *type) // 해시 테이블 초기화 Initialize the hash table
  -> _dictReset(d, 0); _dictReset(d, 1); return DICT_OK;
• 4) int dictResize(dict *d) // 모든 요소를 ​​포함하는 최소 크기로 테이블 크기를 조정
  -> return dictExpand(d, minimal);
• 5) int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
  
• 6) int dictExpand(dict *d, unsigned long size)
  -> return _dictExpand(d, size, NULL);
• 7) int dictTryExpand(dict *d, unsigned long size)
  -> _dictExpand(d, size, &malloc_failed); return malloc_failed? DICT_ERR : DICT_OK;

◼️ dict 재해싱(rehashing)

• 1) int 📍 dictRehash(dict *d, int n) // HT 확장(expand)과 축소(shrink)에 모두 사용합니다.
  // 완료되면 '0', 미완료(아직 해싱할 키가 남아 있으면) '1'을 리턴합니다.
• 2) long long timeInMilliseconds(void)
• 3) int 📍 dictRehashMilliseconds(dict *d, int ms)
  -> dictRehash(d,100)
• 4) static void _dictRehashStep(dict *d)
  if (d->pauserehash == 0) dictRehash(d,1);
• 5) void *dictMetadata(dict *d) // dict 내의 메타데이터 섹션에 대한 포인터를 반환합니다.

◼️ datatype 별 type_dicts[] Resize(축소), Rehashing(재해싱)

ent810(redis-7.2.7)에서 새로 도입한 datatype 별 type_dicts[]의
Resize(축소)는 tryResizeHashTables() 함수에 dictResize(📍server.db[dbid].type_dicts[i])를 추가하는 것으로 완료되었다.
Rehashing(재해싱)은 incrementallyRehash() 함수에 dictRehashMilliseconds(server.db[dbid].type_dicts[i],1)을 추가하는 것으로 완료되었다.
tryResizeHashTables()와 incrementallyRehash() 함수는 databasesCron()에서 호출한다. server.c databasesCron() /* Resize */ for (j = 0; j < dbs_per_call; j++) { 📍tryResizeHashTables(resize_db % server.dbnum); resize_db++; } /* Rehash */ if (server.activerehashing) { for (j = 0; j < dbs_per_call; j++) { int work_done = 📍incrementallyRehash(rehash_db); } } tryResizeHashTables() if (htNeedsResize()) dictResize(📍server.db[dbid].type_dicts[i]); if (htNeedsResize()) dictResize(server.db[dbid].expires); if (htNeedsResize()) dictResize(server.db[dbid].dict); incrementallyRehash() for 📍dictRehashMilliseconds(server.db[dbid].type_dicts[i],1); // ent810 add dictRehashMilliseconds(server.db[dbid].expires,1); dictRehashMilliseconds(server.db[dbid].dict,1);

◼️ dict add, find, replace

• 1) int dictAdd(dict *d, void *key, void *val) // 대상 해시 테이블에 요소를 추가합니다.
  -> dictAddRaw(d,key,NULL); dictSetVal(d, entry, val);
• 2) dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) // Low level add or find:
  -> dictFindPositionForInsert(d, key, existing); return dictInsertAtPosition(d, key, position);
• 3) void *dictFindPositionForInsert(dict *d, const void *key, dictEntry **existing)
• 4) dictEntry *dictInsertAtPosition(dict *d, void *key, void *position) // Insert
• 5) int dictReplace(dict *d, void *key, void *val) // Add or Overwrite: add return 1, replace return 0.
• 6) dictEntry *dictAddOrFind(dict *d, void *key) // Add or Find: add return new entry, find existing entry
• 7) dictEntry *dictFind(dict *d, const void *key) // return he; or return NULL;
• 8) void *dictFetchValue(dict *d, const void *key) // 값 조회, 없으면 NULL.
  -> he = dictFind(d,key); return he ? dictGetVal(he) : NULL;

◼️ dict delete

• 1) static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree:0/1) // 없으면 'NULL'을 리턴합니다.
• 2) int dictDelete(dict *ht, const void *key) // 삭제
  -> return dictGenericDelete(ht,key,📍nofree:0) ? DICT_OK : DICT_ERR;
• 3) dictEntry *dictUnlink(dict *d, const void *key) // 연결 해제, 실제 삭제는 호출한 쪽에서 dictFreeUnlinkedEntry()를 호출해서 삭제해야 한다.
  -> return dictGenericDelete(d,key,📍nofree:1);
• 4) void dictFreeUnlinkedEntry(dict *d, dictEntry *he) // dictUnlink() 호출 후 항목을 실제로 해제하려면 이 함수를 호출해야 합니다.

◼️ dict clear

• 1) int _dictClear(dict *d, int htidx, void(callback)(dict*)) // 사전(dictionary) 전체 해제
  -> dictFreeKey(d, he); dictFreeVal(d, he);
• 2) void dictRelease(dict *d) // Clear & Release the hash table
  -> _dictClear(d,0,NULL); _dictClear(d,1,NULL); zfree(d);

◼️ dict two phase unlink

• 1) dictEntry *dictTwoPhaseUnlinkFind(dict *d, const void *key, dictEntry ***plink, int *table_index) // 재해시를 일시중지
  -> dictPauseRehashing(d);
• 2) void dictTwoPhaseUnlinkFree(dict *d, dictEntry *he, dictEntry **plink, int table_index) // 재해시 다시 시작(再開)
  -> dictResumeRehashing(d);

◼️ dict Set(입력) key, val

• 1) void dictSetKey(dict *d, dictEntry* de, void *key) // 키 넣기
• 2) void dictSetVal(dict *d, dictEntry *de, void *val) // 값 넣기
• 3) void dictSetUnsignedIntegerVal(dictEntry *de, uint64_t val) // Unsigned Integer -> de->v.u64 = val;
• 4) void dictSetDoubleVal(dictEntry *de, double val) // Double -> de->v.d = val;
• 5) int64_t dictIncrSignedIntegerVal(dictEntry *de, int64_t val) // Incr Signed Integer -> return de->v.s64 += val;
• 6) uint64_t dictIncrUnsignedIntegerVal(dictEntry *de, uint64_t val) // Incr Unsigned Integer -> return de->v.u64 += val;
• 7) double dictIncrDoubleVal(dictEntry *de, double val) // IncrDouble -> return de->v.d += val;

◼️ dict Get(조회) key, val

• 1) void *dictEntryMetadata(dictEntry *de) // return &de->metadata;
• 2) void *dictGetKey(const dictEntry *de) // return de->key;
• 3) void *dictGetVal(const dictEntry *de) // return de->v.val;
• 4) int64_t dictGetSignedIntegerVal(const dictEntry *de) // Get Signed Integer. return de->v.s64;
• 5) uint64_t dictGetUnsignedIntegerVal(const dictEntry *de) // Get Unsigned Integer. return de->v.u64;
• 6) double dictGetDoubleVal(const dictEntry *de) // Get Double. return de->v.d;
• 7) double *dictGetDoubleValPtr(dictEntry *de) // Pointer. return &de->v.d;

◼️ dict Get next, Set next

• 1) static dictEntry *dictGetNext(const dictEntry *de) // return de->next; 항목의 'next' 필드를 반환하거나 항목에 'next' 필드가 없으면 NULL을 반환합니다.
• 2) static dictEntry **dictGetNextRef(dictEntry *de) // Pointer. return &de->next;
• 3) static void dictSetNext(dictEntry *de, dictEntry *next) // de->next = next;

◼️ dict Memory

• 1) size_t dictMemUsage(const dict *d) // 키와 값의 크기를 제외한, dict의 메모리 사용량을 바이트 단위로 반환합니다.
  -> return dictSize(d) * sizeof(dictEntry) + dictSlots(d) * sizeof(dictEntry*);
• 2) size_t dictEntryMemUsage(void) // return sizeof(dictEntry);

◼️ dict이 변경되었는지 확인하는 지문(fingerprint) 생성.

• unsigned long long dictFingerprint(dict *d)

◼️ dict Iterator(반복자)

• 1) void dictInitIterator(dictIterator *iter, dict *d) // dict 반복자 초기화
• 2) void dictInitSafeIterator(dictIterator *iter, dict *d) // iter->safe = 1;
• 3) void dictResetIterator(dictIterator *iter)
• 4) dictIterator *dictGetIterator(dict *d) // iter 메모리 할당. dictIterator *iter = zmalloc(sizeof(*iter));
• 5) ictIterator *dictGetSafeIterator(dict *d) // dictIterator *i = dictGetIterator(d); i->safe = 1; return i;
• 6) dictEntry *dictNext(dictIterator *iter) // 다음 entry로 이동
• 7) void dictReleaseIterator(dictIterator *iter) // iter 해제. zfree(iter);

◼️ dict Random

• 1) dictEntry *dictGetRandomKey(dict *d) // return random key
• 2) dictEntry *dictGetFairRandomKey(dict *d) // return Fair random key
• 3) unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) // return 키 개수. 값은 des에 넣어진다.

◼️ dict 조각 모음

• 1) static void dictDefragBucket(dict *d, dictEntry **bucketref, dictDefragFunctions *defragfns) // 조각 모음

◼️ dict Scan

• 1) static unsigned long rev(unsigned long v) // Function to reverse bits. dictScanDefrag() 함수에서 호출한다.
• 2) unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata)
• 3) unsigned long dictScanDefrag(dict *d, unsigned long v, dictScanFunction *fn, dictDefragFunctions *defragfns, void *privdata)

◼️ private functions

• 1) static int dictTypeExpandAllowed(dict *d) // _dictExpandIfNeeded()에서 호출합니다.
• 2) static int _dictExpandIfNeeded(dict *d) // 필요한 경우 해시 테이블을 확장합니다.
• 3) static signed char _dictNextExp(unsigned long size) // 우리의 해시 테이블 크기는 2의 거듭제곱입니다.
• 4) void *dictFindPositionForInsert(dict *d, const void *key, dictEntry **existing)
• 5) void dictEmpty(dict *d, void(callback)(dict*))
• 6) void dictSetResizeEnabled(dictResizeEnable enable) // 📍dict_can_resize (전역 변수) = enable;
• 7) uint64_t dictGetHash(dict *d, const void *key) // return dictHashKey(d, key);
• 8) dictEntry *dictFindEntryByPtrAndHash(dict *d, const void *oldptr, uint64_t hash)

◼️ Debugging

• 1) size_t _dictGetStatsHt(char *buf, size_t bufsize, dict *d, int htidx, int full)
• 2) void dictGetStats(char *buf, size_t bufsize, dict *d, int full)

◼️ Benchmark

• 1) uint64_t hashCallback(const void *key)
• 2) int compareCallback(dict *d, const void *key1, const void *key2)
• 3) ...