149
人物
5天2億活躍用戶，QQ新春天降紅包活動後台技術揭密
前言
剛剛過去不久的QQ“LBS+AR”天降紅包玩法在5天內達成了2.57億用戶參與、共計領取卡券和現金紅包20.5億次的成績，得到用戶的一致好評，贏得口碑、數據雙豐收。
作為一個全新的項目，後台麵臨著許多挑戰，比如：
1. 海量地圖活動數據管理
在全國960萬平方公裏土地上投放上億的活動任務點，如何管理海量的的地圖/任務數據？
2. 地圖查點方案
如何根據用戶地理位置快速獲取附近可用的任務點？
3. 數千個行政區紅包餘量的實時統計
紅包雨活動是在區級行政區開展的，全國有數千個區級行政區，每個行政區都有數十個不同的紅包任務及獎品，實時返回數千個地區的紅包剩餘量是如何做到的？
本文將從總體上介紹LBS+AR紅包後台係統架構，並逐步解答上述幾個問題。
LBS+AR後台架構鳥瞰
圖一 後台鳥瞰圖（及各係統間大致調用方向）
1. 投放係統：活動、商戶、獎品等信息的可視化配置頁麵
2. 靜態數據層：CDB提供的MySQL服務，包含多個配置表
3. 配置同步係統：負責構建海量活動數據的緩存及同步，包含2個模塊
a) 緩存構建模塊：定期輪詢式地從CDB中讀取活動數據，如果數據發生變化，重新構建AR標準緩存格式的共享內存數據
b) 配置同步服務端：負責接收客戶端請求，將共享內存數據下發到各個業務機器
4. 邏輯層：負責接受客戶端請求，包含2個係統
a) 主邏輯：負責用戶參加地圖紅包的核心邏輯，包含地圖查點、抽獎等流程
b) 采集係統：負責實時獲取各個活動及獎品的發放數據，用於主邏輯獲取活動狀態、客戶端顯示剩餘計數、後台統計活動數據
5. 動態數據層：負責用戶、活動動態數據的存儲，包含4類數據
a) 發獎計數器：每個任務/獎品發放量
b) 用戶曆史記錄：用戶中獎的信息
c) 冷卻與限額：用戶領取的每種獎品的限製信息
d) 疊放計數器：可重複獲取的獎品數量（本次活動是皇室戰爭卡券數）
6. 輔助模塊：完成單個特定任務的模塊
a) 頻率控製：負責控製獎品發放速度
b) 訂單：負責管理財付通現金訂單
c) 一致接口：負責一致性路由，將同一個用戶的請求路由到同一台機器的指定進程
7. 發獎相關係統：負責獎品發放的外部係統
LBS+AR後台係統探微
下麵主要為大家介紹海量配置管理、地圖打點查點和實時的餘量采集係統。
一、海量配置數據管理
LBS+AR紅包與以往的紅包最大的不同在於多了一重地理位置關聯，全國有上千萬的地理位置信息，結合活動的任務獎品數據產生了海量的配置數據，而這些數據都需要快速地實時讀取（詳細數據結構見後文）。這是後台遇到的第一個挑戰。
總體思路
配置數據有如下特點：
1. 數據量可能很大，數據間有緊密的關聯
2. “一次配好，到處使用”，讀量遠高於寫量
根據第一個特性，由於我們有Web投放係統的可視化配置能力，而公司內部的CDB能提供可靠的MySQL服務，有自動容災和備份的功能，故選擇CDB作為靜態數據存儲。
根據第二個特性，我們需要開發一種緩存，放棄寫性能，將讀性能優化到極致。
第一代緩存係統——寫性能換讀性能
緩存係統將數據讀取方式從“遠端磁盤讀取”改為“本地內存讀取”，讀性能提高好幾個數量級，它具有如下特點：
1. 緩存構建模塊定時輪詢數據庫，在共享內存中構建緩存，配置變動可在分鍾級時間內完成。
2. 每張表使用2塊共享內存，一塊用於實時讀，另一塊用於更新，數據更新無感知，對業務零影響。
3. 使用二分法查詢數據，O(logN)的複雜度，性能較優。
第二代緩存係統——O(logN)算法部分變O(1)
由於在地圖查點流程中要執行數十至上百次的“任務與POI關聯數據”查詢，而對億級數據進行二分查找每次要做將近30次的字符串比較，嚴重影響了係統性能。
為了解決這個問題，第二代係統針對POI數據離散化的特點，對量大的數據進行了前綴哈希，將一半的O(logN)操作轉換成O(1)，進一步用寫性能換讀性能，性能得到有效提升，字符串比較的最大次數減少了將近一半。
算法流程：
1. 根據經驗設置前綴長度
2. 遍曆數據構造映射表，映射表存儲了前綴及其對應的起始/末尾序號
3. 以前綴為Key，將映射表記在多階哈希中（指定大小，枚舉階數搜索可行的壓縮方案）
下麵是一個構造映射表的例子：
對於樣例數據：
-
如果取3字節前綴，隻有2個結果，產生的映射表比較容易構造哈希，但最大單條映射的記錄長度是9，二分的次數仍然較多。
-
如果取5字節前綴，最大單條映射的記錄長度是4，二分次數較少，但條目較多，哈希構造較難。
總結如下：
一些可能的問題：
-
為什麼不全部哈希呢？
上億條數據每次改動都做全部哈希，耗費的時間和空間恐怕是天文數字。雖然我們舍棄寫性能換取讀性能，但用幾個小時（幾天）寫耗時換幾納秒的讀耗時，邊際效用已經降到負數了。實踐中做一半即可達到不錯的讀寫平衡。
-
如果映射的記錄長度十分不均勻怎麼辦？
這是此項優化的命門所在。幸運的是我們要優化的數據是POI相關的，而實踐發現POI數據離散性極好，得出的映射記錄數量非常均勻
-
如果哈希一直構造失敗怎麼辦？
此項配置數據改動不多，如果對於某一版本數據構造失敗，一般會有足夠的時間根據數據特性調整前綴長度、增加哈希表大小、擴大階數搜索範圍來確保成功。如果時間比較緊急，也可以放棄此項優化，程序如果檢測到哈希失敗，會自動使用全部二分的方式讀取。即便沒有這項優化，我們還有許多柔性調控策略防止係統過載。
第三代緩存係統——中間層加速同步
上一代係統擴容後的結構如下圖：
每台機器構建數據時都要去數據庫讀一次全量數據並排序，同時要在本地生成，每次大約耗時5分鍾。而在這種架構下，所有機器的讀數據庫操作實際上就是串行的，當邏輯層擴容到100台機器時，完成全部任務將耗費好幾個小時，考慮到配置修改的風險，這種架構在實踐上是不可行的。
第三代架構圖如下（箭頭指數據流向）：
在數據層和邏輯層中間添加一個配置同步係統，先讓少部分配置中心機器優先完成構建，再去帶動數量較多的邏輯層機器，最終達到共同完成。有效解決了上一代平行擴容的問題，效果拔群。
實踐效果
1. 極致讀性能
2. 海量靜態緩存數據的快速構建：完成全部機器近20G不同類型靜態數據的構建和同步隻需要30分鍾
3. 數據同步無感知，實現無縫切換，對業務零影響
二、地圖打點與查點
基於LBS的活動離不開地理位置相關的業務交互。在本次活動中，用戶打開地圖會定期向後台上報坐標，後台需要根據坐標獲取周圍可用的活動任務點，此節介紹打點與查點相關內容。
專業的地圖服務會使用一種樹形數據結構來進行空間查詢，但LBS+AR紅包活動的場景比較簡單，故而選用了一種粒度較粗性能更好的打點查點方案，查詢附近地理信息隻需要進行四則運算，再一次用O(1)的方法解決O(logN)的問題。
地圖格子方法介紹
將整個二位平麵根據坐標分成一個個邊長相等的正方形格子，根據用戶的坐標用簡單的數學運算即可獲取相應的格子ID，時間複雜度O(1)。一個格子是一次查詢的最小粒度。
在本次活動中，我們使用約200米邊長的格子，每次查詢會返回以用戶為中心周圍共計25個格子的任務點。
格子與任務點示例如下：
打點流程介紹
活動的投放是以任務的維度投放，每個任務關聯一個POI集合，每個POI集合中包含幾個到上百萬不等的POI點，每個POI點都有一個經緯度信息（詳細情況見下文數據結構設計）。
打點的責任是將任務為索引的數據重構為以格子ID為索引的數據，通過遍曆緩存係統中的POI/POI集合/任務分片來實現。最終的格式如下：
查點流程介紹
1. 客戶端上報經緯度
2. 根據經緯度計算中心格子ID
3. 根據中心格子ID及半徑配置，獲取全部格子列表
4. 在打點係統中獲得此片區域全部Poi和Task信息
5. 檢查任務狀態後返回給客戶端
三、采集係統進化之路
采集係統的主要職責是：
1. 實時返回區級行政區紅包計數
2. 實時接受主邏輯的查詢，返回獎品發放狀態。
3. 返回活動預告以及參數配置等輔助信息。
這裏麵臨的主要的挑戰是區級行政區的紅包餘量計數，本文將著重介紹餘量計數方案的演化思路。
樸素方案
來一個請求就去讀一次！
進程級緩存方案
上一個方案顯然不可行，而進程級緩存是最初使用的方案。這時采集功能並未單獨成為一個獨立模塊，而是嵌在主邏輯裏的。
主邏輯定期地掃描配置中全部有效任務，讀計數器，將計數存儲在STLMAP中。
假如每次數據緩存5秒，實際活動中約有8w條數據需要處理，每天活動分8場，100台邏輯層機器，對數據層的壓力是400w次每秒，這個級別的讀量幾乎占滿了全部Grocery性能。雖然方案比較成熟，但還是決定優化。
機器級緩存方案
這個方案做了兩件事：
1. 將進程級的緩存上升到機器級，節省40倍進程訪問開銷
2. 將采集流程從主邏輯解耦，單獨部署，減輕100台主邏輯機器綁定的訪問開銷
本方案使用有序的拚接索引+範圍二分查找的方式替代STLMAP進行查詢，使用sf1框架實現，服務與構造進程一體。由於sf1不支持並發外部調用，構造進程使用簡單逐個查詢的方法處理。
（sf1是後台較為常用的一種服務框架，性能較好，但不支持天然異步開發）
夾縫求生的最終優化
上一方案功能上確實可行，但性能上仍然存在問題：sf1框架不好做並發外部調用，用串行的方式查詢數萬條數據，完成一輪更新的時間是分鍾級的，影響產品體驗。
為了優化此問題，我們做了兩級並發：
1. 利用Grocery提供的MultiKeyBatch方法，讓Grocery接口機並發（詳情請參見Grocery API，調用此接口格外注意業務數據大小及打包數量，輕易不要使用！）。示意圖如下：
2. 將構造進程從sf1改為spp，利用mt_task方法並發請求。我們使用了宏定義IMTTask的簡便用法。
需要注意的是，理論上可以隻用第二種並發方式即可滿足“采集模塊”的需求，但從整個係統的角度看，防止數據層過載更加重要，第一種並發方式減少了10倍Grocery Intf請求量和一部分Cache請求量，雖然開發量較大，卻是不可或缺的。
經過兩級並發，分鍾級的構建間隔被縮短到了1秒。但是不能發布！因為遇到了夾縫問題。
采集模塊夾在客戶端和Grocery之間，加速采集會影響Grocery，而減少機器又會影響客戶端更新計數的效果，三個條件互相製約，需要想辦法突破這個夾縫難題。
解決方法是：將查餘量過程的O(logN)流程變成O(1)，性能提升10倍即可。
采集係統的主要業務邏輯是返回地區紅包計數，之前的方案1秒內的數萬次請求每次都會執行包括二分查找在內的全套邏輯，而事實上隻有第一次是有必要的（地區的餘量等信息1秒內的變化微乎其微）。那麼答案就唿之欲出了，隻需要給每個地區的結果做1秒鍾的緩存即可。
最終把可以做緩存的流程全都加上了合理的緩存結構，單機性能成功提升10倍。
後記
本次項目總結的後台開發基本法：
1. 架構問題可以通過讀寫轉換、時空轉換的方式變成算法問題
2. O(logN)問題總有辦法變成O(1)問題
3. 沒人能預知未來。開發海量數據/海量請求的係統時，多用上麵兩個方法，從一開始就要盡力做到最好。
作者介紹 王家彬
-
騰訊後台開發工程師，參與“LBS+AR”天降紅包項目，其所在“2016春節紅包聯合項目團隊”獲得2016公司級業務突破獎。
原文發布時間為：2017-02-20
本文來自雲棲社區合作夥伴DBAplus
最後更新：2017-05-15 10:02:28