哈希算法一直是索引中最為經(jīng)典的方法，它們能高效地儲(chǔ)存與檢索數(shù)據(jù)。但在去年 12 月，Jeff Dean 與 MIT 等研究者將索引視為模型，探索了深度學(xué)習(xí)模型學(xué)習(xí)的索引優(yōu)于傳統(tǒng)索引結(jié)構(gòu)的條件。本文首先將介紹什么是索引以及哈希算法，并描述在機(jī)器學(xué)習(xí)與深度學(xué)習(xí)時(shí)代中，如何將索引視為模型學(xué)習(xí)比哈希算法更高效的表征。

2017 年 12 月，谷歌和麻省理工學(xué)院的研究人員發(fā)表了一篇研究論文 The Case for Learned Index Structures，該論文介紹了他們?cè)凇笇W(xué)習(xí)型索引結(jié)構(gòu)」方面做出的探索。這些研究非常令人興奮，正如作者在摘要中所述：

「[…] 我們相信通過可學(xué)習(xí)的模型取代數(shù)據(jù)管理系統(tǒng)核心組件的想法對(duì)未來的系統(tǒng)設(shè)計(jì)有著深遠(yuǎn)的影響，而我們這項(xiàng)工作對(duì)于未來的發(fā)展僅僅是驚鴻一瞥�！�

事實(shí)上，谷歌和麻省理工學(xué)院研究人員提出的這項(xiàng)研究工作可以同索引世界中最為經(jīng)典有效的 B-Tree 和哈希圖（Hash Map）相匹敵。工程界對(duì)機(jī)器學(xué)習(xí)的未來早已有了許多的觀點(diǎn)，因此這篇研究論文已經(jīng)在 Hacker News，Reddit 乃至世界上所有的工業(yè)論壇中獲得了廣泛的關(guān)注和討論。

新的研究是重新審視一個(gè)領(lǐng)域基礎(chǔ)的絕佳機(jī)會(huì)，而且像索引等基礎(chǔ)性并且已經(jīng)獲得足夠研究的技術(shù)很少會(huì)有機(jī)會(huì)取得更大的突破。本文作為哈希表的入門性介紹，簡(jiǎn)要介紹了影響其快慢的主要因素，并為應(yīng)用于索引構(gòu)建技術(shù)的機(jī)器學(xué)習(xí)概念提供了直觀性理解。

針對(duì)谷歌/麻省理工學(xué)院合作發(fā)表的工作，Peter Bailis 和斯坦福大學(xué)的研究團(tuán)隊(duì)回顧了索引構(gòu)建的基礎(chǔ)知識(shí)，并勸誡我們不要扔掉經(jīng)典的算法書。Bailis 和他在斯坦福大學(xué)的團(tuán)隊(duì)重新構(gòu)建了可學(xué)習(xí)型索引策略，并且通過使用名為 Cuckoo Hashing 的經(jīng)典哈希表策略，在不使用任何機(jī)器學(xué)習(xí)技術(shù)的條件下取得了相似的結(jié)果。

在另一個(gè)對(duì)谷歌/麻省理工學(xué)院合作發(fā)表的工作的回應(yīng)中，Thomas Neumann 描述了另一種實(shí)現(xiàn)與學(xué)習(xí)型索引策略相似性能的方式，這種方式仍然使用了經(jīng)過長久測(cè)試和深入理解的 B-Tree。當(dāng)然，這些討論、對(duì)比實(shí)驗(yàn)和對(duì)進(jìn)一步研究的要求，正是谷歌/麻省理工學(xué)院團(tuán)隊(duì)為之激動(dòng)的理由，他們?cè)谡撐闹袑懙溃?/p>

「需要特別強(qiáng)調(diào)的是：我們并不是要呼吁完全用學(xué)習(xí)型索引結(jié)構(gòu)來替代傳統(tǒng)的索引結(jié)構(gòu)。相反的是，我們勾畫出了一個(gè)全新的索引構(gòu)建方法，它可以彌補(bǔ)現(xiàn)有工作的不足，甚至可以說是在已經(jīng)有數(shù)十年歷史的研究領(lǐng)域中打開了一個(gè)全新的研究方向�！�

那么，究竟是什么引起了人們?nèi)绱说年P(guān)注？哈希圖和 B-Trees（多路搜索樹）是否注定要被新技術(shù)所淘汰？機(jī)器是否即將重寫算法教科書？如果機(jī)器學(xué)習(xí)策略真的比我們所知道和喜愛的通用索引策略更好，那么它對(duì)計(jì)算機(jī)世界又意味著什么呢？學(xué)習(xí)型索引在什么情況下會(huì)超越舊的索引方式呢？

為了解決這些問題，我們需要理解什么索引，它們解決了什么問題以及是什么決定了不同索引之間的優(yōu)劣差異。

