對象處理機制 · Redis 設計與實現（第一版）

# 對象處理機制 [TOC=2,3] 在 Redis 的命令中，用于對鍵（key）進行處理的命令占了很大一部分，而對于鍵所保存的值的類型（后簡稱“鍵的類型”），鍵能執行的命令又各不相同。比如說，[LPUSH](http://redis.readthedocs.org/en/latest/list/lpush.html#lpush "(in Redis 命令參考 v2.8)") 和 [LLEN](http://redis.readthedocs.org/en/latest/list/llen.html#llen "(in Redis 命令參考 v2.8)") 只能用于列表鍵，而 [SADD](http://redis.readthedocs.org/en/latest/set/sadd.html#sadd "(in Redis 命令參考 v2.8)") 和 [SRANDMEMBER](http://redis.readthedocs.org/en/latest/set/srandmember.html#srandmember "(in Redis 命令參考 v2.8)") 只能用于集合鍵，等等。另外一些命令，比如 [DEL](http://redis.readthedocs.org/en/latest/key/del.html#del "(in Redis 命令參考 v2.8)") 、 [TTL](http://redis.readthedocs.org/en/latest/key/ttl.html#ttl "(in Redis 命令參考 v2.8)") 和 [TYPE](http://redis.readthedocs.org/en/latest/key/type.html#type "(in Redis 命令參考 v2.8)") ，可以用于任何類型的鍵，但是，要正確實現這些命令，必須為不同類型的鍵設置不同的處理方式：比如說，刪除一個列表鍵和刪除一個字符串鍵的操作過程就不太一樣。以上的描述說明，Redis 必須讓每個鍵都帶有類型信息，使得程序可以檢查鍵的類型，并為它選擇合適的處理方式。另外，在前面介紹各個底層數據結構時有提到，Redis 的每一種數據類型，比如字符串、列表、有序集，它們都擁有不只一種底層實現（Redis 內部稱之為編碼，encoding），這說明，每當對某種數據類型的鍵進行操作時，程序都必須根據鍵所采取的編碼，進行不同的操作。比如說，集合類型就可以由字典和整數集合兩種不同的數據結構實現，但是，當用戶執行 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 命令時，他/她應該不必關心集合使用的是什么編碼，只要 Redis 能按照 [ZADD](http://redis.readthedocs.org/en/latest/sorted_set/zadd.html#zadd "(in Redis 命令參考 v2.8)") 命令的指示，將新元素添加到集合就可以了。這說明，操作數據類型的命令除了要對鍵的類型進行檢查之外，還需要根據數據類型的不同編碼進行多態處理。為了解決以上問題，Redis 構建了自己的類型系統，這個系統的主要功能包括： - `redisObject` 對象。 - 基于 `redisObject` 對象的類型檢查。 - 基于 `redisObject` 對象的顯式多態函數。 - 對 `redisObject` 進行分配、共享和銷毀的機制。以下小節將分別介紹類型系統的這幾個方面。 Note 因為 C 并不是面向對象語言，這里將 `redisObject` 稱呼為對象一是為了講述的方便，二是希望通過模仿 OOP 的常用術語，讓這里的內容更容易被理解，`redisObject` 實際上是只是一個結構類型。 ### redisObject 數據結構，以及 Redis 的數據類型 `redisObject` 是 Redis 類型系統的核心，數據庫中的每個鍵、值，以及 Redis 本身處理的參數，都表示為這種數據類型。 `redisObject` 的定義位于 `redis.h` ： ~~~ /* * Redis 對象 */ typedef struct redisObject { // 類型 unsigned type:4; // 對齊位 unsigned notused:2; // 編碼方式 unsigned encoding:4; // LRU 時間（相對于 server.lruclock） unsigned lru:22; // 引用計數 int refcount; // 指向對象的值 void *ptr; } robj; ~~~ `type` 、 `encoding` 和 `ptr` 是最重要的三個屬性。 `type` 記錄了對象所保存的值的類型，它的值可能是以下常量的其中一個（定義位于 `redis.h`）： ~~~ /* * 對象類型 */ #define REDIS_STRING 0 // 字符串 #define REDIS_LIST 1 // 列表 #define REDIS_SET 2 // 集合 #define REDIS_ZSET 3 // 有序集 #define REDIS_HASH 4 // 哈希表 ~~~ `encoding` 記錄了對象所保存的值的編碼，它的值可能是以下常量的其中一個（定義位于 `redis.h`）： ~~~ /* * 對象編碼 */ #define REDIS_ENCODING_RAW 0 // 編碼為字符串 #define REDIS_ENCODING_INT 1 // 編碼為整數 #define REDIS_ENCODING_HT 2 // 編碼為哈希表 #define REDIS_ENCODING_ZIPMAP 3 // 編碼為 zipmap #define REDIS_ENCODING_LINKEDLIST 4 // 編碼為雙端鏈表 #define REDIS_ENCODING_ZIPLIST 5 // 編碼為壓縮列表 #define REDIS_ENCODING_INTSET 6 // 編碼為整數集合 #define REDIS_ENCODING_SKIPLIST 7 // 編碼為跳躍表 ~~~ `ptr` 是一個指針，指向實際保存值的數據結構，這個數據結構由 `type` 屬性和 `encoding` 屬性決定。舉個例子，如果一個 `redisObject` 的 `type` 屬性為 `REDIS_LIST` ， `encoding` 屬性為 `REDIS_ENCODING_LINKEDLIST` ，那么這個對象就是一個 Redis 列表，它的值保存在一個雙端鏈表內，而 `ptr` 指針就指向這個雙端鏈表；另一方面，如果一個 `redisObject` 的 `type` 屬性為 `REDIS_HASH` ， `encoding` 屬性為 `REDIS_ENCODING_ZIPMAP` ，那么這個對象就是一個 Redis 哈希表，它的值保存在一個 `zipmap` 里，而 `ptr` 指針就指向這個 `zipmap` ；諸如此類。下圖展示了 `redisObject` 、Redis 所有數據類型、以及 Redis 所有編碼方式（底層實現）三者之間的關系： ![digraph datatype { rankdir=LR; node[shape=plaintext, style = filled]; edge [style = bold]; // obj redisObject [label="redisObject", fillcolor = "#A8E270"]; // type node [fillcolor = "#95BBE3"]; REDIS_STRING [label="字符串\nREDIS_STRING"]; REDIS_LIST [label="列表\nREDIS_LIST"]; REDIS_SET [label="集合\nREDIS_SET"]; REDIS_ZSET [label="有序集合\nREDIS_ZSET"]; REDIS_HASH [label="哈希表\nREDIS_HASH"]; // encoding node [fillcolor = "#FADCAD"]; REDIS_ENCODING_RAW [label="字符串\nREDIS_ENCODING_RAW"]; REDIS_ENCODING_INT [label="整數\nREDIS_ENCODING_INT"]; REDIS_ENCODING_HT [label="字典\nREDIS_ENCODING_HT"]; //REDIS_ENCODING_ZIPMAP [label="zipmap\nREDIS_ENCODING_ZIPMAP"]; REDIS_ENCODING_LINKEDLIST [label="雙端鏈表\nREDIS_ENCODING_LINKEDLIST"]; REDIS_ENCODING_ZIPLIST [label="壓縮列表\nREDIS_ENCODING_ZIPLIST"]; REDIS_ENCODING_INTSET [label="整數集合\nREDIS_ENCODING_INTSET"]; REDIS_ENCODING_SKIPLIST [label="跳躍表\nREDIS_ENCODING_SKIPLIST"]; // edge redisObject -> REDIS_STRING; redisObject -> REDIS_LIST; redisObject -> REDIS_SET; redisObject -> REDIS_ZSET; redisObject -> REDIS_HASH; REDIS_STRING -> REDIS_ENCODING_RAW; REDIS_STRING -> REDIS_ENCODING_INT; REDIS_LIST -> REDIS_ENCODING_LINKEDLIST; REDIS_LIST -> REDIS_ENCODING_ZIPLIST; REDIS_SET -> REDIS_ENCODING_HT; REDIS_SET -> REDIS_ENCODING_INTSET; REDIS_ZSET -> REDIS_ENCODING_SKIPLIST; REDIS_ZSET -> REDIS_ENCODING_ZIPLIST; REDIS_HASH -> REDIS_ENCODING_HT; REDIS_HASH -> REDIS_ENCODING_ZIPLIST;}](https://box.kancloud.cn/2015-09-13_55f4effc4b3c6.svg) 這個圖展示了 Redis 各種數據類型，以及它們的編碼方式。 Note `REDIS_ENCODING_ZIPMAP` 沒有出現在圖中，因為從 Redis 2.6 開始，它不再是任何數據類型的底層結構。 ### 命令的類型檢查和多態有了 `redisObject` 結構的存在，在執行處理數據類型的命令時，進行類型檢查和對編碼進行多態操作就簡單得多了。當執行一個處理數據類型的命令時，Redis 執行以下步驟： 1. 根據給定 `key` ，在數據庫字典中查找和它相對應的 `redisObject` ，如果沒找到，就返回 `NULL` 。 1. 檢查 `redisObject` 的 `type` 屬性和執行命令所需的類型是否相符，如果不相符，返回類型錯誤。 1. 根據 `redisObject` 的 `encoding` 屬性所指定的編碼，選擇合適的操作函數來處理底層的數據結構。 1. 返回數據結構的操作結果作為命令的返回值。作為例子，以下展示了對鍵 `key` 執行 `LPOP` 命令的完整過程： ![digraph command_poly { node [shape=plaintext, style = filled]; edge [style = bold]; lpop [label="LPOP key", fillcolor = "#A8E270"]; get_key_obj_from_db [label="Redis 從數據庫中查找 key \n對應的 redisObject 結構"]; is_obj_nil_or_not [label="數據庫返回 NULL ？",shape=diamond, fillcolor = "#95BBE3"]; return_nil [label="key 不存在\n返回空回復"]; is_type_list_or_not [label="redisObject 的類型為\nREDIS_LIST ？",shape=diamond, fillcolor = "#95BBE3"]; call_poly_pop_function [label="調用多態 pop 函數", shape=diamond, fillcolor = "#95BBE3"]; return_type_error [label="key 不是列表\n返回類型錯誤"]; pop_from_ziplist [label="從 ziplist 中彈出最左節點"]; pop_from_linkedlist [label="從雙端鏈表中彈出最左節點"]; return_pop_item [label="返回被彈出的元素"]; // edge lpop -> get_key_obj_from_db; get_key_obj_from_db -> is_obj_nil_or_not; is_obj_nil_or_not -> return_nil [label="是"]; is_obj_nil_or_not -> is_type_list_or_not [label="否"]; is_type_list_or_not -> call_poly_pop_function [label="是"]; is_type_list_or_not -> return_type_error [label="否"]; call_poly_pop_function -> pop_from_ziplist [label="對象的編碼為\nZIPLIST"]; call_poly_pop_function -> pop_from_linkedlist [label="對象的編碼為\nLINKEDLIST"]; pop_from_ziplist -> return_pop_item; pop_from_linkedlist -> return_pop_item;}](https://box.kancloud.cn/2015-09-13_55f4effc53e50.svg) ### 對象共享有一些對象在 Redis 中非常常見，比如命令的返回值 `OK` 、 `ERROR` 、 `WRONGTYPE` 等字符，另外，一些小范圍的整數，比如個位、十位、百位的整數都非常常見。為了利用這種常見情況，Redis 在內部使用了一個 [Flyweight 模式](http://en.wikipedia.org/wiki/Flyweight_pattern) ：通過預分配一些常見的值對象，并在多個數據結構之間共享這些對象，程序避免了重復分配的麻煩，也節約了一些 CPU 時間。 Redis 預分配的值對象有如下這些： - 各種命令的返回值，比如執行成功時返回的 `OK` ，執行錯誤時返回的 `ERROR` ，類型錯誤時返回的 `WRONGTYPE` ，命令入隊事務時返回的 `QUEUED` ，等等。 - 包括 `0` 在內，小于 `redis.h/REDIS_SHARED_INTEGERS` 的所有整數（`REDIS_SHARED_INTEGERS` 的默認值為 `10000`）因為命令的回復值直接返回給客戶端，所以它們的值無須進行共享；另一方面，如果某個命令的輸入值是一個小于 `REDIS_SHARED_INTEGERS` 的整數對象，那么當這個對象要被保存進數據庫時，Redis 就會釋放原來的值，并將值的指針指向共享對象。作為例子，下圖展示了三個列表，它們都帶有指向共享對象數組中某個值對象的指針： ![digraph shared_integer { // setting node [shape = record, style = filled]; edge [style = bold]; // list // list_a [label = "<head>列表A | 20130101 |<300> * | 10086 | -998 |<1024> *", fillcolor = "#A8E270"]; list_a [label = "<head>列表A | 20130101 |<300> * | 10086 ", fillcolor = "#A8E270"]; list_b [label = "列表B |<81> * | 12345678910 |<999> *", fillcolor = "#95BBE3"]; list_c [label = "列表C |<100> * |<0> * | -25 |<123> *", fillcolor = "#FADCAD"]; sl [label = "<head>共享整數對象數組 |<0> 0 | ... |<81> 81| ... |<100> 100 |<123> 123 | ... |<300> 300 | ... |<999> 999 | ... | 10000 "]; // edge list_a:300 -> sl:300 [color="#A8E270"]; //list_a:999 -> sl:999 [color="#A8E270"]; // list_a:1024 -> sl:1024 [color="#A8E270"]; list_b:81 -> sl:81 [color="#95BBE3"]; list_b:999 -> sl:999 [color="#95BBE3"]; list_c:100 -> sl:100 [color = "#FADCAD"]; list_c:0 -> sl:0 [color = "#FADCAD"]; list_c:123 -> sl:123 [color = "#FADCAD"];}](https://box.kancloud.cn/2015-09-13_55f4effc5dd04.svg) 三個列表的值分別為： - 列表 A ： `[20130101, 300, 10086]` ， - 列表 B ： `[81, 12345678910, 999]` ， - 列表 C ： `[100, 0, -25, 123]` 。 Note 共享對象只能被帶指針的數據結構使用。需要提醒的一點是，共享對象只能被字典和雙端鏈表這類能帶有指針的數據結構使用。像整數集合和壓縮列表這些只能保存字符串、整數等字面值的內存數據結構，就不能使用共享對象。 ### 引用計數以及對象的銷毀當將 `redisObject` 用作數據庫的鍵或者值，而不是用來儲存參數時，對象的生命期是非常長的，因為 C 語言本身沒有自動釋放內存的相關機制，如果只依靠程序員的記憶來對對象進行追蹤和銷毀，基本是不太可能的。另一方面，正如前面提到的，一個共享對象可能被多個數據結構所引用，這時像是“這個對象被引用了多少次？”之類的問題就會出現。為了解決以上兩個問題，Redis 的對象系統使用了[引用計數](http://en.wikipedia.org/wiki/Reference_counting) 技術來負責維持和銷毀對象，它的運作機制如下： - 每個 `redisObject` 結構都帶有一個 `refcount` 屬性，指示這個對象被引用了多少次。 - 當新創建一個對象時，它的 `refcount` 屬性被設置為 `1` 。 - 當對一個對象進行共享時，Redis 將這個對象的 `refcount` 增一。 - 當使用完一個對象之后，或者取消對共享對象的引用之后，程序將對象的 `refcount` 減一。 - 當對象的 `refcount` 降至 `0` 時，這個 `redisObject` 結構，以及它所引用的數據結構的內存，都會被釋放。 ### 小結 - Redis 使用自己實現的對象機制來實現類型判斷、命令多態和基于引用計數的垃圾回收。 - 一種 Redis 類型的鍵可以有多種底層實現。 - Redis 會預分配一些常用的數據對象，并通過共享這些對象來減少內存占用，和避免頻繁地為小對象分配內存。