一、在線特征系統(tǒng)

主流互聯(lián)網(wǎng)產(chǎn)品中，不論是經(jīng)典的計(jì)算廣告、搜索、推薦，還是垂直領(lǐng)域的路徑規(guī)劃、司機(jī)派單、物料智能設(shè)計(jì)，建立在人工智能技術(shù)之上的策略系統(tǒng)已經(jīng)深入到了產(chǎn)品功能的方方面面。相應(yīng)的，每一個(gè)策略系統(tǒng)都離不開(kāi)大量的在線特征，來(lái)支撐模型算法或人工規(guī)則對(duì)請(qǐng)求的精準(zhǔn)響應(yīng)，因此特征系統(tǒng)成為了支持線上策略系統(tǒng)的重要支柱。美團(tuán)點(diǎn)評(píng)技術(shù)博客之前推出了多篇關(guān)于特征系統(tǒng)的文章，如《機(jī)器學(xué)習(xí)中的數(shù)據(jù)清洗與特征處理綜述》側(cè)重于介紹特征生產(chǎn)過(guò)程中的離線數(shù)據(jù)清洗、挖掘方法，《業(yè)務(wù)賦能利器之外賣特征檔案》側(cè)重于用不同的存儲(chǔ)引擎解決不同的特征數(shù)據(jù)查詢需求。而《外賣排序系統(tǒng)特征生產(chǎn)框架》側(cè)重介紹了特征計(jì)算、數(shù)據(jù)同步和線上查詢的特征生產(chǎn)Pipeline。

本文以美團(tuán)酒旅在線特征系統(tǒng)為原型，重點(diǎn)從線上數(shù)據(jù)存取角度介紹一些實(shí)踐中的通用技術(shù)點(diǎn)，以解決在線特征系統(tǒng)在高并發(fā)情形下面臨的問(wèn)題。

1.1 在線特征系統(tǒng)框架——生產(chǎn)、調(diào)度、服務(wù)一體化

在線特征系統(tǒng)就是通過(guò)系統(tǒng)上下文，獲得相關(guān)特征數(shù)據(jù)的在線服務(wù)。其功能可以是一個(gè)簡(jiǎn)單的Key-Value(KV)型存儲(chǔ)，對(duì)線上提供特征查詢服務(wù)，也可以輻射到通用特征生產(chǎn)、統(tǒng)一特征調(diào)度、實(shí)時(shí)特征監(jiān)控等全套特征服務(wù)體系?？梢哉f(shuō)，幾個(gè)人日就可以完成一個(gè)簡(jiǎn)單能用的特征系統(tǒng)，但在復(fù)雜的業(yè)務(wù)場(chǎng)景中，把這件事做得更方便、快速和穩(wěn)定，卻需要一個(gè)團(tuán)隊(duì)長(zhǎng)期的積累。

以上結(jié)構(gòu)圖為一體化特征系統(tǒng)的概貌，自底向上為數(shù)據(jù)流動(dòng)的方向，各部分的功能如下：

數(shù)據(jù)源：用于計(jì)算特征的原始數(shù)據(jù)。根據(jù)業(yè)務(wù)需求，數(shù)據(jù)來(lái)源可能是分布式文件系統(tǒng)(如Hive)，關(guān)系型數(shù)據(jù)庫(kù)(如MySQL)，消息隊(duì)列(如Kafka)等。

特征生產(chǎn)：該部分負(fù)責(zé)從各種數(shù)據(jù)源讀取數(shù)據(jù)，提供計(jì)算框架用于生產(chǎn)特征。生產(chǎn)框架需要根據(jù)數(shù)據(jù)源的類型、不同的計(jì)算需求綜合設(shè)計(jì)，因此會(huì)有多套生產(chǎn)框架。

特征導(dǎo)入：該部分負(fù)責(zé)將計(jì)算好的特征寫(xiě)入到線上存儲(chǔ)供特征服務(wù)讀取。該部分主要關(guān)注導(dǎo)入作業(yè)之間的依賴、并發(fā)寫(xiě)入的速度與一致性等問(wèn)題。

特征服務(wù)：該部分為整個(gè)特征系統(tǒng)的核心功能部分，提供在線特征的存取服務(wù)，直接服務(wù)于上層策略系統(tǒng)。

特征的生命周期按照上述過(guò)程，可以抽象為五個(gè)步驟：讀、算、寫(xiě)、存、取。整個(gè)流程于特征系統(tǒng)框架內(nèi)成為一個(gè)整體，作為特征工程的一體化解決方案。本文主要圍繞特征服務(wù)的核心功能“存”、“取”，介紹一些通用的實(shí)踐經(jīng)驗(yàn)。特征系統(tǒng)的延伸部分，如特征生產(chǎn)、系統(tǒng)框架等主題會(huì)在后續(xù)文章中做詳細(xì)介紹。

