一種建立海量id映射關係的方法
2023-07-15 16:09:06
一種建立海量id映射關係的方法
【專利摘要】本發明揭示了一種建立海量ID映射關係的方法，包括以下步驟：（1）按映射關係A中的主鍵標識碼選擇對應的區塊；（2）判斷當前區塊是否有該映射關係，若是，則執行步驟（3），若否，則執行步驟（5）；（3）讀取該主鍵標識碼之前存儲的映射關係B；（4）判斷映射關係B是否包含映射關係A，若是，則執行步驟（5），若否，則執行步驟（7）；（5）更新內存全索引；（6）將映射數據寫入磁碟；以及（7）插入映射關係成功；本發明能夠實現單機支持多達1B組映射關係，使用多級複合索引擴充存儲能力並提升查詢性能，通過磁碟索引分區記錄映射關係，通過內存全索引實現通過任意ID查詢所在映射關係。
【專利說明】一種建立海量ID映射關係的方法
【技術領域】
[0001] 本發明涉及網絡廣告領域，特別涉及一種建立海量ID映射關係的方法。
【背景技術】
[0002] 眾所周知，網際網路廣告是網際網路行業最主要的贏利模式，流量變現成為網際網路商 業產品非常重要的評價標準。隨著網際網路人群定向技術的發展，網際網路廣告也開始擺脫 單一、古板的交易模式，轉而向更精確高效的交易模式轉變。這中間實時競價（Real Time Bidding,簡稱RTB)扮演了重要一環。
[0003] 在RTB的競價中，bid request中一般會含有一個ADX (Ad Exchange平臺）提供 的訪客標識，這個標識可以理解為類似於USERID的cookie,但是絕對不會是Ad Exchange 系統內部的ID,-般會利用非可逆加密算法做一次hash再給DSP (Demand-Side Platform 的縮寫，可以看做流量的購買方，為廣告主服務)，經過加密後的USERID我們叫做USERID'。 而DSP-般需要針對bid request中的各種維度數據，包括PV信息，用戶特徵信息，廣告位 信息等決定是否購買此次曝光，還現今流行的"再營銷（retargeting)"技術必須依賴用戶 標識，所以這個USERID'是DSP需要的，DSP需要自行維護一個USERID'的映射關係，就是 該USERID'與自己定義的用戶標識的一個映射。
[0004] -般要提供key-value查詢服務可以使用NoSql技術進行解決，但隨著接入的ADX 平臺和廣告主越來越多，DSP方維護的ID映射關係的量也逐漸增多，常規基於內存的NoSql 技術(memcached，redis等)受制於內存容量，同時對鍵值對有較大的膨脹率，單機無法支持 多達1B組ID映射關係的存儲和查詢。多臺的基於內存NoSql小集群對機器資源比較浪費， 無法集中使用，並且存在數據一致性等問題。其他的基於磁碟文件的NoSql技術（LevelDB， SSDB等)無法滿足大量的隨機查詢請求。針對這一現象，亟需解決海量ID映射關係的存儲 以及提供對應的頻繁查詢請求。
[0005] 有鑑於此，一種海量ID映射關係存儲和查詢的裝置應運而生。
【發明內容】
[0006] 本發明提供了一種建立海量ID映射關係的方法，克服了現有技術的困難，能夠實 現單機支持多達1B (10億)組映射關係，使用多級複合索引擴充存儲能力並提升查詢性能， 通過磁碟索引分區記錄映射關係，通過內存全索引實現通過任意ID查詢所在映射關係。
[0007] 本發明提供了一種建立海量ID映射關係的方法，包括以下步驟： (1) 按映射關係A中的主鍵標識碼選擇對應的區塊； (2) 判斷當前區塊是否有該映射關係，若是，則執行步驟（3)，若否，則執行步驟（5); (3) 讀取該主鍵標識碼之前存儲的映射關係B ; (4) 判斷映射關係B是否包含映射關係A，若是，則執行步驟（5)，若否，則執行步驟（7); (5) 更新內存全索引； (6) 將映射數據寫入磁碟；以及 (7)插入映射關係成功。
[0008] 優選地，所述步驟（5)中包括對兩組映射關係A和B進行合併。
[0009] 優選地，所述步驟（5)中包括對於一組新的映射關係或者合併後的映射關係進行 更新內存全索引。
[0010] 優選地，如果索引中指向了另外的主鍵標識碼，則使用當前的主鍵標識碼覆蓋之， 再將這組映射關係寫入到磁碟中。
[0011] 本發明的建立海量ID映射關係的方法包括為所有的ID按不同的類型分配唯一的 識別碼，並映射關係通過識別碼存儲在內存全索引中；根據映射關係中的主鍵的識別碼選 擇對應的分區進行存儲；當主鍵已經存在時，需要按識別碼有選擇的更新內存全索引和固 態存儲設備。通過上述方法本發明單機支持多達1B (10億）組映射關係，使用多級複合索 引擴充存儲能力並提升查詢性能，通過磁碟索引分區記錄映射關係，通過內存全索引實現 通過任意ID查詢所在映射關係。本發明有了第一方Cookie和第三方Cookie的映射庫，使 得DSP可以根據用戶數據分析進行有效的競價，實現利益的最大化。進一步DMP平臺（Data Management Platform。DMP存儲了流量、受眾的各種特徵信息)才得以將分散的第一、第三 方數據進行整合，實現受眾統一識別。
[0012] 以下結合附圖及實施例進一步說明本發明。
[0013]
【專利附圖】
【附圖說明】
[0014] 圖1為本發明的建立海量ID映射關係的方法的流程圖。
[0015]
【具體實施方式】
[0016] 下面通過圖1來介紹本發明的一種具體實施例。
[0017] 實施例1 如圖1所示，本發明的一種建立海量ID映射關係的方法，包括以下步驟： (1) 按映射關係A中的主鍵標識碼選擇對應的區塊； (2) 判斷當前區塊是否有該映射關係，若是，則執行步驟（3)，若否，則執行步驟（5); (3) 讀取該主鍵標識碼之前存儲的映射關係B ; (4) 判斷映射關係B是否包含映射關係A，若是，則執行步驟（5)，若否，則執行步驟（7); (5) 更新內存全索引； (6) 將映射數據寫入磁碟；以及 (7) 插入映射關係成功。
[0018] 其中所述步驟（5)中包括對兩組映射關係A和B進行合併。所述步驟（5)中包括 對於一組新的映射關係或者合併後的映射關係進行更新內存全索引。如果索引中指向了另 外的主鍵標識碼，則使用當前的主鍵標識碼覆蓋之，再將這組映射關係寫入到磁碟中。
[0019] 本發明的【具體實施方式】如下： 本發明中的映射關係的基礎存儲單兀 一組映射關係作為一個獨立的存儲單元，包括： 將上述背景知識中的DSP方ID對應主鍵 ADX方和廣告主第一方受眾的ID對應索引鍵，它們都是各自根據一定的算法用來唯一 標識一個用戶。但不保證跨平臺或廣告主時不會出現衝突，所以還需要記錄ID來源，即平 臺（或廣告主）的類型 其中索引鍵至少包含一個，所以每組ID映射關係可能會以如下形式組織 主鍵：{索引鍵來源1 :索引鍵1，索引鍵來源2 :索引鍵2......} 標識碼是為所有的鍵值唯一分配的，同一類型的鍵值中不會出現相互衝突的標識碼， 標識碼主要用於建立不同的索引，使用64位整數進行表示，可以最大限度地節省內存。
[0020] 固態磁碟索引 數據存儲到磁碟時按按照主鍵進行了分區（Block)索引，各分區的存儲位置之間是相 互獨立並連續的，每個Block裡面記錄映射關係的插入更改以及刪除的所有記錄，這些操 作都是以追加寫入（APPEND)的方式記錄在Block裡面。
[0021] 在同一分區內，本發明採用正向索引的方式建立了主鍵標識碼和磁碟數據中一一 映射關係，可以根據主鍵快速定位磁碟中的存儲位置，然後讀取對應的映射關係。
[0022] 內存全索引 本發明同時也提供根據索引鍵進行查詢映射關係的功能，通過一步轉換可以將這類查 詢請求轉換成根據主鍵查詢映射關係。本發明採用多重交叉索引的方式，每組映射關係中 會記錄索引鍵的不同來源，使用了 HASH索引和BTree索引記錄索引鍵的標識碼映射到的主 鍵標識碼，得到主鍵標識碼之後再根據上述磁碟索引讀取對應的映射關係。
[0023] 對於一組映射關係的插入，首先會根據主鍵標識碼找出所對應的Block，如該主鍵 標識碼已經存在於該Block，則將之前保存的映射關係讀出，與當前待插入的進行對比。
[0024] 如果待插入的映射關係中包含了新的映射結果，或者映射結果發生了變化，則對 兩組映射關係進行合併（Merge)，如有衝突則以待插入的映射關係中的結果為準 對於一組新的映射關係或者合併後的映射關係進行更新內存全索引，如果索引中指向 了另外的主鍵標識碼，則使用當前的主鍵標識碼覆蓋之。再將這組映射關係寫入到磁碟中 查詢 對於映射關係的查詢，如果查詢請求不是主鍵，則會根據內存全索引查詢到對應的主 鍵標識碼，如找不到，則直接返回查詢結果為空。
[0025] 所以查詢請求最終都可以轉化成根據主鍵標識碼查詢映射關係。
[0026] 同樣的，和插入請求類似，首先會根據主鍵標識碼找出所對應的Block，如果主鍵 標識碼已經不存在於該Block，則返回查詢結果為空，否則讀取磁碟文件取出映射關係返 回。
[0027] 刪除 刪除一組映射關係，如果刪除請求不是主鍵標識碼，則會根據內存全索引查詢到對應 的主鍵標識碼，如找不到，則直接返回。
[0028] 所以刪除請求最終都可以轉化成根據主鍵標識碼刪除映射關係。
[0029] 同樣的，首先會根據主鍵標識碼找出所對應的Block，刪除磁碟索引，如果主鍵標 識碼已經不存在於該Block，則無法刪除直接返回。
[0030] 為了提升磁碟的寫性能，所有的操作都是以Append的方式，所以對應一個刪除操 作，磁碟中寫入的是一條只有主鍵標識碼的映射關係（區別於正常情況下至少有一個索引 鍵的映射關係)。
[0031] 刪除磁碟索引的同時需要刪除內存全索引，通過主鍵標識碼先將映射關係從磁碟 中讀取出來，再根據結果中的索引鍵標識碼刪除內存全索引中的相應記錄。
[0032] 另外在刪除內存全索引的時候需要注意，當前的索引鍵標識碼是否仍然指向該主 鍵標識碼，如不是，則表示該索引鍵已經被記錄到另一組映射關係中，則這一條索引無需刪 除。
[0033] 碎片整理 映射關係的更改和刪除會對磁碟文件上的數據造成"空洞"，長期累積下來會造成存儲 空間的浪費，需要進行磁碟碎片整理。
[0034] 本方法基於磁碟索引實現了一種高效安全的碎片整理策略包括 (1) 對需要進行碎片整理的分區建立快照； (2) 根據快照建立交換區； (3) 將原分區的映射關係數據寫到交換區所對應的磁碟文件中； (4) 將原分區在建立快照後的數據同步到交換區中； (5) 用交換區替換原分區，碎片整理完成。
[0035] 當服務檢查到某個分區需要進行磁碟整理後，建立該分區的索引快照，將上述快 照中有效的映射關係數據寫到交換區。
[0036] 快照部分整理並不影響原來的分區持續提供服務，但會造成整理快照時有新的數 據寫到原有分區中，所以接下來一步是將這一部分數據同步到交換區中，而這一部分數據 相對於快照數據來說是非常小的，可以快速完成同步過程。
[0037] 交換區在完成了快照部分的整理，並完整將原分區的新數據也同步過來後，則完 成單個分區的碎片整理，替換掉原分區。
[0038] 定期清除 根據業務需求，如果某組映射關係在一段時間內不再活躍(沒有查詢/更改)，比如30 天內，則需要將這些映射關係從映射庫中移除掉。此外， 通過定期清除也能有效控制映射庫中存儲的數據大小，避免數據無限制地膨脹，以及 膨脹後對性能帶來的影響。
[0039] 因為不是業務主動要求的刪除，則實時性要求不高。基於此，以天為粒度在業務的 低谷期(凌晨）集中刪除過期的映射關係。
[0040] 對於如何確定一組映射關係是否過期，以布隆過濾器實現了一個近似的算法，在 不會誤刪除的情況下，性能和準確率也得到了很好的保證。
[0041] 首先，以天為粒度將當天出現過的主鍵標識碼(包括插入，查詢和更改）插入布隆 過濾器，並以文件的形式保存在普通磁碟上。當定期清除啟動後，會將有效期內的所有布隆 過濾器合併在一起，合併後的過濾器則涵蓋了所有有效的主鍵標識碼。然後通過遍歷映射 庫將沒有出現在過濾器中的映射關係刪除，直至遍歷完成。
[0042] 性能測試報告 分別使用SSD和Flash卡(主要）進行性能測試，考慮到查詢請求中大部分ID是沒有 mapping關係的，所以測試中查詢不存在的key和存在的key的比例為2 :1。
[0043] 測試中主要考察了 QPS，Latency (99%)，CPU和磁碟讀寫情況。
【權利要求】
1. 一種建立海量ID映射關係的方法，其特徵在於，包括以下步驟： (1) 按映射關係A中的主鍵標識碼選擇對應的區塊； (2) 判斷當前區塊是否有該映射關係，若是，則執行步驟（3)，若否，則執行步驟（5); (3) 讀取該主鍵標識碼之前存儲的映射關係B ; (4) 判斷映射關係B是否包含映射關係A，若是，則執行步驟（5)，若否，則執行步驟（7); (5) 更新內存全索引； (6) 將映射數據寫入磁碟；以及 (7) 插入映射關係成功。
2. 如權利要求1所述的建立海量ID映射關係的方法，其特徵在於：所述步驟（5)中包 括對兩組映射關係A和B進行合併。
3. 如權利要求1所述的建立海量ID映射關係的方法，其特徵在於：所述步驟（5)中包 括對於一組新的映射關係或者合併後的映射關係進行更新內存全索引。
4. 如權利要求3所述的建立海量ID映射關係的方法，其特徵在於：如果索引中指向了 另外的主鍵標識碼，則使用當前的主鍵標識碼覆蓋之，再將這組映射關係寫入到磁碟中。
【文檔編號】G06F17/30GK104281717SQ201410603292
【公開日】2015年1月14日 申請日期:2014年10月31日 優先權日:2014年10月31日
【發明者】湯奇峰, 羅青山, 史劍冬 申請人:晶贊廣告（上海）有限公司