影響數(shù)據(jù)檢索效率的幾個因素

數(shù)據(jù)檢索有兩種主要形態(tài)。第一種是純數(shù)據(jù)庫型的。典型的結(jié)構(gòu)是一個關(guān)系型數(shù)據(jù)，比如 mysql。用戶通過 SQL 表達(dá)出所需要的數(shù)據(jù)，mysql 把 SQL 翻譯成物理的數(shù)據(jù)檢索動作返回結(jié)果。第二種形態(tài)是現(xiàn)在越來越流行的大數(shù)據(jù)玩家的玩法。典型的結(jié)構(gòu)是有一個分區(qū)的數(shù)據(jù)存儲，最初這種存儲就是原始的 HDFS，后來開逐步有人在 HDFS 上加上索引的支持，或者干脆用 Elasticsearc 這樣的數(shù)據(jù)存儲。然后在存儲之上有一個分布式的實(shí)時計算層，比如 Hive 或者 Spark SQL。用戶用 Hive SQL 提交給計算層，計算層從存儲里拉取出數(shù)據(jù)，進(jìn)行計算之后返回給用戶。這種大數(shù)據(jù)的玩法起初是因?yàn)?SQL 有很多 ad-hoc 查詢是滿足不了的，干脆讓用戶自己寫 map/reduce 想怎么算都可以了。但是后來玩大了之后，越來越多的人覺得這些 Hive 之類的方案查詢效率怎么那么低下啊。于是一個又一個項(xiàng)目開始去優(yōu)化這些大數(shù)據(jù)計算框架的查詢性能。這些優(yōu)化手段和經(jīng)典的數(shù)據(jù)庫優(yōu)化到今天的手段是沒有什么兩樣的，很多公司打著搞計算引擎的旗號干著重新發(fā)明數(shù)據(jù)庫的活。所以，回歸本質(zhì)，影響數(shù)據(jù)檢索效率的就那么幾個因素。我們不妨來看一看。
    數(shù)據(jù)檢索干的是什么事情
    定位 => 加載 => 變換
    找到所需要的數(shù)據(jù)，把數(shù)據(jù)從遠(yuǎn)程或者磁盤加載到內(nèi)存中。按照規(guī)則進(jìn)行變換，比如按某個字段group by，取另外一個字段的sum之類的計算。
    影響效率的四個因素
    讀取更少的數(shù)據(jù)
    數(shù)據(jù)本地化，充分遵循底層硬件的限制設(shè)計架構(gòu)
    更多的機(jī)器
    更高效率的計算和計算的物理實(shí)現(xiàn)
    原則上的四點(diǎn)描述是非常抽象的。我們具體來看這些點(diǎn)映射到實(shí)際的數(shù)據(jù)庫中都是一些什么樣的優(yōu)化措施。
    讀取更少的數(shù)據(jù)
    數(shù)據(jù)越少，檢索需要的時間當(dāng)然越少了。在考慮所有技術(shù)手段之前，最有效果的恐怕是從業(yè)務(wù)的角度審視一下我們是否需要從那么多的數(shù)據(jù)中檢索出結(jié)果來。有沒有可能用更少的數(shù)據(jù)達(dá)到同樣的效果。減少的數(shù)據(jù)量的兩個手段，聚合和抽樣。如果在入庫之前把數(shù)據(jù)就做了聚合或者抽樣，是不是可以極大地減少查詢所需要的時間，同時效果上并無多少差異呢？極端情況下，如果需要的是一天的總訪問量，比如有1個億。查詢的時候去數(shù)1億行肯定快不了。但是如果統(tǒng)計好了一天的總訪問量，查詢的時候只需要取得一條記錄就可以知道今天有1個億的人訪問了。
    索引是一種非常常見的減少數(shù)據(jù)讀取量的策略了。一般的按行存儲的關(guān)系型數(shù)據(jù)庫都會有一個主鍵。用這個主鍵可以非?？焖俚牟檎业綄?yīng)的行。KV存儲也是這樣，按照Key可以快速地找到對應(yīng)的Value。可以理解為一個Hashmap。但是一旦查詢的時候不是用主鍵，而是另外一個字段。那么最糟糕的情況就是進(jìn)行一次全表的掃描了，也就是把所有的數(shù)據(jù)都讀取出來，然后看要的數(shù)據(jù)到底在哪里，這就不可能快了。減少數(shù)據(jù)讀取量的最佳方案就是，建立一個類似字典一樣的查找表，當(dāng)我們找 username=wentao 的時候，可以列舉出所有有 wentao 作為用戶名的行的主鍵。然后拿這些主鍵去行存儲（就是那個hashmap）里撈數(shù)據(jù)，就一撈一個準(zhǔn)了。
    談到索引就不得不談一下一個查詢使用了兩個字段，如何使用兩個索引的問題。mysql的行為可以代表大部分主流數(shù)據(jù)庫的處理方式：
    基本上來說，經(jīng)驗(yàn)表明有多個單字段的索引，最后數(shù)據(jù)庫會選一最優(yōu)的來使用。其余字段的過濾仍然是通過數(shù)據(jù)讀取到內(nèi)存之后，用predicate去判斷的。也就是無法減少數(shù)據(jù)的讀取量。
    在這個方面基于inverted index的數(shù)據(jù)就非常有特點(diǎn)。一個是Elasticsearch為代表的lucene系的數(shù)據(jù)庫。另外一個是新銳的druid數(shù)據(jù)庫。
    效果就是，這些數(shù)據(jù)庫可以把單字段的filter結(jié)果緩存起來。多個字段的查詢可以把之前緩存的結(jié)果直接拿過來做 AND 或者 OR 操作。
    索引存在的必要是因?yàn)橹鞔鎯]有提供直接的快速定位的能力。如果訪問的就是數(shù)據(jù)庫的主鍵，那么需要讀取的數(shù)據(jù)也就非常少了。另外一個變種就是支持遍歷的主鍵，比如hbase的rowkey。如果查詢的是一個基于rowkey的范圍，那么像hbase這樣的數(shù)據(jù)庫就可以支持只讀取到這個范圍內(nèi)的數(shù)據(jù)，而不用讀取不再這個范圍內(nèi)的額外數(shù)據(jù)，從而提高速度。這種加速的方式就是利用了主存儲自身的物理分布的特性。另外一個更常見的場景就是 partition。比如 mysql 或者 postgresql 都支持分區(qū)表的概念。當(dāng)我們建立了分區(qū)表之后，查找的條件如果可以過濾出分區(qū)，那么可以大幅減少需要讀取的數(shù)據(jù)量。比 partition 更細(xì)粒度一些的是 clustered index。它其實(shí)不是一個索引（二級索引），它是改變了數(shù)據(jù)在主存儲內(nèi)的排列方式，讓相同clustered key的數(shù)據(jù)彼此緊挨著放在一起，從而在查詢的時候避免掃描到無關(guān)的數(shù)據(jù)。比 partition 更粗一些的是分庫分表分文件。比如我們可以一天建立一張表，查詢的時候先定位到表，再執(zhí)行 SQL。比如 graphite 給每個 metric 創(chuàng)建一個文件存放采集來的 data point，查詢的時候給定metric 就可以定位到一個文件，然后只讀取這個文件的數(shù)據(jù)。
    另外還有一點(diǎn)就是按行存儲和按列存儲的區(qū)別。按列存儲的時候，每個列是一個獨(dú)立的文件。查詢用到了哪幾個列就打開哪幾個列的文件，沒有用到的列的數(shù)據(jù)碰都不會碰到。反觀按行存儲，一張中的所有字段是彼此緊挨在磁盤上的。一個表如果有100個字段，哪怕只選取其中的一個字段，在掃描磁盤的時候其余99個字段的數(shù)據(jù)仍然會被掃描到的。
    考慮一個具體的案例，時間序列數(shù)據(jù)。如何使用讀取更少的數(shù)據(jù)的策略來提高檢索的效率呢？首先，我們可以保證入庫的時間粒度，維度粒度是正好是查詢所需要的。如果查詢需要的是5分鐘數(shù)據(jù)，但是入庫的是1分鐘的，那么就可以先聚合成5分鐘的再存入數(shù)據(jù)庫。對于主存儲的物理布局選擇，如果查詢總是針對一個時間范圍的。那么把 timestamp 做為 hbase 的 rowkey，或者 mysql 的 clustered index 是合適。這樣我們按時間過濾的時候，選擇到的是一堆連續(xù)的數(shù)據(jù)，不用讀取之后再過濾掉不符合條件的數(shù)據(jù)。但是如果在一個時間范圍內(nèi)有很多中數(shù)據(jù)，比如1萬個IP，那么即便是查1個IP的數(shù)據(jù)也需要把1萬個IP的數(shù)據(jù)都讀取出來。所以可以把 IP 維度也編碼到 rowkey 或者 clustered index 中。但是假如另外還有一個維度是 OS，那么查詢的時候 IP 維度的 rowkey 是沒有幫助的，仍然是要把所有的數(shù)據(jù)都查出來。這就是僅依靠主存儲是無法滿足各種查詢條件下都能夠讀取更少的數(shù)據(jù)的原因。所以，二級索引是必要的。我們可以把時間序列中的所有維度都拿出來建立索引，然后查詢的時候如果指定了維度，就可以用二級索引把真正需要讀取的數(shù)據(jù)過濾出來。但是實(shí)踐中，很多數(shù)據(jù)庫并不因?yàn)槭褂昧?a href='/map/suoyin/' style='color:#000;font-size:inherit;'>索引使得查詢變快了，有的時候反而變得更慢了。對于 mysql 來說，存儲時間序列的最佳方式是按時間做 partition，不對維度建立任何索引。查詢的時候只過濾出對應(yīng)的 partition，然后進(jìn)行全 partition 掃描，這樣會快過于使用二級索引定位到行之后再去讀取主存儲的查詢方式。究其原因，就是數(shù)據(jù)本地化的問題了。

