5天2億活躍用戶，2017QQ「LBS+AR」天降紅包活動後台揭密

作者：Dovejbwang，騰訊後台開發工程師

商業轉載請聯繫騰訊WeTest獲得授權，非商業轉載請註明出處。

WeTest 導讀

前言

剛剛過去不久的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. 沒人能預知未來。開發海量數據/海量請求的系統時，多用上面兩個方法，從一開始就要儘力做到最好。

另外不能忘了，在海量用戶來襲的前夕，對自己的產品承載能力進行一個測試，及時做好調整和優化。任何企業都是一樣，不要萬事俱備，卻忽略了這個環節，讓用戶乘興而來，敗興而歸···nn騰訊提供了一個可以自主進行伺服器性能測試的環境，用戶只需要填寫域名和簡單的幾個參數就可以獲知自己的伺服器性能情況，目前在騰訊WeTest平台可以免費使用。n

騰訊WeTest伺服器性能測試運用了沉澱十多年的內部實踐經驗總結，通過基於真實業務場景和用戶行為進行壓力測試，幫助遊戲開發者發現伺服器端的性能瓶頸，進行針對性的性能調優，降低伺服器採購和維護成本，提高用戶留存和轉化率。

功能目前免費對外開放中，點擊鏈接：http://wetest.qq.com/gaps/ 可立即體驗！

點擊即可體驗！

如果對使用當中有任何疑問，歡迎聯繫騰訊WeTest企業qq：800024531