摘要：所有的倒排索引都是基于正排數(shù)據(jù)構(gòu)建的。數(shù)據(jù)規(guī)模的難題節(jié)中描述的拆表的方式，本質(zhì)上是將多個數(shù)值型拆成了多個插入記錄，然后再建立倒排索引。

1.1 業(yè)務(wù)背景

精準(zhǔn)廣告場景中，人群定向的常用方法是：根據(jù)各種不同的規(guī)則，將每一個用戶（User）打上豐富的標(biāo)簽。與此同時，廣告主（Member）在根據(jù)規(guī)則圈選投放人群時，系統(tǒng)也會將廣告（Ad）打上各種的標(biāo)簽。當(dāng)一個Ad和一個User被打上同一個標(biāo)簽（Tag）時，就表示該Ad圈定了這個User，即該Ad會參與對該User的展現(xiàn)競價。
本次優(yōu)化的難點出現(xiàn)在一個特定業(yè)務(wù)場景下，我們需要明確的知道一個Ad圈選了哪些User，而我們唯一知道的就是這個Ad被打上的一組Tag（Tag List）。此時，我們需要一個存儲 + 索引的技術(shù)產(chǎn)品，讓我們能夠快速地通過Tag查詢到每個Tag下掛載的所有User（User List）的id。此外，由于廣告業(yè)務(wù)對實時性要求很高，系統(tǒng)還要保證User的實時行為能夠快速在投放系統(tǒng)中生效，當(dāng)一個User的某個行為導(dǎo)致該User身上被追加 或 刪除某些Tag時，所有受到影響Tag下掛載的User List都會發(fā)生變化。

業(yè)務(wù)中的數(shù)據(jù)規(guī)模：

User總數(shù)大約4億

Tag總數(shù)約100w個

平均每個Tag下會掛載100w個User

平均每秒鐘會對2000個tag進(jìn)行查詢

平均每秒鐘會有5w個User會觸發(fā)Tag更新，每次更新平均會更新10個Tag

可見，不管是存儲規(guī)模、每秒檢索結(jié)果的數(shù)據(jù)量 還是 每秒需要進(jìn)行更新的數(shù)據(jù)量都非常龐大。這里需要特別說明的是，User的id信息是一個uint64數(shù)字，后面的優(yōu)化會利用這個特性。

1.2 技術(shù)選型引入的問題

我們需要一個強(qiáng)大的檢索引擎來支持?jǐn)?shù)據(jù)的檢索 + 更新，這個檢索引擎需要支持“tag->多個數(shù)值型userid”的數(shù)據(jù)存儲結(jié)構(gòu)：

查詢時，通過多個tag查詢得到tag下掛載的所有userid

更新時，通過變更的tag 以及 需要add 或 delete 的userid就可以完成變更

但是，在梳理技術(shù)選型時，我們發(fā)現(xiàn)沒有任何一個現(xiàn)有的技術(shù)選型可以支持這種數(shù)據(jù)結(jié)構(gòu)。現(xiàn)有的檢索引擎大都是基于“文檔（doc）搜索”而開發(fā)的，往往將數(shù)據(jù)結(jié)構(gòu)抽象為“doc id->doc”范式的正排查找 和 “關(guān)鍵詞（keyword）-> doc id list”范式的倒排鏈查找。所有的倒排索引都是基于正排數(shù)據(jù)構(gòu)建的。
舉個例子，必須先有如下文檔

才可能有如下倒排索引

可以看出，我們期望的是類似于倒排表的這種數(shù)據(jù)結(jié)構(gòu)，但是為了產(chǎn)出這樣一種數(shù)據(jù)結(jié)構(gòu)，我們不得不建立一張我們根本不需要的正排數(shù)據(jù)表。

1.3 索引結(jié)構(gòu)設(shè)計中的問題

結(jié)合業(yè)務(wù)背景，為了獲得一個“tag->多個數(shù)值型userid”的鏈?zhǔn)浇Y(jié)構(gòu)，我們不得不建立一張以userid為docid，以該userid下所有tag為doc內(nèi)容的正排結(jié)構(gòu)。

然后通過建立倒排的方式得到我們需要的表結(jié)構(gòu)

這樣一來，我們就可以通過tag去檢索User List了。
看上去，我們通過一些冗余存儲解決了數(shù)據(jù)結(jié)構(gòu)的問題，但是實際上我們只滿足了查詢時的要求，還沒有考慮更新。這樣的索引結(jié)構(gòu)有一個嚴(yán)重的問題：倒排表是正排表的輔助表，因此必須通過更新正排表來觸發(fā)倒排表的更新；而正排表中的tag信息作為“doc內(nèi)容”，又必須是整體更新的。
舉個例子，假如此時user id為1的User新增了一個“電子”的標(biāo)簽，我們必須通過將正排表中user id為1的一行整體更新為