1.2 特征系統(tǒng)的核心——存與取

簡(jiǎn)單來(lái)說(shuō)，可以認(rèn)為特征系統(tǒng)的核心功能是一個(gè)大號(hào)的HashMap，用于存儲(chǔ)和快速提取每次請(qǐng)求中相關(guān)維度的特征集合。然而實(shí)際情況并不像HashMap那樣簡(jiǎn)單，以我們的通用在線特征系統(tǒng)(Datahub)的系統(tǒng)指標(biāo)為例，它的核心功能主要需面對(duì)存儲(chǔ)與讀取方面的挑戰(zhàn)：

高并發(fā)：策略系統(tǒng)面向用戶端，服務(wù)端峰值QPS超過(guò)1萬(wàn)，數(shù)據(jù)庫(kù)峰值QPS超過(guò)100萬(wàn)(批量請(qǐng)求造成)。

高吞吐：每次請(qǐng)求可能包含上千維特征，網(wǎng)絡(luò)IO高。服務(wù)端網(wǎng)絡(luò)出口流量均值500Mbps，峰值為1.5Gbps。

大數(shù)據(jù)：雖然線上需要使用的特征數(shù)據(jù)不會(huì)像離線Hive庫(kù)那樣龐大，但數(shù)據(jù)條數(shù)也會(huì)超過(guò)10億，字節(jié)量會(huì)達(dá)到TB級(jí)。

低延遲：面對(duì)用戶的請(qǐng)求，為保持用戶體驗(yàn)，接口的延遲要盡可能低，服務(wù)端TP99指標(biāo)需要在10ms以下。

以上指標(biāo)數(shù)字僅是以我們系統(tǒng)作為參考，實(shí)際各個(gè)部門(mén)、公司的特征系統(tǒng)規(guī)模可能差別很大，但無(wú)論一個(gè)特征系統(tǒng)的規(guī)模怎樣，其系統(tǒng)核心目標(biāo)必定是考慮：高并發(fā)、高吞吐、大數(shù)據(jù)、低延遲，只不過(guò)各有不同的優(yōu)先級(jí)罷了。當(dāng)系統(tǒng)的優(yōu)化方向是多目標(biāo)時(shí)，我們不可能獨(dú)立的用任何一種方式，在有限資源的情況下做到面面俱到。留給我們的是業(yè)務(wù)最重要的需求特性，以及對(duì)應(yīng)這些特性的解決方案。

二、在線特征存取技術(shù)

本節(jié)介紹一些在線特征系統(tǒng)上常用的存取技術(shù)點(diǎn)，以豐富我們的武器庫(kù)。主要內(nèi)容也并非詳細(xì)的系統(tǒng)設(shè)計(jì)，而是一些常見(jiàn)問(wèn)題的通用技術(shù)解決方案。但如上節(jié)所說(shuō)，如何根據(jù)策略需求，利用合適的技術(shù)，制定對(duì)應(yīng)的方案，才是各位架構(gòu)師的核心價(jià)值所在。

2.1 數(shù)據(jù)分層

特征總數(shù)據(jù)量達(dá)到TB級(jí)后，單一的存儲(chǔ)介質(zhì)已經(jīng)很難支撐完整的業(yè)務(wù)需求了。高性能的在線服務(wù)內(nèi)存或緩存在數(shù)據(jù)量上成了杯水車薪，分布式KV存儲(chǔ)能提供更大的存儲(chǔ)空間但在某些場(chǎng)景又不夠快。開(kāi)源的分布式KV存儲(chǔ)或緩存方案很多，比如我們用到的就有Redis/Memcache，HBase，Tair等，這些開(kāi)源方案有大量的貢獻(xiàn)者在為它們的功能、性能做出不斷努力，本文就不更多著墨了。

對(duì)構(gòu)建一個(gè)在線特征系統(tǒng)而言，實(shí)際上我們需要理解的是我們的特征數(shù)據(jù)是怎樣的。有的數(shù)據(jù)非常熱，我們通過(guò)內(nèi)存副本或者是緩存能夠以極小的內(nèi)存代價(jià)覆蓋大量的請(qǐng)求。有的數(shù)據(jù)不熱，但是一旦訪問(wèn)要求穩(wěn)定而快速的響應(yīng)速度，這時(shí)基于全內(nèi)存的分布式存儲(chǔ)方案就是不錯(cuò)的選擇。對(duì)于數(shù)據(jù)量級(jí)非常大，或者增長(zhǎng)非?？斓臄?shù)據(jù)，我們需要選擇有磁盤(pán)兜底的存儲(chǔ)方案——其中又要根據(jù)各類不同的讀寫(xiě)分布，來(lái)選擇存儲(chǔ)技術(shù)。

