背景

在線廣告是互聯網行業常見的商業變現方式。從工程角度看，廣告索引的結構和實現方式直接決定了整個系統的服務性能。本文以美團的搜索廣告系統為藍本，與讀者一起探討廣告系統的工程奧秘。

領域問題

廣告索引需具備以下基本特性：

層次化的索引結構。

實時化的索引更新。

層次投放模型

一般地，廣告系統可抽象為如下投放模型，并實現檢索、過濾等處理邏輯。

該層次結構的上下層之間是一對多的關系。一個廣告主通常創建若干個推廣計劃，每個計劃對應一個較長周期的KPI，比如一個月的預算和投放地域。一個推廣計劃中的多個推廣單元分別用于更精細的投放控制，比如一次點擊的最高出價、每日預算、定向條件等。廣告創意是廣告曝光使用的素材，根據業務特點，它可以從屬于廣告主或推廣計劃層級。

實時更新機制

層次結構可以更準確、更及時地反應廣告主的投放控制需求。投放模型的每一層都會定義若干字段，用于實現各類投放控制。廣告系統的大部分字段需要支持實時更新，比如審核狀態、預算上下線狀態等。例如，當一個推廣單元由可投放狀態變為暫停狀態時，若該變更沒有在索引中及時生效，就會造成大量的無效投放。

業界調研

目前，生產化的開源索引系統大部分為通用搜索引擎設計，基本無法同時滿足上述條件。

• Apache Lucene
  • 全文檢索、支持動態腳本；實現為一個Library。
  • 支持實時索引，但不支持層次結構。
• Sphinx
  • 全文檢索；實現為一個完整的Binary，二次開發難度大。
  • 支持實時索引，但不支持層次結構。

因此，廣告業界要么基于開源方案進行定制，要么從頭開發自己的閉源系統。在經過再三考慮成本收益后，我們決定自行設計廣告系統的索引系統。

索引設計

工程實踐重點關注穩定性、擴展性、高性能等指標。

設計分解

設計階段可分解為以下子需求。

實時索引

廣告場景的更新流，涉及索引字段和各類屬性的實時更新。特別是與上下線狀態相關的屬性字段，需要在若干毫秒內完成更新，對實時性有較高要求。

用于召回條件的索引字段，其更新可以滯后一些，如在幾秒鐘之內完成更新。采用分而治之的策略，可極大降低系統復雜度。

• 屬性字段的更新：直接修改正排表的字段值，可以保證毫秒級完成。
• 索引字段的更新：涉及更新流實時計算、倒排索引等的處理過程，只需保證秒級完成。

此外，通過定期切換全量索引并追加增量索引，由索引快照確保數據的正確性。

層次結構

投放模型的主要實體是廣告主（Advertiser）、推廣計劃（Campaign）、廣告組（Adgroup）、創意（Creative）等。其中：

• 廣告主和推廣計劃：定義用于控制廣告投放的各類狀態字段。
• 廣告組：描述廣告相關屬性，例如競價關鍵詞、最高出價等。
• 創意：與廣告的呈現、點擊等相關的字段，如標題、創意地址、點擊地址等。

一般地，廣告檢索、排序等均基于廣告組粒度，廣告的倒排索引也是建立在廣告組層面。借鑒關系數據庫的概念，可以把廣告組作為正排主表（即一個Adgroup是一個doc），并對其建立倒排索引；把廣告主、推廣計劃等作為輔表。主表與輔表之間通過外鍵關聯。

通過查詢條件，從倒排索引中查找相關docID列表。

對每個docID，可從主表獲取相關字段信息。

使用外鍵字段，分別獲取對應輔表的字段信息。

檢索流程中實現對各類字段值的同步過濾。

可靠高效

廣告索引結構相對穩定且與具體業務場景耦合較弱，為避免Java虛擬機由于動態內存管理和垃圾回收機制帶來的性能抖動，最終采用C++11作為開發語言。雖然Java可使用堆外內存，但是堆外堆內的數據拷貝對高并發訪問仍是較大開銷。項目嚴格遵循《Google C++ Style》，大幅降低了編程門檻。

在“讀多寫少”的業務場景，需要優先保證“讀”的性能。檢索是內存查找過程，屬于計算密集型服務，為保證CPU的高并發，一般設計為無鎖結構。可采用“一寫多讀”和延遲刪除等技術，確保系統高效穩定運轉。此外，巧妙利用數組結構，也進一步優化了讀取性能。

