大數(shù)據(jù)實時處理：百分點實時計算架構(gòu)和算法

1、百分點大數(shù)據(jù)實時計算實踐：架構(gòu)和算法當今時代，數(shù)據(jù)不再昂貴，但從海量數(shù)據(jù)中獲取價值變得昂貴，而要及時獲取價值則更加昂貴，這正是大數(shù)據(jù)實時計算越來越流行的原因。以百分點公司為例,在高峰期每秒鐘會有近萬請求發(fā)送到百分點服務(wù)器上，這些請求包含了用戶行為和個性化推薦請求。如何從這些數(shù)據(jù)中快速挖掘用戶興趣偏好并作出效果不錯的推薦呢？這是百分點推薦引擎面臨的首要問題。本文將從系統(tǒng)架構(gòu)和算法兩方面全介紹百分點公司在實時計算方面的經(jīng)驗和心得體會，供讀者參考。實時計算架構(gòu)工欲善其事，必先利其器。一個穩(wěn)定可靠且高效的底層架構(gòu)是實時計算的必要基礎(chǔ)。圖給出了百分點數(shù)據(jù)大平臺的總體框架，如圖所示，大數(shù)據(jù)平臺包含數(shù)據(jù)存儲

2、和數(shù)據(jù)處理兩個層次。存儲服務(wù)層提供了數(shù)據(jù)處理層需要的各類分布式存儲，包括分布式文件系統(tǒng)（H分布式數(shù)據(jù)庫（）分布式數(shù)據(jù)庫（d、S分布式消息隊列（）分布式搜索引擎（）以及必不可少的。數(shù)據(jù)處理層由四個部分組成。其中應(yīng)用云包含了所有直接面對用戶的b服務(wù)，每個應(yīng)用都會產(chǎn)生日志以及其他實時數(shù)據(jù)，這些數(shù)據(jù)一方面會及時交由實時計算框架進行處理，另一方面也會定期同步至離線計算框架；實時計算框架會處理接收到的實時數(shù)據(jù)，并將處理結(jié)果輸出到數(shù)據(jù)查詢框架或者離線計算框架；離線計算框架則定期對數(shù)據(jù)進行處理，并將處理結(jié)果輸出至數(shù)據(jù)查詢框架；數(shù)據(jù)查詢框架提供了一系列應(yīng)用接口供程序調(diào)取需要的各項數(shù)據(jù)，同時提供了一些工具幫助業(yè)務(wù)

3、人員對海量數(shù)據(jù)進行統(tǒng)計、匯總和分析。在百分點大數(shù)據(jù)平臺中，與實時計算密切相關(guān)的有實時計算框架和數(shù)據(jù)查詢框架，這部分的組件架構(gòu)和數(shù)據(jù)流如圖2所示。中的數(shù)據(jù)會被兩個處理平臺（）和消費并處理。是當下比較流行的開源流處理框架，百分點公司在年中開始使用進行數(shù)據(jù)清洗、統(tǒng)計和一部分分析任務(wù)。在引入之前，百分點所有的實時計算都是基于進行的，它是我們基于中間件開發(fā)的一套流處理平臺。包含有四類組件:負責從中讀取消息，根據(jù)消息內(nèi)容分發(fā)給相應(yīng)的復雜處理接收到的消息，并將處理結(jié)果傳遞給其他在交互關(guān)系或配置更新時及時通知和；負責監(jiān)控和的運行情況,把監(jiān)控信息提交給,還負責系統(tǒng)異常時的報警，以及和發(fā)生故障時進行重啟和遷移。數(shù)