當(dāng)業(yè)務(wù)發(fā)展到一定層次后，單一的特征類型將很難覆蓋所有的業(yè)務(wù)需求。所以在存儲(chǔ)方案選型上，需要根據(jù)特征類型進(jìn)行數(shù)據(jù)分層。分層之后，不同的存儲(chǔ)引擎統(tǒng)一對(duì)策略服務(wù)提供特征數(shù)據(jù)，這是保持系統(tǒng)性能和功能兼得的最佳實(shí)踐。

2.2 數(shù)據(jù)壓縮

海量的離線特征加載到線上系統(tǒng)并在系統(tǒng)間流轉(zhuǎn)，對(duì)內(nèi)存、網(wǎng)絡(luò)帶寬等資源都是不小的開(kāi)銷。數(shù)據(jù)壓縮是典型的以時(shí)間換空間的例子，往往能夠成倍減少空間占用，對(duì)于線上珍貴的內(nèi)存、帶寬資源來(lái)說(shuō)是莫大的福音。數(shù)據(jù)壓縮本質(zhì)思想是減少信息冗余，針對(duì)特征系統(tǒng)這個(gè)應(yīng)用場(chǎng)景，我們積累了一些實(shí)踐經(jīng)驗(yàn)與大家分享。

2.2.1 存儲(chǔ)格式

特征數(shù)據(jù)簡(jiǎn)單來(lái)說(shuō)即特征名與特征值。以用戶畫(huà)像為例，一個(gè)用戶有年齡、性別、愛(ài)好等特征。存儲(chǔ)這樣的特征數(shù)據(jù)通常來(lái)說(shuō)有下面幾種方式：

JSON格式，完整保留特征名-特征值對(duì)，以JSON字符串的形式表示。

元數(shù)據(jù)抽取，如Hive一樣，特征名(元數(shù)據(jù))單獨(dú)保存，特征數(shù)據(jù)以String格式的特征值列表表示。

元數(shù)據(jù)固化，同樣將元數(shù)據(jù)單獨(dú)保存，但是采用強(qiáng)類型定義每個(gè)特征，如Integer、Double等而非統(tǒng)一的String類型。

三種格式各有優(yōu)劣：

JSON格式的優(yōu)點(diǎn)在特征數(shù)量可以是變長(zhǎng)的。以用戶畫(huà)像為例，A用戶可能有年齡、性別標(biāo)簽。B用戶可以有籍貫、愛(ài)好標(biāo)簽。不同用戶標(biāo)簽種類可以差別很大，都能便捷的存儲(chǔ)。但缺點(diǎn)是每組特征都要存儲(chǔ)特征名，當(dāng)特征種類同構(gòu)性很高時(shí)，會(huì)包含大量冗余信息。

元數(shù)據(jù)抽取的特點(diǎn)與JSON格式相反，它只保留特征值本身，特征名作為元數(shù)據(jù)單獨(dú)存放，這樣減少了冗余特征名的存儲(chǔ)，但缺點(diǎn)是數(shù)據(jù)格式必須是同構(gòu)的，而且如果需要增刪特征，需要更改元數(shù)據(jù)后刷新整個(gè)數(shù)據(jù)集。

元數(shù)據(jù)固化的優(yōu)點(diǎn)與元數(shù)據(jù)抽取相同，而且更加節(jié)省空間。然而其存取過(guò)程需要實(shí)現(xiàn)專有序列化，實(shí)現(xiàn)難度和讀寫(xiě)速度都有成本。

特征系統(tǒng)中，一批特征數(shù)據(jù)通常來(lái)說(shuō)是完全同構(gòu)的，同時(shí)為了應(yīng)對(duì)高并發(fā)下的批量請(qǐng)求，我們?cè)趯?shí)踐中采用了元數(shù)據(jù)抽取作為存儲(chǔ)方案，相比JSON格式，有2~10倍的空間節(jié)約(具體比例取決于特征名的長(zhǎng)度、特征個(gè)數(shù)以及特征值的類型)。

2.2.2 字節(jié)壓縮