什么是索引

索引的核心是要提高信息查詢和檢索的便捷性。早在計(jì)算機(jī)發(fā)明之前，人類就一直在對(duì)事物進(jìn)行索引。當(dāng)我們使用整齊的文件柜時(shí)，我們使用的是一個(gè)索引系統(tǒng)。全卷百科全書可被視為一種索引策略，雜貨店里的標(biāo)簽過道也是一種索引。當(dāng)我們有許多東西并且需要在集合中找到或識(shí)別特定的物品時(shí)，索引可以讓我們查詢的過程變得更加高效便捷。

Zenodotus，亞歷山大大圖書館的第一任館員，負(fù)責(zé)組織管理圖書館龐大的館藏。他設(shè)計(jì)的系統(tǒng)包括按照流派將書籍分組放入房間，并按字母順序放置書本。他的同行 Callimachus 走得更遠(yuǎn)，引入了一個(gè)名為 pinakes 的中央目錄，它允許圖書管理員查找作者，并確定該作者的每本書在圖書館中的位置。包括 1876 年被發(fā)明的杜威十進(jìn)制系統(tǒng)（Dewey Decimal System）在內(nèi)，許許多多的圖書館索引構(gòu)建方式相繼被發(fā)明出來。

在亞歷山大圖書館，索引被用于將一段信息（書或作者的名字）映射到圖書館內(nèi)的物理位置。盡管我們的計(jì)算機(jī)是數(shù)字設(shè)備，但計(jì)算機(jī)中的任何特定數(shù)據(jù)實(shí)際上都駐留在至少一個(gè)物理位置。無論是文本、最近的信用卡交易記錄還是視頻，數(shù)據(jù)都存在于計(jì)算機(jī)上的某個(gè)物理磁盤位置。

在 RAM 和固態(tài)硬盤驅(qū)動(dòng)器中，數(shù)據(jù)作為電壓存儲(chǔ)在一系列晶體管中。在較老的旋轉(zhuǎn)硬盤驅(qū)動(dòng)器中，數(shù)據(jù)以磁盤格式存儲(chǔ)在磁盤的特定圓弧上。當(dāng)我們將計(jì)算機(jī)中的信息編入索引時(shí)，我們創(chuàng)建了一些算法，將部分?jǐn)?shù)據(jù)映射到計(jì)算機(jī)中的物理位置。我們稱這個(gè)地址為地址。在計(jì)算機(jī)中，被索引的信息全部都是以比特形式存在的數(shù)據(jù)，索引用于將這些數(shù)據(jù)映射到它們的地址。

數(shù)據(jù)庫是索引編制的典型用例。數(shù)據(jù)庫旨在保存大量信息，并且一般來說，我們希望高效地檢索這些信息。搜索引擎的核心是對(duì)互聯(lián)網(wǎng)上可用信息的龐大索引，哈希表、二叉搜索樹、字典樹、B-樹和布隆過濾器都是索引的形式。

很容易想象在亞歷山大圖書館的迷宮大廳找到具體書籍會(huì)有多難，但我們不應(yīng)該理所當(dāng)然地認(rèn)為人類產(chǎn)生數(shù)據(jù)的大小呈指數(shù)級(jí)增長�；ヂ�(lián)網(wǎng)上人們可以獲取到的數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超過任何時(shí)代的任何單個(gè)圖書館的容量，而谷歌的目標(biāo)是將所有數(shù)據(jù)都編入索引。人類為索引創(chuàng)造了許多策略，我們?cè)诒疚挠懻摿藲v史上最多產(chǎn)的數(shù)據(jù)結(jié)構(gòu)之一，并且恰好是一種索引結(jié)構(gòu)的哈希表。

什么是哈希表

初看起來，哈希表是基于哈希函數(shù)的簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)，我們有許多種行為不同并且被用于不同目的的哈希函數(shù)。在接下來的部分中，我們將只描述哈希表中使用的哈希函數(shù)，而不對(duì)加密哈希函數(shù)、校驗(yàn)和或任何其他類型的哈希函數(shù)展開討論。

哈希函數(shù)接受一些輸入值（例如數(shù)字或文本）并返回一個(gè)整數(shù)，我們稱之為哈希碼或哈希值。對(duì)于任何給定相同的輸入，哈希碼總是相同的，這意味著哈希函數(shù)必須是確定性的。

在構(gòu)建哈希表時(shí)，我們首先為哈希表分配一些空間（在內(nèi)存或磁盤中），我們可以視為創(chuàng)建一個(gè)任意大小的新數(shù)組。如果我們有很多數(shù)據(jù)，我們可能會(huì)使用較大的數(shù)組，如果我們只有少量數(shù)據(jù)，則可以使用更小的數(shù)組。任何時(shí)候我們想索引一個(gè)單獨(dú)的數(shù)據(jù)，就需要?jiǎng)?chuàng)建一個(gè)鍵值對(duì)，其中鍵（Key）是關(guān)于數(shù)據(jù)的一些標(biāo)識(shí)信息，而值（Value）是數(shù)據(jù)本身。

