Redis資料結構

一、概述

首先在 Redis 内部會使用一個 RedisObject 對象來表示所有的 

key

 和 

value。

Redis是典型的Key-Value類型資料庫，Key為字元類型，Value的類型常用的為五種類型：String、Hash 、List 、 Set 、 sortedSet。Value還支援的進階類型：HyperLogLog、布隆過濾器、GeoHash、BitM ap、Pub/Sub、Stream

二、String資料類型

可以是String，也可是是任意的byte[]類型的數組，如圖檔等。String 在 redis 内部存儲預設就是一個字元串，被 redisObject 所引用，當遇到 incr,decr 等操作時會轉成數值型進行計算，此時 redisObject 的 encoding 字段為int。

1、大小限制

最大為512Mb，基本可以存儲任意圖檔啦。常用指令的時間複雜度為O(1)，讀寫一樣的快。常用指令：get、set、incr、decr、mget等，參照Redis常用指令中文版http://doc.redisfans.com/string/index.html。

2、應用場景

String是最常用的一種資料類型，普通的key/ value 存儲都可以歸為此類，即可以完全實作目前 Memcached 的功能，并且效率更高。還可以享受Redis的定時持久化，記錄檔及 Replication等功能。除了提供與 Memcached 一樣的get、set、incr、decr 等操作外，Redis還提供了下面一些操作： 

• 擷取字元串長度
• 往字元串append内容
• 設定和擷取字元串的某一段内容
• 設定及擷取字元串的某一位（bit）
• 批量設定一系列字元串的内容

3、使用場景

正常key-value緩存應用。正常計數: 微網誌數, 粉絲數。

三 、Hash（HashMap，哈希映射表）

Redis 的 Hash 實際是内部存儲的 Value 為一個 HashMap，并提供了直接存取這個 Map 成員的接口。Hash将對象的各個屬性存入Map裡，可以隻讀取/更新對象的某些屬性。另外不同的子產品可以隻更新自己關心的屬性而不會互相并發覆寫沖突。

不同程式通過 key（使用者 ID） + field（屬性标簽）就可以并發操作各自關心的屬性資料 

1、實作原理

Redis Hash 對應 Value 内部實際就是一個 HashMap，實際這裡會有2種不同實作， Hash 的成員比較少時 Redis 為了節省記憶體會采用類似一維數組的方式來緊湊存儲，而不會采用真正的 HashMap 結構，對應的 value redisObject 的 encoding 為 zipmap，當成員數量增大時會自動轉成真正的 HashMap，此時 encoding 為 ht**。一般操作複雜度是O(1)，要同時操作多個field時就是O(N)，N是field的數量。

2、使用場景

存儲部分變更資料，如使用者資訊等。

3、常用操作

• O(1)操作：hget、hset等等
• O(n)操作：hgetallRedis 可以直接取到全部的屬性資料，但是如果内部 Map 的成員很多，那麼涉及到周遊整個内部 Map 的操作，由于 Redis 單線程模型的緣故，這個周遊操作可能會比較耗時，而另其它用戶端的請求完全不響應，這點需要格外注意。

三、 List（雙向連結清單）

Redis list 的應用場景非常多，也是 Redis 最重要的資料結構之一，比如 twitter 的關注清單，粉絲清單等都可以用 Redis 的 list 結構來實作，還提供了生産者消費者阻塞模式（B開頭的指令），常用于任務隊列，消息隊列等。

1、實作方式

Redis list 的實作為一個雙向連結清單，即可以支援反向查找和周遊，更友善操作，不過帶來了部分額外的記憶體開銷，Redis 内部的很多實作，包括發送緩沖隊列等也都是用的這個資料結構。　　

2、用作消息隊列中放置資料丢失的解決方法

如果消費者把job給Pop走了又沒處理完就當機了怎麼辦？

• 消息生産者保證不丢失

加多一個sorted set，分發的時候同時發到list與sorted set，以分發時間為score，使用者把job做完了之後要用ZREM消掉sorted set裡的job，并且定時從sorted set中取出逾時沒有完成的任務，重新放回list。 如果發生重複可以在sorted set中在查詢确認一遍，或者将消息的消費接口設計成幂等性。

• 消息消費者保證不丢失

