古风名字,绝色狂妃仙魅小说,完美世界有声小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

系統(tǒng)架構(gòu)設(shè)計(jì)之?dāng)?shù)據(jù)庫的核心數(shù)據(jù)結(jié)構(gòu)

從最基本層面看，數(shù)據(jù)庫只需做兩件事：

10年積累的網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有相城免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

向它插入數(shù)據(jù)肘，它就保存數(shù)據(jù)
之后查詢時(shí)，返回那些數(shù)據(jù)

本文討論如何存儲(chǔ)輸入的數(shù)據(jù)，并在收到查詢請求時(shí)，如何重新找到數(shù)據(jù)。

為何關(guān)注數(shù)據(jù)庫內(nèi)部的存儲(chǔ)和檢索呢？你不可能從頭開始實(shí)現(xiàn)存儲(chǔ)引擎，往往需要從眾多現(xiàn)有的存儲(chǔ)引擎中選擇適合業(yè)務(wù)的存儲(chǔ)引擎。為針對特定工作負(fù)載而對數(shù)據(jù)庫調(diào)優(yōu)時(shí)，就得對存儲(chǔ)引擎底層機(jī)制有所了解。

針對事務(wù)型工作負(fù)載、分析型負(fù)載的存儲(chǔ)引擎優(yōu)化存在很大差異。

事務(wù)處理與分析處理”和“面向列的存儲(chǔ)”部分，分析型優(yōu)化的存儲(chǔ)引擎。

先討論存儲(chǔ)引擎，用于大家比較熟悉的兩種數(shù)據(jù)庫，傳統(tǒng)關(guān)系數(shù)據(jù)庫和NoSQL數(shù)據(jù)庫。研究兩個(gè)存儲(chǔ)引擎家族，即日志結(jié)構(gòu)的存儲(chǔ)引擎和面向頁的存儲(chǔ)引擎，比如B-tree。

數(shù)據(jù)庫核心：數(shù)據(jù)結(jié)構(gòu)

最簡單的數(shù)據(jù)庫，由兩個(gè)Bash函數(shù)實(shí)現(xiàn)：

#!/bin/bash

db_set() { 
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s／^$1,//" tail -n 1
}

這兩個(gè)函數(shù)實(shí)現(xiàn)一個(gè)K.V存儲(chǔ)。當(dāng)調(diào)用 db_set key value，它將在數(shù)據(jù)保存你所輸入的key value key value幾乎可以是任何內(nèi)容。例如值可以是JSON文檔。然后調(diào)用db_get key，它會(huì)查找與輸入key相關(guān)聯(lián)的最新值并返回。

例如：

$ db_set 123456 '{"name":"London", "attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42 {"name":"San Francisco", "attractions":["Golden Gate Bridge"]}

它底層的存儲(chǔ)格式其實(shí)非常簡單：一個(gè)純文本文件。其中每行包含一個(gè)K.V，用逗號(hào)分隔（大致像一個(gè)csv文件，忽略轉(zhuǎn)義問題）。每次調(diào)用db_set，即追加新內(nèi)容到文件末尾，因此，若多次更新某K，舊版本值不會(huì)被覆蓋，而需查看文件中最后一次出現(xiàn)的K來找到最新V（因此在db_get中使用tail -n 1）。

$ db_set 42 '{"name":"San Francisco", "attractions":["Exploratorium"]}'