4、據(jù)查詢框架由圖中最下層的三個組件組成，其中()封裝了一系列的數(shù)據(jù)查詢邏輯并以和服務(wù)的形式供各種應(yīng)用調(diào)用；(或者輸出到各類存儲服務(wù)中；負責維護和的交互關(guān)系和配置信息，并）提供了實時查詢用戶行為和標簽明細，以及近實時的用戶多維度統(tǒng)計、匯總和分析功能，這些功能是以和應(yīng)用方式提供的;是對和的一次封裝，以和服務(wù)方式對外提供近實時搜索功能。百分點公司的主要服務(wù)都是運行在這套架構(gòu)上的，它擁有良好的穩(wěn)定性和擴展性，一般來說只需要增加水平擴展結(jié)點即可提高數(shù)據(jù)處理能力,這為百分點業(yè)務(wù)的穩(wěn)定發(fā)展奠定了技術(shù)基礎(chǔ)。實時計算算法要真正實現(xiàn)大數(shù)據(jù)實時計算，光有框架是不行的，還必須針對特定業(yè)務(wù)開發(fā)特定的處理流程和算法。相比較

5、離線計算而言，實時計算在算法方面需要考慮的更多，這是因為實時計算能夠用到的存儲資源遠不如離線，而且處理過程的時間限制要比離線計算嚴格，這都要求實時計算算法必須做相當多的優(yōu)化。在這一節(jié)中，筆者將以海量計數(shù)問題為例介紹百分點公司在實時計算算法方面的經(jīng)驗。目前，百分點數(shù)據(jù)平臺上包含了近千萬的電商單品數(shù)據(jù)，實時追蹤這些單品的瀏覽和交易數(shù)據(jù)是必須的，這也是做個性化推薦、商品畫像、銷量預測和用戶畫像等業(yè)務(wù)的必要前提。我們的問題是：如何設(shè)計一種算法使得我們可以實時查看任意單品最近24小時的瀏覽量1？這個問題描述起來很簡單，但稍加思索就會發(fā)現(xiàn)做起來并不容易。下面我們先給出一個簡單方案，而后按照一定的原則逐步精

6、化到最佳方案。簡單方案圖按秒計數(shù)方1-看到這個問題時，大部分讀者會很快想到如圖所示的算法方案。圖中紅色、藍色和綠色的方塊分別表示不同的單品。在這個方案中，我們?yōu)槊總€單品保存一份瀏覽信息,它包含兩個數(shù)據(jù)結(jié)構(gòu)：歷史瀏覽量列表（簡稱歷史），一個列表，列表中每個元素包含一個時間戳和一個整數(shù)，分別代表過去24小時中2的某一秒及這一秒鐘的瀏覽量，按時間順序排序。這個列表的最長會包含24*3600=個8元6素4，0但0一般情況下極少有單品時時刻刻都被瀏覽，我們可以假設(shè)這個列表的平均長度不超過。累計瀏覽量（簡稱累計量），一個整數(shù)，代表截止到最后一次訪問時的瀏覽量。如圖所示，假設(shè)藍色單品對應(yīng)的數(shù)據(jù)是禾口。這表示

7、時刻的該單品1現(xiàn)實中，我們往往只需要查看當天的瀏覽量，即從當天的0點開始到當前時間的瀏覽量，這與文中的提到的問題是完全不同的，前者是指定了起始時間，后者是按時間窗口滾動。研究按時間窗口滾動的問題是非常重要的，特別是針對包含時間衰減的數(shù)據(jù)模型和算法而言。2“過去24小時”這一說法不是特別準確，但對理解計算過程有幫助。讀者在后面的處理過程中會發(fā)現(xiàn)，如果某個單品沒有被瀏覽，那它對應(yīng)的這個列表永遠不會被修改。瀏覽量是,時刻是,是最后一次記錄到瀏覽該單品的時刻，瀏覽量是n截止到,該單品的總瀏覽量是。當單品瀏覽源源不斷進入到消息隊列時，處理進程（或線程），會實時讀取到這些信息，并修改對應(yīng)單品的數(shù)據(jù)信息。例

8、如，讀取到時亥0對藍色單品的瀏覽記錄時，會進行下面的操作：得到當前時刻；TOC o 1-5 h z對數(shù)據(jù)庫中藍色單品數(shù)據(jù)加鎖，加鎖成功后讀取出數(shù)據(jù)，假設(shè)歷史是，累計量是；累計量遞增，即從修改為如果,則更新歷史為，否則更新為；最后刪除時間戳小于的列表元素，刪除的同時從累計量中減去對應(yīng)時刻的瀏覽量，例如只有元素,則操作完成后的瀏覽量為；將新的歷史和累計量輸出至數(shù)據(jù)庫，釋放鎖。不難驗證這個方案是可以正確得出每個單品小時內(nèi)的瀏覽量的,并且只要在資源（計算、存儲和網(wǎng)絡(luò)）充足的情況下,數(shù)據(jù)庫中單品的瀏覽量是實時更新的。這個方案也是分布式實時計算中最簡單最常見的一種模式。避免鎖圖不包含鎖的方案第一個方案中需

9、要對數(shù)據(jù)庫加鎖,無論加鎖粒度多細,都會嚴重影響計算效率。雖然像一類的內(nèi)存數(shù)據(jù)庫提供了這樣的原子操作，但這種操作多數(shù)情況下只適用于整型數(shù)據(jù)，并不適合本問題的歷史數(shù)據(jù)。要想提高實時處理效率,避免鎖是非常重要的。一種常見的做法是將并行操作串行化,就像中的階段一樣,將相同的數(shù)據(jù)交由同一個處理?；谶@個原理,我們3實際情況要比這里復雜一些，因為消息隊列中的消息不一定完全按時間遞增排序，屆時還必須將新的數(shù)據(jù)插入或合并到適當?shù)奈恢貌判小？梢詫⒎桨父脑鞛槿鐖D4所示，我們新增一個數(shù)據(jù)分發(fā)處理過程，它的作用是保證同一個單品的所有數(shù)據(jù)都會發(fā)送給同一個處理程序。例如將藍色單品交由處理,紅色交由處理,綠色交由處理。這樣