靈活擴展

正排表、主輔表間的關系等是相對穩定的，而表內的字段類型需要支持擴展，比如用戶自定義數據類型。甚至，倒排表類型也需要支持擴展，例如地理位置索引、關鍵詞索引、攜帶負載信息的倒排索引等。通過繼承接口，實現更多的定制化功能。

邏輯結構

從功能角度，索引由Table和Index兩部分組成。如上圖所示，Index實現由Term到主表docID的轉換；Table實現正排數據的存儲，并通過docID實現主表與輔表的關聯。

分層架構

索引庫分為三層：

接口層：以API方式對外提供索引的構建、更新、檢索、過濾等功能。

能力層：實現基于倒排表和正排表的索引功能，是系統的核心。

存儲層：索引數據的內存布局和到文件的持久化存儲。

索引實現

本節將自底向上，從存儲層開始，逐一描述各層的設計細節和挑戰點。

存儲層

存儲層負責內存分配以及數據的持久化，可使用mmap實現到虛擬內存空間的映射，由操作系統實現內存與文件的同步。此外，mmap也便于外部工具訪問或校驗數據的正確性。

將存儲層抽象為分配器（Allocator）。針對不同的內存使用場景，如對內存連續性的要求、內存是否需要回收等，可定制實現不同的分配器。

以下均為基于mmap的各類分配器，這里的“內存”是指調用進程的虛擬地址空間。實際的代碼邏輯還涉及復雜的Metadata管理，下文并未提及。

簡單的分配策略

• LinearAllocator

  • 分配連續地址空間的內存，即一整塊大內存；當空間需要擴展時，會采用新的mmap文件映射，并延遲卸載舊的文件映射。
  • 新映射會導致頁表重新裝載，大塊內存映射會導致由物理內存裝載帶來的性能抖動。
  • 一般用于空間需求相對固定的場景，如HashMap的bucket數組。

• SegmentAllocator

  • 為解決LinearAllocator在擴展時的性能抖動問題，可將內存區分段存儲，即每次擴展只涉及一段，保證性能穩定。
  • 分段導致內存空間不連續，但一般應用場景，如倒排索引的存儲，很適合此法。
  • 默認的段大小為64MB。

集約的分配策略

頻繁的增加、刪除、修改等數據操作將導致大量的外部碎片。采用壓縮操作，可以使占用的內存更緊湊，但帶來的對象移動成本卻很難在性能和復雜度之間找到平衡點。在工程實踐中，借鑒Linux物理內存的分配策略，自主實現了更適于業務場景的多個分配器。

• PageAllocator
  • 頁的大小為4KB，使用伙伴系統（Buddy System）的思想實現頁的分配和回收。
  • 頁的分配基于SegmentAllocator，即先分段再分頁。

在此簡要闡述伙伴分配器的處理過程，為有效管理空閑塊，每一級order持有一個空閑塊的FreeList。設定最大級別order=4，即從order=0開始，由低到高，每級order塊內頁數分別為1、2、4、8、16等。分配時先找滿足條件的最小塊；若找不到則在上一級查找更大的塊，并將該塊分為兩個“伙伴”，其中一個分配使用，另一個置于低一級的FreeList。

下圖呈現了分配一個頁大小的內存塊前后的狀態變化，分配前，分配器由order=0開始查找FreeList，直到order=4才找到空閑塊。

將該空閑塊分為頁數為8的2個伙伴，使用前一半，并將后一半掛載到order=3的FreeList；逐級重復此過程，直到返回所需的內存塊，并將頁數為1的空閑塊掛在到order=0的FreeList。

當塊釋放時，會及時查看其伙伴是否空閑，并盡可能將兩個空閑伙伴合并為更大的空閑塊。這是分配過程的逆過程，不再贅述。

雖然PageAllocator有效地避免了外部碎片，卻無法解決內部碎片的問題。為解決這類小對象的分配問題，實現了對象緩存分配器（SlabAllocator）。

• SlabAllocator
  • 基于PageAllocator分配對象緩存，slab大小以頁為單位。
  • 空閑對象按內存大小定義為多個SlabManager，每個SlabManager持有一個PartialFreeList，用于放置含有空閑對象的slab。

