《深入分布式緩存》之談一談SNS關系設計的演進

版權聲明：本文為半吊子子全棧工匠（wireless_com，同公衆号)原創文章，未經允許不得轉載。 https://blog.csdn.net/wireless_com/article/details/79258584

我們先從最簡單的設計開始。

基于DB的最簡方案

表達使用者資訊和互相關系，基于DB隻需要兩張表可實作，示意如圖12-2：

圖12-2 使用者資訊與使用者關系表示意圖

relation表主要有兩個字段followerId和followeeId，一行relation記錄表示使用者關系拓撲的一條邊，由followerId代表的使用者指向followeeId代表的使用者。

userInfo表關注每個使用者的詳細資訊，比如使用者名、注冊時間等描述資訊。它可以是多個字段，本示例為了簡化描述，統一将這些描述資訊簡化成一個字段。

1. 場景實作

基于relation相關的展示和操作可以如下方式實作。

1）某使用者（例如使用者B）timeline/feed頁面的relation摘要資訊展示，可以通過兩條SQL實作：

SELECT COUNT(*) FROM table_relation WHEREfollowerId=’userB’;

SELECT COUNT(*) FROM table_relation WHEREfolloweeId=’userB’;

上述兩條語句分别展示出了userB的follower和followee數量。

2）某使用者（例如使用者B）relation頁面詳細資訊展示，分成兩個子頁面：follower清單展示和followee清單展示：

SELECT followeeId FROM table_relation WHERE followerId=’userB’;

SELECT userId,userInfo FROM table_user_info

