《NoSQL權威指南》——2.1 列式資料庫的曆史

本節書摘來自異步社群出版社《nosql權威指南》一書中的第2章，第2.1節，作者：【美】joe celko（喬•塞科） ，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

列式存儲以及倒排或不按順序存儲檔案的方式并不是最新提出的。taxir是1969年為生物學建立的第一個列式資料庫存儲系統。加拿大統計局于1976年實作了rapid系統，并将其用于加拿大人口和住房普查資料的處理和檢索，以及其他與統計相關的一些應用。rapid被拿來與世界各地的其他統計機構共享，并在20世紀80年代被廣泛使用。直到20世紀90年代，它一直被加拿大統計局使用。

多年來，sybase iq是市面上唯一一個可以商用的列式dbms。然而，當olap（online analytical processing，聯機分析處理）越來越流行後，其他産品廠商看到，可以将某些用于多元資料集和彙總的技術應用到更通用的資料庫上。

由于一個列隻有一種簡單的資料類型，可以做很大程度的壓縮。如果需要重建行，必須打破單一資料集模型并且為行進行編号，就像在一個順序檔案中所做的一樣。每一行是通過檢查該行行号進行重構的。具有相同的資料值的連續行号可以按範圍模組化：<code>{start_position, end_position,data_value}</code>。這是最簡單的壓縮格式，但也是非常強大的。很多資料以離散值進行編碼，是以在同一列中常常會有大量相同的值。

然後，我們可以針對特定領域和所用的資料類型，使用内置的專門例程對資料值進行壓縮。如果有某個域占用與資料值相同或者比資料值更大的空間，這就是很愚蠢的做法，而成本也随之（資料列更大）而來（占用了更多的空間，同時也降低了效率）。使用短記号為較長值建構查找表是很容易的，參考<code>{domain_token, data_value}</code>，現在模型變為<code>{start_position, end_position, domain_token}</code>。

例如，美國的電話号碼中區号使用的正規表達式是<code>[2-9][0-9][0-9]</code>，這意味着我們至多可以有800個區号。代替這3個ascii字元，可以用smallint或bcd[1]來生成記号，并得到一個小的查找表。這個例子并沒有獲得很大的節省，但就是這樣的小資料逐漸增加，形成了tb級資料庫。另一個更有力的例子是美國城市和城鎮的名字，截至2012年，美國大約有超過30 000個城市和城鎮。2位元組的整數可以存儲65 535個記号。很少有名字隻有兩個字母的城市，其中還有不少名字是重複的，如美伊利諾斯州首府斯普林菲爾德是最常見的小鎮的名字，這也是這個名字常常用在電視節目（如《辛普森一家》）中的原因。同樣，一個2位元組的整數大概可以表示180年内的日期[2]。

這也為我們提供了能夠加入一定的完整性限制的獨立環節。例如，666和777是有效的區号，但截至2012年還被沒有被配置設定使用。同樣，在電影中看到的555是不存在的電話區号。撥号前的klondike 5[3]是用來保證（表示）的電話号碼不能被呼叫的。在美國老電影、卡通片以及現代美國電視節目中都回聽到這個區号。我們可以在查找表中簡單地将這些無效的值去掉！

各種形式的文本壓縮方式是衆所周知的。對于資料庫的資料來講，我們希望壓縮是無損的，這也就意味着，當我們解壓的時候，得到的内容與壓縮前的内容是完全一緻的。在音樂和視訊中，為了速度和空間，在不傷及内容的情況下可以犧牲一些品質。lempel-ziv（lz）壓縮方式是無損存儲中最流行的算法。deflate[4]是針對解壓縮速度和壓縮率而優化的lz的變體，但壓縮速度可能會很慢。deflate用于pkzip、gzip和png等。lzw（lempel-ziv-welch）用于gif圖檔。另外，值得注意的是lzr（lz-renau）方法，它是zip方法的基礎。

lz方法使用重複字元串的替換表，表本身往往是霍夫曼編碼的（如shri、lzx）。這種方法非常适用于人類語言的壓縮，因為文法詞綴和結構詞（介詞、連詞、冠詞、小标記等）構成了大量的文本。但編碼方案也傾向于遵循模式（pattern）。在美國，銀行賬号以美國銀行家協會銀行編号的代碼開始的，産品序列号中會包括産品線等内容。分層和矢量編碼方案采用了這種壓縮方式。