提到數(shù)據(jù)壓縮，很容易就會(huì)想到利用無(wú)損字節(jié)壓縮算法。無(wú)損壓縮的主要思路是將頻繁出現(xiàn)的模式(Pattern)用較短的字節(jié)碼表示?？紤]到在線特征系統(tǒng)的讀寫(xiě)模式是一次全量寫(xiě)入，多次逐條讀取，因此壓縮需要針對(duì)單條數(shù)據(jù)，而非全局壓縮。目前主流的Java實(shí)現(xiàn)的短文本壓縮算法有Gzip、Snappy、Deflate、LZ4等，我們做了兩組實(shí)驗(yàn)，主要從單條平均壓縮速度、單條平均解壓速度、壓縮率三個(gè)指標(biāo)來(lái)對(duì)比以上各個(gè)算法。

數(shù)據(jù)集：我們選取了2份線上真實(shí)的特征數(shù)據(jù)集，分別取10萬(wàn)條特征記錄。記錄為純文本格式，平均長(zhǎng)度為300~400字符(600~800字節(jié))。

壓縮算法：Deflate算法有1~9個(gè)壓縮級(jí)別，級(jí)別越高，壓縮比越大，操作所需要的時(shí)間也越長(zhǎng)。而LZ4算法有兩個(gè)壓縮級(jí)別，我們用0，1表示。除此之外，LZ4有不同的實(shí)現(xiàn)版本：JNI、Java Unsafe、Java Safe，詳細(xì)區(qū)別參考 https://github.com/lz4/lz4-java ，這里不做過(guò)多解釋。

實(shí)驗(yàn)結(jié)果圖中的毫秒時(shí)間為單條記錄的壓縮或解壓縮時(shí)間。壓縮比的計(jì)算方式為壓縮前字節(jié)碼長(zhǎng)度/壓縮后字節(jié)碼長(zhǎng)度?？梢钥闯?，所有壓縮算法的壓縮/解壓時(shí)間都會(huì)隨著壓縮比的上升而整體呈上升趨勢(shì)。其中LZ4的Java Unsafe、Java Safe版由于考慮平臺(tái)兼容性問(wèn)題，出現(xiàn)了明顯的速度異常。

從使用場(chǎng)景(一次全量寫(xiě)入，多次逐條讀取)出發(fā)，特征系統(tǒng)主要的服務(wù)指標(biāo)是特征高并發(fā)下的響應(yīng)時(shí)間與特征數(shù)據(jù)存儲(chǔ)效率。因此特征壓縮關(guān)注的指標(biāo)其實(shí)是：快速的解壓速度與較高的壓縮比，而對(duì)壓縮速度其實(shí)要求不高。因此綜合上述實(shí)驗(yàn)中各個(gè)算法的表現(xiàn)，Snappy是較為合適我們的需求。

2.2.3 字典壓縮

壓縮的本質(zhì)是利用共性，在不影響信息量的情況下進(jìn)行重新編碼，以縮減空間占用。上節(jié)中的字節(jié)壓縮是單行壓縮，因此只能運(yùn)用到同一條記錄中的共性，而無(wú)法顧及全局共性。舉個(gè)例子：假設(shè)某個(gè)用戶維度特征所有用戶的特征值是完全一樣的，字節(jié)壓縮逐條壓縮不能節(jié)省任何的存儲(chǔ)空間，而我們卻知道實(shí)際上只有一個(gè)重復(fù)的值在反復(fù)出現(xiàn)。即便是單條記錄內(nèi)部，由于壓縮算法窗口大小的限制，長(zhǎng)Pattern也很難被顧及到。因此，對(duì)全局的特征值做一次字典統(tǒng)計(jì)，自動(dòng)或人工的將頻繁P(pán)attern加入到字典并重新編碼，能夠解決短文本字節(jié)壓縮的局限性。

2.3 數(shù)據(jù)同步

當(dāng)每次請(qǐng)求，策略計(jì)算需要大量的特征數(shù)據(jù)時(shí)(比如一次請(qǐng)求上千條的廣告商特征)，我們需要非常強(qiáng)悍的在線數(shù)據(jù)獲取能力。而在存儲(chǔ)特征的不同方法中，訪問(wèn)本地內(nèi)存毫無(wú)疑問(wèn)是性能最佳的解決方式。想要在本地內(nèi)存中訪問(wèn)到特征數(shù)據(jù)，通常我們有兩種有效手段：內(nèi)存副本和客戶端緩存。

2.3.1 內(nèi)存副本技術(shù)

