# 看 valkey 的資料結構
## serverObj
在Valkey 資料庫中的每個值都由一個 `robj`（原 redisObject，現在改名成 serverObject）表示，其中包含類型、編碼和引用計數……等資訊。

typedef struct serverObject robj;

struct serverObject {
    unsigned type : 4;
    unsigned encoding : 4;
    unsigned lru : LRU_BITS; /* LRU time (relative to global lru_clock) or
                              * LFU data (least significant 8 bits frequency
                              * and most significant 16 bits access time). */
    // ...
    unsigned refcount : OBJ_REFCOUNT_BITS;
    void *ptr;
};

- type: 標識資料類型 (string, list, set, hash, sorted set, stream, or module，以下將介紹)
- encoding: 指定優化的內部表示格式
- refcount: 記憶體管理的引用計數
- ptr: 指向實際資料的位置

### robj 用途
進行指令的處理。
以處理 SETRANGE 命令時的部分程式碼為例。

// t_string.c
        o = createObject(OBJ_STRING, sdsnewlen(NULL, offset + sdslen(value)));
        dbAdd(c->db, c->argv[1], &o); // serverDb *db, robj *key, robj **valref

- 使用 createObject 將 SDS 字串包裝成 robj。具體而言是先使用 `sdsbewlen` 創建指定長度的 SDS 字串，之後 assign 給 robj 中的 ptr，另外，robj 中的 type 設為 OBJ_STRING、refcount 設 1。
- dbAdd 會將此 robj 加入到資料庫中。此函式行為會做相關初始化、 根據 key 而決定的雜湊表 (`kvstore`)與其索引，將加到 key-value 適當位置，並做 `notifyKeyspaceEvent()`。

## 兩版通用雜湊表
舊版的通用雜湊實作是在 dict.c，而在 valkey 8.1 引入新的 hashtable.c。
目前 8.1 中，尚未將所有通用雜湊都改用 hashtable，但如以上提及的 kvstore，就改使用 hashtabl 了。

## dict.c
在 valkey 原始檔案中，有 dict.c 還有 t_hash.c 與 t_set.c 三者檔案中，第一個檔案是提供通用的 key-value 的操作，後兩者在特定情況下會使用 dict.c 作為底層儲存，但也會根據資料大小和特性選擇其他更適合的編碼方式（如 listpack、intset） 來改進記憶體使用與效能。

### dict.c 提供通用的 key-value
具有幾大特色
- 由陣列存值，並用 single linked list 做 chaining 以解決 collision 所組成
- 基本雜湊表操作：新增、刪除、查找
- 動態調整大小：自動擴展和收縮
- 增量式重新雜湊(Incremental rehashing)

### struct
需先了解兩個資料結構: `struct dictEntry` 還有 `struct dict`
#### 1. dictEntry
這是 hash table 中的每個 entry，也就是 key-value 對：

`dictEntry` 是一個共用抽象名詞，實際上背後可能是兩種不同的 struct
- `dictEntryNormal` 用在傳統情況下（key 是獨立指標）。
- `dictEntryEmbedded` 將 key (以及有時是 value) 直接嵌入到 dictEntry 結構體內部，而不是透過一個單獨的指標指向另一個記憶體位置，藉此省記憶體與減少指標跳轉

以下用 dictEntryNormal 理解 entry，會存有 key, value 還有指向下一項的指標。

typedef struct {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; /* Next entry in the same hash bucket. */
} dictEntryNormal;

#### 2. dict
存 hashTable 內容的就是 `ht_table[2]`，其餘 struct 成員皆是處理雜湊時所需。

struct dict {
    dictType *type; // Operation type of this dict, providing callbacks such as hash, comparison, free, etc.
    dictEntry **ht_table[2]; // Two hash tables, supporting Incremental rehash ([0]: old, [1]: new)
    unsigned long ht_used[2]; // Number of entries actually used in each table
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* Exponent of hash table size (actual size = 2^exp) */
    int16_t pauseAutoResize; /* If >0 automatic resizing is disallowed (<0 indicates coding error) */
    void *metadata[]; // Used to remember its position in the rehashing list
};

所有資料可能會分散於 `ht_table[0]` 或 `ht_table[1]` 之中，具體在 rehash 部分再說明。

dictType 為 **callback 函式集合**，讓 `dict` 支援多種 key/value 的處理邏輯，例如：
- `hashFunction`：計算 hash 值
- `keyCompare`：比對 key 是否相等
- `keyDestructor` / `valDestructor`：釋放記憶體
- `no_value`：設定是否為 set 模式（只有 key，沒有 value）

dict 結構的示意圖
> It's a chained hash table, so if multiple keys are hashed to the same slot in the table, their key-value entries form a linked list. That's what the "next" pointer in the dictEntry is for.

