另一個問題則是更新隊列的長度。如果不進行任何優(yōu)化，更新隊列理論上是無限長的，甚至?xí)^數(shù)據(jù)集的大小。一個優(yōu)化方法是我們限制住更新隊列的最大長度，一旦長度超過限制，則執(zhí)行合并（Merge）操作。Merge操作將隊列中的數(shù)據(jù)進行兩兩合并，合并后的版本號以較大的版本號為準(zhǔn)，合并后的更新數(shù)據(jù)集是兩個數(shù)據(jù)集的并。Merge后，新的隊列長度下降為原更新隊列的一半。
Merge之后的更新隊列，我們依然可以使用相同的算法進行同步Diff計算：在隊列中找到大于上一次更新版本號的所有數(shù)據(jù)集。可以看到由于版本號的合并，算出的Diff不再是完全精準(zhǔn)的更新數(shù)據(jù)，在隊列中最早的更新數(shù)據(jù)集有可能包含部分已經(jīng)同步過的數(shù)據(jù)——但這樣的退化并不影響同步正確性，僅僅會造成少量的同步冗余，冗余的量取決于Diff中最早的數(shù)據(jù)集經(jīng)過Merge的次數(shù)。
MerkleTree同步——數(shù)據(jù)集對比算法
基于版本號的同步使用的是類似RedoLog的思想，將業(yè)務(wù)變動的歷史記錄下來，并通過回放未同步的歷史記錄得到Diff。由于記錄不斷增長的RedoLog需要不小的開銷，所以采用了Merge策略來退化原始日志（Log）。對于批量或者微批量的更新來說，基于版本號的同步算法能較好的工作；相反，若數(shù)據(jù)是實時更新的，將會出現(xiàn)大量的RedoLog，并快速的退化，影響同步的效率。
Merkle Tree同步算法走的是另一條路，簡單來說就是通過每次直接比較兩個數(shù)據(jù)集的差異來獲取Diff。首先看一個最簡單的算法：每次內(nèi)存副本將所有數(shù)據(jù)的Hash值發(fā)送給數(shù)據(jù)源，數(shù)據(jù)源比較整個數(shù)據(jù)集，對于Hash值不同的數(shù)據(jù)執(zhí)行同步操作——這樣就精確計算出了兩個數(shù)據(jù)集之間的Diff。但顯而易見的問題，是每次傳輸所有數(shù)據(jù)的Hash值可能并不比多傳幾個數(shù)據(jù)輕松。Merkle Tree同步算法就是使用Merkle Tree數(shù)據(jù)結(jié)構(gòu)來優(yōu)化這一比較過程。
Merkle Tree簡單來說是就是把所有數(shù)據(jù)集的hash值組織成一棵樹，這棵樹的葉子節(jié)點描述一個（或一組）數(shù)據(jù)的Hash值。而中間節(jié)點的值由其所有兒子的Hash值再次Hash得到，描述了以它為根的子樹所包含的數(shù)據(jù)的整體Hash。顯然，在不考慮Hash沖突的情況下，如果兩顆Merkle Tree根節(jié)點相同，代表這是兩個完全相同的數(shù)據(jù)集。
Merkle Tree同步協(xié)議由副本發(fā)起，將副本根節(jié)點值發(fā)送給數(shù)據(jù)源，若與數(shù)據(jù)源根節(jié)點hash值一致，則沒有數(shù)據(jù)變動，同步完成。否則數(shù)據(jù)源將把根結(jié)點的所有兒子節(jié)點的hash發(fā)送給副本，進行遞歸比較。對于不同的hash值，一直持續(xù)獲取直到葉子節(jié)點，就可以完全確定已經(jīng)改變的數(shù)據(jù)。以二叉樹為例，所有的數(shù)據(jù)同步最多經(jīng)過LogN次交互完成。
2.3.2 客戶端緩存技術(shù)
當(dāng)數(shù)據(jù)規(guī)模大，無法完全放入到內(nèi)存中，冷熱數(shù)據(jù)分明，對于數(shù)據(jù)時效性要求又不高的時候，通常各類業(yè)務(wù)都會采用客戶端緩存?？蛻舳司彺娴募袑崿F(xiàn)，是特征服務(wù)延伸的一部分。通用的緩存協(xié)議和使用方式不多說，從在線特征系統(tǒng)的業(yè)務(wù)角度出發(fā)，這里給出幾個方向的思考和經(jīng)驗。
接口通用化——緩存邏輯與業(yè)務(wù)分離
一個特征系統(tǒng)要滿足各類業(yè)務(wù)需求，它的接口肯定是豐富的。從數(shù)據(jù)含義角度分有用戶類、商戶類、產(chǎn)品類等等，從數(shù)據(jù)傳輸協(xié)議分有Thrift、HTTP，從調(diào)用方式角度分有同步、異步，從數(shù)據(jù)組織形式角度分有單值、List、Map以及相互嵌套等等……一個良好的架構(gòu)設(shè)計應(yīng)該盡可能將數(shù)據(jù)處理與業(yè)務(wù)剝離開，抽象各個接口的通用部分，一次緩存實現(xiàn)，多處接口同時受益復(fù)用。下面以同步異步接口為例介紹客戶端接口通用化。
同步接口只有一步：
向服務(wù)端發(fā)起請求得到結(jié)果。
異步接口分為兩步：
向服務(wù)端發(fā)起請求得到Future實例。
向Future實例發(fā)起請求，得到數(shù)據(jù)。
同步和異步接口的數(shù)據(jù)處理只有順序的差別，只需要梳理好各個步驟的執(zhí)行順序即可。引入緩存后，數(shù)據(jù)處理流程對比如下：