我們需要將值插入哈希表中，將數(shù)據(jù)的鍵發(fā)送給哈希函數(shù)。哈希函數(shù)返回一個(gè)整數(shù)（哈希碼），我們使用這個(gè)整數(shù)（以數(shù)組的大小為模）作為我們數(shù)組中數(shù)值的存儲(chǔ)索引。如果我們想從哈希表中檢索值，我們只需重新計(jì)算鍵中的哈希碼并從數(shù)組中的該位置獲取數(shù)據(jù)，這個(gè)位置就是我們數(shù)據(jù)的物理地址。

在使用杜威十進(jìn)制系統(tǒng)的圖書館中，「鍵」是書本所屬的一系列分類，「值」是書本身�！腹�希碼」是我們使用杜威十進(jìn)制過程創(chuàng)建的數(shù)值，例如一本解析幾何編碼得到了 516.3 的「哈希碼」，自然科學(xué)是 500、數(shù)學(xué)是 510、幾何是 516、解析幾何是 516.3。在這種方式下，杜威十進(jìn)制系統(tǒng)可以被視為書籍的哈希函數(shù)，然后這些書將被放在與其哈希值對(duì)應(yīng)的一組書架上，并按作者的字母順序排列在書架內(nèi)。

我們的比喻不是特別地完美，與杜威十進(jìn)制數(shù)字不同，哈希表中用于索引的哈希值通常不會(huì)提供信息——在完美的比喻中，圖書館目錄將包含每本書基于某一條相關(guān)信息的確切位置（可能是其標(biāo)題，也許是作者的姓氏，也許是它的 ISBN 號(hào)碼……），但除非所有具有相同鍵的書籍被放在同一個(gè)書架上，并且我們可以使用鍵在庫目錄中查找到書架編號(hào)，否則書籍的分組或排序就是沒有意義的。

從根本上來說，這個(gè)簡(jiǎn)單的過程全都是由哈希表來完成的。然而，為了確保哈希索引的正確性和效率，我們又在此基礎(chǔ)上構(gòu)建了許多復(fù)雜的部分。

基于哈希索引的性能考量

哈希表中復(fù)雜性和優(yōu)化的主要來源是哈希沖突（hash collisions）問題。當(dāng)兩個(gè)或更多個(gè)鍵產(chǎn)生相同的哈希碼時(shí)會(huì)發(fā)生沖突�？紤]如下的一個(gè)簡(jiǎn)單的哈希函數(shù)，我們假定其中的鍵為整數(shù)：

function hashFunction(key) {
  return (key * 13) % sizeOfArray; 
}

雖然任何唯一的整數(shù)在乘以 13 時(shí)會(huì)產(chǎn)生唯一的結(jié)果，但由于鴿巢原理（Pigeonhole principle），我們無法在每個(gè)桶只放一個(gè)物品的情況下將 6 個(gè)物品放入 5 個(gè)桶中，最終的哈希碼仍然會(huì)重復(fù)出現(xiàn)。因?yàn)槲覀兊拇鎯?chǔ)量是有限的，所以我們不得不使用哈希值來對(duì)數(shù)組的大小取模，因此我們總會(huì)遇到?jīng)_突。

我們馬上會(huì)討論處理這些不可避免的沖突時(shí)所采用的常用策略，但首先應(yīng)該注意的是，哈希函數(shù)的選擇可以增加或減少?zèng)_突的幾率。想象一下，我們總共有 16 個(gè)存儲(chǔ)位置，且必須從如下兩個(gè)函數(shù)中選擇一個(gè)作為哈希函數(shù)：

function hash_a(key) {
  return (13 * key) % 16;
}

function hash_b(key){
  return (4 * key) % 16;
}

在這種情況下，如果我們要對(duì)數(shù)字 0-32 進(jìn)行哈希，hash_b 會(huì)產(chǎn)生 28 個(gè)沖突或重疊。7 個(gè)沖突分別產(chǎn)生于哈希值 0、4、8 和 12（前四個(gè)插入不發(fā)生沖突，但是后面的每個(gè)插入都會(huì)發(fā)生沖突）。然而，hash_a 會(huì)平均分散沖突，每個(gè)索引沖突 1 次，總共碰撞 16 次。這是因?yàn)樵?hash_b 中，4 是哈希表大小 16 的一個(gè)因子，因?yàn)槲覀冊(cè)?hash_a 中選擇了一個(gè)素?cái)?shù)，除非我們的表大小是 13 的倍數(shù)，我們不會(huì)遇到選擇 hash_b 時(shí)的分組問題。