圖片來源: [A new hash table](https://valkey.io/blog/new-hash-table/)

### 雜湊表中判斷該 expand 或 shrink
當雜湊表的元素數量達到一定的比率時，會根據需要自動進行擴容或收縮操作。這些操作是由全局設置和具體雜湊表類型的控制函式來決定的。

`DICT_RESIZE_ENABLE` 與 `DICT_RESIZE_FORBID` 是個全域變數，去控制全局 dict 是否可以 resize，而使用 `dictTypeResizeAllowed()`，則是更細緻的控制，根據具體的 dictType 的 `resizeAllowed()` 再次判斷此雜湊表是否可以擴容

**擴容（Expand）**
雜湊表會在兩個條件觸發擴容
- 當元素數量與儲存桶的比率（元素數量 / 桶數量），且雜湊表的元素數量 (`d->ht_used[0]`) 大於等於當前桶數的大小 (`DICTHT_SIZE(d->ht_size_exp[0]`)，則觸發擴容。
- 即使 DICT_RESIZE_FORBID（禁止擴容），但元素數量超過 `dict_force_resize_ratio` (預設是 4) 倍的桶數時，仍會觸發擴容。

程式邏輯如下：

// int dictExpandIfNeeded(dict* d)
if ((dict_can_resize == DICT_RESIZE_ENABLE && d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||
    (dict_can_resize != DICT_RESIZE_FORBID &&
     d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0]))) {
    if (dictTypeResizeAllowed(d, d->ht_used[0] + 1)) dictExpand(d, d->ht_used[0] + 1);
    return DICT_OK;
}

補充相關:
- `DICTHT_SIZE(exp)` 巨集計算桶的大小，根據 exp 的值，返回 2 的 exp 次方作為桶的數量。若 exp 為 -1，則返回 0
- `dict_can_resize` 預設為 `DICT_RESIZE_ENABLE`，表示允許擴容。

**收縮(Shrink)**
觸發收縮條件：

- 收縮則是當雜湊表的負載因子過低 (1/8)時觸發：
- 即使禁止擴容，但元素數量與桶數的比率 達 1/32 下限，仍會觸發收縮

// int dictShrinkIfNeeded(dict* d)

if ((dict_can_resize == DICT_RESIZE_ENABLE &&
     d->ht_used[0] * HASHTABLE_MIN_FILL <= DICTHT_SIZE(d->ht_size_exp[0])) ||
    (dict_can_resize != DICT_RESIZE_FORBID &&
     d->ht_used[0] * HASHTABLE_MIN_FILL * dict_force_resize_ratio <= DICTHT_SIZE(d->ht_size_exp[0]))) {
    if (dictTypeResizeAllowed(d, d->ht_used[0])) dictShrink(d, d->ht_used[0]);
    return DICT_OK;
}

相關補充
- `#define HASHTABLE_MIN_FILL 8`
- `static unsigned int dict_force_resize_ratio = 4`

### rehashing 的步驟 (`dictShrink` 還有 `dictExpand`)

**rehasing**
當要做擴容還是收縮時,需要創建新的雜湊表，這導致雜湊表的 size 和 sizemask 變化，而 key 的查詢與 sizemask 有關，因此此時必須對對雜湊表中的每一個 key 重新計算索引，插入新的雜湊表。rehash 指的是重新插入值到新雜湊表的整個過程。

**Incremental rehahsing**
避免確保 rehashing 阻塞主執行緒太長時間，每次字典訪問(包括查找、插入、刪除)都會推進 rehashing 進度，在 rehashing 期間，所有數據仍然可以被正確找到。

**在增刪查改中的 rehashing**

- 插入（dictAdd、dictReplace）：新的鍵值對總是直接插入到 `dict.ht[1]` 中。這確保了 `ht[0]` 只會縮小並最終變為空。
- 尋找、修改和刪除（dictFind、dictDelete）：這些操作必須同時檢查 `dict.ht[0]` 和 `dict.ht[1]`。它們首先嘗試在 `dict.ht[0]` 中尋找鍵。如果在那裡找不到，則檢查 `dict.ht[1]`。這保證了資料的一致性，因為在 rehash 期間，鍵可能駐留在任一表中。

**rehash 的處理過程是這樣的: (`dictResizeWithOptionalCheck`)**
1. 計算新雜湊表的大小(newsize)，值取決於目前要做的是擴容還是收縮:
- 如果是擴容，則 newsize 為第一個大於等於 `ht[0].used+1` 的 $2^n$
- 如果收縮， newsize 是大於或等於 `ht[0].used` 的 2 的最小冪（最小大小為 4，以防止表過小）。
2. 依照 newsize 申請記憶體空間，建立 new_ht_table ,並賦值給`dict.ht[1]`
3. 設定`dict.rehashidx = 0`，標示開始 rehash。(This rehashidx acts as a pointer, indicating the next bucket in ht[0] to be rehashing)
<!-- 將`dict.ht[0]`中的每一個 dictEntry 都 rehash 到 `dict.ht[1]` -->
4. 增量遷移 (`dictRehash(dict, n)` 函式)
- 當如果`dict.ht[0].table[rehashidx]` 的 entry 做 rehash 到 `dict.ht[1]` 後，就將 rehashidx++。直至`dict.ht[0]` 的 n 個數都 rehash 到 `dict.ct.ht[1]`
5. rehash 的收尾。將 `dict.ht[1]` 值給 `dict.ht[0]`，給 `dict.ht[1]` 初始化為空雜湊表，釋放原來的 `dict.ht[0]` 的記憶體空間
6. 將 rehashidx 賦值為 -1,代表 rehash 結束