$ db_get 42 {"name":"San Francisco", "attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]} 42, {"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

簡單情況，追加到文件尾部方式通常夠高效了，因而db_set函數(shù)性能很好。類似db_set，許多數(shù)據(jù)庫內(nèi)部都使用日志（log），日志是個(gè)僅支持追加式更新的數(shù)據(jù)文件。雖然真正的數(shù)據(jù)庫有很多更復(fù)雜問題要考慮（如并發(fā)控制、回收磁盤空間以控制日志文件大小、處理錯(cuò)誤和部分完成寫記錄等），但基本原理相同。

日志這個(gè)詞通常指應(yīng)用程序的運(yùn)行輸出日志，來記錄發(fā)生了什么事情。日志則是個(gè)更通用的含義，表示一個(gè)僅能追加的記錄序列集合。它可能是人類不可讀的，可能是二進(jìn)制格式而只能被其他程序來讀取。

另一方面，若日志文件保存大量記錄，則db_get性能會(huì)很差。每次想查找一個(gè)K，db_get 必須從頭到尾掃描整個(gè)數(shù)據(jù)庫文件來查找K的出現(xiàn)位置。在算法術(shù)語中，查找開銷是O（n），即若數(shù)據(jù)庫記錄條數(shù)加倍，則查找需要兩倍時(shí)間。這一點(diǎn)并不好。

為高效查找數(shù)據(jù)庫中特定K的V，需要數(shù)據(jù)結(jié)構(gòu)：索引。它們背后基本想法都是保留一些額外元數(shù)據(jù)，這些元數(shù)據(jù)作為路標(biāo)，幫助定位想要數(shù)據(jù)。若希望用幾種不同方式搜索相同數(shù)據(jù)，在數(shù)據(jù)的不同部分，可能要定義多種不同的索引。

索引是基于原始數(shù)據(jù)派生而來的額外數(shù)據(jù)結(jié)構(gòu)。很多數(shù)據(jù)庫允許單獨(dú)添加、刪除索引，而不影響數(shù)據(jù)庫內(nèi)容，它只會(huì)影響查詢性能。維護(hù)額外結(jié)構(gòu)勢必會(huì)引入開銷，特別是在新數(shù)據(jù)寫入時(shí)。對于寫人，它很難超過簡單追加文件方式的性能，因?yàn)槟且呀?jīng)是最簡單的寫操作。由于每次寫數(shù)據(jù)時(shí)，需更新索引，所以任何類型索引基本都會(huì)降低寫速度。

存儲(chǔ)系統(tǒng)中重要的trade off

合適的索引能加速查詢，但每個(gè)索引都會(huì)降低寫速度。默認(rèn)情況下，數(shù)據(jù)庫通常不會(huì)對所有內(nèi)容索引，它需要SE或DBA基于對應(yīng)用程序典型查詢模式的了解，手動(dòng)決定索引。就是為應(yīng)用提供最有利加速同時(shí)，避免引入過多不必要的開銷。

哈希索引

以KV數(shù)據(jù)的索引開始。KV類型并非唯一能索引的數(shù)據(jù)，但隨處可見，而且是其他更復(fù)雜索引的基礎(chǔ)。

KV存儲(chǔ)與大多數(shù)編程語言所內(nèi)置的字典結(jié)構(gòu)類似，一般采用hash map或hash table實(shí)現(xiàn)。既然已有內(nèi)存數(shù)據(jù)結(jié)構(gòu)的hash map ，為何不用它們在磁盤上直接索引數(shù)據(jù)？

假設(shè)數(shù)據(jù)存儲(chǔ)全部采用追加式文件組成，最簡單的索引策略：保存內(nèi)存中的hash map，將每個(gè)K一一映射到數(shù)據(jù)文件中特定的字節(jié)偏移量，這就能找到每個(gè)值的位置：

圖1

每當(dāng)在文件中追加新的KV對時(shí)，還要更新hashma來反映剛寫入的數(shù)據(jù)的偏移量（包括插入新K與更新已有K）。當(dāng)查找一個(gè)值時(shí)，使用hashmap找到文件中的偏移量，即存儲(chǔ)位置，然后讀取其內(nèi)容。

聽著簡單，但的確可行。Bitcask（Riak默認(rèn)的存儲(chǔ)引擎）就是這么做的。Bitcask提供高性能讀寫，但所有K必須能放入內(nèi)存。而V則可以使用比可用內(nèi)存更多的空間，只需一次磁盤尋址，就能將V從磁盤加載到內(nèi)存，若那部分?jǐn)?shù)據(jù)文件已在文件系統(tǒng)的緩存中，則讀取根本不需要任何磁盤I/O。

Bitcask這種存儲(chǔ)引擎適合每個(gè)K的V經(jīng)常更新場景。如：

K，視頻的URL
V，播放次數(shù)（每次有人點(diǎn)擊播放按鈕時(shí)遞增）

在這種工作負(fù)載下，有大量寫操作，但沒有太多不同的K，即每個(gè)K都有大量寫操作，但將所有K保存在內(nèi)存中還是可行的。

至此，只追加寫到一個(gè)文件，那如何避免最終用完磁盤空間？可將日志分為特定大小的段，當(dāng)日志文件達(dá)到一定大小時(shí)就關(guān)閉，并開始寫到一個(gè)新的段文件中。然后，就能壓縮這些段：

圖2：壓縮KV 更新日志文件，僅保留每個(gè)K的最新值

壓縮意味著在日志中丟棄重復(fù)K，只保留每個(gè)K的最近更新。