[page]
    數(shù)據(jù)本地化
    數(shù)據(jù)本地化的實(shí)質(zhì)是軟件工程師們要充分尊重和理解底層硬件的限制，并且用各種手段規(guī)避問題最大化利用手里的硬件資源。本地化有很多種形態(tài)
    最常見的最好理解的本地化問題是網(wǎng)絡(luò)問題。我們都知道網(wǎng)絡(luò)帶寬不是無限的，比本地磁盤慢多了。如果可能盡量不要通過網(wǎng)絡(luò)去訪問數(shù)據(jù)。即便要訪問，也應(yīng)該一次抓取多一些數(shù)據(jù)，而不是一次搞一點(diǎn)，然后搞很多次。因?yàn)榫W(wǎng)絡(luò)連接和來回的開銷是非常高的。這就是 data locality 的問題。我們要把計算盡可能的靠近數(shù)據(jù)，減少網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)量。
    這種帶寬引起的本地化問題，還有很多。網(wǎng)絡(luò)比硬盤慢，硬盤比內(nèi)存慢，內(nèi)存比L2緩存慢。做到極致的數(shù)據(jù)庫可以讓計算完全發(fā)生在 L2 緩存內(nèi)，盡可能地避免頻繁地在內(nèi)存和L2之間倒騰數(shù)據(jù)。
    另外一種形態(tài)的問題化問題是磁盤的順序讀和隨機(jī)讀的問題。當(dāng)數(shù)據(jù)彼此靠近地物理存放在磁盤上的時候，順序讀取一批是非?？斓摹Ｈ绻枰S機(jī)讀取多個不連續(xù)的硬盤位置，磁頭就要來回移動從而使得讀取速度快速下降。即便是 SSD 硬盤，順序讀也是要比隨機(jī)讀快的。
    基于盡可能讓數(shù)據(jù)讀取本地化的原則，檢索應(yīng)該盡可能地使用順序讀而不是隨機(jī)讀。如果可以的話，把主存儲的row key或者clustered index設(shè)計為和查詢提交一樣的。時間序列如果都是按時間查，那么按時間做的row key可以非常高效地以順序讀的方式把數(shù)據(jù)拉取出來。類似地，按列存儲的數(shù)據(jù)如果要把一個列的數(shù)據(jù)都取出來加和的話，可以非常快地用順序讀的方式加載出來。
    二級索引的訪問方式典型的隨機(jī)讀。當(dāng)查詢條件經(jīng)過了二級索引查找之后得到一堆的主存儲的 key，那么就需要對每個 key 進(jìn)行一次隨機(jī)讀。即便彼此僅靠的key可以用順序讀做一些優(yōu)化，總體上來說仍然是隨機(jī)讀的模式。這也就是為什么時間序列數(shù)據(jù)在 mysql 里建立了索引反而比沒有建索引還要慢的原因。
    為了盡可能的利用順序讀，人們就開始想各種辦法了。前面提到了 mysql 里的一行數(shù)據(jù)的多個列是彼此緊靠地物理存放的。那么如果我們把所需要的數(shù)據(jù)建成多個列，那么一次查詢就可以批量獲得更多的數(shù)據(jù)，減少隨機(jī)讀取的次數(shù)。也就是把之前的一些行變?yōu)榱械姆绞絹泶娣?，減少行的數(shù)量。這種做法的經(jīng)典案例就是時間序列數(shù)據(jù)，比如可以一分鐘存一行數(shù)據(jù)，每一秒的值變成一個列。那么行的數(shù)量可以變成之前的1/60。
    但是這種行變列的做法在按列存儲的數(shù)據(jù)庫里就不能直接照搬了，有些列式數(shù)據(jù)庫有column family的概念，不同的設(shè)置在物理上存放可能是在一起的也可能是分開的。對于 Elasticsearch 來說，要想減少行的數(shù)量，讓一行多pack一些數(shù)據(jù)進(jìn)去，一種做法就是利用 nested document。內(nèi)部 Elasticsearch 可以保證一個 document 下的所有的 nested document是物理上靠在一起放在同一個 lucene 的 segment 內(nèi)。
    網(wǎng)絡(luò)的data locality就比較為人熟知了。map reduce的大數(shù)據(jù)計算模式就是利用map在數(shù)據(jù)節(jié)點(diǎn)的本地把數(shù)據(jù)先做一次計算，往往計算的結(jié)果可以比原數(shù)據(jù)小很多。然后再通過網(wǎng)絡(luò)傳輸匯總后做 reduce 計算。這樣就節(jié)省了大量網(wǎng)絡(luò)傳輸數(shù)據(jù)的時間浪費(fèi)和資源消耗?，F(xiàn)在 Elasticsearch 就支持在每個 data node 上部署 spark。由 spark 在每個 data node 上做計算。而不用把數(shù)據(jù)都查詢出來，用網(wǎng)絡(luò)傳輸?shù)?spark 集群里再去計算。這種數(shù)據(jù)庫和計算集群的混合部署是高性能的關(guān)鍵。類似的還有 storm 和 kafka 之間的關(guān)系。
    網(wǎng)絡(luò)的data locality還有一個老大難問題就是分布式大數(shù)據(jù)下的多表join問題。如果只是查詢一個分布式表，那么把計算用 map reduce 表達(dá)就沒有多大問題了。但是如果需要同時查詢兩個表，就意味著兩個表可能不是在物理上同樣均勻分布的。一種最簡單的策略就是找出兩張表中最小的那張，然后把表的內(nèi)容廣播到每個節(jié)點(diǎn)上，再做join。復(fù)雜一些的是對兩個單表做 map reduce，然后按照相同的 key 把部分計算的結(jié)果匯集在一起。第三種策略是保證數(shù)據(jù)分布的方式，讓兩張表查詢的時候需要用到的數(shù)據(jù)總在一起。沒有完美的方案，也不大可能有完美的方案。除非有一天網(wǎng)絡(luò)帶寬可以大到忽略不計的地步。
    更多的機(jī)器
    這個就沒有什么好說的了。多一倍的機(jī)器就多一倍的 CPU，可以同時計算更多的數(shù)據(jù)。多一倍的機(jī)器就多一倍的磁頭，可以同時掃描更多的字節(jié)數(shù)。很多大數(shù)據(jù)框架的故事就是講如何如何通過 scale out 解決無限大的問題。但是值得注意的是，集群可以無限大，數(shù)據(jù)可以無限多，但是口袋里的銀子不會無限多的。堆機(jī)器解決問題比升級大型機(jī)是要便宜，但是機(jī)器堆多了也是非常昂貴的。特別是 Hive 這些從一開始就是分布式多機(jī)的檢索方案，剛開始的時候效率并不高。堆機(jī)器是一個乘數(shù)，當(dāng)數(shù)據(jù)庫本來單機(jī)性能不高的時候，乘數(shù)大并不能起到?jīng)Q定性的作用。
    更高效的計算和計算實(shí)現(xiàn)
    檢索的過程不僅僅是磁盤掃描，它還包括一個可簡單可復(fù)雜的變換過程。使用 hyperloglog，count min-sketch等有損算法可以極大地提高統(tǒng)計計算的性能。數(shù)據(jù)庫的join也是一個經(jīng)常有算法創(chuàng)新的地方。
    計算實(shí)現(xiàn)就是算法是用C++實(shí)現(xiàn)的還是用java，還是python實(shí)現(xiàn)的。用java是用大Integer實(shí)現(xiàn)的，還是小int實(shí)現(xiàn)的。不同的語言的實(shí)現(xiàn)方式會有一些固定的開銷。不是說快就一定要C++，但是 python 寫 for 循環(huán)是顯然沒有指望的。任何數(shù)據(jù)檢索的環(huán)節(jié)只要包含 python/ruby 這些語言的逐條 for 循環(huán)就一定快不起來了。
    結(jié)論
    希望這四點(diǎn)可以被記住，成為一種指導(dǎo)性的優(yōu)化數(shù)據(jù)檢索效率的思維框架。無論你是設(shè)計一個mysql表結(jié)構(gòu)，還是優(yōu)化一個spark sql的應(yīng)用。從這四個角度想想，都有哪些環(huán)節(jié)是在拖后腿的，手上的工具有什么樣的參數(shù)可以調(diào)整，讓隨機(jī)讀變成順序讀，表結(jié)構(gòu)怎么樣設(shè)計可以最小化數(shù)據(jù)讀取的量。要做到這一點(diǎn)，你必須非常非常了解工具的底層實(shí)現(xiàn)。而不是盲目的相信，xx數(shù)據(jù)庫是最好的數(shù)據(jù)庫，所以它一定很快之類的。如果你不了解你手上的數(shù)據(jù)庫或者計算引擎，當(dāng)它快的時候你不知道為何快，當(dāng)它慢的時候你就更加無從優(yōu)化了。