10、在處理過程中不需要對數(shù)據(jù)庫加鎖，因為不存在資源競爭。這樣可以極大的提高計算效率，于是整個計算過程變?yōu)椋旱玫疆斍皶r刻；讀取數(shù)據(jù)庫中藍色單品信息，假設(shè)歷史是2累計量是；累計遞增，即從修改為如果，則更新歷史為，否則更新為；最后刪除時間戳小于的列表元素，刪除的同時從累量中減去對應(yīng)時刻的瀏覽量；將新的歷史和累計量輸出至數(shù)據(jù)庫。步驟和省去了鎖操作，整個系統(tǒng)的并發(fā)性和吞吐量會得到大大提高。當然，沒有免費的午餐，這種方案的缺點在于存在單點隱患，例如一旦由于某些原因掛掉了，那么藍色單品的數(shù)據(jù)將得不到及時處理，計數(shù)結(jié)果將無法保證實時。這種計算過程對系統(tǒng)監(jiān)控和故障轉(zhuǎn)移會有很高的要求。P1數(shù)據(jù)分層方案二已經(jīng)可以大大提

11、高計算效率，但這還不夠，我們可以看到在計算步驟和中總是要把歷史和累計量同時從數(shù)據(jù)庫中讀出或?qū)懭?，實際上這是沒有必要的，因為只有累計量才是外部必須使用的數(shù)據(jù)，而歷史只是算法的中間數(shù)據(jù)。這樣，我們可以區(qū)別對待歷史和累計量，我們將歷史和累計量都緩存在計算進程中，定期更新歷史至數(shù)據(jù)庫，而累計量則實時更新。新的方案如錯誤！未找到引用源。所示，計算過程變?yōu)?得到當前時刻;s如果本地沒有藍色單品的信息,則從數(shù)據(jù)庫中讀取藍色單品信息;否則直接使用本地緩存的信息。假設(shè)歷史是t.tt,累計量是;t累計量遞增，即從修改為如果tt,則更新歷史為tt;最后刪除時間戳小于tt，否則更新為tttt的列表兀素，刪除的同時從累

12、計量中減去對應(yīng)時亥啲瀏覽量；v）將新的累計量輸出至數(shù)據(jù)庫；如果滿足一定的條件（例如上次輸出時間足夠久遠，或者處理的消息量達到一定數(shù)量），則將歷史輸出至數(shù)據(jù)庫。這種方案可以大大降低數(shù)據(jù)庫壓力、數(shù)據(jù)和序列化反序列化次數(shù)，從而提高整個系統(tǒng)的處理效率。數(shù)據(jù)分層實際上是計算機中一種常用的路數(shù)，例如硬件中的高速緩存內(nèi)存磁盤,系統(tǒng)中的緩沖區(qū)磁盤文件，數(shù)據(jù)庫的內(nèi)存索引、系統(tǒng)緩存等等。我們使用的開源搜索引擎。就使用了同樣的思路達到近實時索引。0包含磁盤全量索引和實時增加的內(nèi)存增量索引，并引入了“soft提交”的方式更新新索引。新數(shù)據(jù)到達后，0會使用“soft提交的方式更新內(nèi)存增量索引,在檢索的時候通過同時請求全

13、量索引和增量索引并合并的方式獲得到最新的數(shù)據(jù)。之后會在服務(wù)器空閑的時候,0會把內(nèi)存增量索引合并到磁盤全量索引中保證數(shù)據(jù)完整。當然，這種方案也對系統(tǒng)的穩(wěn)定性提出了更高的要求,因為一旦掛掉那么它緩存的數(shù)據(jù)將丟失,及時及時重啟，這些數(shù)據(jù)也無法恢復,那么在一段時間內(nèi)我們將無法得到準確的實時瀏覽量。模糊化現(xiàn)在,我們來考慮存儲資源問題。假設(shè)時間戳和整型都用。類型（字節(jié)）保存，那么按照方案一中的估計，我們對每個單品的需要記錄的數(shù)據(jù)大小約為0）字節(jié)K萬單品的數(shù)據(jù)總量將超過,如果考慮到數(shù)據(jù)庫和本地緩存因素，那么整個系統(tǒng)需要的存儲量至少是！這對于計數(shù)這個問題而言顯然是得不償失的，我們必須嘗試將數(shù)據(jù)量降低，在這個問