我們可以運(yùn)行下面的腳本來觀察這一過程：

function hash_a(key) {
  return (13 * key) % 16;
}

function hash_b(key){
  return (4 * key) % 16;
}

let table_a = Array(16).fill(0);
let table_b = Array(16).fill(0);

for(let i = 0; i < 32; i++) {
  let hash_code_a = hash_a(i);
  let hash_code_b = hash_b(i);

  table_a[hash_code_a] += 1;
  table_b[hash_code_b] += 1;
}

console.log(table_a); // [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
console.log(table_b); // [8,0,0,0,8,0,0,0,8,0,0,0,8,0,0,0]

好的哈希函數(shù)可以在表中更均勻地分布哈希碼間的沖突。

這種哈希策略，將輸入的鍵乘以素?cái)?shù)是一種非常常見的做法。質(zhì)數(shù)減少了輸出哈希碼與數(shù)組大小共有一個(gè)公因式的可能性，從而減少了碰撞發(fā)生的可能。由于哈希表已經(jīng)存在了相當(dāng)長的一段時(shí)間，因此有很多不同種類的優(yōu)秀哈希函數(shù)可供選擇。

乘法移位哈希（Multiply-shift hashing）與 素?cái)?shù)取模策略類似，但避免了相對(duì)昂貴的模運(yùn)算，有利于快速進(jìn)行移位操作。MurmurHash 和 Tabulation Hashing 是乘法移位哈希函數(shù)家族的強(qiáng)力替代品。對(duì)這些哈希函數(shù)進(jìn)行的基準(zhǔn)測(cè)試包括檢查它們的計(jì)算速度，生成的哈希碼的分布以及它們處理不同類型數(shù)據(jù)（例如除整數(shù)以外的字符串和浮點(diǎn)數(shù)）的靈活性。

如果我們選擇一個(gè)好的哈希函數(shù)，我們可以降低沖突率并且仍然保持較高的計(jì)算速度。不幸的是，無論我們選擇什么哈希函數(shù)，沖突總是難以避免的，決定如何處理沖突將對(duì)我們哈希表的整體性能產(chǎn)生重大影響。碰撞處理的兩個(gè)常用策略是鏈接（Chaining）和線性探測(cè)（Linear Probing）。

鏈接簡(jiǎn)單易用，我們不是在哈希表的每個(gè)索引處存儲(chǔ)每個(gè)條目，而是存儲(chǔ)鏈表的頭部指針。當(dāng)一個(gè)條目通過我們的哈希函數(shù)與一個(gè)已經(jīng)填充的索引相沖突時(shí)，我們將它添加為鏈表中的最后一個(gè)元素。查找不再是嚴(yán)格的「常數(shù)項(xiàng)時(shí)間」，因?yàn)槲覀儽仨毐闅v鏈表來查找特定項(xiàng)目。如果我們的哈希函數(shù)存在很多沖突，我們將會(huì)有很長的鏈。此外，由于對(duì)于長鏈的查找，哈希表的性能會(huì)隨著時(shí)間的推移而降低。

鏈接：重復(fù)的沖突會(huì)創(chuàng)建更長的鏈接列表，但不會(huì)占用數(shù)組的其它索引。

線性探測(cè)在概念上很簡(jiǎn)單，但實(shí)現(xiàn)起來還是很麻煩的。在線性探測(cè)中，我們?nèi)匀粸槊總�(gè)元素在哈希表保留一個(gè)索引。當(dāng)索引 i 發(fā)生沖突時(shí)，我們檢查索引 i + 1 是否為空，如果是，我們將數(shù)據(jù)存儲(chǔ)在那里，如果 i + 1 也有一個(gè)元素，我們檢查 i + 2，然后 i + 3 等，直到找到一個(gè)空插槽。只要我們找到一個(gè)空插槽，我們就將該值插入。相似地，我們可能無法實(shí)現(xiàn)常數(shù)級(jí)時(shí)間復(fù)雜度的查找，并且如果在一個(gè)索引中遇到多個(gè)沖突，那么我們最終將不得不搜索一系列長序列，然后才能找到要查找的條目。更重要的是，每當(dāng)沖突發(fā)生時(shí)，后續(xù)發(fā)生沖突的幾率都會(huì)增加。因?yàn)榕c鏈接不同，每個(gè)傳入的項(xiàng)目最終會(huì)都占據(jù)一個(gè)新的索引。

線性探測(cè)：給定與上面鏈接圖像相同的數(shù)據(jù)和哈希函數(shù)，我們得到一個(gè)新的結(jié)果。導(dǎo)致沖突的元素（紅色）現(xiàn)在駐留在同一個(gè)數(shù)組中，并從沖突索引開始按順序占據(jù)索引。

