[[429518]]

在計算機領域，有一個有趣的趨勢，往系統(tǒng)中寫入數(shù)據需要做更多的工作。我們需要對數(shù)據進行重新組織、合并、重新建立數(shù)據庫索引等操作，才能使寫入的內容更加有用。如果不這樣做，必須實現(xiàn)內容搜索或其他工作來支持未來的數(shù)據讀取。

數(shù)據庫中的索引

我關系數(shù)據庫的索引是個有趣而令人困惑的概念，索引如何在對應用程序透明的情況下優(yōu)化訪問的呢?當然，更新索引意味著另外的磁盤訪問，因為 b + 樹的索引不適合放在內存中。如果以后讀取數(shù)據，那么對數(shù)據庫進行更改的額外工作是值得的。

下一個令人困惑的問題是，應該編制多少索引?是否應該對每一列都建立索引?什么時候應該把一列數(shù)據編入索引?我索引越多，讀取查詢就會變得越快。同時，索引越多，數(shù)據更新的速度就越慢。

這是一個常見的權衡方案，快速讀意味著慢速寫。

行存儲與列存儲

將高性能更新與行存儲聯(lián)系起來是很自然的，如果按列組織數(shù)據的話，因為具有相同值的許多邏輯行在物理上彼此相近，柱狀數(shù)據庫執(zhí)行查詢的速度非常快。但是，更新列存儲就不那么容易了。

通常，行存儲中的更新單獨保存，因為每一行的數(shù)據較小，查詢會以相對快速的方式檢查行。這些查詢與更快的列存儲的結果相結合，以提供統(tǒng)一的準確結果。新的行存儲更新會定期與列存儲合并，以創(chuàng)建新的列存儲，這可以以類似于 LSM 樹中合并的級聯(lián)方式完成。

當插入到一個列存儲區(qū)中時，這種重寫和整合新數(shù)據的負擔是一種寫入數(shù)據放大的形式，在這種形式下，一次寫入之后會變成更多的寫入。

LSM樹的應用

LSM樹最早是在1996年提出的，這個想法是將對鍵值存儲的更改作為事務跟蹤，并在內存中保留新的值。事務提交時，可以將最近鍵值對的排序集合寫入磁盤中唯一命名的文件。此文件包含已排序的鍵值對以及文件中鍵的索引。一旦寫入磁盤，新提交的更改不需要保存在內存中。

逐鍵查找值看起來就像在隨機地點找東西時的樣子。在一個小房間里線性搜索自己的錢包可能是易于處理，但是當搜索空間在大型酒店里就不那么容易了。為了減少數(shù)據讀取時的煩瑣，LSM 樹組織數(shù)據的方法是邊讀邊重寫。

當從存儲引擎新寫入一個新文件時，它有一堆鍵值對。為了便于查找鍵，這些鍵與前面編寫的文件合并。每個 LSM 樹都具有某種形式的扇出，其中較低級別的樹保存在更多的文件中。LSM 樹的深度取決于扇出、每個文件的大小以及樹中鍵值對的數(shù)量。一般來說，大部分存儲都位于樹的最底層。

因此，在越來越受歡迎的 LSM 結構中，有各種各樣的實現(xiàn)選擇:

平衡合并

當一個新文件被添加到一個級別時，在循環(huán)遍歷中選擇下一個文件，并將其與下一個級別的文件合并。假設從10個文件中選擇一個扇出，會發(fā)現(xiàn)文件中的鍵范圍通常涵蓋了下面級別中大約10個文件中的鍵范圍。把11個文件合并在一起，一個下降到下個級別，進而得到11個文件。現(xiàn)在，下一級已經被一個文件增加了，所以需要重復并再次合并。

分層合并

在進行合并之前，讓一堆文件在每個級別上堆疊起來。假設在每個級別合并之前堆積了10個文件，大大減少了所需的合并數(shù)量。

平衡合并有著很大的寫入放大， 每次將一個新的鍵值對寫入到級別0，在每個級別上都要重寫10到11次，但是讀取數(shù)據的成本較少。分層合并的寫入放大要低得多，因為新文件在合并之前會在每個級別上堆疊起來，所以合并的次數(shù)會減少，寫入的內容也會減少，但是數(shù)據讀取所付出的努力要多得多。

索引和搜索

搜索在許多方面都是數(shù)據庫索引的變體。在數(shù)據庫中，索引標識一般以行 id 或主鍵的形式隱藏在數(shù)據庫中。在關系型數(shù)據庫系統(tǒng)中，索引更新是通過事務集成的，我們能夠看到性能差異。

搜索系統(tǒng)在處理文檔方面有些不同。大多數(shù)搜索系統(tǒng)在文檔發(fā)生變更后異步更新搜索索引， 這是與某種形式的ID交織在一起。搜索使得讀取文檔更加容易。它極大地降低了數(shù)據讀取時的成本，而創(chuàng)建和合并搜索索引是一項復雜的工作，也是數(shù)據寫入放大的一種形式。

搜索的索引需要語料庫，以找到最近寫入或更新的文檔。其中每一個都需要有一個標識符，然后需要對其進行處理以定位搜索條件(有時稱為 n-grams，https://en.wikipedia.org/wiki/n-gram)。在一個典型的文檔中找到這些 n-gram 中的每一個元素都需要發(fā)送到包含許多索引元素的索引器。因此，文檔標識符與可搜索文檔中的每個術語(或 n-gram)相關聯(lián)，所有這一切都是因為用戶進行了寫操作或創(chuàng)建了文檔。每個文檔都需要做大量的工作，而且還有很多很多的文檔。

數(shù)據的規(guī)范化

在關系數(shù)據庫的世界里，一般要在數(shù)據庫中保存規(guī)范化數(shù)據，努力避免更新異常被認為是極其重要的。大多數(shù)系統(tǒng)的分布式趨勢在增強，其中大多數(shù)都有包含其數(shù)據的鍵值對，這些鍵值對是為了擴展分片使用的。通過將相關數(shù)據分組為一個鍵值對，很容易獲取這個值 ，然后發(fā)出請求到遠程系統(tǒng)。

如果規(guī)范化這個大型分片系統(tǒng)中的數(shù)據，規(guī)范化的值將可能不會在同一個分片上，執(zhí)行分布式聯(lián)接比執(zhí)行集中式聯(lián)接更加煩人。

為了解決這個問題，一般在數(shù)據上加上版本號，方案雖然并不完美，但比起分布式通信或者跨非規(guī)范化數(shù)據進行大規(guī)模更新，它的挑戰(zhàn)性要小得多。大規(guī)模的分布式系統(tǒng)對一致讀的語義施加了很大的壓力，這反過來可以被看作是寫入放大和讀讀成本之間的緊張關系。

一句話小結

隨著分布式系統(tǒng)的普遍化，數(shù)據系統(tǒng)的讀寫權衡越來越關鍵，辨認系統(tǒng)中數(shù)據讀寫的使用模式，才能進行設計上的權衡和優(yōu)化。