/* * Copyright (c) 2009-Present, Redis Ltd. * All rights reserved. * * Copyright (c) 2024-present, Valkey contributors. * All rights reserved. * * Licensed under your choice of (a) the Redis Source Available License 2.0 * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the * GNU Affero General Public License v3 (AGPLv3). * * KVSTORE * ------- * Index-based KV store implementation. This file implements a KV store comprised * of an array of dicts (see dict.c) The purpose of this KV store is to have easy * access to all keys that belong in the same dict (i.e. are in the same dict-index) * * For example, when Redis is running in cluster mode, we use kvstore to save * all keys that map to the same hash-slot in a separate dict within the kvstore * struct. * This enables us to easily access all keys that map to a specific hash-slot. * * Portions of this file are available under BSD3 terms; see REDISCONTRIBUTIONS for more information. */ #ifndef DICTARRAY_H_ #define DICTARRAY_H_ #include "dict.h" #include "adlist.h" typedef struct _kvstore kvstore; /* Structure for kvstore iterator that allows iterating across multiple dicts. */ typedef struct _kvstoreIterator { kvstore *kvs; long long didx; long long next_didx; dictIterator di; } kvstoreIterator; /* Structure for kvstore dict iterator that allows iterating the corresponding dict. */ typedef struct _kvstoreDictIterator { kvstore *kvs; long long didx; dictIterator di; } kvstoreDictIterator; typedef int (kvstoreScanShouldSkipDict)(dict *d, int didx); typedef int (kvstoreExpandShouldSkipDictIndex)(int didx); typedef int (kvstoreRandomShouldSkipDictIndex)(int didx); /* kvstoreType: Callback structure for kvstore-specific operations. * Similar to dictType for dict, this allows kvstore to be a generic data structure * without hardcoding dependencies on specific subsystems. */ typedef struct kvstoreType { /* Allow kvstore to carry extra caller-defined metadata. The * extra memory is initialized to 0 when a kvstore is allocated. */ size_t (*kvstoreMetadataBytes)(kvstore *kvs); /* Allow a per slot dicts to carry extra caller-defined metadata. The * extra memory is initialized to 0 when each dict is allocated. */ size_t (*dictMetadataBytes)(dict *d); /* Check if a dict at given index can be freed. Used by kvstore when * KVSTORE_FREE_EMPTY_DICTS is set. Return 1 if can free, 0 otherwise. * Parameters: kvstore pointer, dict index */ int (*canFreeDict)(kvstore *kvs, int didx); /* Called when kvstore becomes empty. */ void (*onKvstoreEmpty)(kvstore *kvs); /* Called when per slot dict becomes empty. Parameters: kvstore pointer, * dict index. */ void (*onDictEmpty)(kvstore *kvs, int didx); } kvstoreType; /* Basic metadata allocated per dict. * If additional metadata needed, embed this structure as the first member * in a new, larger structure. */ typedef struct { listNode *rehashing_node; /* list node in rehashing list */ } kvstoreDictMetaBase; #define KVSTORE_ALLOCATE_DICTS_ON_DEMAND (1<<0) #define KVSTORE_FREE_EMPTY_DICTS (1<<1) kvstore *kvstoreCreate(kvstoreType *type, dictType *dtype, int num_dicts_bits, int flags); void kvstoreEmpty(kvstore *kvs, void(callback)(dict*)); void kvstoreRelease(kvstore *kvs); unsigned long long kvstoreSize(kvstore *kvs); unsigned long kvstoreBuckets(kvstore *kvs); size_t kvstoreMemUsage(kvstore *kvs); unsigned long long kvstoreScan(kvstore *kvs, unsigned long long cursor, int onlydidx, dictScanFunction *scan_cb, kvstoreScanShouldSkipDict *skip_cb, void *privdata); int kvstoreExpand(kvstore *kvs, uint64_t newsize, int try_expand, kvstoreExpandShouldSkipDictIndex *skip_cb); int kvstoreGetFairRandomDictIndex(kvstore *kvs, kvstoreExpandShouldSkipDictIndex *skip_cb, int fair_attempts, int slow_fallback); void kvstoreGetStats(kvstore *kvs, char *buf, size_t bufsize, int full); int kvstoreFindDictIndexByKeyIndex(kvstore *kvs, unsigned long target); int kvstoreGetFirstNonEmptyDictIndex(kvstore *kvs); int kvstoreGetNextNonEmptyDictIndex(kvstore *kvs, int didx); int kvstoreNumNonEmptyDicts(kvstore *kvs); int kvstoreNumAllocatedDicts(kvstore *kvs); int kvstoreNumDicts(kvstore *kvs); void kvstoreMoveDict(kvstore *kvs, kvstore *dst, int didx); /* kvstore iterator specific functions */ void kvstoreIteratorInit(kvstoreIterator *kvs_it, kvstore *kvs); void kvstoreIteratorReset(kvstoreIterator *kvs_it); dict *kvstoreIteratorNextDict(kvstoreIterator *kvs_it); int kvstoreIteratorGetCurrentDictIndex(kvstoreIterator *kvs_it); dictEntry *kvstoreIteratorNext(kvstoreIterator *kvs_it); /* Rehashing */ void kvstoreTryResizeDicts(kvstore *kvs, int limit); uint64_t kvstoreIncrementallyRehash(kvstore *kvs, uint64_t threshold_us); size_t kvstoreOverheadHashtableLut(kvstore *kvs); size_t kvstoreOverheadHashtableRehashing(kvstore *kvs); unsigned long kvstoreDictRehashingCount(kvstore *kvs); /* Specific dict access by dict-index */ unsigned long kvstoreDictSize(kvstore *kvs, int didx); void kvstoreInitDictIterator(kvstoreDictIterator *kvs_di, kvstore *kvs, int didx); void kvstoreInitDictSafeIterator(kvstoreDictIterator *kvs_di, kvstore *kvs, int didx); void kvstoreResetDictIterator(kvstoreDictIterator *kvs_di); dictEntry *kvstoreDictIteratorNext(kvstoreDictIterator *kvs_di); dictEntry *kvstoreDictGetRandomKey(kvstore *kvs, int didx); dictEntry *kvstoreDictGetFairRandomKey(kvstore *kvs, int didx); unsigned int kvstoreDictGetSomeKeys(kvstore *kvs, int didx, dictEntry **des, unsigned int count); int kvstoreDictExpand(kvstore *kvs, int didx, unsigned long size); unsigned long kvstoreDictScanDefrag(kvstore *kvs, int didx, unsigned long v, dictScanFunction *fn, dictDefragFunctions *defragfns, void *privdata); typedef dict *(kvstoreDictLUTDefragFunction)(dict *d); unsigned long kvstoreDictLUTDefrag(kvstore *kvs, unsigned long cursor, kvstoreDictLUTDefragFunction *defragfn); void *kvstoreDictFetchValue(kvstore *kvs, int didx, const void *key); dictEntry *kvstoreDictFind(kvstore *kvs, int didx, void *key); dictEntry *kvstoreDictAddRaw(kvstore *kvs, int didx, void *key, dictEntry **existing); dictEntryLink kvstoreDictTwoPhaseUnlinkFind(kvstore *kvs, int didx, const void *key, int *table_index); void kvstoreDictTwoPhaseUnlinkFree(kvstore *kvs, int didx, dictEntryLink plink, int table_index); int kvstoreDictDelete(kvstore *kvs, int didx, const void *key); dict *kvstoreGetDict(kvstore *kvs, int didx); void kvstoreFreeDictIfNeeded(kvstore *kvs, int didx); void *kvstoreGetDictMeta(kvstore *kvs, int didx, int createIfNeeded); void *kvstoreGetMetadata(kvstore *kvs); dictEntryLink kvstoreDictFindLink(kvstore *kvs, int didx, void *key, dictEntryLink *bucket); void kvstoreDictSetAtLink(kvstore *kvs, int didx, void *kv, dictEntryLink *link, int newItem); /* dict with distinct key & value (no_value=1) currently is used only by pubsub. */ void kvstoreDictSetKey(kvstore *kvs, int didx, dictEntry* de, void *key); void kvstoreDictSetVal(kvstore *kvs, int didx, dictEntry *de, void *val); #ifdef REDIS_TEST int kvstoreTest(int argc, char *argv[], int flags); #endif #endif /* DICTARRAY_H_ */