可能聽起來鏈接是更好的選擇，但線性探測(cè)往往被認(rèn)為具有更好的性能特征。大多數(shù)情況下，這是由于鏈表的緩存利用率較差以及使用數(shù)組有利于提高緩存利用率。簡(jiǎn)答來說，檢查鏈表中的所有鏈接比檢查相同大小數(shù)組的所有索引要慢得多。這是因?yàn)槊總�(gè)數(shù)組中的索引在物理上相鄰，而在鏈表中，每個(gè)新節(jié)點(diǎn)在創(chuàng)建時(shí)都會(huì)被賦予一個(gè)位置。這個(gè)新節(jié)點(diǎn)不一定與鏈表中的相鄰節(jié)點(diǎn)在物理上相鄰。其結(jié)果是，在鏈表中，列表順序中「彼此相鄰」的節(jié)點(diǎn)在 RAM 芯片內(nèi)的物理位置上并不實(shí)際相鄰。由于 CPU 高速緩存的工作原理，訪問相鄰內(nèi)存位置的速度很快，而隨機(jī)訪問內(nèi)存位置的速度則要慢得多。

機(jī)器學(xué)習(xí)基礎(chǔ)

為了理解機(jī)器學(xué)習(xí)是如何重建哈希表（和其他索引）的關(guān)鍵特征的，有必要快速重新審視一下統(tǒng)計(jì)模型的主要思想。在統(tǒng)計(jì)學(xué)中，模型是可以接受一些向量為輸入并返回標(biāo)簽（分類模型）或數(shù)據(jù)值（回歸模型）的函數(shù)。輸入向量包含所有數(shù)據(jù)點(diǎn)的相關(guān)信息，輸出的標(biāo)簽或數(shù)據(jù)是模型的預(yù)測(cè)值。

在預(yù)測(cè)高校學(xué)生能否進(jìn)入哈佛學(xué)習(xí)的模型中，輸入向量可能包含學(xué)生的 GPA、SAT 成績(jī)、參加的課外俱樂部的數(shù)量以及其他與學(xué)術(shù)成就相關(guān)的值；輸出的標(biāo)簽可以是 True 或 False（可以進(jìn)入哈佛或不可以進(jìn)入哈佛）。

在預(yù)測(cè)抵押貸款違約率的模型中，輸入向量可能包含信用值、信用卡賬戶數(shù)量、逾期付款頻率、年收入以及與申請(qǐng)抵押人財(cái)務(wù)狀況相關(guān)的其他值，該模型會(huì)返回一個(gè) 0 到 1 范圍內(nèi)的數(shù)字代表違約的可能性。

一般而言，可以用機(jī)器學(xué)習(xí)建立統(tǒng)計(jì)學(xué)模型。機(jī)器學(xué)習(xí)從業(yè)者將大量數(shù)據(jù)和機(jī)器學(xué)習(xí)算法相結(jié)合，在數(shù)據(jù)集上運(yùn)行算法得到的結(jié)果是訓(xùn)練好的模型。機(jī)器學(xué)習(xí)的核心在于創(chuàng)造可以自動(dòng)從原始數(shù)據(jù)中建立準(zhǔn)確模型的算法，該算法無需人工幫助機(jī)器「理解」這些數(shù)據(jù)實(shí)際上表示什么。這與其他形式的人工智能，如人類廣泛考察數(shù)據(jù)、告訴計(jì)算機(jī)這些數(shù)據(jù)的意義（如定義啟發(fā)式）以及定義計(jì)算機(jī)如何使用這些數(shù)據(jù)（如使用極小極大算法或 A* 尋路算法）是不同的。盡管在實(shí)踐中，機(jī)器學(xué)習(xí)常常和經(jīng)典的非學(xué)習(xí)技術(shù)相結(jié)合；AI 智能體一般會(huì)同時(shí)使用學(xué)習(xí)和非學(xué)習(xí)策略以完成目標(biāo)。

以著名的 AI 象棋棋手「深藍(lán)」和最近廣受關(guān)注的 AI 圍棋棋手「AlphaGo」為例。深藍(lán)是完全的非學(xué)習(xí) AI；程序員和象棋專家合作為深藍(lán)創(chuàng)建了一個(gè)函數(shù)，該函數(shù)以棋局狀態(tài)為輸入（所有棋子的位置以及棋手的回合），返回的值與該位置有多「好」相關(guān)。深藍(lán)從不「學(xué)習(xí)」任何東西——人類棋手編寫了機(jī)器的評(píng)估函數(shù)。深藍(lán)的主要特征是樹搜索算法，該算法計(jì)算了所有可能的落子處、以及對(duì)手對(duì)這些落子方法可能做出的回應(yīng)以及未來可能會(huì)產(chǎn)生的移動(dòng)。

AlphaGo 樹搜索的可視化。（來源：https://blogs.loc.gov/maps/category/game-theory/）