以此來觸發(fā)倒排表中“電子”一行變更為

這不滿足我們在本小節(jié)開始時提到的“更新時，通過變更的tag 以及 需要add 或 delete 的userid就可以完成變更”。在這里，若我們想更新tag下的User List，我們必須提供該tag下的所有user id。由于tag下有百萬量級的user id，這種更新方式帶來的網(wǎng)絡(luò)帶寬開銷、cpu開銷是巨大的，以至于無法接受。

2.1 索引結(jié)構(gòu)初步設(shè)計

本節(jié)將介紹一種巧妙的索引結(jié)構(gòu)設(shè)計方式，可以在技術(shù)選型受限的情況下，通過犧牲部分存儲來實現(xiàn)“tag->多個數(shù)值型userid”的鏈?zhǔn)浇Y(jié)構(gòu)。雖然這種設(shè)計方式?jīng)]有真正的解決如此大規(guī)模數(shù)據(jù)下的檢索問題，但對一些中小型場景仍有借鑒意義。
當(dāng)我們遇到1.3節(jié)中提到的問題時，一種可行的思路是“拆分正排表doc粒度”。嘗試將1.3節(jié)中的正排表拆分成如下結(jié)構(gòu)

然后對tag建立倒排索引（忽略主鍵）

可以發(fā)現(xiàn)，建立得到倒排索引與1.3節(jié)中的一致，滿足查詢需求。
再來看更新，當(dāng)我們需要給user id為1的User新增了一個“電子”標(biāo)簽，只需要在正排表中插入一行

倒排表中“電子”一行就會變?yōu)?/p>

這樣一來，就同時解決了檢索和更新的問題。

2.2 數(shù)據(jù)規(guī)模的難題

2.1節(jié)中描述的拆表的方式，本質(zhì)上是將“tag->多個數(shù)值型userid”拆成了多個“user_tag插入記錄”，然后再建立倒排索引。前面1.1節(jié)中提到：有100w個不同的tag，平均每個tag下有100w個userid，計算下來，user_tag插入記錄的記錄數(shù)量在1萬億左右。雖然每一個記錄占用的存儲空間非常小（64B左右），但是由于檢索內(nèi)核出于自身設(shè)計的一些考慮，往往會設(shè)置單機(jī)存儲doc數(shù)量的上限閾值。如此龐大的記錄數(shù)量超出了上限閾值，即使是采用集群式存儲，由于單閾值的存在，也會導(dǎo)致大量的機(jī)器資源開銷與浪費。
舉個例子，假設(shè)單機(jī)最多存20億個doc，采用水平分列的方式，需要500列才能存下1萬億條記錄，若考慮到主備容災(zāi)，則需要至少1000臺機(jī)器。而實際上，每臺機(jī)器的磁盤都沒有占滿，僅使用了128GB（20億 * 64B = 128GB）。
為了解決這個問題，先要梳理下究竟是什么原因?qū)е铝薲oc數(shù)量如此之大。拋開我們無法決定的業(yè)務(wù)背景，導(dǎo)致doc數(shù)量膨脹的主因是大量的tag下有大量的userid，拆分之后出現(xiàn)了驚人數(shù)量的tag_userid主鍵。但是，不同的下掛載的userid之間是有大量重復(fù)的，如果我們能消除這種重復(fù)現(xiàn)象，就能在很大程度上減輕膨脹。

一個很容易地想到的方法是分組。由于業(yè)務(wù)上要求我們用tag進(jìn)行檢索，因此我們只能將userid分組。分組之后，每個tag下掛載的是userGroupId，一個UserGroup下可以再次掛載很多userid。這樣，doc主鍵就變成了tag_userGroupId，預(yù)期數(shù)量可以顯著減少（注意“預(yù)期”這個詞，將在2.4節(jié)中說明）。

但還有一個問題需要解決，那就是雖然Tag0和Tag1下面都掛了userGroup1，但是Tag0下掛載的是user1、user9，Tag1下掛載的是user5、user7。所以，不同tag下掛載同一個userGroup時，group中包含的user是不一樣的。由于我們的主鍵是tag_userGroupId，這個問題可以很好的得到解決。
還是接2.1節(jié)中的例子，假設(shè)user1和user2屬于group1，user3屬于group2，那么如下建立正排表。

倒排表對應(yīng)的是如下結(jié)構(gòu)：

可以看出，檢索出的userid結(jié)果和2.1節(jié)中是一樣的。