當(dāng)數(shù)據(jù)總量不大時(shí)，策略使用方可以在本地完全鏡像一份特征數(shù)據(jù)，這份鏡像叫內(nèi)存副本。使用內(nèi)存副本和使用本地的數(shù)據(jù)完全一致，使用者無(wú)需關(guān)心遠(yuǎn)端數(shù)據(jù)源的存在。內(nèi)存副本需要和數(shù)據(jù)源通過(guò)某些協(xié)議進(jìn)行同步更新，這類同步技術(shù)稱為內(nèi)存副本技術(shù)。在線特征系統(tǒng)的場(chǎng)景中，數(shù)據(jù)源可以抽象為一個(gè)KV類型的數(shù)據(jù)集，內(nèi)存副本技術(shù)需要把這樣一個(gè)數(shù)據(jù)集完整的同步到內(nèi)存副本中。

推拉結(jié)合——時(shí)效性和一致性

一般來(lái)說(shuō)，數(shù)據(jù)同步為兩種類型：推(Push)和拉(Pull)。Push的技術(shù)比較簡(jiǎn)單，依賴目前常見(jiàn)的消息隊(duì)列中間件，可以根據(jù)需求做到將一個(gè)數(shù)據(jù)變化傳送到一個(gè)內(nèi)存副本中。但是，即使實(shí)現(xiàn)了不重不漏的高可靠性消息隊(duì)列通知(通常代價(jià)很大)，也還面臨著初始化啟動(dòng)時(shí)批量數(shù)據(jù)同步的問(wèn)題——所以，Push只能作為一種提高內(nèi)存副本時(shí)效性的手段，本質(zhì)上內(nèi)存副本同步還得依賴Pull協(xié)議。Pull類的同步協(xié)議有一個(gè)非常好的特性就是冪等，一次失敗或成功的同步不會(huì)影響下一次進(jìn)行新的同步。

Pull協(xié)議有非常多的選擇，最簡(jiǎn)單的每次將所有數(shù)據(jù)全量拉走就是一種基礎(chǔ)協(xié)議。但是在業(yè)務(wù)需求中需要追求數(shù)據(jù)同步效率，所以用一些比較高效的Pull協(xié)議就很重要。為了縮減拉取數(shù)據(jù)量，這些協(xié)議本質(zhì)上來(lái)說(shuō)都是希望高效的計(jì)算出盡量精確的數(shù)據(jù)差異(Diff)，然后同步這些必要的數(shù)據(jù)變動(dòng)。這里介紹兩種我們?cè)?jīng)在工程實(shí)踐中應(yīng)用過(guò)的Pull型數(shù)據(jù)同步協(xié)議。

基于版本號(hào)同步——回放日志(RedoLog)和退化算法

在數(shù)據(jù)源更新時(shí)，對(duì)于每一次數(shù)據(jù)變化，基于版本號(hào)的同步算法會(huì)為這次變化分配一個(gè)唯一的遞增版本號(hào)，并使用一個(gè)更新隊(duì)列記錄所有版本號(hào)對(duì)應(yīng)的數(shù)據(jù)變化。

內(nèi)存副本發(fā)起同步請(qǐng)求時(shí)，會(huì)攜帶該副本上一次完成同步時(shí)的最大版本號(hào)，這意味著所有該版本號(hào)之后的數(shù)據(jù)變化都需要被拉取過(guò)來(lái)。數(shù)據(jù)源方收到請(qǐng)求后，從更新隊(duì)列中找到大于該版本號(hào)的所有數(shù)據(jù)變化，并將數(shù)據(jù)變化匯總，得到最終需要更新的Diff，返回給發(fā)起方。此時(shí)內(nèi)存副本只需要更新這些Diff數(shù)據(jù)即可。

對(duì)于大多數(shù)的業(yè)務(wù)場(chǎng)景，特征數(shù)據(jù)的生成會(huì)收口到一個(gè)統(tǒng)一的更新服務(wù)中，所以遞增版本號(hào)可以串行的生成。如果在分布式的數(shù)據(jù)更新環(huán)境中，則需要利用分布式id生成器來(lái)獲取遞增版本號(hào)。

另一個(gè)問(wèn)題則是更新隊(duì)列的長(zhǎng)度。如果不進(jìn)行任何優(yōu)化，更新隊(duì)列理論上是無(wú)限長(zhǎng)的，甚至?xí)^(guò)數(shù)據(jù)集的大小。一個(gè)優(yōu)化方法是我們限制住更新隊(duì)列的最大長(zhǎng)度，一旦長(zhǎng)度超過(guò)限制，則執(zhí)行合并(Merge)操作。Merge操作將隊(duì)列中的數(shù)據(jù)進(jìn)行兩兩合并，合并后的版本號(hào)以較大的版本號(hào)為準(zhǔn)，合并后的更新數(shù)據(jù)集是兩個(gè)數(shù)據(jù)集的并。Merge后，新的隊(duì)列長(zhǎng)度下降為原更新隊(duì)列的一半。