近幾年，已經用最小完美雜湊演算法[5]做了大量的工作（如果還不太了解這一技術，請參見“散列快速入門”）。當列是一組相對靜态的字元串時，這種方式是最理想的。任何值的集合，甚至那些沒有共同子串的值，被散列成短的、固定長度的、能夠被更快地進行計算的資料記号。

對這種模型比較幼稚的看法是，它是複雜的、大的、緩慢的。這隻說對了一半。與簡單的順序字段讀取相比，它的确是複雜的，但是它并不慢，而且也不大。

有一個觀點是計算機處理單元（cpu）是瓶頸，但随後的smp（對稱多處理）、群集和mpp（大規模并行處理）技術讓我們獲得了數百或數千倍的cpu，可以比以往任何時候的運作速度都快。有點兒it民俗意味的摩爾定律[6]（moore’s law）認為每18個月計算機處理速度就會提升一倍，成本會降為之前的一半。但與此同時，資料量也越來越大。10年前，20 gb就被認為是無法控制的了，現在小型網際網路創業公司已經開始管理tb級的資料。

mpp使用許多獨立的cpu并行地運作同一個程式。mpp與smp類似，但在smp中，所有cpu共享相同的記憶體，而在mpp系統中，每個cpu都有自己的記憶體。

需要權衡考慮的是，mpp系統中更難程式設計，因為處理器必須互相通信并互相協調。另一方面，smp系統在所有cpu試圖在同時通路相同的記憶體位置時會發生阻塞。然而，這些cpu常常會發生閑置。這是由于cpu的l1、l2（尤其是l2）緩存目前缺少快速支撐大吞吐量資料的能力。在基于行的資料模型中，我們依然需要在cpu和存儲間移動整條記錄。

打一個比方，如個人電子産品，如果你隻想從專輯購買幾首曲目，在itunes中隻購買這幾首曲目會很便宜。當你最想要專輯中大多數曲目，購買整張專輯會更加省錢和省時間，盡管你隻播放其中的一些曲目。而“查詢”與“搜尋并檢索”是不一樣的問題。一條查詢要麼需要某個列要麼不需要，并且在做查詢編譯時就可以知道需要哪些列，不需要哪些列。得益于現代處理器的速度和大型儲存設備，把資料組裝成行的方式在速度上遠遠快于從轉動的磁盤中讀單個位元組的速度。2012年，ibm已經能夠将db2中的表的大小減為原始表的1/3或更小。由于<code>{domain_token, data_value}</code>這樣的資料就是全部要讀的資料，這種空間的節省帶來很多回報，現在可以把資料放在更快的存儲器上，如固态硬碟（ssd）。

列式存儲和基于行的存儲（資料庫）之間的顯著不同的是，一個表中所有的列都不會存儲在資料頁中。這避免了存儲在資料頁上的大量的中繼資料。這些中繼資料因産品不同而各異，但是最常見的中繼資料是每個資料頁中的行（記錄）相對起始位置的位移以及可能一些其他關于資料頁的中繼資料。在這些中繼資料中還有每一行中的每一列相較起始位置的位移，以及這一列的值是否是null。這就是sql資料管理系統獲知在磁盤何處放置讀寫磁頭并傳回哪些資料的方式。

特别是，在早期的sql産品中向行中加入一個<code>varchar(n)</code>列時，它們将按<code>create table</code>語句中列的順序配置設定。不過，這也意味着這些列<code>（這裡特指varchar(n)的列）</code>将為全部n個字元配置設定存儲，即便實際存儲的資料很短（例如，實際的資料長度小于n的情況）。我們曾經使用的方案是手動地将所有的<code>varchar(n)</code>列放到ddl語句中的尾部。目前，db2和oracle已經在産品内部實作—在輸出時對列進行重新排列，并且對使用者隐藏這些細節。

列式資料庫模型可以就地（或在适當的位置）壓縮資料，或者對指向字元串清單的指針進行存儲。例如，<code>first_name</code>與查找表<code>{1 = aaron, 2 = abe,3 = albert, …, 9999 = zebadiah, …}</code>對應。但是現在可以做一個折中，我們仍然可以将<code>varchar(n)</code>存儲為固定長度，以加快搜尋，但卻并不會受到太大影響，這是因為查找表很小，查找表中的每個值隻出現一次，是以我們還是會有相對較小的存儲量。