由于壓縮經(jīng)常會(huì)使段更?。僭O(shè)K在一個(gè)段內(nèi)被平均重寫多次），也能在執(zhí)行壓縮時(shí)將個(gè)段合并：

圖3：同時(shí)執(zhí)行段壓縮和多段的合并

由于段在寫入后不會(huì)再被修改，所以合并的段會(huì)被寫入一個(gè)新文件。對這些凍結(jié)段的合并和壓縮過程可在后臺(tái)線程完成，而在運(yùn)行時(shí)，仍能繼續(xù)使用舊的段文件繼續(xù)正常的讀寫請求。合并過程完成后，將讀請求切換到新的合并段上，舊的段文件就能安全刪除了。

每個(gè)段現(xiàn)在都有自己的內(nèi)存哈希表，將K映射到文件的偏移量。為找到鍵的值，先檢查最新的段的 hashmap；若K不存在，則檢查第二最新的段，依此類推。因?yàn)楹喜⑦^程可維持較少的段數(shù)量，因此查找一般無需檢查太多hashmap。

實(shí)現(xiàn)難點(diǎn)

(1) 文件格式

CSV不是日志最佳格式，二進(jìn)制格式更快，更簡單。首先以字節(jié)為單位，記錄字符串的長度，然后跟上原始的字符串（無需轉(zhuǎn)義）。

(2) 刪除記錄

若要?jiǎng)h除一個(gè)K及其V，則必須在數(shù)據(jù)文件中中追加一個(gè)特殊的刪除記錄（有時(shí)稱為邏輯刪除）。合并日志段時(shí)，一旦發(fā)現(xiàn)邏輯刪除標(biāo)記，就會(huì)丟棄這個(gè)已刪除鍵的所有值。

(3) 崩潰恢復(fù)

若數(shù)據(jù)庫重啟，則內(nèi)存的hashmap將丟失。原則上，可通過從頭到尾讀取整個(gè)段文件，記錄每個(gè)鍵的最新值的偏移量，來恢復(fù)每個(gè)段的hashmap。但若段文件很大，這可能耗時(shí)久，這將使服務(wù)器重啟很慢。Bitcask通過存儲(chǔ)加速恢復(fù)磁盤上每個(gè)段的哈希映射的快照，可以更快地加載到內(nèi)存中。

(4) 部分寫入記錄

數(shù)據(jù)庫可能隨時(shí)崩潰，包括將記錄追加到日志的過程中。Bitcask文件包含校驗(yàn)值，這樣就能發(fā)現(xiàn)損壞部分并丟棄。

(5) 并發(fā)控制

由于寫是以嚴(yán)格的先后順序追加到日志，所以常見實(shí)現(xiàn)是只有一個(gè)寫線程。數(shù)據(jù)文件段是追加的且不可變，所以它們能被多線程同時(shí)讀取。

追加的日志看起來很浪費(fèi)：為何不更新文件，用新值覆蓋舊值？

追加寫設(shè)計(jì)的優(yōu)勢

追加和分段合并是順序?qū)?，一般比隨機(jī)寫快得多，尤其是在旋轉(zhuǎn)式磁盤。某種程度上，順序?qū)懺诨陂W存的固態(tài)硬盤（SSD）也很合適
若段文件是追加的或不可變的，則并發(fā)和崩潰恢復(fù)就簡單得多。如不必?fù)?dān)心在重寫值時(shí)發(fā)生崩潰的情況，導(dǎo)致留下一個(gè)包含部分舊值和部分新值混雜的文件
合并舊段能避免數(shù)據(jù)文件隨時(shí)間推移，數(shù)據(jù)文件出現(xiàn)碎片化問題

哈希索引的劣勢

散列表必須能放進(jìn)內(nèi)存若你有很多鍵，那真是倒霉。原則上，可在磁盤上維護(hù)一個(gè)hashmap，但磁盤上的hashmap很難表現(xiàn)優(yōu)秀，需大量隨機(jī)訪問I/O，當(dāng)hash變滿時(shí)，繼續(xù)增長代價(jià)昂貴，并且哈希沖突需要復(fù)雜處理邏輯
范圍查詢效率不高如無法輕松掃描kitty00000到kitty99999之間的所有K，只能采用逐個(gè)查找的方式查詢每個(gè)K

本文題目：系統(tǒng)架構(gòu)設(shè)計(jì)之?dāng)?shù)據(jù)庫的核心數(shù)據(jù)結(jié)構(gòu)
轉(zhuǎn)載來源：http://www.fisionsoft.com.cn/article/cdhodgi.html