為每個worker多加一個的list，彈出任務時改用RPopLPush，将job同時放到worker自己的list中，完成時用LREM消掉。如果叢集管理(如zookeeper)發現worker已經挂掉，就将worker的list内容重新放回主list

• 複合操作：RPopLPush/ BRPopLPush，彈出來傳回給client的同時，把自己又推入另一個list，是原子操作。

　　　　　　

•  按值進行的操作：LRem(按值删除元素)、LInsert(插在某個值的元素的前後)，複雜度是O(N)，N是List長度，因為List的值不唯一，是以要周遊全部元素，而Set隻要O(log(N))

4、 set（HashSet）

Set就是HashSet，可以将重複的元素随便放入而Set會自動去重，底層實作也是HashMap，并且 set 提供了判斷某個成員是否在一個 set 集合内的重要接口，這個也是 list 所不能提供的。

• 實作原理

　　　　set 的内部實作是一個 value 永遠為 null 的 HashMap，實際就是通過計算 hash 的方式來快速排重的，這也是 set 能提供判斷一個成員是否在集合内的原因。

• 常見操作

• • 增删改查：SAdd/SRem/SIsMember/SCard/SMove/SMembers等等。除了SMembers都是O(1)。
  • 集合操作：SInter/SInterStore/SUnion/SUnionStore/SDiff/SDiffStore，各種集合操作。交集運算可以用來顯示線上好友(線上使用者 交集 好友清單)，共同關注(兩個使用者的關注清單的交集)。O(N)，并集和差集的N是集合大小之和，交集的N是小的那個集合的大小的2倍。

5、 Sorted Set（插入有序Set集合）

set 不是自動有序的，而** sorted set 可以通過使用者額外提供一個優先級（score）的參數來為成員排序，并且是插入有序的，即自動排序**。當你需要一個有序的并且不重複的集合清單，那麼可以選擇 sorted set 資料結構，比如 twitter 的 public timeline 可以以發表時間作為 score 來存儲，這樣擷取時就是自動按時間排好序的。

• 實作方式

内部使用 HashMap 和跳躍表（SkipList）來保證資料的存儲和有序

　　Sorted Set的實作是HashMap(element->score, 用于實作ZScore及判斷element是否在集合内)，和SkipList(score->element,按score排序)的混合體。SkipList有點像平衡二叉樹那樣，不同範圍的score被分成一層一層，每層是一個按score排序的連結清單。　　　　

• 常用操作　　

ZAdd/ZRem是O(log(N))；ZRangeByScore/ZRemRangeByScore是O(log(N)+M)，N是Set大小，M是結果/操作元素的個數。複雜度的log取對數很關鍵，可以使，1000萬大小的Set，複雜度也隻是幾十不到。但是，如果一次命中很多元素M很大則複雜度很高。

6、 Redis使用與記憶體優化

上面的一些實作上的分析可以看出 redis 實際上的記憶體管理成本非常高，即占用了過多的記憶體，屬于用空間換時間。作者對這點也非常清楚，是以提供了一系列的參數和手段來控制和節省記憶體

• 建議不要開啟VM（虛拟記憶體）選項

　　　　VM 選項是作為 Redis 存儲超出實體記憶體資料的一種資料在記憶體與磁盤換入換出的一個持久化政策，将嚴重地拖垮系統的運作速度，是以要關閉 VM 功能，請檢查你的 redis.conf 檔案中 vm-enabled 為 no。

• 設定最大記憶體選項

　　　　最好設定下 redis.conf 中的 maxmemory 選項，該選項是告訴 Redis 當使用了多少實體記憶體後就開始拒絕後續的寫入請求，該參數能很好的保護好你的 Redis 不會因為使用了過多的實體記憶體而導緻 swap，最終嚴重影響性能甚至崩潰。

• 一般還需要設定記憶體飽和回收政策
  • volatile-lru：從已設定過期時間的資料集（server.db[i].expires）中挑選最近最少使用的資料淘汰
  • volatile-ttl：從已設定過期時間的資料集（server.db[i].expires）中挑選将要過期的資料淘汰
  • volatile-random：從已設定過期時間的資料集（server.db[i].expires）中任意選擇資料淘汰
  • allkeys-lru：從資料集（server.db[i].dict）中挑選最近最少使用的資料淘汰
  • allkeys-random：從資料集（server.db[i].dict）中任意選擇資料淘汰
  • no-enviction（驅逐）：禁止驅逐資料