慧都年終巨獻，Aspose系列產(chǎn)品黃金版+白金版享<8折>優(yōu)惠！ 截止日期2014/12/31

最近討論的一個傳統(tǒng)的問題，問題本身比較簡單，針對key-list類型的數(shù)據(jù)，如何優(yōu)化方案做到性能與成本的tradeoff。Key-list在社交產(chǎn)品及面向用戶的產(chǎn)品中非常普遍，如一個用戶的好友關(guān)系 {“uid”:{1,2,3,4,5}}，表示某個uid有1,2,3,4,5好友；一條微博下面的評論id列表結(jié)構(gòu)是 {“weibo_id”: {comment_id1, comment_id2……}}，一個用戶發(fā)表的微博id列表等。

在list長度較小時，我們可以直接使用數(shù)據(jù)庫的翻頁功能，如

SELECT * FROM LIST_TABLE LIMIT offset, row_count;

根據(jù)經(jīng)驗，在大部分場景下，單個業(yè)務(wù)的list數(shù)據(jù)長度99%的情況在1000條以下，在數(shù)據(jù)規(guī)模較小時，上面的方法非常適合。但剩下的1%情況下，數(shù)據(jù)可能多達100萬條，在數(shù)據(jù)規(guī)模較大的時候，當訪問offset較大的數(shù)據(jù)集，上述方法非常低效。但在考慮方案的時候不能忽視這些超大數(shù)據(jù)集的問題，因此要實現(xiàn)一個適合各種變長list場景的翻頁方案，業(yè)界并沒有簡單高效的方案。這也反映出常說的80%的時間在優(yōu)化20%的功能。

List數(shù)據(jù)訪問模型常見的有兩種方式

1. 扶梯方式

扶梯方式在導(dǎo)航上通常只提供上一頁/下一頁這兩種模式，部分產(chǎn)品甚至不提供上一頁功能，只提供一種“更多/more”的方式，也有下拉自動加載更多的方式，在技術(shù)上都可以歸納成扶梯方式。

扶梯方式在技術(shù)實現(xiàn)上比較簡單及高效，根據(jù)當前頁最后一條的偏移往后獲取一頁即可，在MySQL可使用以下方法實現(xiàn)。

SELECT * FROM LIST_TABLE WHERE id > offset_id LIMIT n;

由于where條件中指定了位置，根據(jù)B-TREE實現(xiàn)原理，算法復(fù)雜度是O(log n)

2. 電梯方式

另外一種數(shù)據(jù)獲取方式在產(chǎn)品上體現(xiàn)成精確的翻頁方式，如1,2,3…&hellip;n，同時在導(dǎo)航上也可以由用戶輸入直達n頁。國內(nèi)大部分產(chǎn)品經(jīng)理對電梯方式有特殊的喜好，如圖

但電梯方式在技術(shù)實現(xiàn)上相對成本較高，當使用以下SQL時

SELECT * FROM LIST_TABLE LIMIT offset, row_count;

我們可以使用MySQL explain來分析，從下文可以看到，當offset=10000時候，實際上MySQL也掃描了10000行記錄。

為什么會這樣？在MySQL中，索引通常是b-tree方式（但存儲引擎如InnoDB實際是b+tree），如圖

從圖中可以看到，使用電梯方式時候，當用戶指定翻到第n頁時候，并沒有直接方法尋址到該位置，而是需要從第一樓逐個count，scan到count*page時候，獲取數(shù)據(jù)才真正開始，所以導(dǎo)致效率不高。對應(yīng)的算法復(fù)雜度是O(n)，n指offset，也就是page*count。

另外Offset并不能有效的緩存以便轉(zhuǎn)化成前一種訪問模式，這是由于

1、在數(shù)據(jù)存在新增及刪除的情況下，只要有一條變化，原先的樓層可能會全部發(fā)生變化。在一個用戶并發(fā)訪問的場景，頻繁變化的場景比較常見。

2、電梯使用比較離散，可能一個20萬條的list，用戶使用了一次電梯直達100樓之后就走了，這樣即使緩存100樓之下全部數(shù)據(jù)也不能得到有效利用。

以上描述的場景屬于單機版本，在數(shù)據(jù)規(guī)模較大時候，互聯(lián)網(wǎng)系統(tǒng)通常使用分庫的方式來保存，實現(xiàn)方法更為復(fù)雜。在面向用戶的產(chǎn)品中，數(shù)據(jù)分片通常會將同一用戶的數(shù)據(jù)存在相同的分區(qū)，以便更有效率的獲取當前用戶的數(shù)據(jù)。如下圖所示

圖中的不同年份的數(shù)據(jù)的格子是邏輯概念，實際上同一用戶的數(shù)據(jù)是保存在一張表中。因此方案在常見的使用場景中存在很大不足，大部分產(chǎn)品用戶只訪問最近產(chǎn)生的數(shù)據(jù)，歷史的數(shù)據(jù)只有極小的概率被訪問到，因此同一個區(qū)域內(nèi)部的數(shù)據(jù)訪問是非常不均勻，如圖中2014年生成的屬于熱數(shù)據(jù)，2012年以前的屬于冷數(shù)據(jù)，只有極低的概率被訪問到。但為了承擔(dān)紅色部分的訪問，數(shù)據(jù)庫通常需要高速昂貴的設(shè)備如SSD，因此上面方案所有的數(shù)據(jù)都需要存在SSD設(shè)備中，即使這些數(shù)據(jù)已經(jīng)不被訪問。

簡單的解決方案是按時間遠近將數(shù)據(jù)進行進一步分區(qū)，如圖。

注意在上圖中使用時間方式sharding之后，在一個時間分區(qū)內(nèi)，也需要用前一種方案將數(shù)據(jù)進行sharding，因為一個時間片區(qū)通常也無法用一臺服務(wù)器容納。

上面的方案較好的解決了具體場景對于key list訪問性能及成本的tradeoff，但是它存在以下不足

1、數(shù)據(jù)按時間進行滾動無法全自動，需要較多人為介入或干預(yù)

2、數(shù)據(jù)時間維度需要根據(jù)訪問數(shù)據(jù)及模型進行精巧的設(shè)計，如果希望實現(xiàn)一個公用的key-list服務(wù)來存儲所有業(yè)務(wù)的數(shù)據(jù)，這個公用服務(wù)可能很難實現(xiàn)

3、為了實現(xiàn)電梯直達功能，需要增加額外的二級索引，比如2013年某用戶總共有多少條記錄

由于以上問題，尤其是二級索引的引入，顯然它不是理想中的key list實現(xiàn)，后文繼續(xù)介紹適合長尾翻頁key list設(shè)計的一些思路及嘗試。

作者: TimYang

狂歡繼續(xù)！【年終大促 巔峰盛"慧" 】促銷火熱進行中 iPhone 6 Plus、 iPhone 6、iPad Air滿就送，還不趕快買買買！