截止到目前為止，檢索上的功能已經(jīng)打通。這種方法的本質(zhì)上將一張復(fù)合表拆分成了多張簡單表，中間通過一個虛擬外鍵進(jìn)行關(guān)聯(lián)。從工程上來看，這種方式的本質(zhì)是用時間去換取空間：犧牲每次檢索時進(jìn)行關(guān)聯(lián)的計算開銷，去換取存儲上的壓力減輕。
接下來在看更新鏈路中的問題。在這個場景中，索引設(shè)計要考慮的最關(guān)鍵的問題就是更新時的doc粒度。如1.3節(jié)中提到的，由于更新是以doc為粒度更新的，若doc中的內(nèi)容過大，則無法進(jìn)行有效更新。拆表后，doc中的內(nèi)容是“當(dāng)前tag_userGroupId下包含的userid list”，其doc規(guī)模介于1.3節(jié)和2.1節(jié)中提出的兩種方案之間，且具有一定的隨機(jī)性。若tag_userGroupId下包含的userid較多，則更新時壓力較大，效率較低。

2.3 數(shù)值型數(shù)據(jù)的存儲優(yōu)化

為了解決tag_userGroupId下包含的userid較多導(dǎo)致更新效率較低的問題，我們需要找到一種優(yōu)化的存儲方式，對多值userid進(jìn)行存儲壓縮。這里介紹的一種方式是bitmap壓縮。
當(dāng)數(shù)據(jù)是數(shù)值型，且數(shù)值分布比較集中時，可以建立bitmap存儲，每個bit表示一個userid是否存在（0或1），userid則作為尋址bit位置的索引。這種方法仍然是時間換空間，用bitmap反解的計算開銷去換取存儲空間。

這里影響壓縮效率的關(guān)鍵點是映射計算后，bit是否集中分布，若分布過于離散，則會出現(xiàn)很多bit空洞。當(dāng)出現(xiàn)很多bit空洞時，一般有兩種辦法：

優(yōu)化映射計算的方法
在進(jìn)行映射的時候，要保證映射后數(shù)據(jù)盡可能的集中

對空洞進(jìn)行再次壓縮
由于一般不一定能找到一種理想的映射計算方法，比較常見的是對bitmap空間進(jìn)行再次壓縮，壓縮方法有很多種，這部分讀者可以自行設(shè)計，這里簡述兩種壓縮方法。
（1）自適應(yīng)存儲
當(dāng)空洞較多時，bitmap存儲的效果有可能劣于暴力存儲，可以根據(jù)業(yè)務(wù)特點計算出兩種方案的臨界值，自適應(yīng)判斷使用哪種存儲
（2）bitmap再壓縮
當(dāng)出現(xiàn)較多字節(jié)空洞的時候，可以采用<字節(jié)id，字節(jié)值>的方式存儲非空洞字節(jié)

2.4 數(shù)據(jù)分組規(guī)則設(shè)計

2.2節(jié)中提到，將userid分組變?yōu)閁serGroup的核心目的在于減少doc數(shù)量，這里需要設(shè)計分組的規(guī)則。一個比較極端的案例就是4億user分組后，變成了4億個UserGroup，每個UserGroup下一個User。為了達(dá)成盡可能減少doc數(shù)量的目的，在設(shè)計規(guī)則時，應(yīng)關(guān)注userid的bit分布特性，將公共部分提取出來當(dāng)作userGroupId，并將這些user劃入該組下。
這本質(zhì)上是一次“特征提取”的過程，將數(shù)值樣本中的共性盡可能豐富的提取出來。

至此，超大規(guī)模檢索中的索引設(shè)計告一段落，現(xiàn)在總結(jié)下問題分析過程中的一些關(guān)鍵點。
1、在進(jìn)行索引設(shè)計時，不能只考慮檢索上的功能與性能是否滿足要求，還要考慮更新時的功能與性能，給出綜合的解決方案
2、當(dāng)遇到數(shù)據(jù)表過大的場景時，第一時間要反思是否自己對表的設(shè)計不合理，能否對表進(jìn)行拆分
3、當(dāng)需要基于規(guī)則對數(shù)值型數(shù)據(jù)進(jìn)行分組時，并不是只有取整和取模兩種簡單的分組方式，要結(jié)合數(shù)據(jù)特征，給出效果較好的分組方式
4、當(dāng)暴力存儲占用存儲空間較大時，可以考慮能否用bitmap的方式壓縮存儲；若bitmap空洞較多，可以考慮進(jìn)行進(jìn)一步的壓縮

如果感興趣，歡迎關(guān)注微信技術(shù)公眾號