AlphaGo 執(zhí)行的也是樹搜索。與深藍(lán)的相似之處在于，AlphaGo 預(yù)測(cè)了可能的每一步之后的好幾步，而不同點(diǎn)在于 AlphaGo 在沒有圍棋專家明確指導(dǎo)的情況下建立了其自己的評(píng)估函數(shù)。在這種情況中，評(píng)估函數(shù)是一個(gè)訓(xùn)練好的模型。AlphaGo 的機(jī)器學(xué)習(xí)算法將棋盤狀態(tài)（每一個(gè)位置是黑子、白子還是沒有棋子）作為輸入向量，標(biāo)簽表示了哪一方的棋手（白棋或黑棋）會(huì)贏。使用這些信息，機(jī)器學(xué)習(xí)算法在數(shù)十萬種游戲中都可以確定該如何評(píng)估當(dāng)前狀態(tài)。AlphaGo 通過觀察數(shù)以百萬的例子教會(huì)自己在哪落子贏得游戲的可能性更高。

將模型作為索引，背離 ML 范式

谷歌的研究人員首先在他們的文章中提出索引是模型的前提，或者說至少可以將機(jī)器學(xué)習(xí)模型當(dāng)索引用。理由是：模型是接受一些輸入，然后返回一個(gè)標(biāo)簽的機(jī)器；如果輸入是關(guān)鍵詞，而標(biāo)簽是模型對(duì)內(nèi)存地址的判斷，模型就可以當(dāng)索引用。盡管聽起來很清晰明了，但是索引的問題似乎不能完美契合于機(jī)器學(xué)習(xí)。在一些領(lǐng)域中，谷歌團(tuán)隊(duì)已經(jīng)離開了機(jī)器學(xué)習(xí)范式以實(shí)現(xiàn)他們自己的目標(biāo)。

一般情況下，機(jī)器學(xué)習(xí)模型是在已知數(shù)據(jù)上訓(xùn)練，目標(biāo)是評(píng)估沒見到的數(shù)據(jù)。若我們對(duì)數(shù)據(jù)進(jìn)行索引，就沒法接受評(píng)估值。索引唯一的用處在于得到內(nèi)存中一些數(shù)據(jù)的確切定位。一個(gè)箱子外的神經(jīng)網(wǎng)絡(luò)（或其他機(jī)器學(xué)習(xí)器）無法精確到這種程度。谷歌通過在訓(xùn)練過程中追蹤最大（正）和最小（負(fù)）誤差以解決這個(gè)問題。將這些值作為邊界，ML 索引可以在界限內(nèi)進(jìn)行搜索，找到元素的確切位置。

另一個(gè)出發(fā)點(diǎn)是機(jī)器學(xué)習(xí)從業(yè)者一般都要小心避免他們的模型對(duì)訓(xùn)練數(shù)據(jù)「過擬合」；一個(gè)「過擬合」模型會(huì)在訓(xùn)練數(shù)據(jù)上產(chǎn)生很高的預(yù)測(cè)準(zhǔn)確率，但在訓(xùn)練集以外的數(shù)據(jù)上表現(xiàn)得很糟糕。另一方面，從定義上講，索引是過度擬合的。訓(xùn)練集是被索引過的數(shù)據(jù)，這也使其成為測(cè)試集。由于查找必須發(fā)生在索引的實(shí)際數(shù)據(jù)上，在這種機(jī)器學(xué)習(xí)的應(yīng)用上更容易遇到過擬合的問題。同時(shí)，如果模型已經(jīng)對(duì)現(xiàn)有數(shù)據(jù)過擬合了，再向索引添加項(xiàng)目可能會(huì)在預(yù)測(cè)時(shí)造成可怕的錯(cuò)誤；正如文章中所述：

「在這個(gè)模型的普遍性和『最后一英里』的表現(xiàn)間發(fā)生了有趣的取舍；可以這么說，『最后一英里』的預(yù)測(cè)結(jié)果越好，模型的過擬合就越嚴(yán)重，就越不適用于新的數(shù)據(jù)項(xiàng)目�！�

最后，一般而言，模型的訓(xùn)練過程是整個(gè)過程中最昂貴的部分。不幸的是，在廣泛的數(shù)據(jù)庫應(yīng)用程序（和其他索引應(yīng)用程序）中，將數(shù)據(jù)添加到索引中是很常見的。該團(tuán)隊(duì)坦言這方面的限制：

「迄今為止，我們的結(jié)果都將注意力集中在只讀存儲(chǔ)區(qū)數(shù)據(jù)庫系統(tǒng)的索引結(jié)構(gòu)上。正如我們已經(jīng)指出的那樣，目前的設(shè)計(jì)，即使沒有任何重大的修改，也已經(jīng)可以替換現(xiàn)在的數(shù)據(jù)庫中的索引結(jié)構(gòu)了——前者的索引結(jié)構(gòu)可能每天只更新一次，而后者則需要在合并 SSTable 的過程中批量創(chuàng)建 B-樹�！埂�—（SSTable 是谷歌的「BigTable」的重要元件）