14、題中可行的是降低歷史的存儲精度。我們將歷史定義為小時級別精度，這樣每個單品的歷史至多有24個，數(shù)據(jù)量最多392字節(jié),萬單品的信息總量將變?yōu)?系統(tǒng)總的存儲量不超過,這是可以接受的。如果考慮用t類型代替o類型存儲時間（小時數(shù)），則存儲量可以進一步降低到不足g這樣新的計算過程變?yōu)椋旱玫疆斍皶r刻精確到小時的部分t如果本地沒有藍色單品的信息,則從數(shù)據(jù)庫中讀取藍色單品信息;否則直接使用本地緩存的信息。假設(shè)歷史是t.tt，累計量是；累計量遞增，即從修改為如果tt,則更新歷史為ttt，否則更新為tttX;最后刪除小時數(shù)小于的列表兀素，刪除的同時從累計量中減去對應(yīng)時刻的瀏覽量；將新的瀏覽量輸出至數(shù)據(jù)庫；如果滿足

15、一定的條件，則將歷史輸出至數(shù)據(jù)庫。在這種方案下，數(shù)據(jù)庫中存儲的并不是過去24小時內(nèi)的瀏覽量，而是過去23小時多一點內(nèi)的。例如在月日：時數(shù)據(jù)庫中的瀏覽量實際上是月日：到月日：的瀏覽量！這種降低數(shù)據(jù)精度的方法我們可以稱之為模糊化，它是用資源換效率的一種方法。在對數(shù)據(jù)精確性不是特別敏感的領(lǐng)域，這種方法可以大大降低系統(tǒng)資源使用量、提高系統(tǒng)的處理效率。利用模糊化的實時算法快速得到近似結(jié)果，而后用離線算法慢慢修正結(jié)果的精確度，是百分點在大數(shù)據(jù)處理中經(jīng)常使用的招數(shù)。局部精化12-1241112klk2k3k424圖局部精華示意圖有時候，模糊化會掩蓋掉一些重要的細節(jié)信息，達不到業(yè)務(wù)需求的要求。例如，電商有很多

16、的秒殺活動，此時必須及時監(jiān)測單品瀏覽量，如果我們還按小時維度進行計算，那顯然不能滿足要求。這種情況下我們就必須對局部數(shù)據(jù)進行細化，它是模糊化的逆操作，我們稱之為局部精化。如錯誤！未找到引用源。所示，第小時的數(shù)據(jù)是很敏感的，我們希望它的數(shù)據(jù)能更實時一些，那我們可以將第小時的數(shù)據(jù)切分的更細，對它做分鐘、分鐘甚至秒級別的計算，而其他時間段仍舊采用小時精度。這種方案會增加系統(tǒng)的設(shè)計和開發(fā)難度，而且必須有靈活的配置才能滿足多變的業(yè)務(wù)需求。數(shù)據(jù)建模除了局部細化，還有一種方法可以提高數(shù)據(jù)的精確度，這就是數(shù)據(jù)建模。在方案四中我們提到在小時精度下，實際上只能得到23小時多一點之前的瀏覽量，有一部分數(shù)據(jù)丟失了沒有

17、用到。實際上我們可以將丟棄掉的數(shù)據(jù)利用起來得到更好的結(jié)果。最簡單思路是假設(shè)同一小時內(nèi)單品的瀏覽量是線性增加的，那么我們顯然可以利用相鄰兩個小時的瀏覽歷史推算出任意時刻的瀏覽量?；氐椒桨杆闹械睦樱?月2日12：15的實時瀏覽量可以通過下面的公式計算得出：其中代表月日之間的瀏覽量，依次類推，代表月日之間的瀏覽量。公式中的X估計了月日：之間的瀏覽量，這樣就得出了從月日：到月日：之間小時內(nèi)的瀏覽量。圖某單品的全天瀏覽分利用更復雜的瀏覽量分布模型得出精度更高的估計圖給出了某單品一天的瀏覽分布曲線，這個分布適用于絕數(shù)的商品以及絕大多數(shù)的時間。因此，我們完全可以利用這個分布來更精確的我們還可以估計每個單品的瀏覽量，利j用這個模型我們甚至不需要記錄瀏覽歷史，只需要知道當天:到當前的瀏XX覽總量就可以計算出前小時內(nèi)的瀏覽量，甚至預測接下來的瀏覽量情況!當然，模型也不是萬能的，模型本身的建立和更新也是有代價的，如果建模方法不恰當或者模型更新61718不及時，很有可能得出的結(jié)果會很差。小結(jié)本文首先介紹了百分點