顯然，随着在資料頁上插入記錄或删除記錄，這些中繼資料映射必須被更新。删除是很容易的，被删除的行可以立即被打上标記并在列被讀取時被忽略。插入的新資料可以被添加到列結構的末端。盡管這種方式運作起來沒問題，但最好仍然是将相關的資料做成叢集[7]，以保持資料規模很小，并使資料值更容易搜尋。有實用程式來恢複（還原）存儲—其他記憶體管理系統的垃圾收集程式的列式資料庫版本。

列式資料庫也可以有索引，但實際上大多數沒有。事實上，列式存儲本身就是索引。位移也必須通過索引來處理。

散列快速浏覽

索引和指針鍊涉及本地資料的實體搜尋、查找。給定一個需要搜尋的鍵，可以從指針鍊中的一個節點周遊到另一個節點，直到找到與搜尋值對應的節點，或發現這個節點不存在。

散列是以數學為基礎的磁盤通路技術。先定義好搜尋鍵，然後把它放入公式中，公式會傳回一個數組或查找表的位置。該位置包含實體存儲位址，可以直接去通路它通過一次磁盤通路來找到該資料。

對于量較大的資料，散列比索引快得多。随着資料量的增加樹形結構的索引會變得更深。在樹中查找資料需要周遊，直至最終找到一個葉子結點滿足查詢條件。這可能意味着資料量大的情況下需要更多的磁盤通路。

兩個或多個不同的搜尋鍵會産生相同的散列鍵的情況是可能的，這就是所謂的沖突或（更文雅地說）散列碰撞。這種情況下，搜尋鍵可以使用另一個函數重新進行散列，第二個函數常常是與第一個散列函數同族的函數，但是與第一個函數相比，會在一些常量上有所變化。有證據證明，某些散列函數最多5次重新進行散列計算，就會産生獨一無二的結果。

沒有沖突的散列函數稱為完美的散列函數。如果散列函數在數組中沒有空插槽，那麼它就是最小的。一個最小完美散列函數需要滿足：搜尋值的集合是固定的，以便散列函數可以作用于編譯器和類似的資料集中的關鍵字。

大多數雜湊演算法的基本工具如下。

數字化挑選。給定一個搜尋鍵，從數中提取一些數字，也許會對這些數字重

新排列。如果能夠做到随機分布，就是一項很好的技術。事實上，這種方法被百貨公司用在訂貨視窗上，使用姓氏的第一個字母對某些字母進行分類（s代表史密斯，j代表瓊斯、約翰遜等，但幾乎沒有人會用到x、y和z）。但是，客戶的電話号碼的最後兩位數字是随機地均勻分布。

除法。配有一個素數（m）的mod（&lt;鍵&gt;，m）函數應該是非常好的散列函數（lum et al.，1971）。它會給出(0, (m − 1))區間内的結果。total和image/3000資料庫[8]中會内置一系列大素數用來配置設定散清單。

乘法。這種技術是對一個鍵做平方，然後取出中間的數字。5位數的鍵将産生一個10位數字的平方，使用中間3位會具有良好的效果。例如，54 3212=2 950 771 041，中間的數字是077作為散列。散列必須來自中間的數字，否則可能會得到太多的聚類（即重複的結果）。

折疊。這種技術取出n個數字的連續子集，并簡單地将它們進行相加。例如，給定一個5位數的鍵，可以将所有5個數字相加，就獲得了在範圍（0≤散列值≤45）的結果。如果使用雙數[9]，那麼得到的範圍将是（0≤散列值≤207）。這是一個很弱的技術，是以往往不會使用，或是被用來代替某些算法并且一般與另一種技術結合使用。

沖突解決技術也是多種多樣的，最常見的一種是使用桶（bucket）。一個桶代表可容納多個值的散清單的位置。下面是兩種基本的方法。

開放尋址。這種方法試圖在散清單中找到仍處于打開狀态的桶。最簡單的方式是從沖突的位置開始，并且将此點作為起點對開放空間進行位址遞增式的線性搜尋。其他類似的技術使用了比位址遞增方式更加複雜的函數。常用的函數是使用二次方程式和僞随機數生成器。

外部鍊。可以将新的值添加到一個連結清單中，這個連結清單可能是存儲在主存中或部分存儲在磁盤上。但是在正确選擇主存表的大小的情況下，溢出到磁盤的資料可以控制在主存中散清單大小的15%以下。這種方法是非常有效的。