學(xué)習(xí)哈希

本文研究了使用機(jī)器學(xué)習(xí)模型代替標(biāo)準(zhǔn)哈希函數(shù)的可能性。研究人員們想要了解的問題之一是：了解數(shù)據(jù)的分布可以幫助我們更好地創(chuàng)建索引嗎？用我們之前討論過的傳統(tǒng)的策略（移位乘法、Murmur Hash、素?cái)?shù)乘法……），完全忽略了數(shù)據(jù)的分布。每一個(gè)傳入的項(xiàng)目都被視為獨(dú)立的值，而非作為具有數(shù)值屬性的較大數(shù)據(jù)集的一部分考慮的。結(jié)果是，即使在很多先進(jìn)的哈希表中，也存在大量空間浪費(fèi)的問題。

實(shí)現(xiàn)哈希表的內(nèi)存利用率只有約 50%，這意味著哈希表占用了數(shù)據(jù)存儲(chǔ)實(shí)際所需空間的兩倍。也就是說，當(dāng)我們存儲(chǔ)與數(shù)組中存儲(chǔ)數(shù)量一樣多的項(xiàng)時(shí)，有一半的地址是空的。用機(jī)器學(xué)習(xí)模型替換標(biāo)準(zhǔn)哈希表中的哈希函數(shù)，研究人員發(fā)現(xiàn)浪費(fèi)的空間顯著減少了。

這并非特別令人意外的結(jié)果：通過在輸入數(shù)據(jù)上進(jìn)行訓(xùn)練，學(xué)習(xí)到的哈希函數(shù)可以在一些空間更均勻地分布數(shù)值，因?yàn)?ML 模型已經(jīng)知道了數(shù)據(jù)的分布！這是一種強(qiáng)有力的、可以顯著減少基于哈希的索引所需存儲(chǔ)量的方式。相應(yīng)的也有一些限制：ML 模型比我們上面所述的標(biāo)準(zhǔn)哈希函數(shù)計(jì)算得要慢一些，而且需要訓(xùn)練，但標(biāo)準(zhǔn)哈希函數(shù)不需要。

也許可以將基于哈希函數(shù)的 ML 用于關(guān)鍵在于有效的內(nèi)存使用的情況，但是在這些情況中計(jì)算能力不再是瓶頸。谷歌和麻省理工的研究團(tuán)隊(duì)認(rèn)為數(shù)據(jù)庫就是一個(gè)很好的例子，因?yàn)樗饕�在很昂貴的過程中每天重建一次；使用更多的計(jì)算時(shí)間以達(dá)到顯著的節(jié)省內(nèi)存的目的，這對(duì)許多數(shù)據(jù)庫環(huán)境而言都是一場(chǎng)勝利。

但在此還是要有一個(gè)超展開，接下來進(jìn)入布谷鳥哈希。

布谷鳥哈希（Cuckoo Hashing）

布谷鳥哈希發(fā)明于 2001 年，以布谷鳥類的名字命名。布谷鳥哈希是用鏈接技術(shù)和線性探測(cè)處理哈希沖突的替代（而非哈希函數(shù)的替代）。該策略一如其名，因?yàn)槟承┎脊萨B種類中，準(zhǔn)備產(chǎn)卵的雌鳥會(huì)找到一個(gè)有主的巢，并將巢里的蛋挪出去，然后把自己的蛋下在里面。在布谷鳥哈希中，傳入的數(shù)據(jù)會(huì)竊取舊數(shù)據(jù)的地址，就像布谷鳥會(huì)竊取別的鳥類的巢一樣。

工作原理如下：當(dāng)創(chuàng)建哈希表時(shí)將表分為兩個(gè)空間，將這兩個(gè)空間分別稱為主地址空間和次地址空間。之后，分別初始化兩個(gè)哈希函數(shù)，每一個(gè)函數(shù)分配給一個(gè)地址空間。這些哈希函數(shù)有可能非常相似——例如它們可能都屬于「素?cái)?shù)乘法」，其中每個(gè)哈希函數(shù)都會(huì)使用不同的素?cái)?shù)。將這兩個(gè)函數(shù)稱為主哈希函數(shù)和次哈希函數(shù)。

最初，插入布谷鳥哈希只會(huì)利用主哈希函數(shù)和主地址空間。當(dāng)哈希沖突發(fā)生時(shí)，新數(shù)據(jù)會(huì)驅(qū)逐舊數(shù)據(jù)，然后用次哈希函數(shù)對(duì)舊數(shù)據(jù)進(jìn)行哈希，并將其放入次地址空間中。

