Redis 數據結構與內存管理策略（上）
Redis 數據類型特點與使用場景
String、List、Hash、Set、Zset
案例：滬江團購系統大促hot-top介面cache設計
Redis 內存數據結構與編碼
OBJECTencoding key、DEBUG OBJECTkey
簡單動態字元串（simple dynamic string）
鏈表（linked list）
字典（dict）
跳錶（skip list）
整數集合（int set）
壓縮表（zip list）
Redis Object 類型與映射
Redis 內存管理策略
鍵 過期時間、生存時間
過期鍵刪除策略
AOF、RDB處理過期鍵策略
RedisLRU演算法
Redis 持久化方式
AOF(Append-only file)
RDB(Redis DataBase)
Redis 數據類型特點與使用場景
redis為我們提供了5種數據類型，基本上我們使用頻率最高的就是string，而對其他四種數據類型使用的頻次稍弱於string。
一方面是由於string使用起來比較簡單，可以方便存儲複雜大對象，使用場景比較多。還有一個原因就是由於redis expire time只能設置在key上，像list、hash、set、zset屬於集合類型，會管理一組item，我們無法在這些集合的item上設置過期時間，所以使用expire time來處理集合的cache失效會變得稍微複雜些。但是string使用expire time來管理過期策略會比較簡單，因為它包含的項少。這裡說的集合是寬泛的類似集合。
導致我們習慣性的使用string而忽視其他四種數據類型的另一個深層次原因，大多是由於我們對另外四種數據類型的使用和原理不是太了解。這個時候往往會忽視在特定場景下使用某種數據類型可能會比string性能高出很多，比如使用hash結構來提高某個實體的某個項的修改等。
這裡我們不打算羅列這5種數據類型的使用方法，這些資料網上有很多。我們主要討論這5種數據類型的功能特點，這些特點分別適合用於處理哪些現實的業務場景，最重要的是我們如何組合性的使用這5種數據類型來解決複雜的cache問題。
String、List、Hash、Set、ZsetString
string是redis提供的字元串類型。可以針對string類型獨立設置expire time。通常用來存儲長字元串數據，比如，某個對象的json字元串。
string類型我們在使用上最巧妙的是可以動態拼接key。通常我們可以將一組id放在set里，然後動態查找string還是否存在，如果不存在說明已經過期或者由於數據修改主動delete了，需要再做一次cache數據load。
雖然set無法設置item的過期時間，但是我們可以將set item與string key關聯來達到相同的效果。
上圖中的左邊是一個key為set:order:ids的set集合，它可能是一個全量集合，也可能是某個查詢條件獲取出來的一個集合。
有時候複雜點的場景需要多個set集合來支撐計算，在redis 伺服器里可能會有很多類似這樣的集合。
這些集合我們可以稱為功能數據，這些數據是用來輔助cache計算的，當進行各種集合運算之後會得出當前查詢需要返回的子集，最後我們才會去獲取某個訂單真正的數據。
這些string:order:字元串key並不一定是為了服務一種場景，而是整個系統最底層的數據，各種場景最後都需要獲取這些數據。那些set集合可以認為是查詢條件數據，用來輔助查詢條件的計算。
redis為我們提供了TYPE命令來查看某個key的數據類型，如：string類型：
List
list在提高throughput的場景中非常適用，因為它特有的LPUSH、RPUSH、LPOP、RPOP功能可以無縫的支持生產者、消費者架構模式。
這非常適合實現類似Java ConcurrencyFork/Join框架中的work-stealing 演算法 (工作竊取)。
java fork/join框架使用並行來提高性能，但是會帶來由於並發take task帶來的race condition (競態條件)問題，所以採用work-stealing 演算法來解決由於競爭問題帶來的性能損耗。
上圖中模擬了一個典型的支付callback峰值場景。在峰值出現的地方一般我們都會使用加buffer的方式來加快請求處理速度，這樣才能提高並發處理能力，提高throughput。
支付gateway收到callback之後不做任何處理直接交給分發器。分發器是一個無狀態的cluster，每個node通過向註冊中心pull handler queue list，也就是獲取下游處理器註冊到註冊中心裡的消息通道。
每一個分發器node會維護一個本地queue list，然後順序推送消息到這些queue list即可。這裡會有點小問題，就是支付gateway調用分發器的時候是如何做load balance，如果不是平均負載可能會有某個queue list高出其他queue list。
而分發器不需要做soft load balance，因為哪怕某個queue list比其他queue list多也無所謂，因為下游message handler會根據work-stealing演算法來竊取其他消費慢的queue list。
redis list 的LPUSH、RPUSH、LPOP、RPOP特性確實可以在很多場景下提高這種橫向擴展計算能力。
Hash
hash數據類型很明顯是基於hash演算法的，對於項的查找時間複雜度是O(1)的，在極端情況下可能出現項hash衝突問題，redis內部是使用鏈表加key判斷來解決的。具體redis內部的數據結構我們在後面有介紹，這裡就不展開了。
hash數據類型的特點通常可以用來解決帶有映射關係，同時又需要對某些項進行更新或者刪除等操作。如果不是某個項需要維護，那麼一般可以通過使用string來解決。
如果有需要對某個欄位進行修改，使用string很明顯是會多出很多開銷，需要讀取出來反序列化成對象然後操作，然後再序列化寫回redis，這中間可能還有並發問題。
那我們可以使用redis hash提供的實體屬性hash存儲特性，我們可以認為hash value是一個hash table，實體的每一個屬性都是通過hash得到屬性的最終數據索引。
上圖使用hash數據類型來記錄頁面的a/b metrics，左邊的是首頁index的各個區域的統計，右邊是營銷marketing的各個區域統計。
在程序里我們可以很方便的使用redis的atomic特性對hash某個項進行累加操作。
使用redis hash increment進行原子增加操作。HINCRBY命令可以原子增加任何給定的整數，也可以通過HINCRBYFLOAT來原子增加浮點類型數據。
Set
set集合數據類型可以支持集合運算，不能存儲重複數據。
set最大的特點就是集合的計算能力，inter 交集、union 並集、diff 差集，這些特點可以用來做高性能的交叉計算或者剔除數據。
set集合在使用場景上還是比較多和自由的。舉個簡單的例子，在應用系統中比較常見的就是商品、活動類場景。用一個set緩存有效商品集合，再用一個set緩存活動商品集合。如果商品出現上下架操作只需要維護有效商品set，每次獲取活動商品的時候需要過濾下是否有下架商品，如果有就需要從活動商品中剔除。
當然，下架的時候可以直接刪除緩存的活動商品，但是活動是從marketing系統中load出來的，就算我將cache里的活動商品刪除，當下次再從marketing系統中load活動商品時候還是會有下架商品。當然這只是舉例，一個場景有不同的實現方法。
上圖中左右兩邊是兩個不同的集合，左邊是營銷域中的可用商品ids集合，右邊是營銷域中活動商品ids集合，中間計算出兩個集合的交集。
在一些複雜的場景中，也可以使用SINTERSTORE命令將交集計算後的結果存儲在一個目標集合中。 這在使用pipeline命令管道中特別有用，將SINTERSTORE命令包裹在pipeline命令串中可以重複使用計算出來的結果集。
由於redis是Signle-Thread 單線程模型，基於這個特性我們就可以使用redis提供的pipeline 管道來提交一連串帶有邏輯的命令集合，這些命令在處理期間不會被其他客戶端的命令干擾。
Zset
zset排序集合與set集合類似，但是zset提供了排序的功能。在介紹set集合的時候我們知道set集合中的成員是無序的，zset填補了集合可以排序的空隙。
zset最強大的功能就是可以根據某個score 比分值進行排序，這在很多業務場景中非常急需。比如，在促銷活動里根據商品的銷售數量來排序商品，在旅遊景區里根據流入人數來排序熱門景點等。
基本上人們在做任何事情都需要根據某些條件進行排序。
其實zset在我們應用系統中能用到地方到處都是，這裡我們舉一個簡單的例子，在團購系統中我們通常需要根據參團人數來排序成團列表，大家都希望參加那些即將成團的團。
上圖是一個根據團購code創建的zset，score 分值就是參團人數累加和。
zset本身提供了很多方法用來進行集合的排序，如果需要score分值可以使用withscore字句帶出每一項的分值。
在一些比較特殊的場合可能需要組合排序，可能有多個zset分別用來對同一個實體在不同維度的排序，按時間排序、按人數排序等。這個時候就可以組合使用zset帶來的便捷性，利用pipeline再結合多個zset最終得出組合排序集合。
案例：滬江團購系統大促hot-top介面cache設計
我們總結了redis提供的5種數據類型的各自特點和一般的使用場景。但是我們不僅僅可以分開使用這些數據類型，我們完全可以綜合使用這些數據類型來完成複雜的cache場景。
下面我們分享一個使用多個zset、string來優化團購系統前台介面的例子。由於篇幅和時間限制，這裡只介紹跟本次案例相關的信息。
hot-top介面是指熱點、排名介面的意思，表示它的瀏覽量、並發量比較高，一般大促的時候都會有幾個這種性能要求比較高的介面。
我們先來分析一個查詢介面所包含的常規信息。
首先一個查詢介面肯定是有query condition 查詢條件，然後是sort 排序信息、最後是page 分頁信息。這是一般介面所承擔的基本職責，當然，特殊場景下還需要支持master/slave replication時關於數據session 一致性的要求，需要提供跟蹤標記來回master查詢數據，這裡就不展開了。
我們可以抽象出這幾個維度的信息：
query condition
查詢條件，companyid=100，sellerid=1010101 諸如此類。
sort
排序信息，一般是默認一個列排序，但是在複雜的場景下會有可能讓介面使用者定製排序欄位，比如一些租戶信息列。
page
分頁信息，簡單理解就是數據記錄排完序之後的第幾行到第幾行。
由於這裡我們純粹用redis來提高cache能力，不涉及到有關於任何搜索的能力，所以這裡忽略其他複雜查詢的情況。其實我們在複雜的地方使用了elastcsearch來提高搜索能力。
上述我們分析總結出了一個查詢介面的基本信息，這裡還有一個有關於高並發介面的設計原則就是將hot-top介面和一般search介面分離開，因為只有分而治之才能分別根據特點選用不同的技術。如果我們不分職責將所有的查詢場景封裝在一個介面里，那麼在後面優化介面性能的時候基本就很麻煩了，有些場景是無法或者很難用cache來解決的，因為介面里耦合了各種場景邏輯，就算勉強能實現性能也不會高。
前面做這些鋪墊是為了能在介紹案例的時候達成一個基本的共識。現在我們來看下這個團購系統的hot-top介面的具體邏輯。
在大促的時候需要展現團購列表，這個介面的訪問量是非常大的，團購活動需要根據參團人數倒序排序，並且分頁返回指定數量的團列表。
我們假設這個介面名為getTopGroups(getTopGroupsRequest request)
query condition 查詢條件問題
我們來仔細分析下，首先不同的查詢條件從DB里查詢出來的數據是不一樣的，也就是說查詢出來的團列表是不一樣的，可能有company 公司、channel 渠道等過濾條件。由於一個團購活動下不會有太多團，頂多上百個是極限了，所以一個查詢條件出來的團列表也頂多幾十個，而且根據場景分析熱點查詢條件不會超過十個，所以我們選擇將查詢條件 hash出一個code來緩存本次查詢條件的全量團列表集合，但是這些結果集是沒有任何排序的。
sort 排序問題
再看根據參團人數排序問題，我們立刻就可以想到使用zset來處理團排序問題，因為只有一個排序維度，所以一個zset就夠了。我們使用一個zset來緩存所有團的參團人數集合，它是一個全量的團排序集合。
那麼我們如何將用戶的查詢條件出來的團列表根據參團人數排序尼，剛好可以使用zset的交集運算直接計算出當前這個集合的zset子集。
page 分頁問題
通過對已經排序之後的團列表zset使用zrange來獲取出分頁集合。
我們來看下完整的流程，如何處理查詢、排序、分頁的。
上圖從query condition計算hash code，然後通過DB查詢出當前條件全量團列表。
zset:marketing:groupon:hottop:available:group key表示全量團的參團人數，用一個zset來緩存。接著將這兩個zset計算交集，就可以得出當前查詢所需要的帶有參團人數的zset，最後在使用zrevrange獲取分頁區間。
有了返回的團code集合之後就可以通過mget來批量獲取string類型的團詳情信息，這裡就不貼出代碼了。
由於篇幅和時間關係，這裡就不展開太多的業務場景介紹了。這其中還涉及到計算cache過期時間的問題，這也跟促銷活動的運營規則有關係，還涉及到有可能query condition hash衝突問題等，但是這些已經不與我們本節主題相關。
Redis 內存數據結構與編碼
我們已經了解了redis提供的5種數據類型，那麼redis內部到底是如何支持這5種數據類型的，也就是說redis到底是使用什麼樣的數據結構來存儲、查找我們設置在內存中的數據。
雖然我們使用5種數據類型來緩存數據，但是redis會根據我們存儲數據的不同而選用不同的數據結構和編碼。
我們日常使用的是redis提供的5種數據類型，但是這5種數據類型在內存中的數據結構和編碼有很多種。隨著我們存儲的數據類型的不同、數據量的大小不同都會引起內存數據結構的動態調整。
本節只是做數據結構和編碼的一般性介紹，不做過多細節討論，一方面是關於redis源碼分析的資料網上有很多，還有一個原因就是redis每一個版本的實現有很大差異，一旦展開細節討論每一個點每一個數據結構都會很複雜，所以我們這裡就不展開討論這些，只是起到拋磚引玉作用。
OBJECTencoding key、DEBUG OBJECTkey
我們知道使用type命令可以查看某個key是否是5種數據類型之一，但是當我們想查看某個key底層是使用哪種數據結構和編碼來存儲的時候可以使用OBJECT encoding命令。
同樣一個key，但是由於我們設置的值不同而redis選用了不同的內存數據結構和編碼。雖然redis提供的string數據類型，但是redis會自動識別我們cache的數據類型是int還是string。
如果我們設置的是字元串，且這個字元串長度不大於39位元組那麼將使用embstr來編碼，如果大於39位元組將使用raw來編碼。redis 4.0將這個閥值擴大了45個位元組。
TAG:深度訓練 |