對象的內存分配過程，即從對應的PartialFreeList獲取含有空閑對象的slab，并從該slab分配對象。反之，釋放過程為分配的逆過程。

綜上，實時索引存儲結合了PageAllocator和SlabAllocator，有效地解決了內存管理的外部碎片和內部碎片問題，可確保系統高效穩定地長期運行。

能力層

能力層實現了正排表、倒排表等基礎的存儲能力，并支持索引能力的靈活擴展。

正向索引

也稱為正排索引（Forward Index），即通過主鍵（Key）檢索到文檔（Doc）內容，以下簡稱正排表或Table。不同于搜索引擎的正排表數據結構，Table也可以單獨用于NoSQL場景，類似于Kyoto Cabinet的哈希表。

Table不僅提供按主鍵的增加、刪除、修改、查詢等操作，也配合倒排表實現檢索、過濾、讀取等功能。作為核心數據結構，Table必須支持頻繁的字段讀取和各類型的正排過濾，需要高效和緊湊的實現。

為支持按docID的隨機訪問，把Table設計為一個大數組結構（data區）。每個doc是數組的一個元素且長度固定。變長字段存儲在擴展區（ext區），僅在doc中存儲其在擴展區的偏移量和長度。與大部分搜索引擎的列存儲不同，將data區按行存儲，這樣可針對業務場景，盡可能利用CPU與內存之間的緩存來提高訪問效率。

此外，針對NoSQL場景，可通過HashMap實現主鍵到docID的映射（idx文件），這樣就可支持主鍵到文檔的隨機訪問。由于倒排索引的docID列表可以直接訪問正排表，因此倒排檢索并不會使用該idx。

反向索引

也稱作倒排索引（Inverted Index），即通過關鍵詞（Keyword）檢索到文檔內容。為支持復雜的業務場景，如遍歷索引表時的算法粗排邏輯，在此抽象了索引器接口Indexer。

具體的Indexer僅需實現各接口方法，并將該類型注冊到IndexerFactory，可通過工廠的NewIndexer方法獲取Indexer實例，類圖如下：

當前實現了三種常用的索引器：

• NoPayloadIndexer：最簡單的倒排索引，倒排表為單純的docID列表。
• DefaultPayloadIndexer：除docID外，倒排表還存儲keyword在每個doc的負載信息。針對業務場景，可存儲POI在每個Node粒度的靜態質量分或最高出價。這樣在訪問正排表之前，就可完成一定的倒排優選過濾。
• GEOHashIndexer：即基于地理位置的Hash索引。

上述索引器的設計思路類似，僅闡述其共性的兩個特征：

• 詞典文件term：存儲關鍵詞、簽名哈希、posting文件的偏移量和長度等。與Lucene采用的前綴壓縮的樹結構不同，在此實現為哈希表，雖然空間有所浪費，但可保證穩定的訪問性能。
• 倒排表文件posting：存儲docID列表、Payload等信息。檢索操作是順序掃描倒排列表，并在掃描過程中做一些基于Payload的過濾或倒排鏈間的布爾運算，如何充分利用高速緩存實現高性能的索引讀取是設計和實現需要考慮的重要因素。在此基于segmentAllocator實現分段的內存分配，達到了效率和復雜度之間的微妙平衡。

出于業務考慮，沒有采用Lucene的Skip list結構，因為廣告場景的doc數量沒有搜索引擎多，且通常為單個倒排列表的操作。此外，若后續doc數量增長過快且索引變更頻繁，可考慮對倒排列表的元素構建B+樹結構，實現倒排元素的快速定位和修改。

接口層

接口層通過API與外界交互，并屏蔽內部的處理細節，其核心功能是提供檢索和更新服務。

配置文件

配置文件用于描述整套索引的Schema，包括Metadata、Table、Index的定義，格式和內容如下：

可見，Index是構建在Table中的，但不是必選項；Table中各個字段的定義是Schema的核心。當Schema變化時，如增加字段、增加索引等，需要重新構建索引。篇幅有限，此處不展開定義的細節。

檢索接口

檢索由查找和過濾組成，前者產出查找到的docID集合，后者逐個對doc做各類基礎過濾和業務過濾。

