為什么長尾數據的翻頁技術實現復雜
今天要討論一個傳統的問題，問題本身比較簡單，就是針對大數據，如何優化方案做到性能與成本的平衡。我們經常會遇到一種Key-list類型數據， 如一個用戶的好友關系 {“uid”:{1,2,3,4,5}}，表示uid包含有5個好友；一條微博下面的評論id列表{“weibo_id”: {comment_id1, comment_id2……}}，一個用戶發表的微博id列表等。
在list長度較少時候，我們可以直接的使用數據庫的翻頁功能，如
- SELECT * FROM LIST_TABLE LIMIT offset, row_count;
根據經驗，在大部分場景下，單個業務的list數據長度99%在1000條以下，在數據規模較小時候，上面的方法非常適合。但剩下的1%的數據可能多達100萬條，在數據規模較大的時候，當訪問offset較大的數據，上述方法非常低效（可參看Why does MYSQL higher LIMIT offset slow the query down?），但在實現方案的時候不能忽視這些超大數據集的問題，因此要實現一個適合各種變長list的翻頁方案，考慮到數據的長尾問題，并沒有簡單高效的方案。這也體現了常說的80%+的時間在優化20%-的功能。
List數據訪問模型常見的有兩種方式
1. 扶梯方式
扶梯方式在導航上通常只提供上一頁/下一頁這兩種模式，部分產品甚至不提供上一頁功能，只提供一種“更多/more”的方式，也有下拉自動加載更多的方式，在技術上都可以歸納成扶梯方式。
（圖：blogspot的導航條）
（圖：很多瀑布流式的產品只提供一個more的導航條）
扶梯方式在技術實現上比較簡單及高效，根據當前頁***一條的偏移往后獲取一頁即可，在MySQL可使用以下方法實現。
- SELECT * FROM LIST_TABLE WHERE id > offset_id LIMIT n;
由于where條件中指定了位置，因此算法復雜度是O(log n)
2. 電梯方式
另外一種數據獲取方式在產品上體現成精確的翻頁方式，如1,2,3……n，同時在導航上也可以由用戶輸入直達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時候，獲取數據才真正開始，所以導致效率不高。對應的算法復雜度是O(n)，n指offset，也就是page*count。
另外Offset并不能有效的緩存，這是由于
1、在數據存在新增及刪除的情況下，只要有一條變化，原先的樓層可能會全部發生變化。在一個用戶并發訪問的場景，頻繁變化的場景比較常見。
2、電梯使用比較離散，可能一個20萬條的list，用戶使用了一次電梯直達100樓之后就走了，這樣即使緩存100樓之下全部數據也不能得到有效利用。
以上描述的場景屬于單機版本，在數據規模較大時候，互聯網系統通常使用分庫的方式來保存，實現方法更為復雜。
在面向用戶的產品中，數據分片通常會將同一用戶的數據存在相同的分區，以便更有效率的獲取當前用戶的數據。如下圖所示
（圖：數據按用戶uid進行hash拆分）
圖中的不同年份的數據的格子是邏輯概念，實際上同一用戶的數據是保存在一張表中。因此方案在常見的使用場景中存在很大不足，大部分產品用戶只訪問最 近產生的數據，歷史的數據只有極小的概率被訪問到，因此同一個區域內部的數據訪問是非常不均勻，如圖中2014年生成的屬于熱數據，2012年以前的屬于 冷數據，只有極低的概率被訪問到。但為了承擔紅色部分的訪問，數據庫通常需要高速昂貴的設備如SSD，因此上面方案所有的數據都需要存在SSD設備中，即 使這些數據已經不被訪問。
簡單的解決方案是按時間遠近將數據進行進一步分區，如圖。
注意在上圖中使用時間方式sharding之后，在一個時間分區內，也需要用前一種方案將數據進行sharding，因為一個時間片區通常也無法用一臺服務器容納。
上面的方案較好的解決了具體場景對于key list訪問性能及成本的平衡，但是它存在以下不足
-
數據按時間進行滾動無法全自動，需要較多人為介入或干預
-
數據時間維度需要根據訪問數據及模型進行精巧的設計，如果希望實現一個公用的key-list服務來存儲所有業務的數據，這個公用服務可能很難實現
-
為了實現電梯直達功能，需要增加額外的二級索引，比如2013年某用戶總共有多少條記錄
由于以上問題，尤其是二級索引的引入，顯然它不是理想中的key list實現，后文繼續介紹適合大數據翻頁key list設計的一些思路及嘗試。
