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

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

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

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

User總數(shù)大約4億

Tag總數(shù)約100w個(gè)

平均每個(gè)Tag下會(huì)掛載100w個(gè)User

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

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

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

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

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

查詢時(shí)，通過(guò)多個(gè)tag查詢得到tag下掛載的所有userid

更新時(shí)，通過(guò)變更的tag 以及 需要add 或 delete 的userid就可以完成變更

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

才可能有如下倒排索引

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

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

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

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

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

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

這不滿足我們?cè)诒拘」?jié)開(kāi)始時(shí)提到的“更新時(shí)，通過(guò)變更的tag 以及 需要add 或 delete 的userid就可以完成變更”。在這里，若我們想更新tag下的User List，我們必須提供該tag下的所有user id。由于tag下有百萬(wàn)量級(jí)的user id，這種更新方式帶來(lái)的網(wǎng)絡(luò)帶寬開(kāi)銷、cpu開(kāi)銷是巨大的，以至于無(wú)法接受。

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

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

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

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

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

這樣一來(lái)，就同時(shí)解決了檢索和更新的問(wèn)題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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