Merge之后的更新隊(duì)列，我們依然可以使用相同的算法進(jìn)行同步Diff計(jì)算：在隊(duì)列中找到大于上一次更新版本號(hào)的所有數(shù)據(jù)集?？梢钥吹接捎诎姹咎?hào)的合并，算出的Diff不再是完全精準(zhǔn)的更新數(shù)據(jù)，在隊(duì)列中最早的更新數(shù)據(jù)集有可能包含部分已經(jīng)同步過(guò)的數(shù)據(jù)——但這樣的退化并不影響同步正確性，僅僅會(huì)造成少量的同步冗余，冗余的量取決于Diff中最早的數(shù)據(jù)集經(jīng)過(guò)Merge的次數(shù)。

MerkleTree同步——數(shù)據(jù)集對(duì)比算法

基于版本號(hào)的同步使用的是類似RedoLog的思想，將業(yè)務(wù)變動(dòng)的歷史記錄下來(lái)，并通過(guò)回放未同步的歷史記錄得到Diff。由于記錄不斷增長(zhǎng)的RedoLog需要不小的開(kāi)銷，所以采用了Merge策略來(lái)退化原始日志(Log)。對(duì)于批量或者微批量的更新來(lái)說(shuō)，基于版本號(hào)的同步算法能較好的工作;相反，若數(shù)據(jù)是實(shí)時(shí)更新的，將會(huì)出現(xiàn)大量的RedoLog，并快速的退化，影響同步的效率。

Merkle Tree同步算法走的是另一條路，簡(jiǎn)單來(lái)說(shuō)就是通過(guò)每次直接比較兩個(gè)數(shù)據(jù)集的差異來(lái)獲取Diff。首先看一個(gè)最簡(jiǎn)單的算法：每次內(nèi)存副本將所有數(shù)據(jù)的Hash值發(fā)送給數(shù)據(jù)源，數(shù)據(jù)源比較整個(gè)數(shù)據(jù)集，對(duì)于Hash值不同的數(shù)據(jù)執(zhí)行同步操作——這樣就精確計(jì)算出了兩個(gè)數(shù)據(jù)集之間的Diff。但顯而易見(jiàn)的問(wèn)題，是每次傳輸所有數(shù)據(jù)的Hash值可能并不比多傳幾個(gè)數(shù)據(jù)輕松。Merkle Tree同步算法就是使用Merkle Tree數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化這一比較過(guò)程。

Merkle Tree簡(jiǎn)單來(lái)說(shuō)是就是把所有數(shù)據(jù)集的hash值組織成一棵樹(shù)，這棵樹(shù)的葉子節(jié)點(diǎn)描述一個(gè)(或一組)數(shù)據(jù)的Hash值。而中間節(jié)點(diǎn)的值由其所有兒子的Hash值再次Hash得到，描述了以它為根的子樹(shù)所包含的數(shù)據(jù)的整體Hash。顯然，在不考慮Hash沖突的情況下，如果兩顆Merkle Tree根節(jié)點(diǎn)相同，代表這是兩個(gè)完全相同的數(shù)據(jù)集。

Merkle Tree同步協(xié)議由副本發(fā)起，將副本根節(jié)點(diǎn)值發(fā)送給數(shù)據(jù)源，若與數(shù)據(jù)源根節(jié)點(diǎn)hash值一致，則沒(méi)有數(shù)據(jù)變動(dòng)，同步完成。否則數(shù)據(jù)源將把根結(jié)點(diǎn)的所有兒子節(jié)點(diǎn)的hash發(fā)送給副本，進(jìn)行遞歸比較。對(duì)于不同的hash值，一直持續(xù)獲取直到葉子節(jié)點(diǎn)，就可以完全確定已經(jīng)改變的數(shù)據(jù)。以二叉樹(shù)為例，所有的數(shù)據(jù)同步最多經(jīng)過(guò)LogN次交互完成。

2.3.2 客戶端緩存技術(shù)