// Performs N steps of incremental rehashing. 
int dictRehash(dict *d, int n) {
    // Perform incremental rehash
    while (n-- && d->ht_used[0] != 0) {
        while (d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        /* Move all the keys in this bucket from the old to the new hash HT */
        rehashEntriesInBucketAtIndex(d, d->rehashidx);
        d->rehashidx++;
    }
    return !dictCheckRehashingCompleted(d);

- `rehashEntriesInBucketAtIndex()` 將指定桶（`ht[0][d->rehashidx]`）中的所有 dictEntry 從舊雜湊表搬遷到新雜湊表

當所有元素都完成搬遷後，`dictCheckRehashingCompleted()` 會檢查 `ht[0]` 是否已經空了，並將 `ht[1]` 賦值給 `ht[0]`，ht[1] 清空，並設 `d->rehashidx = -1;`，表示完成 reahsing 過程。

:::success
疑問: mt-redis 怎麼處理 rehashing?

這問題需要先看他的資料結構

typedef struct q_dictEntry {
    unsigned type:4;   // four data structure types: string, list, set, zset and hash
    void *key;
    union {
        void *val;
        int64_t s64;
    } v;
    struct cds_lfht_node node;
    struct rcu_head rcu_head;
} q_dictEntry;

typedef struct q_dict {
    unsigned int size;
    struct cds_lfht *table;
    void *privdata;
} q_dict;

typedef struct q_dictIterator {
    q_dict *d;
    struct cds_lfht_iter iter;
} q_dictIterator;

在 q_dict 中沒有 `ht_table[2]`，在 mt-redis 中的 q_dict 中的 lock-free hash table 本身就支持動態調整大小，不需要像傳統 dict 那樣進行手動的 incremental rehashing。

調用 `#include <urcu/rculfhash.h>`，使用 cds (Concurrent Data Structures) 的 API

rculfhash 的介紹
> Lock-Free Resizable RCU Hash Table. RCU used to provide existence guarantees. Provides scalable updates, and scalable RCU read-side lookups and traversals.
> Unique and duplicate keys are supported. Provides "uniquify add" and "replace add" operations, along with associated read-side traversal uniqueness guarantees. Automatic hash table resize based on number of elements is supported. See the API for more details.
:::

### 新增 element 到雜湊表之中
`dictAdd()` 流程圖

dictAdd(dict, key, val)
│
├──▶ dictAddRaw(dict, key, NULL)
│     │
│     ├──▶ dictFindPositionForInsert() → 找插入位置（或發現 key 已存在），其中會討論是否擴容
│     ├──▶ dictType->keyDup()（若有）→ 複製 key
│     └──▶ dictInsertAtPosition() → 插入 dictEntry
│
├──▶ dictSetVal() → 設定 value（這 hashTable 非 set）
└──▶ return DICT_OK

**`void *dictFindPositionForInsert(dict *d, const void *key, dictEntry **existing)`**
(dictAddRaw 中賦值給 exisiting 值是 NULL)

> dictFindPositionForInsert 用來計算 key 的雜湊值，並返回要插入的位置（如果該位置已經有相同的 key，則返回 NULL 並填充 existing 變數）。

具體操作:
1. 計算 key 的雜湊值 (`hash`)，後得 idx，idx 是新元素在雜湊表(dict 中 ht0)的位置

    uint64_t hash = dictHashKey(d, key);
    idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);

2. 判斷是否正在 rehashing，就著就判斷
- 如果當前操作碰巧存取了 `ht[0]` 中一個還沒被 rehash 的 butcket (`idx >= d->rehashidx` 並且 `ht_table[0][idx] 不為空）`)，那就 就將透過 `dictBucketRehash()` 在同一個 bucket 中做 rehashing
- 否則，透過 ` dictRehashStep(d)` 將 rehash 所有的 buckets。(如果 ht0 中沒有有效位置，則需要在全表範圍內繼續進行桶的重新雜湊，這部分見 `dictRehash(d, 1)`)

    if (dictIsRehashing(d)) {
        if ((long)idx >= d->rehashidx && d->ht_table[0][idx]) {
            dictBucketRehash(d, idx);
        } else {
            dictRehashStep(d);
        }
    }

- dictIsRehashing(d) 用來檢查是否正在進行雜湊表的擴展或收縮過程。

:::success
Q: valkey 只有是單執行緒 ，為甚麼還需要判斷是否有正在進行 rehashing?
A: 因為是 incremental rehashing，這允許 Valkey 不因為雜湊表大小變化造成了阻塞，藉由逐步完成數據的遷移，確保了高響應性和可用性
:::

3. 遍歷兩張雜湊表（`ht_table[0]` 和 `ht_table[1]`）來檢查 idx 位置是否已經有該 key。如果已經有，則返回 NULL，並且可以填充 existing，指向原有的 dictEntry。

    dictExpandIfAutoResizeAllowed(d);
    for (table = 0; table <= 1; table++) {
        if (table == 0 && (long)idx < d->rehashidx) continue;
        idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        /* Search if this slot does not already contain the given key */
        he = d->ht_table[table][idx];
        while (he) {
            void *he_key = dictGetKey(he);
            if (key == he_key || dictCompareKeys(d, key, he_key)) {
                if (existing) *existing = he;
                return NULL;
            }
            he = dictGetNext(he);
        }

- dictCompareKeys() : 檢查計算出的位置是否已有相同的鍵
4. 返回插入的位置
若無相同的 key，則返回該位置（`bucket`）

    dictEntry **bucket = &d->ht_table[dictIsRehashing(d) ? 1 : 0][idx];
    return bucket;

**`dictEntry *dictInsertAtPosition(dict *d, void *key, void *position)`**
<!-- position 是 bucket。 entry 是? -->
1. htidx 決定 element 是要插入到哪一個表裡，如果正在進行 rehashing，則元素插入到 `ht_table[1]` 中，否則插入到 `ht_table[0]` 中

// dictEntry *dictInsertAtPosition(dict *d, void *key, void *position) {
    int htidx = dictIsRehashing(d) ? 1 : 0;

2. 創建 entryEntry (`entry`) 之後，就插入到 bucket 位置，並更新該表的元素數量。

    *bucket = entry;
    d->ht_used[htidx]++;

**dictSetVal**
會根據 dictEntry 類型（嵌入式或普通型）來設置對應的值

void dictSetVal(dict *d, dictEntry *de, void *val) {
    DICT_SET_VALUE(de, v.val, val);
}

#define DICT_SET_VALUE(de, field, val)      
        if (entryIsNormal(de)) {                              \
            dictEntryNormal *_de = decodeEntryNormal(de);     \
            _de->field = val; 

static inline void *decodeMaskedPtr(const dictEntry *de) {
    return (void *)((uintptr_t)(void *)de & ~ENTRY_PTR_MASK);
}
// #define ENTRY_PTR_MASK 7     /* 111 */

所以 dictSetVal 等於是 (void*)(de & 111)->v.val = val
(v 是指 structEntry 中型別為 union 的成員)

#### dictFind
流程圖

dictFind(d, key)
│
├──▶ dictSize(d) == 0? --> 是 -> 返回 NULL
│
├──▶ dictHashKey(d, key) --> 計算雜湊值 h
│
├──▶ idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[0]) --> 計算雜湊索引
│
├──▶ dictIsRehashing(d)? --> 是
│     ├──▶ 是否處理正在重雜湊的槽位 -> 如果有，則進行 `dictBucketRehash(d, idx)`
│     └──▶ 否 -> 進行 incremental rehash -> `dictRehashStep(d)`
│
├──▶ 遍歷 `ht_table[0]` 和 `ht_table[1]`：
│     ├──▶ 找到該槽位的 `dictEntry`，若是 linked list，則遍歷 `dictEntry`
│     ├──▶ 若找到匹配的 key，返回對應的 `dictEntry`
│     └──▶ 若無匹配，繼續下一個槽位或表格
│
└──▶ 最終若未找到，返回 NULL

#### dictDelete

dictDelete(dict, key)
│
├──▶ dictSize(d) == 0? --> 是 → 返回 NULL（字典為空）
│
├──▶ 計算 key 的雜湊值 (h = dictHashKey(d, key))
│
├──▶ dictIsRehashing(d)? --> 是
│     ├──▶ idx >= rehashidx 且 ht_table[0][idx] 存在 → 在新表 (ht[1]) 中查找並刪除
│     └──▶ 否 → 調用 dictRehashStep(d) 進行增量 rehashing
│
├──▶ 遍歷 `ht[0]` 和 `ht[1]` 查找目標 key
│     ├──▶ 找到 key，調用 dictDeleteEntry(d, he, idx) 刪除該元素
│     └──▶ 未找到，繼續查找或返回 NULL
│
└──▶ 返回刪除結果

#### 討論 dict.c 是否合適加入 RCU 以提升並行化層度?
RCU 適用於讀多寫少的場景，但仔細閱讀 dict 的API 實做後發現不適合的幾點：
- `dictRehash`：這涉及到雜湊表擴展，會改變雜湊表的結構
- `dictAdd`、`dictDelete`：這是對字典進行插入、刪除操作的方法，會修改雜湊表，過程中會 incremental rehash
- `dictFind`：這是查找操作，並不會直接修改資料，但過程中也會 做 incremental rehash

因此對於 RCU 加入此核心的雜湊資料結構，並不適合。

然而可考慮如 mt-redis 一般，使用 lock-free hash table API，不需要實作 incremental rehash。

## hashtable.c
valkey 8.1 引入的新的雜湊表，因為發現舊有的 dict.c 實作有幾點缺點，例如如為了查找鍵值 "FOO" 並存取其值"BAR"，這仍然需要從記憶體中讀取四次。如果發生雜湊衝突，它必須針對每次 collision 額外追蹤另外兩個指針，因此需要從記憶體中多讀取兩次（鍵值和下一個指針）。 <!-- 補 dict collision 的處理過程-->

hashtable.c 的設計
table 不再是指向 dictEntry 而是 bucket。
當 bucket 較滿，使用 bucket chain 方式去擴展，也就是最後一個元素的 slot 將替換成指向 child bucket 的指針。

struct hashtable {
    hashtableType *type;
    ssize_t rehash_idx;        /* -1 = rehashing not in progress. */
    bucket *tables[2];         /* 0 = main table, 1 = rehashing target.  */
    size_t used[2];            /* Number of entries in each table. */
    int8_t bucket_exp[2];      /* Exponent for num buckets (num = 1 << exp). */
    int16_t pause_rehash;      /* Non-zero = rehashing is paused */
    // ...
};


在同一個 Bucket 或 Bucket Chain 的元素沒有做內部排序。當新 entry 要插入 buckt 時，可以使用任何空閒 slot。

#define ENTRIES_PER_BUCKET 12
#define BUCKET_BITS_TYPE uint16_t

typedef struct hashtableBucket {
    BUCKET_BITS_TYPE chained : 1;
    BUCKET_BITS_TYPE presence : ENTRIES_PER_BUCKET;
    uint8_t hashes[ENTRIES_PER_BUCKET];
    void *entries[ENTRIES_PER_BUCKET];
} bucket;

bucket 模樣，其中的 meta 區域 (chain, presence 與 hashes) 大約 14 Bytes。 (32系統、64系統)
`chained` 使用 bit field 的寫法表示只佔 1 Bit。表示是否有接 child bucket。`present` 表示在 Bucket 中每一個 slot 是否是有值的。`chain` 與 `present` 佔 2 Bytes。`hashes` 為每一個 entry 的 secondary hash，當 hash collision 發生會用上的成員。

64-bit version, 7 entries per bucket:
1 bit 7 bits [1 byte] x 7 [8 bytes] x 7 = 64 bytes
chained presence hashes entries

32-bit version, 12 entries per bucket:
1 bit 12 bits 3 bits [1 byte] x 12 2 bytes [4 bytes] x 12 = 64 bytes
chained presence unused hashes unused entries

### 如果發生 hash collision
Bucket Chaining
## Strings
字串 (String)
實作檔案: `src/t_string.c`
<!-- 物件定義: `src/object.c` -->
實作檔案: `src/sds.c`, `src/sds.c`

字串存儲位元組序列，包括文本、serialized objects 和二進位陣列。字串通常用於緩存，但它們支援其他功能，這些功能**允許實現計數器並執行 bitwise 運算**。

### C 的字串的問題
舉例:

char *s = "hello";

1. 獲得字串長度需要運算 (算到 `\0`)
2. 非二進位安全 (不可以出現 `\0` 等特殊字元在字串中)
3. 不可修改

## SDS 特色
1. **二進位安全 (Binary Safe)**：SDS 字串可以包含任意位元組，包括 `\0` 字元，因為其長度是明確儲存在字串頭部
2. **自動擴容 (Automatic Resizing)**：當進行追加操作時，如果現有緩衝區空間不足，SDS 會自動擴大緩衝區，並且會預分配額外的空間 (貪婪模式，`SDS_MAX_PREALLOC`) 以減少頻繁的重新分配
3. **相容 C 字串 (C String Compatible)**：SDS 字串**始終以 `\0` 終止**，這使得它可以直接傳遞給需要 C 字串的函式 (例如 `printf()`)

## valkey 中 set command 看見與 sds 的關係

robj *createStringObject(const char *ptr, size_t len) {
    // if len > OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createRawStringObject(ptr, len);
}

robj *createRawStringObject(const char *ptr, size_t len) {
    return createObject(OBJ_STRING, sdsnewlen(ptr, len));
}

`sdsnewlen()` 將創建一個全新的 SDS 實例並初始化其內容

## simple dynamic string (SDS)
支援五種 sdshdr 種類:
sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64
(sdshdr5 不再使用)

以 sdshrd8 的結構體為例:

struct __attribute__ ((__packed__)) sdshrd8 {
	uint8_t len;
	uint8_t alloc; 
	unsigned char flags; 
	char buf[];
}

`__attribute__((__packed__))`使結構中沒有額外的填充位元組。

header 包含三個成員:
- len 表示 buf 保存的字串長度。
- alloc 為 buf 總長度，不包含 header 與 \0 結尾。
- flag 表示 SDS 的類型，flags 是用來控制 SDS 的 header 大小 。

flag 有以下類型:
<!-- `SDS_TYPE_5`: 用於短字串 (長度小於 32 個字元)。長度和類型資訊都儲存在一個 `unsigned char` 中。這種 header 不包含 `alloc` 資訊-->
- `SDS_TYPE_8`: 用於長度小於 256 個字元的字串。
- `SDS_TYPE_16`: 用於長度小於 216 個字元的字串。
- `SDS_TYPE_32`: 用於長度小於 232 個字元的字串。
- `SDS_TYPE_64`: 用於長度小於 264 個字元的字串。

buf 為一個字元陣列。這個字元數組的長度等於最大容量 +1。真正有效的字串長度通常小於最大容量。因此在真正的字串資料之後會有 '\0' 字元與若有空餘其未用的位元組，這允許在不重新分配記憶體的前提下，讓字串資料向後做有限的擴展。

### sdsnewlen 看到返回 buf 的開頭位置
sdsnewlen()（以及其他所有返回 sds 型別的函式，如 sdscat、sdsdup 等）返回的 sds 都不是返回 sdshdr 的開頭，而是 buf 開頭位置。

typedef char *sds;

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * The string is always null-terminated (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    // ...
    return sdswrite(sh, bufsize, type, init, initlen);
}

/* Writes an sds with type `type` into a buffer `buf` of size `bufsize`. Returns
 * an sds handle to the string within the buffer. Use `sdsReqType(length)` to
 * compute the type and `sdsReqSize(length, type)` to compute the required
 * buffer size. You can use a larger `bufsize` than required, but usable size
 * can't be greater than `sdsTypeMaxSize(type)`. */
sds sdswrite(char *buf, size_t bufsize, char type, const char *init, size_t initlen) {
    assert(bufsize >= sdsReqSize(initlen, type));
    int hdrlen = sdsHdrSize(type);
    size_t usable = bufsize - hdrlen - 1;
    sds s = buf + hdrlen;
    unsigned char *fp = ((unsigned char *)s) - 1; /* flags pointer. */

    switch (type) {
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8, s);
            sh->len = initlen;
            assert(usable <= sdsTypeMaxSize(type));
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (init == SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(s, 0, initlen);
    if (initlen && init) memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

`sdsnew()` 設計成讓 sds 指向字串數據 (`buf`)的開頭，這樣才能與 C 語言的 char* 習慣所對齊。

因此 sds 能如 C 字串的能直接讀取。

sds my_string = sdsnew("hello");
char *content = my_string; 
printf("%s\n", content);

而讀取 sds 的 header 會以 `s[-1]` 取 flag 或 `SDS_HDR` 巨集取得 header 的開頭位置。

#define SDS_HDR(T, s) ((struct sdshdr##T *)((s) - (sizeof(struct sdshdr##T))))

`sizeof(struct sdshdr##T)` 會計算出對應類型 T 的 SDS header （len, alloc, flags） 的總大小

<!--  -->

### sds 具備動態擴容的功能
sds 分成貪婪與非貪婪模式，
前者根據是新增的字串長度新增並保有預留空間。後者為指擴容成剛剛好的大小。

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    // ...
    size_t avail = sdsavail(s);
    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;
    
    // get the size of header
    hdrlen = sdsHdrSize(type); 
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }
    // ...
    use_realloc = (oldtype == type);
    if (use_realloc) {
        // new header doesn't change
        newsh = s_realloc_usable(sh, hdrlen + newlen + 1, &bufsize);
        // ...
    } else {
        newsh = s_malloc_usable(hdrlen + newlen + 1, &bufsize);
        // ...
    }

- 如果新字串大小小於 1MB (`SDS_MAX_PREALLOC = 1024 * 1024` )，新空間可擴成字串長度的兩倍 + 1。
- 如果新字串大小大於 1M，新空間可擴成字串長度 + 1M + 1，採用一個較為保守的預分配策略。

見程式中的 `if (use_realloc)` 是處理的是當 SDS 擴展時，新計算出的 SDS 類型 (type) 與原始 SDS 的類型 (oldtype) 相同 的情況。這意味著 SDS header 的結構不變，因此用 s_relloc_usable() 擴展現有記憶體。然而 type 與 oldtype 不相同時，則表示 header 結構有變化，不能簡單使用 realloc，需要使用 malloc 進行重新分配並複製。

### SDS 的惰性空間釋放機制
sdsclear() 函式將字串長度設為 0，但不釋放已分配的記憶體，而是將其保留為可用空間，以便後續的追加操作就不需要重新分配記憶體

void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

新增內容的函式 (如 `sdscatlen()`) 在寫入 buf 之前，會呼叫 `sdsMakeRoomFor`

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

在 sdsMakeRoomFor() 中，我們就可以看到記憶體重用機制。

if (avail >= addlen) return s;

當可用空間 (`sdsavail(s)`) 大於等於新增的長度 (`addlen`)，那就直接返回原 SDS (`s`)，不進行任何記憶體分配。

然而也有主動釋放記憶體的強況，如 `trimStringObjectIfNeeded()` 中能看到當可用空間超過字串長度 10% 時會調用顯性空間釋放的 `sdsRemoveFreeSpace()` 來釋放多餘空間。

`sdsRemoveFreeSpace()` 會移除多餘的可用空間，保留原本內容，返回一個新的 SDS 指針，原指針將失效。

/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s, int would_regrow) {
    return sdsResize(s, sdslen(s), would_regrow);
}

void trimStringObjectIfNeeded(robj *o, int trim_small_values) {
    if (o->encoding != OBJ_ENCODING_RAW) return;
    /* A string may have free space in the following cases:
     * 1. When an arg len is greater than PROTO_MBULK_BIG_ARG the query buffer may be used directly as the SDS string.
     * 2. When utilizing the argument caching mechanism in Lua.
     * 3. When calling from RM_TrimStringAllocation (trim_small_values is true). */
    size_t len = sdslen(o->ptr);
    if (len >= PROTO_MBULK_BIG_ARG || trim_small_values ||
        (server.executing_client && server.executing_client->flag.script && len < LUA_CMD_OBJCACHE_MAX_LEN)) {
        if (sdsavail(o->ptr) > len / 10) {
            o->ptr = sdsRemoveFreeSpace(o->ptr, 0);
        }
    }
}

或是當客戶查詢的緩衝空間中，系統檢查有超過 4KB 的可用空間，並且客戶端閒置超過 2 秒沒有處理資料，即會使用 `sdsRemoveFreeSpace()` 釋放多餘空間。

/* The client query buffer is an sds.c string that can end with a lot of
 * free space not used, this function reclaims space if needed.
 */
int clientsCronResizeQueryBuffer(client *c) {
        /* Only resize the query buffer if the buffer is actually wasting at least a
     * few kbytes */
    if (sdsavail(c->querybuf) > 1024 * 4) {
        /* There are two conditions to resize the query buffer: */
        if (idletime > 2) {
            /* 1) Query is idle for a long time. */
            size_t remaining = sdslen(c->querybuf) - c->qb_pos;
            if (!c->flag.primary && !remaining) {
                /* If the client is not a primary and no data is pending,
                 * The client can safely use the shared query buffer in the next read - free the client's querybuf. */
                sdsfree(c->querybuf);
                /* By setting the querybuf to NULL, the client will use the shared query buffer in the next read.
                 * We don't move the client to the shared query buffer immediately, because if we allocated a private
                 * query buffer for the client, it's likely that the client will use it again soon. */
                c->querybuf = NULL;
            } else {
                c->querybuf = sdsRemoveFreeSpace(c->querybuf, 1);
            }

`sdsFree()` 是調用 zfree_with_size，完全釋放整個 SDS 字串的記憶體，包括 header 和 buffer，之後該 SDS 指針就不能再使用了

### 討論 sds 是否合適加入 RCU 以提升並行化程度?

## Lists
Lists are lists of strings sorted by insertion order.

實作檔案: `src/t_list.c`
底層結構: `src/quicklist.c` , `src/listpack.c`
當 listpack 過大時，會轉換為 quicklist

關於 zliplist:
能在 sever.h 能看到註解寫 No longer used: old list/hash/zset encoding.
目前 valkey 使用 ziplist ，僅用於載入舊 RDB 檔案時實現向後相容
### listpack

typedef struct {
	unsigned char *sval;
	uint32_t slen;
	long long lval;
} listpackEntry;

- `unsigned char *sval;`: 如果元素是一個字串，`sval` 指向其內容。
- `uint32_t slen;`: 如果元素是一個字串，`slen` 是其長度。
- `long long lval;`: 如果元素是一個整數，`lval` 存儲其值。
- 在實際使用時，`sval` 和 `lval` 只有一個會被設置，另一個為 `NULL` 或不相關。

### quicklist

quicklist 是 linked list + ziplist
結構示意圖：
`[head] ⇄ [ziplist1] ⇄ [ziplist2] ⇄ [ziplist3] ⇄ [tail]`

每個 `ziplistX` 都是一塊小型的 ziplist 記憶體區塊
#### 與 quicklist 相關的四個 strcut

quicklist 是容器，quicklistNode 是節點，quicklistIter 提供遍歷能力，quicklistEntry 封裝元素訊息

quicklist  
├── head ──→ quicklistNode ──→ quicklistNode ──→ ... ──→ tail  
│                │                   │  
│                └── entry (listpack) └── entry (listpack)  
│  
└── quicklistIter ──→ current (指向某個 quicklistNode)  
                      │  
                      └── quicklistEntry (當前元素訊息)

主要容器

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;                  /* total count of all entries in all listpacks */
    unsigned long len;                    /* number of quicklistNodes */
    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count : QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

指向一個 listpack，有指向前後指標是為了正反遍歷

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;  //  stores actual data (listpack or plain data)
    size_t sz;                           /* entry size in bytes */
    unsigned int count : 16;             /* count of items in listpack */
    unsigned int encoding : 2;           /* RAW==1 or LZF==2 */
} quicklistNode;

quicklistIter 提供遍歷能力

typedef struct quicklistIter {
    quicklist *quicklist;
    quicklistNode *current;
    unsigned char *zi; /* points to the current element */
    long offset;       /* offset in current listpack */
    int direction;
} quicklistIter;

quicklistEntry 是提供當前元素訊息

typedef struct quicklistEntry {
    const quicklist *quicklist; // quicklist to which this entry belongs
    quicklistNode *node;  // quicklistNode where this entry is located
    unsigned char *zi; // pointer within listpack
    unsigned char *value; 
    long long longval;
    size_t sz;
    int offset;
} quicklistEntry;

## Sets
Sets are unordered collections of unique strings that act like the sets from your favorite programming language. With a Set, you can add, remove, and test for existence in O(1) time (in other words, regardless of the number of set elements).

集合 (Set)
實作檔案: src/t_set.c

valkey 針對不同情況，提供有三種 set，
- Intset：一種記憶體高效率的編碼方式，適用於僅包含整數的集合。使用 binary search 做搜尋。
- Listpack：一種緊湊的編碼方式，適用於小型集合。用於包含非整數值或集合規模足夠小的情況。
- Hashtable：一種更具可擴展性的編碼方式，適用於大型集合。查找時間為 O(1)。

### IntSet 概論
當 Set 中所有元素都是整數且數量不多時，Valkey 會自動選擇使用 intset 這種緊湊的資料結構來儲存，以減少記憶體開銷。

IntSet 結構定義

typedef struct intset {
    uint32_t encoding;
    uint32_t length; // the number of elements in the set
    int8_t contents[]; // store the elements of set
} intset;

Valkey 定義了三種編碼類型
intset 透過 encoding 欄位來動態調整其儲存的整數大小
分別為 16 位元, 32 位元, 64 位元 的整數

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

所有在 insert 中的元素唯一並且是升序儲存，因此查找元素時適用 binary Search， O(log N) 的時間複雜度

**inset 範例一**
假設已經插入 [16, 2, 5] 到 intset 裡:

------------------------------------------------------------------
| encoding:  INTSET_ENC_INT16 | length: 3 | contents: [2, 5, 16] |
------------------------------------------------------------------

**創建 intset (`intsetNew()`)**

/* Create an empty intset. */
intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = INTSET_ENC_INT16;
    is->length = 0;
    return is;
}

**插入元素 (`intsetAdd`)**
插入新值 (newVal)可能會有兩種情況
1. newVal 適用於目前編碼
2. 新值的大小超過目前編碼可容納的範圍，這需要做 intset 升級

情況一
1. 在 contents 做 binary search 找 newVal 的該插入的索引 (`pos`)
- 如果找到 intSet 中找到與 newVal 相同的值，就不插入，返回 NULL
2. 對 contents 做擴容 (`intsetResize()`)
3. 使用 memmove 將 contents 中 `pos` 以後的所以元素都向後移一位，之後也將 newVal 插入到 contents 中
4. 更新 length

情況二舉例
假設 intset 為 [2, 5, 16] (編碼 INTSET_ENC_INT16)，現在要插入一個 newVal = 50000。由於 50000 超過 int16_t 的範圍，intset 需要升級

升級操作: (`intsetUpgradeAndAdd`)
1. contents 的型別需改可容納 newVal (`intsetResize()`)
2. 倒序的方式將原有的值填回 content (例如 16 -> 5 -> 2)
3. 把 newVal 插入 content 最後一位
4. 把 encoding 與 length 更新成正確的值

最終，這個 intset 將會是

--------------------------------------------------------------------------
| encoding:  INTSET_ENC_INT32 | length: 4 | contents: [ 2, 5, 16, 50000] |
--------------------------------------------------------------------------

**刪除元素 (`intsetRemove`)**
從 value 從 intset 移除
1. 檢查是否需要刪除
檢查編碼之後，使用 binary Search 找到 value 的編碼位置 (`pos`)
2. 若非元素最後一值，就 pos 位置後的元素皆向前一位
3. 使用 `intsetResize(is, len - 1)` 來縮小 intset 的大小
4. 更新長度 len - 1
5. 返回更新後的 intset

**查尋元素 (intsetFind)**
1. 檢查編碼
2. 使用 binary Search 搜尋

uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is, value, NULL);
}

#### 討論 intset 是否合適加入 RCU 以提升並行化程度?

## Hashes
Hashes are record types modeled as collections of field-value pairs. As such, Hashes resemble Python dictionaries, Java HashMaps, and Ruby hashes.

雜湊表 (Hash)
實作檔案: `src/t_hash.c`

- Listpack：一種用於小型雜湊的記憶體高效編碼方式。適用於雜湊值足夠小且不包含非常大的欄位或值的情況。
- Hashtable：一種用於較大雜湊值的更具可擴展性的編碼方式。提供 O(1) 的查找時間。

## Sorted sets
Sorted Sets are collections of unique strings that maintain order by each string's associated score.

有序集合 (Sorted Set/ZSet)
實作檔案: `src/t_zset.c`

## Streams
A Stream is a data structure that acts like an append-only log. Streams help record events in the order they occur and then syndicate them for processing.

串流 (Stream)
實作檔案: `src/t_stream.c`
Listpack 編碼：適用於元素有限且值較小的小型有序集合
Skiplist 編碼：適用於較大的有序集合或超出 Listpack 閾值的情況

## Geospatial indexes
Geospatial indexes are useful for finding locations within a given geographic radius or bounding box.

## Bitmaps

## Bitfields
Bitfields efficiently encode multiple counters in a string value. Bitfields provide atomic get, set, and increment operations and support different overflow policies.

## HyperLogLog
The HyperLogLog data structures provide probabilistic estimates of the cardinality (i.e., number of elements) of large sets.

## Bloom Filter
Bloom filters are a space efficient probabilistic data structure that allows adding elements and checking if item/s are definitely not present, or if there is a possibility they exist (with the configured false positive rate).

The Bloom filter data type / command support is provided by the valkey-bloom module.