用于哈希沖突的布谷鳥哈希：黃色數(shù)據(jù)驅(qū)逐綠色數(shù)據(jù)，綠色數(shù)據(jù)在第二地址空間找到了新家（在次要空間頂部索引的淡綠色圓點(diǎn)）。

如果該次要地址已經(jīng)被占用，則會(huì)再一次進(jìn)行驅(qū)逐，在次要空間的數(shù)據(jù)會(huì)被發(fā)送回主要地址空間。因?yàn)橛锌赡茉斐蔁o限循環(huán)的驅(qū)逐，一般而言會(huì)設(shè)置一個(gè)每次插入驅(qū)逐的閾值；如果驅(qū)逐次數(shù)到達(dá)閾值，就會(huì)重建哈希表，重建過程可能包括為該表分配更多空間或是選擇新的哈希函數(shù)。

二次驅(qū)逐（Double eviction）：傳入的黃色圓點(diǎn)驅(qū)逐了綠色的，綠色的驅(qū)逐紅色的，紅色圓點(diǎn)在主地址空間找到了歸宿（淡紅色圓點(diǎn)）。

眾所周知，這種策略在內(nèi)存受限的情況下是非常有效的。所謂「二次冪（power of two choices）」就允許布谷鳥哈希即便在高利用率的情況下也有很穩(wěn)定的表現(xiàn)（這在鏈接技術(shù)或線性探索中是不會(huì)出現(xiàn)的）。

Bails 和他在斯坦福的研究團(tuán)隊(duì)發(fā)現(xiàn)，只要進(jìn)行適當(dāng)優(yōu)化，布谷鳥哈�？梢苑浅？�，即使在利用率高達(dá) 99% 的情況下，也能有不錯(cuò)的表現(xiàn)（http://dawn.cs.stanford.edu/2018/01/11/index-baselines/）。從本質(zhì)上講，布谷鳥哈希通過利用二次冪可以在無需昂貴訓(xùn)練階段的情況下實(shí)現(xiàn)「機(jī)器學(xué)習(xí)」的高度利用。

索引的下一步是什么？

最終，每個(gè)人都對(duì)學(xué)習(xí)索引結(jié)構(gòu)的潛力感到興奮。隨著更多 ML 工具的廣泛應(yīng)用，以及像 TPU 這樣硬件的進(jìn)步使得機(jī)器學(xué)習(xí)工作負(fù)載更快，索引可以從機(jī)器學(xué)習(xí)策略中受益良多。與此同時(shí)，像布谷鳥哈希（cuckoo hashing）這樣漂亮的算法提醒我們，機(jī)器學(xué)習(xí)并不是萬能的。融合了具有令人難以置信的力量的機(jī)器學(xué)習(xí)技術(shù)和像「二次冪」這樣的舊理論的工作將繼續(xù)推動(dòng)計(jì)算機(jī)效率和能力的界限。

看起來，索引的基本原理不會(huì)一夜之間就被機(jī)器學(xué)習(xí)策略替代，但是自微調(diào)索引的想法是強(qiáng)大而令人興奮的概念。隨著我們?cè)絹碓缴朴脵C(jī)器學(xué)習(xí)，以及在提升計(jì)算機(jī)處理機(jī)器學(xué)習(xí)工作負(fù)載的效率上做出的不斷的努力，利用這些優(yōu)勢(shì)的新想法肯定會(huì)找到其主流用途。下一代 DynamoDB 或 Cassandra 可能也會(huì)很好地利用機(jī)器學(xué)習(xí)策略；日后 PostgreSQL 或 MySQL 的應(yīng)用也會(huì)采用這樣的策略。最終，這都取決于未來研究所能取得的成就，這些成就會(huì)繼續(xù)建立在最先進(jìn)的非線性策略和「AI 革命」的尖端技術(shù)上。

出于必要性的考慮，本文簡(jiǎn)化了許多細(xì)節(jié)。想要了解更多細(xì)節(jié)的讀者請(qǐng)參閱：

• The Case For Learned Indexes (Google/MIT) (https://www.arxiv-vanity.com/papers/1712.01208/)
• Don’t Throw Out Your Algorithms Book Just Yet: Classical Data Structures That Can Outperform Learned Indexes (Stanford) (http://dawn.cs.stanford.edu/2018/01/11/index-baselines/)
• A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing (https://bigdata.uni-saarland.de/publications/p249-richter.pdf) (Saarland University)

 

來自：http://www.itsiwei.com/22294.html

 

標(biāo)簽： Google Mysql 大數(shù)據(jù) 谷歌 互聯(lián)網(wǎng) 腳本 數(shù)據(jù)庫 搜索 搜索引擎 網(wǎng)絡(luò)

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。