當(dāng)數(shù)據(jù)規(guī)模大，無(wú)法完全放入到內(nèi)存中，冷熱數(shù)據(jù)分明，對(duì)于數(shù)據(jù)時(shí)效性要求又不高的時(shí)候，通常各類業(yè)務(wù)都會(huì)采用客戶端緩存?？蛻舳司彺娴募袑?shí)現(xiàn)，是特征服務(wù)延伸的一部分。通用的緩存協(xié)議和使用方式不多說(shuō)，從在線特征系統(tǒng)的業(yè)務(wù)角度出發(fā)，這里給出幾個(gè)方向的思考和經(jīng)驗(yàn)。

接口通用化——緩存邏輯與業(yè)務(wù)分離

一個(gè)特征系統(tǒng)要滿足各類業(yè)務(wù)需求，它的接口肯定是豐富的。從數(shù)據(jù)含義角度分有用戶類、商戶類、產(chǎn)品類等等，從數(shù)據(jù)傳輸協(xié)議分有Thrift、HTTP，從調(diào)用方式角度分有同步、異步，從數(shù)據(jù)組織形式角度分有單值、List、Map以及相互嵌套等等……一個(gè)良好的架構(gòu)設(shè)計(jì)應(yīng)該盡可能將數(shù)據(jù)處理與業(yè)務(wù)剝離開(kāi)，抽象各個(gè)接口的通用部分，一次緩存實(shí)現(xiàn)，多處接口同時(shí)受益復(fù)用。下面以同步異步接口為例介紹客戶端接口通用化。

同步接口只有一步：

向服務(wù)端發(fā)起請(qǐng)求得到結(jié)果。

異步接口分為兩步：

向服務(wù)端發(fā)起請(qǐng)求得到Future實(shí)例。

向Future實(shí)例發(fā)起請(qǐng)求，得到數(shù)據(jù)。

同步和異步接口的數(shù)據(jù)處理只有順序的差別，只需要梳理好各個(gè)步驟的執(zhí)行順序即可。引入緩存后，數(shù)據(jù)處理流程對(duì)比如下：

不同顏色的處理框表示不同的請(qǐng)求。異步流程需要使用方的兩次請(qǐng)求才能獲取到數(shù)據(jù)。像圖中“用服務(wù)端數(shù)據(jù)更新緩存”(update cache)、“服務(wù)端數(shù)據(jù)與緩存數(shù)據(jù)匯總”(merge data)步驟在異步流程里是在第二次請(qǐng)求中完成的，區(qū)別于同步流程第一次請(qǐng)求就完成所有步驟。將數(shù)據(jù)流程拆分為這些子步驟，同步與異步只是這些步驟的不同順序的組合。因此讀寫(xiě)緩存(search cache、update cache)這兩個(gè)步驟可以抽象出來(lái)，與其余邏輯解耦。

數(shù)據(jù)存儲(chǔ)——時(shí)間先于空間，客戶端與服務(wù)端分離

客戶端之于服務(wù)端，猶如服務(wù)端之于數(shù)據(jù)庫(kù)，其實(shí)數(shù)據(jù)存儲(chǔ)壓縮的思路是完全一樣的。具體的數(shù)據(jù)壓縮與存儲(chǔ)策略在上文數(shù)據(jù)壓縮章節(jié)已經(jīng)做了詳細(xì)介紹，這里主要想說(shuō)明兩點(diǎn)問(wèn)題：

客戶端壓縮與服務(wù)端壓縮由于應(yīng)用場(chǎng)景的不同，其目標(biāo)是有差異的。服務(wù)端壓縮使用場(chǎng)景是一次性高吞吐寫(xiě)入，逐條高并發(fā)低延遲讀取，它主要關(guān)注的是讀取時(shí)的解壓時(shí)間和數(shù)據(jù)存儲(chǔ)時(shí)的壓縮比。而客戶端緩存屬于數(shù)據(jù)存儲(chǔ)分層中最頂端的部分，由于讀寫(xiě)的場(chǎng)景都是高并發(fā)低延遲的本地內(nèi)存操作，因此對(duì)壓縮速度、解壓速度、數(shù)據(jù)量大小都有很高要求，它要做的權(quán)衡更多。

其次，客戶端與服務(wù)端是兩個(gè)完全獨(dú)立的模塊，說(shuō)白了，雖然我們會(huì)編寫(xiě)客戶端代碼，但它不屬于服務(wù)的一部分，而是調(diào)用方服務(wù)的一部分?？蛻舳说臄?shù)據(jù)壓縮應(yīng)該盡量與服務(wù)端解耦，切不可為了貪圖實(shí)現(xiàn)方便，將兩者的數(shù)據(jù)格式耦合在一起，與服務(wù)端的數(shù)據(jù)通信格式應(yīng)該理解為一種獨(dú)立的協(xié)議，正如服務(wù)端與數(shù)據(jù)庫(kù)的通信一樣，數(shù)據(jù)通信格式與數(shù)據(jù)庫(kù)的存儲(chǔ)格式?jīng)]有任何關(guān)系。