• Search：返回正排過濾后的ResultSet，內部組合了對DoSearch和DoFilter的調用。
• DoSearch：查詢doc，返回原始的ResultSet，但并未對結果進行正排過濾。
• DoFilter：對DoSearch返回的ResultSet做正排過濾。

一般僅需調用Search就可實現全部功能；DoSearch和DoFilter可用于實現更復雜的業務邏輯。

以下為檢索的語法描述：

/{table}/{indexer|keyfield}?query=xxxxxx&filter=xxxxx

第一部分為路徑，用于指定表和索引。第二部分為參數，多個參數由&分隔，與URI參數格式一致，支持query、filter、Payload_filter、index_filter等。

由query參數定義對倒排索引的檢索規則。目前僅支持單類型索引的檢索，可通過index_filter實現組合索引的檢索。可支持AND、OR、NOT等布爾運算，如下所示：

query=(A&B|C|D)!E

查詢語法樹基于Bison生成代碼。針對業務場景常用的多個term求docID并集操作，通過修改Bison文法規則，消除了用于存儲相鄰兩個term的doc合并結果的臨時存儲，直接將前一個term的doc并入當前結果集。該優化極大地減少了臨時對象開銷。

由filter參數定義各類正排表字段值過濾，多個鍵值對由“;”分割，支持單值字段的關系運算和多值字段的集合運算。

由Payload_filter參數定義Payload索引的過濾，目前僅支持單值字段的關系運算，多個鍵值對由“;”分割。

詳細的過濾語法如下：

此外，由index_filter參數定義的索引過濾將直接操作倒排鏈。由于構造檢索數據結構比正排過濾更復雜，此參數僅適用于召回的docList特別長但通過索引過濾的docList很短的場景。

結果集

結果集ResultSet的實現，參考了java.sql.ResultSet接口。通過cursor遍歷結果集，采用inline函數頻繁調用的開銷。

實現為C++模板類，主要接口定義如下：

• Next：移動cursor到下一個doc，成功返回true，否則返回false。若已經是集合的最后一條記錄，則返回false。
• GetValue：讀取單值字段的值，字段類型由泛型參數T指定。如果獲取失敗返回默認值def_value。
• GetMultiValue：讀取多值字段的值，返回指向值數組的指針，數組大小由size參數返回。讀取失敗返回null，size等于0。

更新接口

更新包括對doc的增加、修改、刪除等操作。參數類型Document，表示一條doc記錄，內容為待更新的doc的字段內容，key為字段名，value為對應的字段值。操作成功返回0，失敗返回非0，可通過GetErrorString接口獲取錯誤信息。

• 增加接口Add：將新的doc添加到Table和Index中。
• 修改接口Update：修改已存在的doc內容，涉及Table和Index的變更。
• 刪除接口Delete：刪除已存在的doc，涉及從Table和Index刪除數據。

更新服務對接實時更新流，實現真正的廣告實時索引。

更新系統

除以上描述的索引實現機制，生產系統還需要打通在線投放引擎與商家端、預算控制、反作弊等的更新流。

挑戰與目標

數據更新系統的主要工作是將原始多個維度的信息進行聚合、平鋪、計算后，最終輸出線上檢索引擎需要的維度和內容。

業務場景導致上游觸發可能極不規律。為避免更新流出現的抖動，必須對實時更新的吞吐量做優化，留出充足的性能余量來應對觸發的尖峰。此外，更新系統涉及多對多的維度轉換，保持計算、更新觸發等邏輯的可維護性是系統面臨的主要挑戰。

吞吐設計

雖然更新系統需要大量的計算資源，但由于需要對幾十種外部數據源進行查詢，因此仍屬于IO密集型應用。優化外部數據源訪問機制，是吞吐量優化的主要目標。

在此，采取經典的批量化方法，即集群內部，對于可以批量查詢的一類數據源，全部收攏到一類特定的worker上來處理。在短時間內，worker聚合數據源并逐次返回給各個需要數據的數據流。處理一種數據源的worker可以有多個，根據同類型的查詢匯集到同一個worker批量查詢后返回。在這個劃分后，就可以做一系列的邏輯優化來提升吞吐量。

分層抽象

除生成商家端的投放模型數據，更新系統還需處理針對各種業務場景的過濾，以及廣告呈現的各類專屬信息。業務變更可能涉及多個數據源的邏輯調整，只有簡潔清晰的分成抽象，才能應對業務迭代的復雜度。

