介紹
我在莫斯科舉行的 GopherCon Russia 2019 會議上用英語發表了這份報告，並在下諾夫哥羅德的一次聚會上用俄語發表了這份報告。 我們正在談論點陣圖索引 - 不像 B 樹那麼常見，但同樣有趣。 分享 會議上的演講為英文，文字記錄為俄文。
我們將看看位圖索引是如何運作的，什麼時候比其他索引更好，什麼時候比其他索引差，以及在什麼情況下它比其他索引快得多； 讓我們來看看哪些流行的 DBMS 已經有了點陣圖索引； 讓我們嘗試用 Go 來寫自己的程式碼。 “作為甜點”，我們將使用現成的庫來創建我們自己的超快速專業資料庫。
我真心希望我的作品對您有用且有趣。 去！
介紹
大家好！ 現在是晚上六點，我們都累極了。 是時候談論無聊的資料庫索引理論了，對吧？ 別擔心，我到處都會有幾行原始碼。 🙂
拋開所有笑話不談，這份報告充滿了訊息，而我們的時間不多了。 那麼就讓我們開始吧。
今天我主要講以下內容：
- 什麼是索引；
- 什麼是位圖索引；
- 哪裡使用了它，哪裡沒有使用它，以及為什麼；
- Go 中的簡單實作和編譯器的一些麻煩；
- Go 彙編器中的實作稍微不那麼簡單，但效率更高；
- 點陣圖索引的「問題」；
- 現有的實施。
那什麼是索引呢？
索引是我們除了主資料之外維護和更新的一個單獨的資料結構。 它用於加快搜尋速度。 如果沒有索引，搜尋將需要完全遍歷資料（這個過程稱為全掃描），而這個過程具有線性演算法複雜度。 但資料庫通常包含大量數據，線性複雜度太慢。 理想情況下，我們會得到一個對數或常數。
這是一個非常複雜的主題，充滿了微妙之處和權衡，但在回顧了數十年的資料庫開發和研究之後，我願意說只有幾種廣泛使用的方法來建立資料庫索引。
第一種方法是分層縮小搜尋空間，將搜尋空間劃分為較小的部分。
我們通常使用不同類型的樹來做到這一點。 一個例子是你衣櫃裡的一大盒材料，其中包含分為不同主題的小盒子材料。 如果您需要材料，您可能會在一個寫著「材料」而不是寫著「Cookies」的盒子裡尋找它們，對吧？
第二種方法是立即選擇所需的元素或元素組。 我們在哈希映射或反向索引中執行此操作。 使用哈希映射與前面的範例非常相似，但你的衣櫃裡不是一盒盒子，而是一堆裝最終物品的小盒子。
第三種方法是消除搜尋的需要。 我們使用布隆過濾器或布穀鳥過濾器來做到這一點。 第一個會立即給出答案，使您無需搜索。
最後一種方法是充分利用現代硬體賦予我們的所有能力。 這正是我們在點陣圖索引中所做的。 是的，在使用它們時，我們有時需要遍歷整個索引，但我們做得非常有效率。
正如我所說，資料庫索引的主題非常廣泛並且充滿了妥協。 這意味著有時我們可以同時使用多種方法：如果我們需要進一步加快搜尋速度，或者如果我們需要覆蓋所有可能的搜尋類型。
今天我將討論其中最不為人所知的方法 - 位圖索引。
我是誰來談論這個話題？
我在 Badoo 擔任團隊負責人（也許您更熟悉我們的其他產品 Bumble）。 我們已經在全球擁有超過 400 億用戶，並擁有許多為他們選擇最佳匹配的功能。 我們使用自訂服務（包括點陣圖索引）來做到這一點。
那什麼是點陣圖索引呢？
點陣圖索引，顧名思義，使用點陣圖或位元集來實現搜尋索引。 從鳥瞰角度來看，此索引由一個或多個代表任何實體（例如人）及其屬性或參數（年齡、眼睛顏色等）的位圖以及使用位元運算（AND、OR、NOT）的演算法組成。 ）來回答搜尋查詢。
我們被告知，點陣圖索引最適合併且非常適合那些將多個低基數列中的查詢組合起來的搜尋（例如“眼睛顏色”或“婚姻狀況”與“距市中心的距離”之類的內容） 。 但稍後我將證明它們也適用於高基數列。
讓我們來看看點陣圖索引最簡單的範例。
想像一下，我們有一個莫斯科餐廳列表，其二元屬性如下：
- 靠近地鐵；
- 有私人停車場；
- 有陽台（有露台）；
- 您可以預訂餐桌（接受預訂）；
- 適合素食者（素食主義者友善）；
- 昂貴（昂貴）。
讓我們為每個餐廳指定一個從 0 開始的序號，並為 6 個位圖分配記憶體（每個特徵一個）。 然後，我們將根據餐廳是否具有此屬性來填充這些點陣圖。 如果餐廳 4 有陽台，則「有陽台」位圖中的第 4 位將設定為 1（如果沒有陽台，則設定為 0）。
現在我們有了最簡單的點陣圖索引，我們可以用它來回答以下查詢：
- “顯示素食餐廳”；
- “給我看看帶陽台的便宜餐廳，你可以在那裡預訂餐桌。”
如何？ 我們來看看吧。 第一個請求非常簡單。 我們需要做的就是獲取「素食友善」點陣圖並將其轉換為暴露位圖的餐廳清單。
第二個請求稍微複雜一些。 我們需要在“昂貴”位圖上使用NOT 位圖來獲取便宜餐館的列表，然後將其與“我可以預訂餐桌”位圖進行AND 運算，並將結果與“有一個陽台”位圖進行AND 運算。 產生的點陣圖將包含滿足我們所有標準的機構清單。 在此範例中，這只是 Yunost 餐廳。
其中涉及很多理論，但不用擔心，我們很快就會看到程式碼。
點陣圖索引用在哪裡？
如果您 Google 點圖索引，90% 的答案都會以某種方式與 Oracle DB 相關。 但其他 DBMS 可能也支援這樣一個很酷的東西，對吧？ 並不真地。
讓我們來看看主要嫌疑犯名單。
MySQL尚不支援點陣圖索引，但有一個提案建議添加此選項（).
PostgreSQL 不支援點陣圖索引，但使用簡單的點陣圖和位元操作來組合跨多個其他索引的搜尋結果。
Tarantool 具有位集索引並支援對其進行簡單搜尋。
Redis 有簡單的位域）而無法搜尋它們。
MongoDB還不支援點陣圖索引，但也有一個Proposal建議加入這個選項
Elasticsearch 在內部使用點陣圖).
- 但是我們家出現了一位新鄰居：皮洛薩。 這是一個用 Go 寫的新的非關聯式資料庫。 它僅包含位圖索引並以它們為基礎。 我們稍後再討論。
Go 中的實現
但為什麼點陣圖索引很少被使用呢？ 在回答這個問題之前，我想向您展示如何在 Go 中實作一個非常簡單的點陣圖索引。
點陣圖本質上只是資料片段。 在 Go 中，我們使用位元組切片來實現這一點。
對於一個餐廳特徵，我們有一個點陣圖，位圖中的每一位表示特定餐廳是否具有該屬性。
我們需要兩個輔助函數。 其中一個將用於用隨機資料填充我們的點陣圖。 隨機的，但餐廳有一定的機率擁有每個屬性。 例如，我相信莫斯科很少有不能訂座的餐館，在我看來，大約有20%的餐廳適合素食者。
第二個函數會將位圖轉換為餐廳清單。
為了回答「顯示有露台且可以預訂的便宜餐廳」這一查詢，我們需要兩個位元運算：NOT 和 AND。
我們可以透過使用更複雜的 AND NOT 運算子來稍微簡化我們的程式碼。
我們為每個操作都有函數。 它們都遍歷切片，從每個切片中取出相應的元素，透過位元運算將它們組合起來，並將結果放入結果切片中。
現在我們可以使用點陣圖和函數來回答搜尋查詢。
儘管函數非常簡單，但效能並沒有那麼高，而且我們透過在每次呼叫函數時不返回新的結果切片來節省大量資金。
使用 pprof 進行一些分析後，我注意到 Go 編譯器缺少一個非常簡單但非常重要的最佳化：函數內聯。
事實上，Go 編譯器非常害怕通過切片的循環，並且斷然拒絕內聯包含此類循環的函數。
但我並不害怕，我可以透過使用 goto 而不是循環來欺騙編譯器，就像過去的美好時光一樣。
而且，正如您所看到的，現在編譯器將愉快地內聯我們的函數！ 結果，我們設法節省了大約 2 微秒。 不錯！
如果仔細觀察彙編輸出，第二個瓶頸很容易看出。 編譯器在我們最熱的循環內加入了切片邊界檢查。 事實上，Go 是一種安全語言，編譯器擔心我的三個參數（三個切片）的大小不同。 畢竟，那麼理論上就會存在發生所謂緩衝區溢位的可能性。
讓我們透過向編譯器顯示所有切片的大小相同來讓編譯器放心。 我們可以透過在函數的開頭添加一個簡單的檢查來做到這一點。
看到這一點，編譯器很高興地跳過了檢查，最終我們又節省了 500 奈秒。
大佬們
好吧，我們設法從簡單的實作中擠出一些效能，但這個結果實際上比目前硬體可能的結果要差得多。
我們所做的只是基本的位元操作，並且我們的處理器非常有效率地執行這些操作。 但不幸的是，我們用非常小的工作片段「餵養」我們的處理器。 我們的函數逐字節執行操作。 我們可以非常輕鬆地調整程式碼以使用 UInt8 切片來處理 64 位元組區塊。
正如您所看到的，這個小變化通過將批量大小增加了八倍，使我們的程式速度提高了八倍。 增益可以說是線性的。
彙編程式中的實現
但這還沒結束。 我們的處理器可以處理 16、32 甚至 64 位元組的區塊。 這種「廣泛」操作稱為單指令多資料（SIMD；一條指令，許多資料），而轉換程式碼以使其使用此類操作的過程稱為向量化。
不幸的是，Go 編譯器在向量化方面遠非出色。 目前，向量化 Go 程式碼的唯一方法是使用 Go 彙編器手動取得和放置這些操作。
Go 彙編器是一個奇怪的野獸。 您可能知道彙編語言與您正在編寫的電腦的體系結構密切相關，但 Go 中的情況並非如此。 Go 彙編器更像是 IRL（中間表示語言）或中間語言：它實際上是獨立於平台的。 羅布派克 (Rob Pike) 表現出色 幾年前在丹佛的 GopherCon 上討論過這個主題。
此外，Go 使用了一種不尋常的 Plan 9 格式，它與普遍接受的 AT&T 和 Intel 格式不同。
可以肯定地說，手工編寫 Go 彙編程式並不是最有趣的。
但幸運的是，已經有兩個進階工具可以幫助我們編寫 Go 彙編器：PeachPy 和 avo。 這兩個實用程式分別從用 Python 和 Go 編寫的高階程式碼產生 Go 彙編程式。
這些實用程式簡化了暫存器分配、編寫循環等操作，並且通常簡化了進入 Go 彙編程式設計世界的過程。
我們將使用 avo，因此我們的程式將幾乎是常規的 Go 程式。
這是 avo 程式最簡單的範例。 我們有一個 main() 函數，它內部定義了 Add() 函數，其意義是將兩個數字相加。 這裡有一些輔助函數可以按名稱取得參數並取得空閒且合適的處理器暫存器之一。 每個處理器操作在 avo 上都有一個對應的函數，如 ADDQ 所示。 最後，我們看到一個用於儲存結果值的輔助函數。
透過呼叫gogenerate，我們將在avo上執行程序，結果會產生兩個檔案：
- add.s 以及 Go 彙編器中的結果程式碼；
- Stub.go 帶有函數頭來連接兩個世界：Go 和彙編器。
現在我們已經了解了 avo 的作用和作用，讓我們看看我們的函數。 我實現了函數的標量和向量 (SIMD) 版本。
讓我們先看看標量版本。
與前面的範例一樣，我們要求一個免費且有效的通用暫存器，我們不需要計算參數的偏移量和大小。 avo 為我們做了這一切。
我們曾經使用標籤和 goto（或跳轉）來提高效能並欺騙 Go 編譯器，但現在我們從一開始就這樣做。 重點是周期是一個更高層次的概念。 在組譯程式中，我們只有標籤和跳轉。
其餘的程式碼應該已經熟悉並且可以理解。 我們模擬一個帶有標籤和跳躍的循環，從兩個切片中取出一小段數據，將它們與位元操作組合起來（在本例中為 AND NOT），然後將結果放入結果切片中。 全部。
這就是最終的彙編程式碼的樣子。 我們不必計算偏移量和大小（以綠色突出顯示）或追蹤所使用的暫存器（以紅色突出顯示）。
如果我們將彙編語言實現的效能與 Go 中最佳實現的效能進行比較，我們會發現它們是相同的。 這是預期的。 畢竟，我們沒有做任何特別的事情——我們只是重現了 Go 編譯器會做的事情。
不幸的是，我們不能強制編譯器內聯用組譯語言寫的函式。 Go 編譯器目前還沒有這樣的功能，儘管很長一段時間以來一直有人要求添加它。
這就是為什麼不可能從組合語言中的小函數中獲得任何好處。 我們需要編寫大型函數，或使用新的 math/bits 包，或繞過組譯語言。
現在讓我們來看看函數的向量版本。
對於此範例，我決定使用 AVX2，因此我們將使用對 32 位元組區塊進行操作的操作。 程式碼的結構與標量版本非常相似：載入參數、請求空閒的共用暫存器等。
一項創新是更廣泛的向量運算使用特殊的寬寄存器。 對於 32 個位元組區塊，這些暫存器是以 Y 為前綴的。這就是為什麼您在程式碼中看到 YMM() 函數的原因。 如果我將 AVX-512 與 64 位元區塊一起使用，則前綴將為 Z。
第二個創新是我決定使用一種稱為循環展開的優化，這意味著在跳到循環開頭之前手動執行八次循環操作。 這種最佳化減少了程式碼中的分支數量，並受到可用空閒暫存器數量的限制。
那麼，性能呢？ 她很漂亮！ 與最佳 Go 解決方案相比，我們實現了約七倍的加速。 令人印象深刻，對吧？
但即使是這種實作也可以透過使用 AVX-512、預取或查詢調度程式的 JIT（即時編譯器）來加速。 但這肯定是一個單獨報告的主題。
點陣圖索引的問題
現在我們已經了解了 Go 中位圖索引的簡單實現以及彙編語言中更有效率的實現，最後讓我們談談為什麼點陣圖索引很少使用。
較舊的論文提到了位圖索引的三個問題，但較新的論文和我認為它們不再相關。 我們不會深入探討每個問題，而是從表面上看待它們。
高基數問題
所以，我們被告知位圖索引只適用於基數較低的字段，即那些值很少的字段（例如，性別或眼睛顏色），原因是此類字段的通常表示形式（一個每個值位）在在高基數的情況下，它將佔用太多空間，而且，這些點陣圖索引將很難（很少）填充。
有時我們可能會使用不同的表示形式，例如我們用來表示數字的標準表示形式。 但壓縮演算法的出現改變了一切。 在過去的幾十年裡，科學家和研究人員提出了大量的點陣圖壓縮演算法。 它們的主要優點是不需要解壓縮位圖來執行位元操作－我們可以直接對壓縮位圖執行位元操作。
最近，混合方法開始出現，例如咆哮點陣圖。 他們同時使用三種不同的位圖表示形式 - 點陣圖本身、陣列和所謂的位元運行 - 並在它們之間進行平衡，以最大限度地提高效能並最大限度地減少記憶體消耗。
您可以在最受歡迎的應用程式中找到咆哮的點陣圖。 各種程式語言已經有大量的實現，其中包括超過三種的 Go 實作。
另一種可以幫助我們處理高基數的方法稱為分箱。 想像一下，您有一個代表人身高的欄位。 高度是一個浮點數，但我們人類可不這麼認為。 對我們來說，身高185,2公分和185,3公分沒有差別。
事實證明，我們可以將相似的值分成1公分以內的組別。
如果我們還知道很少有人身高低於 50 厘米和高於 250 厘米，那麼我們基本上可以將具有無限基數的字段轉變為基數約為 200 個值的字段。
當然，如果有必要，我們可以事後進行額外的過濾。
高頻寬問題
點陣圖索引的下一個問題是更新它們的成本可能非常高。
資料庫必須能夠在可能有數百個其他查詢正在搜尋資料的同時更新資料。 我們需要鎖來避免並發資料存取或其他共享問題。 凡是有一個大鎖的地方，就會出現一個問題──鎖爭用，當這個鎖變成瓶頸時。
這個問題可以透過使用分片或版本索引來解決或規避。
分片是一件簡單且眾所周知的事。 您可以像對任何其他資料一樣對點陣圖索引進行分片。 您將獲得一堆小鎖，而不是一個大鎖，從而消除鎖爭用。
解決該問題的第二種方法是使用版本化索引。 您可以擁有一份用於搜尋或閱讀的索引副本，以及一份用於寫入或更新的索引副本。 並且在某個時間段內（例如，每 100 毫秒或 500 毫秒一次）複製它們並交換它們。 當然，這種方法僅適用於您的應用程式可以處理稍微滯後的搜尋索引的情況。
這兩種方法可以同時使用：您可以擁有分片版本索引。
更複雜的查詢
點陣圖索引的最後一個問題是，我們被告知它們不太適合更複雜類型的查詢，例如跨度查詢。
事實上，如果你想一想，像 AND、OR 等位運算不太適合「顯示房價在每晚 200 到 300 美元之間的酒店」這樣的查詢。
一個幼稚且非常不明智的解決方案是獲取每個美元值的結果，並透過位元「或」運算將它們組合起來。
更好的解決方案是使用分組。 例如，50 美元為一組。 這將使我們的進程加快 50 倍。
但透過使用專為此類請求建立的視圖也可以輕鬆解決該問題。 在科學論文中，它被稱為範圍編碼點陣圖。
在這種表示中，我們不僅僅為某個值（例如 200）設定一位，而是將該值和所有值設定得更高。 200及以上。 300 相同：300 以上。 等等。
使用這種表示形式，我們只需遍歷索引兩次即可回答此類搜尋查詢。 首先，我們將獲得房間費用低於或 300 美元的酒店列表，然後我們將從其中刪除房間費用低於或 199 美元的酒店。 準備好。
您會感到驚訝，但即使是地理查詢也可以使用點陣圖索引。 訣竅是使用用幾何圖形圍繞座標的幾何表示。 例如，Google 的 S2。 該圖形應該能夠以三個或更多可編號的相交線的形式表示。 這樣我們就可以將地理查詢變成「沿著間隙」（沿著這些編號線）的幾個查詢。
就緒解決方案
我希望我對您有點感興趣，現在您的武器庫中又多了一個有用的工具。 如果您需要做這樣的事情，您就會知道該往哪個方向看。
然而，並不是每個人都有時間、耐心或資源從頭開始建立點陣圖索引。 尤其是更先進的技術，例如使用 SIMD。
幸運的是，有幾個現成的解決方案可以幫助您。
咆哮的點陣圖
首先，還有我已經討論過的相同的咆哮點位圖庫。 它包含創建成熟的點陣圖索引所需的所有必要容器和位元操作。
不幸的是，目前沒有一個 Go 實作使用 SIMD，這意味著 Go 實現的效能低於 C 實作等。
毛毛屬
另一個可以幫助您的產品是 Pilosa DBMS，實際上它只有位圖索引。 這是一個相對較新的解決方案，但它正在迅速贏得人心。
Pilosa 在內部使用咆哮位圖，並讓您能夠使用它們，簡化並解釋了我上面談到的所有內容：分組、範圍編碼點陣圖、欄位的概念等。
讓我們快速看一下使用 Pilosa 回答您已經熟悉的問題的範例。
該示例與您之前看到的非常相似。 我們創建 Pilosa 伺服器的客戶端，創建索引和必要的字段，然後用帶有機率的隨機資料填充字段，最後執行熟悉的查詢。
之後，我們對「昂貴」欄位使用 NOT，然後將結果（或 AND）與「露台」欄位和「預訂」欄位相交。 最後，我們得到最終結果。
我真的希望在可預見的將來這種新型索引也會出現在像MySQL和PostgreSQL這樣的DBMS中——點陣圖索引。
結論
如果你還沒睡的話，謝謝。 由於時間有限，我必須簡要討論許多主題，但我希望這次演講有用，甚至可能具有激勵性。
點陣圖索引很有必要了解一下，即使您現在不需要它們。 讓它們成為您工具箱中的另一個工具。
我們研究了 Go 的各種效能技巧以及 Go 編譯器還不能很好處理的事情。 但這對於每個 Go 程式設計師來說絕對有用。
這就是我想告訴你的。 謝謝你！
來源： www.habr.com