《三天给你聊清楚redis》第1天先唠唠redis是个啥（18629字）
后端需要知道的關于redis的事，基本都在這里了。
此文后續會改為粉絲可見，所以喜歡的請提前關注。
你的點贊和評論是我創作的最大動力，謝謝。
1、入門
Redis是一款基于鍵值對的NoSQL數據庫，它的值支持多種數據結構：
字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。
? Redis將所有的數據都存放在內存中，所以它的讀寫性能十分驚人，用作數據庫，緩存和消息代理。
Redis具有內置的復制，Lua腳本，LRU逐出，事務和不同級別的磁盤持久性，并通過Redis Sentinel和Redis Cluster自動分區提供了高可用性。
? Redis典型的應用場景包括：緩存、排行榜、計數器、社交網絡、消息隊列等
1.1NoSql入門概述
1）單機Mysql的美好時代
瓶頸：
?
- 數據庫總大小一臺機器硬盤內存放不下
- 數據的索引（B + tree）一個機器的運行內存放不下
- 訪問量（讀寫混合）一個實例不能承受
?
2）Memcached（緩存）+ MySql + 垂直拆分
通過緩存來緩解數據庫的壓力，優化數據庫的結構和索引
垂直拆分指的是：分成多個數據庫存儲數據（如：賣家庫與買家庫）
?
3）MySql主從復制讀寫分離
?
4）分表分庫+水平拆分+MySql集群
?
MySql擴展的瓶頸
常用的Nosql
Redis
memcache
Mongdb
以上幾種Nosql 請到各自的官網上下載并參考使用
Nosql 的核心功能點
KV(存儲)
Cache(緩存)
Persistence(持久化)
……
1.2redis的介紹和特點:
? ? ? ?問題：
? ? ? ? ? ? ? ?傳統數據庫：持久化存儲數據。
? ? ? ? ? ? ? ?solr索引庫:大量的數據的檢索。
? ? ? ? ? ? ? ?在實際開發中，高并發環境下，不同的用戶會需要相同的數據。因為每次請求，
? ? ? ? ? ? ? ?在后臺我們都會創建一個線程來處理，這樣造成，同樣的數據從數據庫中查詢了N次。
? ? ? ? ? ? ? ?而數據庫的查詢本身是ＩＯ操作，效率低，頻率高也不好。
? ? ? ? ? ? ? ?總而言之，一個網站總歸是有大量的數據是用戶共享的，但是如果每個用戶都去數據庫查詢
? ? ? ? ? ? ? ?效率就太低了。
? ? ? ?解決：
? ? ? ? ? ? ? ?將用戶共享數據緩存到服務器的內存中。 ? ? ? ?
? ? ? ?特點：
? ? ? ? ? ? ? ?1、基于鍵值對
? ? ? ? ? ? ? ?2、非關系型(redis)
? ? ? ? ? ? ? ? ? ? ? ?關系型數據庫:存儲了數據以及數據之間的關系,oracle,mysql
? ? ? ? ? ? ? ? ? ? ? ?非關系型數據庫:存儲了數據,redis,mdb.
? ? ? ? ? ? ? ?3、數據存儲在內存中，服務器關閉后，持久化到硬盤中
? ? ? ? ? ? ? ?4、支持主從同步
? ? ? ? ? ? ? ?實現了緩存數據和項目的解耦。
? ? ? ?redis存儲的數據特點：
? ? ? ? ? ? ? ?大量數據
? ? ? ? ? ? ? ?用戶共享數據
? ? ? ? ? ? ? ?數據不經常修改。
? ? ? ? ? ? ? ?查詢數據
? ? ? ?redis的應用場景：
? ? ? ? ? ? ? ?網站高并發的主頁數據
? ? ? ? ? ? ? ?網站數據的排名
? ? ? ? ? ? ? ?消息訂閱
1.3redis——數據結構和對象的使用介紹? ??
? ? ? ?
redis官網
微軟寫的windows下的redis
我們下載第一個
額案后基本一路默認就行了
安裝后，服務自動啟動，以后也不用自動啟動。
出現這個表示我們連接上了。
?
redis命令參考鏈接
1.3.1String
數據結構
struct sdshdr{//記錄buf數組中已使用字節的數量int len;//記錄buf數組中未使用的數量int free;//字節數組，用于保存字符串char buf[]; }常見操作
127.0.0.1:6379> set hello world OK 127.0.0.1:6379> get hello "world" 127.0.0.1:6379> del hello (integer) 1 127.0.0.1:6379> get hello (nil) 127.0.0.1:6379>應用場景
String是最常用的一種數據類型，普通的key/value存儲都可以歸為此類，value其實不僅是String，也可以是數字：比如想知道什么時候封鎖一個IP地址（訪問超過幾次）。INCRBY命令讓這些變得很容易，通過原子遞增保持計數。
1.3.2LIST
數據結構
typedef struct listNode{//前置節點struct listNode *prev;//后置節點struct listNode *next;//節點的值struct value; }常見操作
> lpush list-key item (integer) 1 > lpush list-key item2 (integer) 2 > rpush list-key item3 (integer) 3 > rpush list-key item (integer) 4 > lrange list-key 0 -1 1) "item2" 2) "item" 3) "item3" 4) "item" > lindex list-key 2 "item3" > lpop list-key "item2" > lrange list-key 0 -1 1) "item" 2) "item3" 3) "item"應用場景
Redis list的應用場景非常多，也是Redis最重要的數據結構之一。
我們可以輕松地實現最新消息排行等功能。
Lists的另一個應用就是消息隊列，可以利用Lists的PUSH操作，將任務存在Lists中，然后工作線程再用POP操作將任務取出進行執行。
1.3.3HASH
數據結構
dictht是一個散列表結構，使用拉鏈法保存哈希沖突的dictEntry。
typedef struct dictht{//哈希表數組dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩碼，用于計算索引值unsigned long sizemask;//該哈希表已有節點的數量unsigned long used; }typedef struct dictEntry{//鍵void *key;//值union{void *val;uint64_tu64;int64_ts64;}struct dictEntry *next; }Redis的字典dict中包含兩個哈希表dictht，這是為了方便進行rehash操作。在擴容時，將其中一個dictht上的鍵值對rehash到另一個dictht上面，完成之后釋放空間并交換兩個dictht的角色。
typedef struct dict {dictType *type;void *privdata;dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */unsigned long iterators; /* number of iterators currently running */ } dict;rehash操作并不是一次性完成、而是采用漸進式方式，目的是為了避免一次性執行過多的rehash操作給服務器帶來負擔。
漸進式rehash通過記錄dict的rehashidx完成，它從0開始，然后沒執行一次rehash例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，這一次會把 dict[0] 上 table[rehashidx] 的鍵值對 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。
在 rehash 期間，每次對字典執行添加、刪除、查找或者更新操作時，都會執行一次漸進式 rehash。
采用漸進式rehash會導致字典中的數據分散在兩個dictht中，因此對字典的操作也會在兩個哈希表上進行。
例如查找時，先從ht[0]查找，沒有再查找ht[1]，添加時直接添加到ht[1]中。
常見操作
> hset hash-key sub-key1 value1 (integer) 1 > hset hash-key sub-key2 value2 (integer) 1 > hset hash-key sub-key1 value1 (integer) 0 > hgetall hash-key 1) "sub-key1" 2) "value1" 3) "sub-key2" 4) "value2" > hdel hash-key sub-key2 (integer) 1 > hdel hash-key sub-key2 (integer) 0 > hget hash-key sub-key1 "value1" > hgetall hash-key 1) "sub-key1" 2) "value1"1.3.4SET
常見操作
> sadd set-key item (integer) 1 > sadd set-key item2 (integer) 1 > sadd set-key item3 (integer) 1 > sadd set-key item (integer) 0 > smembers set-key 1) "item2" 2) "item" 3) "item3" > sismember set-key item4 (integer) 0 > sismember set-key item (integer) 1 > srem set-key item (integer) 1 > srem set-key item (integer) 0 > smembers set-key 1) "item2" 2) "item3"應用場景
Redis為集合提供了求交集、并集、差集等操作，故可以用來求共同好友等操作。
1.3.5ZSET
數據結構
typedef struct zskiplistNode{//后退指針struct zskiplistNode *backward;//分值double score;//成員對象robj *obj;//層struct zskiplistLever{//前進指針struct zskiplistNode *forward;//跨度unsigned int span;}lever[];}typedef struct zskiplist{//表頭節點跟表尾結點struct zskiplistNode *header, *tail;//表中節點的數量unsigned long length;//表中層數最大的節點的層數int lever;}跳躍表，基于多指針有序鏈實現，可以看作多個有序鏈表。
與紅黑樹等平衡樹相比，跳躍表具有以下優點：
- 插入速度非常快速，因為不需要進行旋轉等操作來維持平衡性。
- 更容易實現。
- 支持無鎖操作。
常見操作
> zadd zset-key 728 member1 (integer) 1 > zadd zset-key 982 member0 (integer) 1 > zadd zset-key 982 member0 (integer) 0 > zrange zset-key 0 -1 1) "member1" 2) "member0" > zrange zset-key 0 -1 withscores 1) "member1" 2) "728" 3) "member0" 4) "982" > zrangebyscore zset-key 0 800 withscores 1) "member1" 2) "728" > zrem zset-key member1 (integer) 1 > zrem zset-key member1 (integer) 0 > zrange zset-key 0 -1 withscores 1) "member0" 2) "982"應用場景
以某個條件為權重，比如按頂的次數排序
ZREVRANGE命令可以用來按照得分來獲取前100名的用戶，ZRANK可以用來獲取用戶排名，非常直接而且操作容易。
Redis sorted set的使用場景與set類似，區別是set不是自動有序的，而sorted set可以通過用戶額外提供一個優先級(score)的參數來為成員排序，并且是插入有序的，即自動排序。
?
redis命令參考鏈接
1.4Spring整合Redis
引入依賴
- spring-boot-starter-data-redis
配置Redis
- 配置數據庫參數
- 編寫配置類，構造RedisTemplate
這個springboot已經幫我們配了，但是默認object，我想改成string
import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.data.redis.connection.RedisConnectionFactory; import org.springframework.data.redis.core.RedisTemplate; import org.springframework.data.redis.serializer.RedisSerializer;@Configuration public class RedisConfig {@Beanpublic RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {RedisTemplate<String, Object> template = new RedisTemplate<>();template.setConnectionFactory(factory);// 設置key的序列化方式template.setKeySerializer(RedisSerializer.string());// 設置value的序列化方式template.setValueSerializer(RedisSerializer.json());// 設置hash的key的序列化方式template.setHashKeySerializer(RedisSerializer.string());// 設置hash的value的序列化方式template.setHashValueSerializer(RedisSerializer.json());template.afterPropertiesSet();return template;}}
訪問Redis
- redisTemplate.opsForValue()
- redisTemplate.opsForHash()
- redisTemplate.opsForList()
- redisTemplate.opsForSet()
- redisTemplate.opsForZSet()
這樣還是稍微有點麻煩，我們其實可以綁定key
// 多次訪問同一個key@Testpublic void testBoundOperations() {String redisKey = "test:count";BoundValueOperations operations = redisTemplate.boundValueOps(redisKey);operations.increment();operations.increment();operations.increment();operations.increment();operations.increment();System.out.println(operations.get());}2、數據結構原理總結
這部分在我看來是最有意思的，我們有必要了解底層數據結構的實現，這也是我最感興趣的。
比如，你知道redis中的字符串怎么實現的嗎？為什么這么實現？
你知道redis壓縮列表是什么算法嗎？
你知道redis為什么拋棄了紅黑樹反而采用了跳表這種新的數據結構嗎？
你知道hyperloglog為什么用如此小的空間就可以有這么好的統計性能和準確性嗎？
你知道布隆過濾器為什么這么有效嗎？有沒有數學證明過？
你是否還能很快寫出來快排？或者不斷優化性能的排序？是不是只會調庫了甚至庫函數怎么實現的都不知道？真的就是快排？
包括數據庫，持久化，處理事件、客戶端服務端、事務的實現、發布和訂閱等功能的實現，也需要了解。
2.1數據結構和對象的實現
- 1） 字符串
redis并未使用傳統的c語言字符串表示，它自己構建了一種簡單的動態字符串抽象類型。
在redis里，c語言字符串只會作為字符串字面量出現，用在無需修改的地方。
當需要一個可以被修改的字符串時，redis就會使用自己實現的SDS（simple dynamic string）。比如在redis數據庫里，包含字符串的鍵值對底層都是SDS實現的，不止如此，SDS還被用作緩沖區（buffer）：比如AOF模塊中的AOF緩沖區以及客戶端狀態中的輸入緩沖區。
下面來具體看一下sds的實現：
struct sdshdr {int len;//buf已使用字節數量（保存的字符串長度）int free;//未使用的字節數量char buf[];//用來保存字符串的字節數組 };sds遵循c中字符串以'\0'結尾的慣例，這一字節的空間不算在len之內。
這樣的好處是，我們可以直接重用c中的一部分函數。比如printf；
? ? sds相對c的改進
? ? 獲取長度：c字符串并不記錄自身長度，所以獲取長度只能遍歷一遍字符串，redis直接讀取len即可。
? ? 緩沖區安全：c字符串容易造成緩沖區溢出，比如：程序員沒有分配足夠的空間就執行拼接操作。而redis會先檢查sds的空間是否滿足所需要求，如果不滿足會自動擴充。
? ? 內存分配：由于c不記錄字符串長度，對于包含了n個字符的字符串，底層總是一個長度n+1的數組，每一次長度變化，總是要對這個數組進行一次內存重新分配的操作。因為內存分配涉及復雜算法并且可能需要執行系統調用，所以它通常是比較耗時的操作。? ?
? ? redis內存分配：
1、空間預分配：如果修改后大小小于1MB，程序分配和len大小一樣的未使用空間，如果修改后大于1MB，程序分配? 1MB的未使用空間。修改長度時檢查，夠的話就直接使用未使用空間，不用再分配。?
2、惰性空間釋放：字符串縮短時不需要釋放空間，用free記錄即可，留作以后使用。
? ? 二進制安全
c字符串除了末尾外，不能包含空字符，否則程序讀到空字符會誤以為是結尾，這就限制了c字符串只能保存文本，二進制文件就不能保存了。
而redis字符串都是二進制安全的，因為有len來記錄長度。
- 2） 鏈表
作為一種常用數據結構，鏈表內置在很多高級語言中，因為c并沒有，所以redis實現了自己的鏈表。
鏈表在redis也有一定的應用，比如列表鍵的底層實現之一就是鏈表。（當列表鍵包含大量元素或者元素都是很長的字符串時）
發布與訂閱、慢查詢、監視器等功能也用到了鏈表。
具體實現：
//redis的節點使用了雙向鏈表結構 typedef struct listNode {// 前置節點struct listNode *prev;// 后置節點struct listNode *next;// 節點的值void *value; } listNode; //其實學過數據結構的應該都實現過 typedef struct list {// 表頭節點listNode *head;// 表尾節點listNode *tail;// 鏈表所包含的節點數量unsigned long len;// 節點值復制函數void *(*dup)(void *ptr);// 節點值釋放函數void (*free)(void *ptr);// 節點值對比函數int (*match)(void *ptr, void *key); } list;總結一下redis鏈表特性：
雙端、無環、帶長度記錄、
多態：使用?void*?指針來保存節點值， 可以通過?dup?、?free?、?match?為節點值設置類型特定函數， 可以保存不同類型的值。
- 3）字典
其實字典這種數據結構也內置在很多高級語言中，但是c語言沒有，所以redis自己實現了。
應用也比較廣泛，比如redis的數據庫就是字典實現的。不僅如此，當一個哈希鍵包含的鍵值對比較多，或者都是很長的字符串，redis就會用字典作為哈希鍵的底層實現。
來看看具體是實現：
//redis的字典使用哈希表作為底層實現 typedef struct dictht {// 哈希表數組dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩碼，用于計算索引值// 總是等于 size - 1unsigned long sizemask;// 該哈希表已有節點的數量unsigned long used;} dictht;table?是一個數組， 數組中的每個元素都是一個指向dictEntry?結構的指針， 每個?dictEntry?結構保存著一個鍵值對。
圖為一個大小為4的空哈希表。
我們接著就來看dictEntry的實現：
typedef struct dictEntry {// 鍵void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下個哈希表節點，形成鏈表struct dictEntry *next; } dictEntry;（v可以是一個指針， 或者是一個?uint64_t?整數， 又或者是一個?int64_t?整數。）
next就是解決鍵沖突問題的，沖突了就掛后面，這個學過數據結構的應該都知道吧，不說了。
?
下面我們來說字典是怎么實現的了。
typedef struct dict {// 類型特定函數dictType *type;// 私有數據void *privdata;// 哈希表dictht ht[2];// rehash 索引int rehashidx; //* rehashing not in progress if rehashidx == -1 } dict;type?和?privdata?是對不同類型的鍵值對， 為創建多態字典而設置的：
type?指向?dictType?， 每個?dictType?保存了用于操作特定類型鍵值對的函數， 可以為用途不同的字典設置不同的類型特定函數。
而?privdata?屬性則保存了需要傳給那些類型特定函數的可選參數。
而dictType就暫時不展示了，不重要而且字有點多。。。還是講有意思的東西吧? ? rehash（重新散列）
隨著我們不斷的操作，哈希表保存的鍵值可能會增多或者減少，為了讓哈希表的負載因子維持在合理的范圍內，有時需要對哈希表進行合理的擴展或者收縮。?一般情況下， 字典只使用?ht[0]?哈希表，?ht[1]?哈希表只會在對?ht[0]?哈希表進行 rehash 時使用。
redis字典哈希rehash的步驟如下：
1）為ht[1]分配合理空間：如果是擴展操作，大小為第一個大于等于ht[0]*used*2的，2的n次冪。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果是收縮操作，大小為第一個大于等于ht[0]*used的，2的n次冪。
2）將ht[0]中的數據rehash到ht[1]上。
3）釋放ht[0]，將ht[1]設置為ht[0]，ht[1]創建空表，為下次做準備。
? ? 漸進rehash
數據量特別大時，rehash可能對服務器造成影響。為了避免，服務器不是一次性rehash的，而是分多次。
我們維持一個變量rehashidx，設置為0，代表rehash開始，然后開始rehash，在這期間，每個對字典的操作，程序都會把索引rehashidx上的數據移動到ht[1]。
隨著操作不斷執行，最終我們會完成rehash，設置rehashidx為-1.
需要注意：rehash過程中，每一次增刪改查也是在兩個表進行的。
- 4）整數集合
整數集合（intset）是 Redis 用于保存整數值的集合抽象數據結構， 可以保存?int16_t?、?int32_t?、?int64_t?的整數值， 并且保證集合中不會出現重復元素。
實現較為簡單：
typedef struct intset {// 編碼方式uint32_t encoding;// 集合包含的元素數量uint32_t length;// 保存元素的數組int8_t contents[]; } intset;各個項在數組中從小到大有序地排列， 并且數組中不包含任何重復項。
雖然?intset?結構將?contents?屬性聲明為?int8_t?類型的數組， 但實際上?contents?數組并不保存任何?int8_t?類型的值 ——?contents?數組的真正類型取決于?encoding?屬性的值：
如果?encoding?屬性的值為?INTSET_ENC_INT16?， 那么?contents?就是一個?int16_t?類型的數組， 數組里的每個項都是一個?int16_t?類型的整數值 （最小值為?-32,768?，最大值為?32,767?）。
如果?encoding?屬性的值為?INTSET_ENC_INT32?， 那么?contents?就是一個?int32_t?類型的數組， 數組里的每個項都是一個?int32_t?類型的整數值 （最小值為?-2,147,483,648?，最大值為?2,147,483,647?）。
如果?encoding?屬性的值為?INTSET_ENC_INT64?， 那么?contents?就是一個?int64_t?類型的數組， 數組里的每個項都是一個?int64_t?類型的整數值 （最小值為?-9,223,372,036,854,775,808?，最大值為?9,223,372,036,854,775,807?）。
? ? 升級
c語言是靜態類型語言，不允許不同類型保存在一個數組。這樣第一，靈活性較差，第二，有時會用掉不必要的內存
比如用long long儲存1
為了提高整數集合的靈活性和節約內存，我們引入升級策略。
當我們要將一個新元素添加到集合里， 并且新元素類型比集合現有元素的類型都要長時， 集合需要先進行升級。
分為三步進行：
因為每次添加新元素都可能會引起升級， 每次升級都要對已有元素類型轉換， 所以添加新元素的時間復雜度為?O(N)?。
因為引發升級的新元素比原數據都長，所以要么他是最大的，要么他是最小的。我們把它放在開頭或結尾即可。
?
? ? 降級
略略略，不管你們信不信，整數集合不支持降級操作。。我也不知道為啥
- 5）壓縮列表
壓縮列表是列表鍵和哈希鍵的底層實現之一。
當一個列表鍵只包含少量列表項，并且列表項都是小整數或者短字符串，redis就會用壓縮列表做列表鍵底層實現。
壓縮列表是 Redis 為了節約內存而開發的， 由一系列特殊編碼的連續內存塊組成的順序型（sequential）數據結構。
一個壓縮列表可以包含任意多個節點（entry）， 每個節點可以保存一個字節數組或者一個整數值。
具體實現：
具體說一下entry：
由三個部分組成：
1、previous_entry_length:記錄上一個節點的長度，這樣我們就可以從最后一路遍歷到開頭。
2、encoding：記錄了content所保存的數據類型和長度。（具體編碼不寫了，不重要）
3、content：保存節點值，可以是字節數組或整數。（具體怎么壓縮的等我搞明白再補）
? ? 連鎖更新
前面說過， 每個節點的?previous_entry_length?屬性都記錄了前一個節點的長度：
- 如果前一節點的長度<?254?KB， 那么?previous_entry_length?需要用?1?字節長的空間
- 如果前一節點的長度>=254?KB， 那么?previous_entry_length?需要用?5?字節長的空間
現在， 考慮這樣一種情況： 在一個壓縮列表中， 有多個連續的、長度介于?250?字節到?253?字節之間的節點 ，這時， 如果我們將一個長度大于等于?254?字節的新節點?new?設置為壓縮列表的表頭節點。。。。
然后腦補一下，就會導致連鎖擴大每個節點的空間對吧？e(i)因為e(i-1)的擴大而擴大，i+1也是如此，以此類推。。。
?
刪除節點同樣會導致連鎖更新。
這個事情只是想說明一個問題：插入刪除操作的最壞時間復雜度其實是o(n*n)，因為每更新一個節點都要o(n)。
但是，也不用太過擔心，因為這種特殊情況并不多見，這些命令的平均復雜度依舊是o(n)。
?
2.2 跳表專欄
2.2.1跳表是啥
為什么選擇了跳表而不是紅黑樹？
跳表是個啥東西請看這個文章。
我們知道，節點插入時隨機出一個層數，僅僅依靠一個簡單的隨機數操作而構建出來的多層鏈表結構，能保證它有一個良好的查找性能嗎？為了回答這個疑問，我們需要分析skiplist的統計性能。
在分析之前，我們還需要著重指出的是，執行插入操作時計算隨機數的過程，是一個很關鍵的過程，它對skiplist的統計特性有著很重要的影響。這并不是一個普通的服從均勻分布的隨機數，它的計算過程如下：
- 首先，每個節點肯定都有第1層指針（每個節點都在第1層鏈表里）。
- 如果一個節點有第i層(i>=1)指針（即節點已經在第1層到第i層鏈表中），那么它有第(i+1)層指針的概率為p。
- 節點最大的層數不允許超過一個最大值，記為MaxLevel。
這個計算隨機層數的偽碼如下所示：
randomLevel() level := 1 // random()返回一個[0...1)的隨機數 while random() < p and level < MaxLevel do level := level + 1 return levelrandomLevel()的偽碼中包含兩個參數，一個是p，一個是MaxLevel。在Redis的skiplist實現中，這兩個參數的取值為：
p = 1/4 MaxLevel = 322.2.2skiplist的算法性能分析
在這一部分，我們來簡單分析一下skiplist的時間復雜度和空間復雜度，以便對于skiplist的性能有一個直觀的了解。如果你不是特別偏執于算法的性能分析，那么可以暫時跳過這一小節的內容。
我們先來計算一下每個節點所包含的平均指針數目（概率期望）。節點包含的指針數目，相當于這個算法在空間上的額外開銷(overhead)，可以用來度量空間復雜度。
根據前面randomLevel()的偽碼，我們很容易看出，產生越高的節點層數，概率越低。定量的分析如下：
- 節點層數至少為1。而大于1的節點層數，滿足一個概率分布。
- 節點層數恰好等于1的概率為1-p。
- 節點層數大于等于2的概率為p，而節點層數恰好等于2的概率為p(1-p)。
- 節點層數大于等于3的概率為p^2，而節點層數恰好等于3的概率為p^2(1-p)。
- 節點層數大于等于4的概率為p^3，而節點層數恰好等于4的概率為p^3(1-p)。
- ......
因此，一個節點的平均層數（也即包含的平均指針數目），計算如下：
現在很容易計算出：
- 當p=1/2時，每個節點所包含的平均指針數目為2；
- 當p=1/4時，每個節點所包含的平均指針數目為1.33。這也是Redis里的skiplist實現在空間上的開銷。
接下來，為了分析時間復雜度，我們計算一下skiplist的平均查找長度。查找長度指的是查找路徑上跨越的跳數，而查找過程中的比較次數就等于查找長度加1。以前面圖中標出的查找23的查找路徑為例，從左上角的頭結點開始，一直到結點22，查找長度為6。
為了計算查找長度，這里我們需要利用一點小技巧。我們注意到，每個節點插入的時候，它的層數是由隨機函數randomLevel()計算出來的，而且隨機的計算不依賴于其它節點，每次插入過程都是完全獨立的。所以，從統計上來說，一個skiplist結構的形成與節點的插入順序無關。
這樣的話，為了計算查找長度，我們可以將查找過程倒過來看，從右下方第1層上最后到達的那個節點開始，沿著查找路徑向左向上回溯，類似于爬樓梯的過程。我們假設當回溯到某個節點的時候，它才被插入，這雖然相當于改變了節點的插入順序，但從統計上不影響整個skiplist的形成結構。
現在假設我們從一個層數為i的節點x出發，需要向左向上攀爬k層。這時我們有兩種可能：
- 如果節點x有第(i+1)層指針，那么我們需要向上走。這種情況概率為p。
- 如果節點x沒有第(i+1)層指針，那么我們需要向左走。這種情況概率為(1-p)。
用C(k)表示向上攀爬k個層級所需要走過的平均查找路徑長度（概率期望），那么：
C(0)=0 C(k)=(1-p)×(上圖中情況b的查找長度) + p×(上圖中情況c的查找長度)代入，得到一個差分方程并化簡：
C(k)=(1-p)(C(k)+1) + p(C(k-1)+1) C(k)=1/p+C(k-1) C(k)=k/p這個結果的意思是，我們每爬升1個層級，需要在查找路徑上走1/p步。而我們總共需要攀爬的層級數等于整個skiplist的總層數-1。
那么接下來我們需要分析一下當skiplist中有n個節點的時候，它的總層數的概率均值是多少。這個問題直觀上比較好理解。根據節點的層數隨機算法，容易得出：
- 第1層鏈表固定有n個節點；
- 第2層鏈表平均有n*p個節點；
- 第3層鏈表平均有n*p^2個節點；
- ...
所以，從第1層到最高層，各層鏈表的平均節點數是一個指數遞減的等比數列。容易推算出，總層數的均值為log1/pn，而最高層的平均節點數為1/p。
綜上，粗略來計算的話，平均查找長度約等于：
- C(log1/pn-1)=(log1/pn-1)/p
即，平均時間復雜度為O(log n)。
當然，這里的時間復雜度分析還是比較粗略的。比如，沿著查找路徑向左向上回溯的時候，可能先到達左側頭結點，然后沿頭結點一路向上；還可能先到達最高層的節點，然后沿著最高層鏈表一路向左。但這些細節不影響平均時間復雜度的最后結果。另外，這里給出的時間復雜度只是一個概率平均值，但實際上計算一個精細的概率分布也是有可能的。
詳情還請參見William Pugh的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。
2.2.3skiplist與平衡樹、哈希表的比較
- skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節點。
- 在做范圍查找的時候，平衡樹比skiplist操作要復雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現。
- 平衡樹的插入和刪除操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。
- 從內存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分別指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis里的實現一樣，取p=1/4，那么平均每個節點包含1.33個指針，比平衡樹更有優勢。
- 查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實現的。
- 從算法實現難度上來比較，skiplist比平衡樹要簡單得多。
2.2.4Redis中的skiplist和經典有何不同
- 分數(score)允許重復，即skiplist的key允許重復。這在最開始介紹的經典skiplist中是不允許的。
- 在比較時，不僅比較分數（相當于skiplist的key），還比較數據本身。在Redis的skiplist實現中，數據本身的內容唯一標識這份數據，而不是由key來唯一標識。另外，當多個元素分數相同的時候，還需要根據數據內容來進字典排序。
- 第1層鏈表不是一個單向鏈表，而是一個雙向鏈表。這是為了方便以倒序方式獲取一個范圍內的元素。
- 在skiplist中可以很方便地計算出每個元素的排名(rank)。
2.2.5作者的話
最后我們看看，對于這個問題，Redis的作者 @antirez 是怎么說的：
There are a few reasons:
1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
有幾個原因：
1）它們的記憶力不是很強。基本上由你決定。更改有關節點具有給定數量級別的概率的參數將使內存密集度低于btree。
2）排序集通常是許多Zrange或Zrevrange操作的目標，即作為鏈表遍歷跳過列表。通過此操作，跳過列表的緩存區域性至少與其他類型的平衡樹一樣好。
3）它們易于實現、調試等。例如，由于跳過列表的簡單性，我收到了一個補丁（已經在redis master中），其中包含在o（log（n））中實現zrank的擴展跳過列表。它只需要對代碼稍作修改。
2.3HyperLogLog 專欄
HyperLogLog 是一種概率數據結構，用來估算數據的基數。數據集可以是網站訪客的 IP 地址，E-mail 郵箱或者用戶 ID。
基數就是指一個集合中不同值的數目，比如 a, b, c, d 的基數就是 4，a, b, c, d, a 的基數還是 4。雖然 a 出現兩次，只會被計算一次。
使用 Redis 統計集合的基數一般有三種方法，分別是使用 Redis 的 HashMap，BitMap 和 HyperLogLog。前兩個數據結構在集合的數量級增長時，所消耗的內存會大大增加，但是 HyperLogLog 則不會。
Redis 的 HyperLogLog 通過犧牲準確率來減少內存空間的消耗，只需要12K內存，在標準誤差0.81%的前提下，能夠統計2^64個數據。所以 HyperLogLog 是否適合在比如統計日活月活此類的對精度要不不高的場景。
這是一個很驚人的結果，以如此小的內存來記錄如此大數量級的數據基數。下面我們就帶大家來深入了解一下 HyperLogLog 的使用，基礎原理，源碼實現和具體的試驗數據分析。
2.3.1HyperLogLog 在 Redis 中的使用
Redis 提供了?PFADD?、?PFCOUNT?和?PFMERGE?三個命令來供用戶使用 HyperLogLog。
PFADD?用于向 HyperLogLog 添加元素。
> PFADD visitors alice bob carol(integer) 1> PFCOUNT visitors(integer) 3如果 HyperLogLog 估計的近似基數在?PFADD?命令執行之后出現了變化， 那么命令返回 1 ， 否則返回 0 。 如果命令執行時給定的鍵不存在， 那么程序將先創建一個空的 HyperLogLog 結構， 然后再執行命令。
PFCOUNT?命令會給出 HyperLogLog 包含的近似基數。在計算出基數后，?PFCOUNT?會將值存儲在 HyperLogLog 中進行緩存，知道下次?PFADD?執行成功前，就都不需要再次進行基數的計算。
PFMERGE?將多個 HyperLogLog 合并為一個 HyperLogLog ， 合并后的 HyperLogLog 的基數接近于所有輸入 HyperLogLog 的并集基數。
> PFADD customers alice dan(integer) 1> PFMERGE everyone visitors customersOK> PFCOUNT everyone(integer) 42.3.2內存消耗對比實驗
我們下面就來通過實驗真實對比一下下面三種數據結構的內存消耗，HashMap、BitMap 和 HyperLogLog。
我們首先使用 Lua 腳本向 Redis 對應的數據結構中插入一定數量的數，然后執行 bgsave 命令，最后使用 redis-rdb-tools 的 rdb 的命令查看各個鍵所占的內存大小。
下面是 Lua 的腳本
local key = KEYS[1]local size = tonumber(ARGV[1])local method = tonumber(ARGV[2])for i=1,size,1 doif (method == 0)thenredis.call('hset',key,i,1)elseif (method == 1)thenredis.call('pfadd',key, i)elseredis.call('setbit', key, i, 1)endend我們在通過 redis-cli 的?script load?命令將 Lua 腳本加載到 Redis 中，然后使用?evalsha?命令分別向 HashMap、HyperLogLog 和 BitMap 三種數據結構中插入了一千萬個數，然后使用?rdb?命令查看各個結構內存消耗。
我們進行了兩輪實驗，分別插入一萬數字和一千萬數字，三種數據結構消耗的內存統計如下所示。
從表中可以明顯看出，一萬數量級時 BitMap 消耗內存最小， 一千萬數量級時 HyperLogLog 消耗內存最小，但是總體來看，HyperLogLog 消耗的內存都是 14392 字節，可見 HyperLogLog 在內存消耗方面有自己的獨到之處。
2.3.3基本原理
HyperLogLog 是一種概率數據結構，它使用概率算法來統計集合的近似基數。而它算法的最本源則是伯努利過程。
伯努利過程就是一個拋硬幣實驗的過程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。伯努利過程就是一直拋硬幣，直到落地時出現正面位置，并記錄下拋擲次數k。比如說，拋一次硬幣就出現正面了，此時 k 為 1; 第一次拋硬幣是反面，則繼續拋，直到第三次才出現正面，此時 k 為 3。
對于 n 次伯努利過程，我們會得到 n 個出現正面的投擲次數值 k1, k2 ... kn , 其中這里的最大值是k_max。
根據一頓數學推導，我們可以得出一個結論： 2^{k_ max} 來作為n的估計值。也就是說你可以根據最大投擲次數近似的推算出進行了幾次伯努利過程。
下面，我們就來講解一下 HyperLogLog 是如何模擬伯努利過程，并最終統計集合基數的。
HyperLogLog 在添加元素時，會通過Hash函數，將元素轉為64位比特串，例如輸入5，便轉為101(省略前面的0，下同)。這些比特串就類似于一次拋硬幣的伯努利過程。比特串中，0 代表了拋硬幣落地是反面，1 代表拋硬幣落地是正面，如果一個數據最終被轉化了 10010000，那么從低位往高位看，我們可以認為，這串比特串可以代表一次伯努利過程，首次出現 1 的位數為5，就是拋了5次才出現正面。
所以 HyperLogLog 的基本思想是利用集合中數字的比特串第一個 1 出現位置的最大值來預估整體基數，但是這種預估方法存在較大誤差，為了改善誤差情況，HyperLogLog中引入分桶平均的概念，計算 m 個桶的調和平均值。
Redis 中 HyperLogLog 一共分了 2^14 個桶，也就是 16384 個桶。每個桶中是一個 6 bit 的數組。
HyperLogLog 將上文所說的 64 位比特串的低 14 位單獨拿出，它的值就對應桶的序號，然后將剩下 50 位中第一次出現 1 的位置值設置到桶中。50位中出現1的位置值最大為50，所以每個桶中的 6 位數組正好可以表示該值。
在設置前，要設置進桶的值是否大于桶中的舊值，如果大于才進行設置，否則不進行設置。
此時為了性能考慮，是不會去統計當前的基數的，而是將 HyperLogLog 頭的 card 屬性中的標志位置為 1，表示下次進行 pfcount 操作的時候，當前的緩存值已經失效了，需要重新統計緩存值。在后面 pfcount 流程的時候，發現這個標記為失效，就會去重新統計新的基數，放入基數緩存。
在計算近似基數時，就分別計算每個桶中的值，帶入到上文的 DV 公式中，進行調和平均和結果修正，就能得到估算的基數值。
2.3.4HyperLogLog 具體對象
我們首先來看一下 HyperLogLog 對象的定義
struct hllhdr {char magic[4]; /* 魔法值 "HYLL" */uint8_t encoding; /* 密集結構或者稀疏結構 HLL_DENSE or HLL_SPARSE. */uint8_t notused[3]; /* 保留位, 全為0. */uint8_t card[8]; /* 基數大小的緩存 */uint8_t registers[]; /* 數據字節數組 */};HyperLogLog 對象中的?registers?數組就是桶，它有兩種存儲結構，分別為密集存儲結構和稀疏存儲結構，兩種結構只涉及存儲和桶的表現形式，從中我們可以看到 Redis 對節省內存極致地追求。
我們先看相對簡單的密集存儲結構，它也是十分的簡單明了，既然要有 2^14 個 6 bit的桶，那么我就真使用足夠多的?uint8_t?字節去表示，只是此時會涉及到字節位置和桶的轉換，因為字節有 8 位，而桶只需要 6 位。
所以我們需要將桶的序號轉換成對應的字節偏移量 offsetbytes 和其內部的位數偏移量 offsetbits。需要注意的是小端字節序，高位在右側，需要進行倒轉。
當 offset_bits 小于等于2時，說明一個桶就在該字節內，只需要進行倒轉就能得到桶的值。
?offset_bits 大于 2 ，則說明一個桶分布在兩個字節內，此時需要將兩個字節的內容都進行倒置，然后再進行拼接得到桶的值。
Redis 為了方便表達稀疏存儲，它將上面三種字節表示形式分別賦予了一條指令。
-
ZERO : 一字節，表示連續多少個桶計數為0，前兩位為標志00，后6位表示有多少個桶，最大為64。
-
XZERO : 兩個字節，表示連續多少個桶計數為0，前兩位為標志01，后14位表示有多少個桶，最大為16384。
-
VAL : 一字節，表示連續多少個桶的計數為多少，前一位為標志1，四位表示連桶內計數，所以最大表示桶的計數為32。后兩位表示連續多少個桶。
?
Redis從稀疏存儲轉換到密集存儲的條件是：
-
任意一個計數值從 32 變成 33，因為 VAL 指令已經無法容納，它能表示的計數值最大為 32
-
稀疏存儲占用的總字節數超過 3000 字節，這個閾值可以通過 hllsparsemax_bytes 參數進行調整。
2.4LRU專欄
2.4.1LRU介紹和代碼實現
LRU全稱是Least?Recently Used，即最近最久未使用的意思。
LRU算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。（這一段是找的，讓大家理解一下什么是LRU）。
?
說一下我們什么時候見到過LRU：其實老師們肯定都給大家舉過這么個例子：你在圖書館，你把書架子里的書拿到桌子上。。但是桌子是有限的，你有時候不得不把一些書放回去。這就相當于內存和硬盤。這個例子都說過吧？
LRU就是記錄你最長時間沒看過的書，就把它放回去。在cache那里見過吧
?
然后最近在研究redis，又看到了這個LRU，所以就想寫一下吧。
題目：設計一個結構，這個結構可以查詢K-V，但是容量有限，當存不下的時候就要把用的年代最久遠的那個東西扔掉。
其實思路很簡單，我們維護一個雙向鏈表即可，get也就是使用了，我們就把把它提到最安全的位置。新來的KV就依次放即可。
我們就先寫這個雙向鏈表結構
先寫節點結構：
public static class Node<V> {public V value;public Node<V> last;//前public Node<V> next;//后public Node(V value) {this.value = value;}}然后寫雙向鏈表結構： 我們沒必要把鏈表操作都寫了，分析一下，我們只有三個操作：
1、加節點
2、使用了某個節點就把它調到尾，代表優先級最高
3、把優先級最低的移除，也就是去頭部
（不會的，翻我之前的鏈表操作都有寫）
public static class NodeDoubleLinkedList<V> {private Node<V> head;//頭private Node<V> tail;//尾public NodeDoubleLinkedList() {this.head = null;this.tail = null;}public void addNode(Node<V> newNode) {if (newNode == null) {return;}if (this.head == null) {//頭空this.head = newNode;this.tail = newNode;} else {//頭不空this.tail.next = newNode;newNode.last = this.tail;//注意讓本節點前指針指向舊尾this.tail = newNode;//指向新尾}} /*某個點移到最后*/public void moveNodeToTail(Node<V> node) {if (this.tail == node) {//是尾return;}if (this.head == node) {//是頭this.head = node.next;this.head.last = null;} else {//中間node.last.next = node.next;node.next.last = node.last;}node.last = this.tail;node.next = null;this.tail.next = node;this.tail = node;} /*刪除第一個*/public Node<V> removeHead() {if (this.head == null) {return null;}Node<V> res = this.head;if (this.head == this.tail) {//就一個this.head = null;this.tail = null;} else {this.head = res.next;res.next = null;this.head.last = null;}return res;}}鏈表操作封裝完了就要實現這個結構了。
具體思路代碼注釋
public static class MyCache<K, V> {//為了kv or vk都能查private HashMap<K, Node<V>> keyNodeMap;private HashMap<Node<V>, K> nodeKeyMap;//用來做優先級private NodeDoubleLinkedList<V> nodeList;private int capacity;//容量public MyCache(int capacity) {if (capacity < 1) {//你容量連1都不給，搗亂呢throw new RuntimeException("should be more than 0.");}this.keyNodeMap = new HashMap<K, Node<V>>();this.nodeKeyMap = new HashMap<Node<V>, K>();this.nodeList = new NodeDoubleLinkedList<V>();this.capacity = capacity;}public V get(K key) {if (this.keyNodeMap.containsKey(key)) {Node<V> res = this.keyNodeMap.get(key);this.nodeList.moveNodeToTail(res);//使用過了就放到尾部return res.value;}return null;}public void set(K key, V value) {if (this.keyNodeMap.containsKey(key)) {Node<V> node = this.keyNodeMap.get(key);node.value = value;//放新vthis.nodeList.moveNodeToTail(node);//我們認為放入舊key也是使用過} else {Node<V> newNode = new Node<V>(value);this.keyNodeMap.put(key, newNode);this.nodeKeyMap.put(newNode, key);this.nodeList.addNode(newNode);//加進去if (this.keyNodeMap.size() == this.capacity + 1) {this.removeMostUnusedCache();//放不下就去掉優先級最低的}}}private void removeMostUnusedCache() {//刪除頭Node<V> removeNode = this.nodeList.removeHead();K removeKey = this.nodeKeyMap.get(removeNode);//刪除掉兩個map中的記錄this.nodeKeyMap.remove(removeNode);this.keyNodeMap.remove(removeKey);}}?
2.4.2Redis中的LRU算法改進
redis通常使用緩存，是使用一種固定最大內存的使用。當數據達到可使用的最大固定內存時，我們需要通過移除老數據來獲取空間。redis作為緩存是否有效的重要標志是如何尋找一種好的策略：刪除即將需要使用的數據是一種糟糕的策略，而刪除那些很少再次請求的數據則是一種好的策略。
在其他的緩存組件還有個命中率，僅僅表示讀請求的比例。訪問一個緩存中的keys通常不是分布式的。然而訪問經常變化，這意味著不經常訪問，相反，有些keys一旦不流行可能會轉向最經常訪問的keys。 因此，通常一個緩存系統應該盡可能保留那些未來最有可能被訪問的keys。針對keys淘汰的策略是：那些未來極少可能被訪問的數據應該被移除。
但有一個問題：redis和其他緩存系統不能夠預測未來。
LRU算法
緩存系統不能預測未來，原因是：那些很少再次被訪問的key也很有可能最近訪問相當頻繁。如果經常被訪問的模式不會突然改變，那么這是一種很有效的策略。然而，“最近經常被訪問”似乎更隱晦地標明一種 理念。這種算法被稱為LRU算法。最近訪問頻繁的key相比訪問少的key有更高的可能性。
舉個例子，這里有4個不同訪問周期的key，每一個“~”字符代表一秒，結尾的“|”表示當前時刻。
A key每5秒請求一次，B周期是2秒，C、D都是10秒。
訪問頻率最高的是B，因為它的空閑時間最短，這意味著B是4個key中未來最有可能被訪問的key。
同樣的A和C目前的空閑時間是2s和6s也能很好地反映它們本身的周期。然而你可以看到不夠嚴謹：D的訪問周期是10秒，但它卻是4個key中最近被訪問的。
當然，在一個很長的運行周期中，LRU算法能工作得很好。通常有一個更高訪問頻率的key當然有一個更低的空閑周期。LRU算法淘汰最少被訪問key，那些有最大空閑周期的key。實現上也相當容易，只需要額外跟蹤最近被訪問的key即可，有時甚至都需要：把所有我們想要淘汰的對象放到一個鏈表中，當一個對象訪問就移除鏈表頭部元素，當我們要淘汰元素是就直接淘汰鏈表尾部開始。
redis中的LRU:起因
最初，redis不支持LRU算法。當內存有效性成為一個必須被解決的問題時，后來才加上了。通過修改redis對象結構，在每個key對象增加24bit的空間。沒有額外的空間使用鏈表把所有對象放到一個鏈表中（大指針），因此需要實現得更加有效，不能因為key淘汰算法而讓整個服務改動太大。
24bits的對象已經足夠去存儲當前的unxi時間戳。這個表現，被稱為“LRU 時鐘”，key元數據經常被更新，所以它是一個有效的算法。
然后，有另一個更加復雜的問題需要解決：如何選擇訪問間隔最長的key，然后淘汰它。
redis內部采用一個龐大的hash table來保存，添加另外一個數據結構存儲時間間隔顯然不是一個好的選擇。然而我們希望能達到一個LRU本身是一個近似的，通過LRU算法本身來實現。
redis原始的淘汰算法簡單實現：**當需要淘汰一個key時，隨機選擇3個key，淘汰其中間隔時間最長的key。**基本上，我們隨機選擇key，淘汰key效果很好。后來隨機3個key改成一個配置項"N隨機key"。但把默認值提高改成5個后效果大大提高。考慮到它的效果，你根本不用修改他。
然而，你可能會想這個算法如何有效執行，你可以看到我們如何搗毀了很多有趣的數據。也許簡單的N key，我們會遇到很多好的決策，但是當我們淘汰最好的，下一個周期又開始抓。
驗證規則第一條：用肉眼觀察你的算法
其中有一個觀點已經應用到Redis 3.0正式版中了。在redis2.8中一個LRU緩存經常被使用在多個環境，用戶關于淘汰的沒有抱怨太多，但是很明顯我可以提高它，通過不僅僅是增加額外的空間，還有額外的CPU時間。
然而為了提高某項功能，你必須觀察它。有多個不同的方式去觀察LRU算法。你可以通過寫工具觀察，例如模擬不同的工作負載、校驗命中率和失誤率。
程序非常簡單：增加一些指定的keys，然后頻繁地訪問這些keys以至于每一個key都有一個下降的空閑時間。最終超過50%的keys被增加，一半的老key需要被淘汰。
一個完美理想的LRU實現，應該是沒有最新加的key被淘汰，而是淘汰最初的50%的老key。
規則二：不要丟棄重要信息
借助最新的可視化工具，我可以在嘗試新的方法觀察和測試幾分鐘。使用redis最明顯有效的提高算法就是，積累對立的垃圾信息在一個淘汰池中。
基本上，當N keys算法被采用時，通常會分配一個很大的線程pool（默認為16key），這個池按照空閑時間排序，所以只有當有一個大于池中的一個或者池為空的時候，最新的key只會進入到這個池中。
同時，一個新的redis-cli模式去測量LRU算法也增加了(看這個-lru-test選項)。
還有另外一個方式去檢驗LRU算法的好壞，通過一個冪等訪問模式。這個工具通常校驗用一個不同的測試，新算法工作工作效果好于真實世界負載。它也同樣使用流水線和每秒打印訪問日志，因此可以被使用不用為了基準不同的思想，至少可以校驗和觀察明顯的速度回歸。
規則三、最少使用原則（LFU算法）
一切源于一個開放性問題：但你有多個redis 3.2數據庫時，而淘汰算法只能在本機選擇。因此，假如你全部空閑小的key都是DB0號機器，空閑時間長的key都是1號機器，redis每臺機器都會淘汰各自的key。一個更好的選擇當然是先淘汰DB1，最后再淘汰DB0。
當redis被當作緩存使用時很少有情況被分成不同的db上，這不是一個好的處理方式。然而這也是我為什么我再一次修改淘汰代碼的原因。最終，我能夠修改緩存池包括數據庫id，使用單緩存池為多個db，代替多緩存池。這種實現很麻煩，但是通過優化和修改代碼，最終它比普通實現要快到20%。
然而這時候，我對這個redis緩存淘汰算法的好奇心又被點燃。我想要提升它。我花費了幾天想要提高LRU算法實現：或許可以使用更大的緩存池？通過歷史時間選擇最合適被淘汰的key？
經過一段時間，通過優化我的工具，我理解到：LRU算法受限于數據庫中的數據樣本，有時可能相反的場景效果非常好，因此要想提高非常非常難。實際上，能通過展示不同算法的圖片上看這有點非常明顯：每個周期10個keys幾乎和理論的LRU算法表現一致。
當原始算法很難提高時，我開始測試新的算法。 如果我們倒回到博客開始，我們說過LRU實際上有點嚴格。哪些key需要我們真正想要保留：將來有最大可能被訪問，最頻繁被訪問，而不是最近被訪問的key。
淘汰最少被訪問的key算法成為：LFU（Least Frequently Used），將來要被淘汰騰出新空間給新key。
理論上LFU的思想相當簡單，只需要給每個key加一個訪問計數器。每次訪問就自增1，所以也就很容易知道哪些key被訪問更頻繁。
當然，LFU也會帶起其他問題，不單單是針對redis，對于LFU實現：
1、不能使用“移除頂部元素”的方式，keys必須要根據訪問計數器進行排序。每訪問一次就得遍歷所有key找出訪問次數最少的key。
2、LFU不能僅僅是只增加每一訪問的計數器。正如我們所講的，訪問模式改變隨時變化，因此一個有高訪問次數的key，后面很可能沒有人繼續訪問它，因此我們的算法必須要適應超時的情況。
在redis中，第一個問題很好解決：我們可以在LRU的方式一樣：隨機在緩存池中選舉，淘汰其中某項。第二個問題redis還是存在，因此一般對于LFU的思想必須使用一些方式進行減少，或者定期把訪問計數器減半。
24位的LFU實現
LFU有它本身的實現，在redis中我們使用自己的24bit來記錄LRU。
為了實現LFU僅僅需要在每個對象額外新增24bit：
1、一部分用于保存訪問計數器；
2、足夠用于決定什么時候將計數器減半的信息；
我的解決方法是把24bit分成兩列：
16bits8bitslast decr timeLOG_C
16位記錄最后一次減半時間，那樣redis知道上一次減半時間，另外8bit作為訪問計數器。
你可能會想8位的計數器很快就會溢出，是的，相對于簡單計數器，我采用邏輯計數器。邏輯計數器的實現：
基本上計數器的較大者，更小的可能計數器會增加：上面的代碼計算p位于0~1之間，但計數器增長時會越來越小，位于0-1的隨機數r，只會但滿足r<p時計數器才會加一。
你可以配置計數器增長的速率，如果使用默認配置，會發生：
- 100次訪問后，計數器=10；
- 1000次訪問是是18；
- 10萬次訪問是142；
- 100萬次訪問后達到255，并不在繼續增長；
下面，讓我們看看計數器如果進行衰減。16位的被儲存為unix時間戳保留到分鐘級別，redis會隨機掃描key填充到緩存池中，如果最后一個下降的時間大于N分鐘前（可配置化），如果計數器的值很大就減半，或者對于值小的就直接簡單減半。
這里又衍生出另外一個問題，就是新進來的key是需要有機會被保留的。由于LFU新增是得分都是0，非常容易被選舉替換掉。在redis中，開始默認值為5。這個初始值是根據增長數據和減半算法來估算的。模擬顯示得分小于5的key是首選。
代碼和性能
上面描述的算法已經提交到一個非穩定版的redis分支上。我最初的測試顯示：它在冪等模式下優于LRU算法，測試情況是每個key使用用相同數量的內存，然而真實世界的訪問可能會有很大不同。時間和空間都可能改變得很不同，所以我會很開心去學習觀察現實世界中LFU的性能如何，兩種方式在redis實現中對性能的改變。
因此，新增了一個OBJECT FREQ子命令，用于報告給定key的訪問計數器，不僅僅能有效提觀察一個計數器，而且還能調試LFU實現中的bug。
注意運行中切換LRU和LFU，剛開始會隨機淘汰一些key，隨著24bit不能匹配上，然而慢慢會適應。 還有幾種改進實現的可能。Ben Manes發給我這篇感興趣的文章，描述了一種叫TinyLRU算法。鏈接
這篇文章包含一個非常厲害的觀點：相比于記錄當前對象的訪問頻率，讓我們（概率性地）記錄全部對象的訪問頻率，看到了，這種方式我們甚至可以拒絕新key，同樣，我們相信這些key很可能得到很少的訪問，所以一點也不需要淘汰，如果淘汰一個key意味著降低命中/未命中率。
我的感覺這種技術雖然很感興趣GET/SET LFU緩存，但不適用與redis性質的數據服務器：用戶期望keys被創建后至少存在幾毫秒。拒絕key的創建似乎在redis上就是一種錯誤。
然而，redis保留了LFU信息，當一個key被覆蓋時，舉個例子：
24位的LFU計數器會從老的key復制到新對象中。
新的redis淘汰算法不穩定版本還有以下幾個好消息：
1、跨DB策略。在過去的redis只是基于本地的選舉，現在修復為所有策略，不僅僅是LRU。
2、易變ttl策略。基于key預期淘汰存活時間，如今就像其他策略中的使用緩存池。
3、在緩存池中重用了sds對象，性能更好。
這篇博客比我預期要長，但是我希望它反映出一個見解：在創新和對于已經存在的事物實現上，一種解決方案去解決一個特定問題，一個基礎工具。由開發人員以正確的方式使用它。許多redis的用戶把redis作為一個緩存的解決方案，因此提高淘汰策略這一塊經常一次又一次被拿出來探討。
2.6對象
剛寫了redis主要的數據結構：
動態字符串、雙端鏈表、字典、壓縮列表、整數集合、跳表等
redis肯定不能直接使用這些數據結構來實現數據庫，它用這些數據庫建立了一個對象系統，包含：
字符串對象、列表對象、哈希對象、集合對象、有序集合對象
我們可以針對不同的使用場景，為對象設置多種分不同的數據結構實現，從而優化對象在不同場景下的效率。
1）鍵值對
對于redis的鍵值對來說：key只有字符串類型，而v可以是各種類型，
我們習慣把“這個鍵所對應的值是一個列表”表達為這是一個“列表鍵。
TYPE?命令的實現方式也與此類似， 當我們對一個數據庫鍵執行?TYPE?命令時， 命令返回的結果為數據庫鍵對應的值對象的類型， 而不是鍵對象的類型：
# 鍵為字符串對象，值為列表對象redis> RPUSH numbers 1 3 5 (integer) 6redis> TYPE numbers list2）對象
我們看一下redis對象的組成：
typedef struct redisObject {// 類型unsigned type:4;// 編碼unsigned encoding:4;// 指向底層實現數據結構的指針void *ptr;// ... } robj;通過?encoding?屬性來設定對象所使用的編碼， 而不是為特定類型的對象關聯一種固定的編碼， 極大地提升了 Redis 的靈活性和效率， 因為 Redis 可以根據不同的使用場景來為一個對象設置不同的編碼， 從而優化對象在某一場景下的效率。
字符串對象
字符串對象的編碼可以是?int?、?raw?或者?embstr?。
如果一個字符串對象保存的是整數值， 并且這個整數值可以用?long?類型來表示， 那么字符串對象會將整數值保存在字符串對象結構的?ptr屬性里面（將?void*?轉換成?long?）， 并將字符串對象的編碼設置為?int?。
如果字符串對象保存的是一個字符串值， 并且這個字符串值的長度大于?39?字節， 那么字符串對象將使用一個簡單動態字符串（SDS）來保存這個字符串值， 并將對象的編碼設置為?raw?。
如果字符串對象保存的是一個字符串值， 并且這個字符串值的長度小于等于?39?字節， 那么字符串對象將使用?embstr?編碼的方式來保存這個字符串值。
embstr?編碼是專門用于保存短字符串的一種優化編碼方式， 這種編碼和?raw?編碼一樣， 都使用?redisObject?結構和?sdshdr?結構來表示字符串對象，但?raw?編碼會調用兩次內存分配函數來分別創建?redisObject?結構和?sdshdr?結構，而?embstr?編碼則通過調用一次內存分配函數來分配一塊連續的空間， 空間中依次包含?redisObject?和?sdshdr?兩個結構。
?embstr?編碼有以下好處：
3）列表對象
列表對象的編碼可以是?ziplist?或者?linkedlist?。
當列表對象可以同時滿足以下兩個條件時， 列表對象使用?ziplist?編碼：
不能滿足這兩個條件的列表對象需要使用?linkedlist?編碼。
4）哈希對象
哈希對象的編碼可以是?ziplist?或者?hashtable?。
當哈希對象可以同時滿足以下兩個條件時， 哈希對象使用?ziplist?編碼：
不能滿足這兩個條件的哈希對象需要使用?hashtable?編碼。
5）集合對象
集合對象的編碼可以是?intset?或者?hashtable?。
當集合對象可以同時滿足以下兩個條件時， 對象使用?intset?編碼：
不能滿足這兩個條件的集合對象需要使用?hashtable?編碼。
6）有序集合對象
有序集合的編碼可以是?ziplist?或者?skiplist?。
當有序集合對象可以同時滿足以下兩個條件時， 對象使用?ziplist?編碼：
不能滿足以上兩個條件的有序集合對象將使用?skiplist?編碼。
這里多說兩句，各個語言的對象其實都差不多，底層實現也就那幾個，比如java中的容器，c++的STL。java的hashset就是一個哈希而已，hashmap就是k帶了一個v，而”有序的“Treemap使用了紅黑樹這種有平衡性的搜索二叉樹。
redis的有序集合并沒有再采取hash+紅黑樹的操作，而是把平衡樹換成了跳表，實際上性能真的沒差多少，甚至有時比紅黑樹有優勢，比如跳表的性能較為平均，紅黑樹攢了很多次不平衡要調整可能會帶來資源需求的一個高峰，再加上跳表實現簡單的優點，紅黑樹真的沒什么優勢。
并且就算是真的想用一種帶平衡性的搜索樹，現在競賽也是用的華人之光發明的SB樹。
有序集合的優點就是它的有序操作，比如拿最大最小值，紅黑樹時間o(logN),而哈希表只能一個一個遍歷。缺點在于插入一個值的時間也是o(logN),跳表也是。而哈希表插入數是o(1).
要了解底層和這些優缺點
總結
以上是生活随笔為你收集整理的《三天给你聊清楚redis》第1天先唠唠redis是个啥（18629字）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python 等差数列_413. 等差数
- 下一篇： 如何获得onblur中的值_js中onf