工程實踐中，將外部數據源抽象為統一的Schema，既做到了數據源對業務邏輯透明，也可借助編譯器和類型系統來實現完整的校驗，將更多問題提前到編譯期解決。

將數據定義為表（Table）、記錄（Record）、字段（Field）、值（Value）等抽象類型，并將其定義為Scala Path Dependent Type，方便編譯器對程序內部的邏輯進行校驗。

可復用設計

多對多維度的計算場景中，每個字段的處理函數（DFP）應該盡可能地簡單、可復用。例如，每個輸出字段（DF）的DFP只描述需要的源數據字段（SF）和該字段計算邏輯，并不描述所需的SF(1)到SF(n)之間的查詢或路由關系。

此外，DFP也不與最終輸出的層級綁定。層級綁定在定義輸出消息包含的字段時完成，即定義消息的時候需要定義這個消息的主鍵在哪一個層級上，同時綁定一系列的DFP到消息上。

這樣，DFP只需單純地描述字段內容的生成邏輯。如果業務場景需要將同一個DF平鋪到不同層級，只要在該層級的輸出消息上引用同一個DFP即可。

觸發機制

更新系統需要接收數據源的狀態變動，判斷是否觸發更新，并需要更新哪些索引字段、最終生成更新消息。

為實現數據源變動的自動觸發機制，需要描述以下信息：

• 數據間的關聯關系：實現描述關聯關系的語法，即在描述外部數據源的同時就描述關聯關系，后續字段查詢時的路由將由框架處理。
• DFP依賴的SF信息：僅對單子段處理的簡單DFP，可通過配置化方式，將依賴的SF固化在編譯期；對多種數據源的復雜DFP，可通過源碼分析來獲取該DFP依賴的SF，無需用戶維護依賴關系。

生產實踐

早期的搜索廣告是基于自然搜索的系統架構建的，隨著業務的發展，需要根據廣告特點進行系統改造。新的廣告索引實現了純粹的實時更新和層次化結構，已經在美團搜索廣告上線。該架構也適用于各類非搜索的業務場景。

系統架構

作為整個系統的核心，基于實時索引構建的廣告檢索過濾服務（RS），承擔了廣告檢索和各類業務過濾功能。日常的業務迭代，均可通過升級索引配置完成。

此外，為提升系統的吞吐量，多個模塊已實現服務端異步化。

性能優化

以下為監控系統的性能曲線，索引中的doc數量為百萬級別，時延的單位是毫秒。

后續規劃

為便于實時索引與其他生產系統的結合，除進一步的性能優化和功能擴展外，我們還計劃完成多項功能支持。

JNI

通過JNI，將Table作為單獨的NoSQL，為Java提供本地緩存。如廣告系統的實時預估模塊，可使用Table存儲模型使用的廣告特征。

SQL

提供SQL語法，提供簡單的SQL支持，進一步降低使用門檻。提供JDBC，進一步簡化Java的調用。

參考資料

• Apache Lucene http://lucene.apache.org/
• Sphinx http://sphinxsearch.com/
• “Understanding the Linux Virtual Memory Manager” https://www.kernel.org/doc/gorman/html/understand/
• Kyoto Cabinet http://fallabs.com/kyotocabinet/
• GNU Bison https://www.gnu.org/software/bison/

作者簡介

• 倉魁：廣告平臺搜索廣告引擎組架構師，主導實時廣告索引系統的設計與實現。擅長C++、Java等多種編程語言，對異步化系統、后臺服務調優等有深入研究。
• 曉暉：廣告平臺搜索廣告引擎組核心開發，負責實時更新流的設計與實現。在廣告平臺率先嘗試Scala語言，并將其用于大規模工程實踐。
• 劉錚：廣告平臺搜索廣告引擎組負責人，具有多年互聯網后臺開發經驗，曾領導多次系統重構。
• 蔡平：廣告平臺搜索廣告引擎組點評側負責人，全面負責點評側系統的架構和優化。

招聘信息

有志于從事Linux后臺開發，對計算廣告、高性能計算、分布式系統等有興趣的朋友，請通過郵箱與我們聯系。聯系郵箱：liuzheng04@meituan.com 。

總結

以上是生活随笔為你收集整理的美团广告实时索引的设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。