WHERE userId IN (#followeeId#...);

SELECT followerId FROM table_relation WHEREfolloweeId=’userB’;

WHERE userId IN (#followerId#...);

上述四條語句分别展示被使用者B關注的使用者和關注使用者B的使用者清單。

3）某使用者（例如使用者B）關注/取消關注某使用者（例如使用者C）：

INSERT INTO table_relation (followerId,followeeId)

VALUES (‘userB’,’userC’) ;

DELETE FROM table_relation

WHERE followerId=’userB’ and followeeId=’userC’

2. 問題引入

随着使用者數量的增加，table_relation/info表的行數膨脹。如前述小節描述的那樣，億級的使用者，每個使用者相關關系百級，那麼table_relation的行數将膨脹到百億級别，info表膨脹到億級。由此，表的水準拆分（sharding）勢在必行。

水準拆分需要根據表的某個字段做為拆分字段，例如info表的拆分以userId為拆分字段進行，如圖12-3所示：

圖12-3 info 表拆分示例

對于某個使用者的資訊查詢，首先根據userId計算出它的資料在哪個分片，再在對應分片的info表裡查詢到相關資料。userId到分片的映射關系有多種方式，例如hash取模，userId字段的某幾個特殊位，hash取模的一緻性hash映射等，本章不展開。

對于info表，水準拆分字段的選取較為明确，選取userId即可。但是對relation的水準拆分，如何選取拆分字段顯得不那麼簡單了，如圖12-4所示。

圖12-4 最簡版本水準拆分後的問題

假設根據followerId進行拆分，查詢某個使用者關注的人顯得容易，因為相同followerId的資料一定分布在相同分片上；但是一旦需要查詢誰關注了某個使用者，這樣的查詢需要路由到所有分片上進行，因為相同followeeId的資料分散在不同的分片上，查詢效率低。由于對于某個使用者，查詢它的關注者和關注他的使用者的通路量是相似的，是以無論根據followerId還是followeeId進行拆分，總會有一半的場景查詢效率低下。

我們在此基礎上優化DB的table_relation表方案，使之适應sharding。

DB的sharding方案

經過優化後的relation設計如圖12-5 所示：

圖12-5經過優化後的relation設計

首先将原有的relation表垂直拆分為followee表和follower表，分表記錄某個使用者的關注者和被關注者，接下來再對followee和follower兩張表分别基于userId進行水準拆分。

相對于上節的實作方案，sharding後的relation相關操作中，變化的部分如下。

calculate sharding slide index by userB

SELECT COUNT(*) FROM table_followee_xx WHERE userId=’userB’;

SELECT COUNT(*) FROM table_follower_xx WHERE userId=’userB’;

針對使用者B的關系數量查詢可以落在相同分片上進行，是以一次展示隻需要查詢兩次DB。

SELECT followeeId FROM table_followee WHEREfollowerId=’userB’;

SELECT followerId FROM table_follower WHEREfolloweeId=’userB’;

calculate sharding slide index by follower/followeeIds

WHERE userId IN (#followerId#...,#followerId#);

上述三條語句分别展示被使用者B關注的使用者和關注使用者B的使用者清單，其中前兩條可以基于落在相同分片上，DB操作次數為兩次，但最後一條仍需查詢多次DB，我們下文繼續讨論如何優化它。

3）某使用者（例如使用者B）關注某使用者（例如使用者C）：

START TRANSACTION;

INSERT INTO table_follower (userId,followerId)

INSERT INTO table_followee (userId,followeeId)

COMMIT

上述關注使用者的操作由上節所述方案的一條變成了兩條，并且包裝在一個事務中。寫入量增加了一倍，但由于水準拆分帶來的DB能力的提升遠遠超過一倍，是以實際吞吐量的提升仍然能夠做到随着分片數量線性增加。

上述對relation表的查詢操作仍然需要進行count，即使在userId上建了索引仍然存在風險：

q  對于某些使用者，他們被很多人關注（例如大V類使用者），他們在對follower表進行count查詢時，需要在userId上掃描的行數仍然很多，我們稱這些使用者為熱點使用者。每一次展示熱點使用者的關注者數量的操作都是低效的。另一方面，熱點使用者由于被很多使用者關注，它的timeline頁面會被更頻繁的通路，使得原本低效的展示操作總是被高頻的通路，性能風險進一步放大。

q  當某個使用者的follower較多時，通常在relation頁面裡無法一頁展示完，是以需要進行分頁顯示，每一頁顯示固定數量的使用者。然而DB實作分頁時，掃描效率随着offset增加而增加，使得這些熱點使用者的relation頁展示到最後幾頁時，變的低效。

q  使用者詳細資訊的展示，每次展示relation頁面時，需要對每個follower或者followee分别查詢info表，使得info的查詢服務能力無法随着info分片線性增加。

 引入緩存

針對上節所述三個問題，我們首先引入緩存，資料劃分如圖12-6所示：

圖12-6 資料劃分

在DB層，增加userInfo表的備援資訊，将每個使用者的關注者和被關注者的數量存入DB。這樣一來，對于timeline和feed頁的relation摘要展示僅僅通過查詢userInfo表即可完成。

同時引入緩存層，需要注意的是，與關系相關的兩張表，在緩存層對應的value變成了清單，這樣做有兩個原因：

q   清單的存儲使得查詢可以一次IO完成，無需像資料庫那樣經過二級索引依次掃描相同key對應的所有行。然而資料庫很難做到以list做為value的類型并且很好地支撐list相關的增删操作

q   緩存是key-value結構，相同的userId難以分為多個key存儲并且還能保證它們高效掃描（緩存的沒有DB中的基于key字首的range掃描）

同時userInfo和userCnt相關資訊也分别放入了不同的緩存表中，将DB的一張表分為兩張緩存表，原因是info資訊和cnt資訊的展示場景不同，不同key的頻度也不同。

在最上層，對通路量極高的使用者的info資訊進行伺服器端的本地緩存。

引入緩存之後的業務操作實作方式也響應做了調整：

1）某使用者（例如使用者B）timeline/feed頁面的relation摘要資訊展示：展示方式變成了首先根據使用者B做為key查詢緩存，未命中時，再查詢DB

q   同樣首先查詢follower和followee的緩存，對于頻繁被查詢的熱點使用者，它的資料一定在緩存中，由此将DB資料量最多、通路頻度最高的使用者擋在緩存外

q   對于每個使用者的info資訊，熱點使用者由于被更多的使用者關注，他更有可能在詳情頁面被查詢到，是以這類使用者總是在本地緩存中能夠查詢到。同時，本地緩存設定一個不長的過期時間，使得它和分布式緩存層或者資料庫層的資料不會長時間不同步。過期時間的設定和存放本地緩存的伺服器數量相關。

q   每一次插入/删除DB的記錄時，同時需要對對應緩存的list進行變更。我們可以利用Redis的list/set類型value的原子操作，在一次Redis互動内實作list/set的增删。同時在DB的一個事務中，同時更新userInfo表的cnt字段。

q   DB和緩存無法共處于同一個ACID的事務，是以當DB更新之後的緩存更新，通過在DB和緩存中引入兩張變更表即可保證更新事件不丢失：DB每次變更時，在DB的事務中向變更表插入一條記錄，同時有一個唯一的變更ID或者叫版本号，随後再在緩存中進行修改時，同時也設定這個版本号，再回過來删除DB的這條變更記錄。如果緩存更新失敗，通過引入定時任務補償的方式保證變更一定會同步到緩存。

relation的相關操作通過緩存和DB備援的方式基本解決了，但仍然遺留了兩個問題：

1）熱點使用者的follower詳情頁查詢資料量問題。熱點使用者由于有過長的緩存list，它們每次被查詢到的時候有着極高的網絡傳輸量，同時因為熱點，它的查詢頻度也更高，加重了網絡傳輸的負擔。

2）info查詢的multi-key問題仍然沒有完全解決，雖然對熱點使用者本地緩存的方式避免了distributed緩存的查詢，但是每個使用者的follower/followee中，大部分使用者是非熱點使用者，它們無法利用本地緩存。由于這些非熱點使用者的占比更大，info的接收的服務吞吐量需求仍然沒有顯著減少。

3） info查詢中一個重要的資訊是被查詢實體的followee和follower的數量，尤其是followee數量上限很高（部分熱點使用者存在百萬甚至千萬級的量），這兩個cnt數量随時變化着，為了使得查詢的數值實時，系統需要在盡量間隔短的時間重新進行count，對于熱點使用者，如果期望實作秒級資料延遲，那麼意味着每秒需要對百萬甚至千萬級别的資料進行count。如何解決這些動态變化着的資料的大通路量、實時性成為挑戰。

下一小節叙述如何利用二級緩存和備援解決這三個問題。

12.2.4 緩存的優化方案

對于上述兩個遺留問題，可以通過引入增量化來解決。它對解決上述3個問題提供了基礎，其思路是将增量資料做為一等公民（first-class），通過對增量資料的流式處理，支撐relation的各種查詢場景，尤其是熱點場景。

對于本章中的示例系統，在引入緩存後仍存在的熱點場景如下：

1）熱點使用者（follower很多的使用者）的關系詳情查詢：他/她的關注者清單。

2）所有使用者的計數相關摘要，包括熱點使用者的計數摘要、熱點使用者的follower/followee的摘要。

首先來看一下增量資料的流轉，如圖12-7所示：

圖12-7增量資料的流轉

最左側為增量事件的發起者，例如使用者C關注了B和A，則産生兩個follow資料，它們将會分别shuffle到A和B所在的資料分片，使得A、B所在的分片中存放者它們各自的變更資料。這些變更以某種方式按照變更産生時間排序，例如唯一主鍵以createTime時間戳的某種保序壓縮（例如将timemillis做36-base編碼保證字母序關系不變）做為字首讓DB的查詢實作順序掃描，使得變更資料的訂閱方，如計數器或者近期增量清單能夠根據變更事件的時間進行擷取。

1. 獨立的計數服務

對于實時變更着的follower/followee數量的頻繁查詢，采用資料庫的count函數來實作無法保證性能和吞吐量，即便引入緩存，為了保證緩存的時效性，也會因較短間隔的DB count查詢引發性能問題。這些問題通過引入單獨的計數服務使得count計算做到O(1)的查詢複雜度可以得到緩解。

計數服務可以設計成key-value結構，持久化到分布式緩存，key為使用者id，value為該使用者的follower/followee數量。于是查詢服務轉化為對緩存的某個key的簡單get操作。

對于value的寫入，可以利用上述增量化子產品，訂閱使用者收到的變更事件。對于follow事件，直接對key對應的value做自增操作；對于unfollow事件，則做自減操作。例如，對于user C follow了A這個事件，對key為A的value做自增操作。

同時通過對增量化子產品中的每個事件記錄産生的版本（也可根據時間本身自增來實作），和對計數器每個key進行版本記錄，可以實作去重放丢失等需求。

每個key的更新頻率取決于機關時間内針對該key的事件數量。例如對于有1億follower的熱點使用者，假設每個follower每十天變更一次對某個followee的關注與否（實際上變更頻率不會這麼頻繁），那麼改key的變更頻率峰值為500次每秒（自然情況下的峰值約等于當天的所有通路平均分布到5~8小時之後的每秒通路量），小于資料庫單key的寫入吞度量上限（約等于800 tps）。如果考慮批量擷取變更事件，則單key峰值寫入會更低。

2. 根據事件時間排列的relation詳情

當需要檢視某個使用者的relation詳情頁時，涉及對follower/followee清單的分頁查詢。通常單個使用者關注的人數量有限，絕大多數使用者在1000以内，且每次對第一頁的查詢頻度遠高于後續分頁，那麼無論直接将清單存入DB或是分布式緩存，都能做到較高的吞吐量：DB資料以使用者為二級索引，采用預設的排序時大多數情況第一頁一個block可以承載；分布式緩存時單個value可以涵蓋這些followee清單。

但是，對于熱點使用者的follower，情況更加複雜一些：follower的數量不可控，使得：

q   即便是小機率的翻頁操作，對于follower很多的熱點使用者，仍然是高通路量的操作；且每次翻頁的掃描成本很高

q   單個分布式緩存的value清單無法承載過長的follower清單

針對熱點使用者的follower清單查詢問題，采用基于增量化的實作輔助解決。

首先，同一個使用者follower清單的前N頁（假設為前5頁）的通路機率占到總通路量的絕大部分（假設超過99%），而前N頁的follower個數是常數個（假設每頁展示20個follower，前5頁隻有100個follower需要展示）；其次，follower清單的展示以follow時間進行排序，最近加入的follower通常排在最前，即增量化子產品的最新資料最有可能放在首N頁。

基于上述兩個假設，針對這99%通路量的前N頁，可以直接查詢增量資料：做為增量化的消費者每次拉取的最近N頁條變更事件直接存入熱點使用者的follower緩存中，對外提供查詢服務。由于變更事件既有follow也有unfollow，無法直接确定拉取多少條，此時可根據曆史的follow和unfollow數量比例對“N頁條數”進行放大再拉取，之後隻取其中的follow事件部分存入緩存。

欲了解更多有關分布式緩存方面的内容，請閱讀《深入分布式緩存:從原理到實踐》一書。

京東購書，掃描二維碼：