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