如果你居住在印度，當(dāng)不希望接受任何電話(huà)推銷(xiāo)員的騷擾時(shí)，你可以在全國(guó)客戶(hù)偏好登記冊(cè)(National Customer Preference Register，NCPR) 【1 】 中進(jìn)行注冊(cè)。政府維護(hù)了這個(gè)由用戶(hù)注冊(cè)的電話(huà)號(hào)碼組成的數(shù)據(jù)庫(kù)。現(xiàn)在，差不多有4億個(gè)注冊(cè)號(hào)碼。所有注冊(cè)的電話(huà)推銷(xiāo)員必須及時(shí)更新數(shù)據(jù)，以保證他們?cè)谶M(jìn)行推銷(xiāo)時(shí)會(huì)參考這個(gè)偏好設(shè)置進(jìn)行工作。

這些數(shù)據(jù)由一捆ZIP文件(當(dāng)下是40個(gè))提供，每個(gè)ZIP文件包含一個(gè)10M的CSV文件。這篇文章將會(huì)講述這2.4GB壓縮后的數(shù)據(jù)如何基于一些簡(jiǎn)單的方式以一種可搜索的格式適配2GB的內(nèi)存。

數(shù)據(jù)

下面是CSV文件一瞥(出于隱私原因，有些數(shù)據(jù)進(jìn)行了混淆)

關(guān)于存儲(chǔ)在SQL引擎中的一些說(shuō)明

在內(nèi)存為4GB的 Linode 機(jī)房的機(jī)器上， PostgreSQL數(shù)據(jù)表(使用COPY)加載數(shù)據(jù)約需要10分鐘：

real 10m0.159s

user 2m42.243s

sys 0m26.363s

添加一個(gè)主鍵大約耗時(shí)1.5到2個(gè)小時(shí)：

real 118m21.637s

user 0m0.043s

sys 0m0.020s

并使用32GB的硬盤(pán)空間：

觀(guān)察CSV數(shù)據(jù)

分析了數(shù)據(jù)之后，我們可以看到：

* 將近400M行數(shù)據(jù)

* 電話(huà)號(hào)碼全部(phone numbers)是10位

* 服務(wù)區(qū)域碼(service area code)是1-23之間的自然數(shù)

* 偏好(preference)依靠`#`來(lái)界定，可能是`0`或者是{1,2,3,4,5,7}的組合

* Ops類(lèi)型(Opstype)用A表示啟用，用D表示未啟用

* 電話(huà)號(hào)碼類(lèi)型(Phone Type)是{1,2,3}中的一個(gè)

這意味著一行數(shù)據(jù)可以用2個(gè)字節(jié)表示：

***個(gè)字節(jié)：1位存在標(biāo)志位(existence flag)，5位服務(wù)區(qū)域碼，2位電話(huà)號(hào)碼類(lèi)型。

第二個(gè)字節(jié)：7位偏好，1位Ops類(lèi)型。

數(shù)據(jù)可以通過(guò)2*400MB來(lái)表示。存在標(biāo)志位將會(huì)在下面的部分討論。

使之可搜索

每個(gè)條目都會(huì)按照電話(huà)號(hào)碼進(jìn)行頻繁的搜索，而目前我們并沒(méi)有將數(shù)據(jù)與電話(huà)號(hào)碼進(jìn)行匹配。我們需要添加字節(jié)來(lái)存儲(chǔ)電話(huà)號(hào)碼。不幸的是，10個(gè)數(shù)字并不能放入32位中(10 digits won't fit in 32 bits)，使用5*400MB來(lái)存儲(chǔ)數(shù)字并不是一個(gè)樂(lè)觀(guān)的情況，而且根本沒(méi)辦法進(jìn)行搜索。如果數(shù)據(jù)按順序排列(arranged in a sequence)，那么索引為 (2*number) 和 (2*number+1)的內(nèi)存位置便能給出所需的兩個(gè)字節(jié)?？招锌梢杂?**個(gè)字節(jié)中的存在標(biāo)志表示。這意味著我們需要20GB的內(nèi)存(2字節(jié)*10B的數(shù)字)。我們能進(jìn)一步壓縮嗎?該數(shù)組看起來(lái)很稀疏(只有40%被占用)。

我們的解決方案是：使用兩種格式類(lèi)型。

#p#

更進(jìn)一步

我們還發(fā)現(xiàn)對(duì)于大多數(shù)移動(dòng)手機(jī)號(hào)碼的數(shù)組是密集的 【 2 】 。所以，如果10個(gè)數(shù)字分成兩部分——4位的前綴(我們可以稱(chēng)之為頭部)和6位的數(shù)字偏移量(尾部)——這樣一來(lái)，固定的4位前綴的所有可能值按順序排列時(shí)，它們都可以被放入2MB的空間里了。(每個(gè)尾部2字節(jié))?，F(xiàn)在，搜索變得簡(jiǎn)單了，因?yàn)槲覀儼凑瘴膊窟M(jìn)行偏移量計(jì)算，直接訪(fǎng)問(wèn)數(shù)組即可。