內(nèi)存管理——緩存與分代回收的矛盾

緩存的目標(biāo)是讓熱數(shù)據(jù)(頻繁被訪問(wèn)的數(shù)據(jù))能夠留在內(nèi)存，以便提高緩存命中率。而JVM垃圾回收(GC)的目標(biāo)是釋放失去引用的對(duì)象的內(nèi)存空間。兩者目標(biāo)看上去相似，但細(xì)微的差異讓兩者在高并發(fā)的情景下很難共存。緩存的淘汰會(huì)產(chǎn)生大量的內(nèi)存垃圾，使Full GC變得非常頻繁。這種矛盾其實(shí)不限于客戶端，而是所有JVM堆內(nèi)緩存共同面臨的問(wèn)題。下面我們仔細(xì)分析一個(gè)場(chǎng)景：

隨著請(qǐng)求產(chǎn)生的數(shù)據(jù)會(huì)不斷加入緩存，QPS較高的情形下，Young GC頻繁發(fā)生，會(huì)不斷促使緩存所占用的內(nèi)存從新生代移向老年代。緩存被填滿后開(kāi)始采用Least Recently Used(LRU)算法淘汰，冷數(shù)據(jù)被踢出緩存，成為垃圾內(nèi)存。然而不幸的是，由于頻繁的Young GC，有很多冷數(shù)據(jù)進(jìn)入了老年代，淘汰老年代的緩存，就會(huì)產(chǎn)生老年代的垃圾，從而引發(fā)Full GC。

可以看到，正是由于緩存的淘汰機(jī)制與新生代的GC策略目標(biāo)不一致，導(dǎo)致了緩存淘汰會(huì)產(chǎn)生很多老年代的內(nèi)存垃圾，而且產(chǎn)生垃圾的速度與緩存大小沒(méi)有太多關(guān)系，而與新生代的GC頻率以及堆緩存的淘汰速度相關(guān)。而這兩個(gè)指標(biāo)均與QPS正相關(guān)。因此堆內(nèi)緩存仿佛成了一個(gè)通向老年代的垃圾管道，QPS越高，垃圾產(chǎn)生越快!

因此，對(duì)于高并發(fā)的緩存應(yīng)用，應(yīng)該避免采用JVM的分帶管理內(nèi)存，或者可以說(shuō)，GC內(nèi)存回收機(jī)制的開(kāi)銷和效率并不能滿足高并發(fā)情形下的內(nèi)存管理的需求。由于JVM虛擬機(jī)的強(qiáng)制管理內(nèi)存的限制，此時(shí)我們可以將對(duì)象序列化存儲(chǔ)到堆外(Off Heap)，來(lái)達(dá)到繞開(kāi)JVM管理內(nèi)存的目的，例如Ehcache，BigMemory等第三方技術(shù)便是如此。或者改動(dòng)JVM底層實(shí)現(xiàn)(類似之前淘寶的做法)，做到堆內(nèi)存儲(chǔ)，免于GC。

三、結(jié)束語(yǔ)

本文主要介紹了一些在線特征系統(tǒng)的技術(shù)點(diǎn)，從系統(tǒng)的高并發(fā)、高吞吐、大數(shù)據(jù)、低延遲的需求出發(fā)，并以一些實(shí)際特征系統(tǒng)為原型，提出在線特征系統(tǒng)的一些設(shè)計(jì)思路。正如上文所說(shuō)，特征系統(tǒng)的邊界并不限于數(shù)據(jù)的存儲(chǔ)與讀取。像數(shù)據(jù)導(dǎo)入作業(yè)調(diào)度、實(shí)時(shí)特征、特征計(jì)算與生產(chǎn)、數(shù)據(jù)備份、容災(zāi)恢復(fù)等等，都可看作為特征系統(tǒng)的一部分。本文是在線特征系統(tǒng)系列文章的第一篇，我們的特征系統(tǒng)也在需求與挑戰(zhàn)中不斷演進(jìn)，后續(xù)會(huì)有更多實(shí)踐的經(jīng)驗(yàn)與大家分享。一家之言，難免有遺漏和偏頗之處，但是他山之石可以攻玉，若能為各位架構(gòu)師在面向自己業(yè)務(wù)時(shí)提供一些思路，善莫大焉。

來(lái)源：36大數(shù)據(jù)