這個(gè)稀疏的數(shù)列存儲(chǔ)在5字節(jié)的序列中，3個(gè)字節(jié)表示尾部，2個(gè)字節(jié)表示數(shù)據(jù)。尾部按照升序排列，所以搜索變的簡(jiǎn)單了(二分搜索)。

對(duì)于持久化存儲(chǔ)，具有相同前綴的數(shù)字存儲(chǔ)在一個(gè)文件中，該文件的***個(gè)字節(jié)是類(lèi)型的指示框。這些共需1.8GB的空間，這些數(shù)據(jù)可以存儲(chǔ)在內(nèi)存中，通過(guò)webserver進(jìn)行發(fā)布。

加工處理

使用快速Python腳本來(lái)轉(zhuǎn)換CSV數(shù)據(jù)為我們需要的格式是十分耗時(shí)的。分析表明，大部分時(shí)間花費(fèi)在迭代處理2M固定頭部數(shù)據(jù)時(shí)。我們嘗試使用xrange進(jìn)行優(yōu)化，但是5小時(shí)對(duì)于處理整個(gè)數(shù)據(jù)，尤其是PostgreSQL處理僅需要2小時(shí)，實(shí)在太多了。我們希望能有些快速響應(yīng)，更符合心理預(yù)期。相同的程序選擇Rust來(lái)實(shí)現(xiàn)，處理整個(gè)數(shù)據(jù)僅用20-30分鐘。

real 21m4.284s

user 20m58.427s

sys 1m37.607s

查找計(jì)時(shí)

為了測(cè)量該解決方案的速度，我們隨機(jī)生成了相同序列(固定的頭部)的電話(huà)號(hào)碼。結(jié)果如下圖所示。我們選取“9818”和“9000” 開(kāi)頭的號(hào)碼去分別計(jì)算查找密集框(我們稱(chēng)之為類(lèi)型0)和稀疏框(類(lèi)型1)的時(shí)間。對(duì)于SQL解決方案，頭部的密集程度并不影響。注意，在本次測(cè)量中，盡管我們?yōu)榱斯狡鹨?jiàn)，計(jì)時(shí)時(shí)包含了磁盤(pán)的讀寫(xiě)，但是在我們的解決方案中，數(shù)據(jù)一旦被加載或放入內(nèi)存中，不再需要磁盤(pán)訪(fǎng)問(wèn)，之后由于數(shù)據(jù)存儲(chǔ)格式的優(yōu)點(diǎn)，這個(gè)進(jìn)程被加快。

所有的測(cè)試都是在4GB的Linode機(jī)房機(jī)器上跑的，機(jī)器配置如下：

SSD, 4GB RAM, 4 virtual CPU cores, CPU Model: Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz

API和開(kāi)源

在SparkTG，我們尊重客戶(hù)的偏好設(shè)置。盡管我們的客戶(hù)大部分都是與注冊(cè)的客戶(hù)交流，但我們還是保證他們最終不會(huì)撥出一個(gè)無(wú)關(guān)的電話(huà)。我們已經(jīng)將該項(xiàng)目 【3】 開(kāi)源，并且提供API 【4】 來(lái)查找號(hào)碼NCPR狀態(tài)，使得電話(huà)推銷(xiāo)找不到方式撥打注冊(cè)用戶(hù)的電話(huà)。

原文鏈接：http://www.jointforce.com/jfperiodical/article/show/925?utm_source=tuicool