馬上農(nóng)歷新年了，在這里抛虏，給大家拜個(gè)早年博其，祝大家新年快樂，"豬"事順利迂猴！
再和大家說聲抱歉贺奠，這數(shù)據(jù)庫內(nèi)核雜談的第三篇-存儲(chǔ)，讓大家久等了错忱，由于種種原因(主要是懶)儡率，拖了這么久。新一年以清，立個(gè)flag儿普，做到每個(gè)月一篇，希望自己能夠堅(jiān)持下來掷倔。
言歸正傳眉孩，來談存儲(chǔ)。數(shù)據(jù)庫是用來存儲(chǔ)海量數(shù)據(jù)的勒葱。存儲(chǔ)如此大量的數(shù)據(jù)浪汪，自然而然想到的就是以文件的形式存儲(chǔ)在硬盤(HDD或SSD)中。當(dāng)然凛虽，一些商用數(shù)據(jù)庫為了追求性能死遭，是將數(shù)據(jù)優(yōu)先存儲(chǔ)在內(nèi)存中(比如SAP的HANA和MemSQL)來獲得更高速的讀寫。本文主要涉及的是關(guān)系型數(shù)據(jù)庫針對(duì)硬盤的存儲(chǔ)凯旋。對(duì)于內(nèi)存數(shù)據(jù)庫來說呀潭，依然需要硬盤作為備份或者2級(jí)存儲(chǔ)，所以相關(guān)知識(shí)也是適用的至非。
相較于列舉常見的存儲(chǔ)形式然后對(duì)比優(yōu)缺點(diǎn)的分類法钠署，我們今天另辟蹊徑，從"演化論"的角度來看荒椭，不同的存儲(chǔ)形式和優(yōu)化方法是怎么一步一步進(jìn)化出來的谐鼎。
一個(gè)數(shù)據(jù)庫存的是什么呢？這里簡(jiǎn)單介紹一下關(guān)系模型(relational model:?https://en.wikipedia.org/wiki/Relational_model)趣惠。關(guān)系模型由 Ted Codd1970年提出狸棍，關(guān)系模型定義了所有的數(shù)據(jù)都是以元組(tuple)的形式存在，每個(gè)元組定義了多個(gè)屬性(attribute)的鍵值對(duì)信卡，多個(gè)含有相同屬性的元組排列在一起就形成了一個(gè)關(guān)系(relation)隔缀。元組，屬性和關(guān)系對(duì)應(yīng)到數(shù)據(jù)庫中的概念就是行(row)傍菇，列(column), 和表(table)猾瘸。一個(gè)表定義了多個(gè)column，每個(gè)column有一個(gè)type丢习，每個(gè)row對(duì)應(yīng)于每一個(gè)column都有一個(gè)取值(取值滿足type的定義)牵触，每個(gè)表又由多個(gè)row構(gòu)成。不同的數(shù)據(jù)庫雖然有庫（database)咐低，schema或者命名空間(namespace)等不同級(jí)別的邏輯抽象揽思，但是表卻是每個(gè)關(guān)系型數(shù)據(jù)庫最基本的存儲(chǔ)對(duì)象。
好了见擦，確認(rèn)了數(shù)據(jù)庫需要存儲(chǔ)的基本單元是表钉汗。那么給定一張表羹令，應(yīng)該怎么存在文件中呢？如果還能回想起上一講的內(nèi)容损痰，你會(huì)說福侈，可以用comma-separated-value(CSV)格式的文件來存儲(chǔ)。確實(shí)卢未，CSV文件中的每一行對(duì)應(yīng)于一條row肪凛，每個(gè)row的不同column用逗號(hào)隔開，一個(gè)文件對(duì)應(yīng)了一張表辽社。下圖截取了一段Titanic幸存者的CSV文件伟墙。
這樣的一一對(duì)應(yīng)確實(shí)清楚。那么問題來了滴铅，上述的CSV形式有什么缺點(diǎn)嗎戳葵？有些讀者發(fā)現(xiàn)了，文件里并沒有定義column的類型和命名失息。我們來看應(yīng)該怎樣補(bǔ)全這個(gè)定義譬淳。方法一，我們把CSV文件的第一行預(yù)留給column的定義盹兢，如下圖所示邻梆，補(bǔ)上了所有column的命名(原文中并沒有定義類型，我們可以自行腦補(bǔ)绎秒，在每個(gè)column后面加入"(type)")浦妄。
方法二，把column的定義(我們通常稱之為表的元數(shù)據(jù))和數(shù)據(jù)分開存儲(chǔ)见芹。比如存在一個(gè)叫titanic_survivor.header的文件中剂娄，下圖給了文件的示意。
比較這兩種方法玄呛，哪一種更好呢阅懦？我們可以從支持?jǐn)?shù)據(jù)庫操作的角度出發(fā)來看。對(duì)于表徘铝，數(shù)據(jù)庫系統(tǒng)會(huì)支持新增一個(gè)新屬性耳胎，修改或刪除已有屬性。如果把屬性放在csv文件的第一行惕它，對(duì)于任何一種屬性操作怕午，需要對(duì)文件進(jìn)行大量的改動(dòng)：對(duì)于刪除一個(gè)已有屬性，需要?jiǎng)h除所有行的對(duì)應(yīng)數(shù)據(jù)來保證CSV文件的有效性淹魄，對(duì)于新增一個(gè)新屬性郁惜，同樣需要修改每一行。如果數(shù)據(jù)文件非常大(1 billion rows), 會(huì)消耗大量時(shí)間來更新數(shù)據(jù)甲锡。對(duì)于第二種方法兆蕉，修改的代價(jià)就小很多羽戒，只需要對(duì)header文件進(jìn)行修改即可。你可能會(huì)有疑問恨樟，如果單單修改header文件半醉，豈不是和數(shù)據(jù)文件就對(duì)應(yīng)不上了。一個(gè)可行的解決方案就是在對(duì)header文件修改時(shí)劝术，加上標(biāo)注。比如對(duì)于刪除一個(gè)現(xiàn)有屬性呆奕，只需要標(biāo)注這個(gè)屬性被刪除养晋，并不直接在header文件里刪除這個(gè)屬性的定義。當(dāng)數(shù)據(jù)庫對(duì)表的數(shù)據(jù)進(jìn)行讀取時(shí)梁钾，我們只需要同時(shí)讀取header文件绳泉，然后根據(jù)最新的定義，對(duì)于讀取的每一行數(shù)據(jù)姆泻，忽略已經(jīng)被刪除的屬性值即可零酪。同理，當(dāng)新增一個(gè)新屬性時(shí)拇勃，標(biāo)注這是一個(gè)新屬性四苇，并給定默認(rèn)值(不給定數(shù)據(jù)庫會(huì)定義為NULL)，那在讀取每一行數(shù)據(jù)時(shí)方咆，如果沒有新屬性月腋，就賦予默認(rèn)值即可。
這種分離元數(shù)據(jù)和數(shù)據(jù)的另一個(gè)好處在于瓣赂，方便數(shù)據(jù)庫統(tǒng)一管理所有表的元數(shù)據(jù)榆骚。幾乎所有的數(shù)據(jù)庫都會(huì)提供類似于information schema的功能，用來顯示數(shù)據(jù)庫的各種元數(shù)據(jù)煌集。比如有幾個(gè)namespace妓肢，對(duì)于每個(gè)namespace分別有幾個(gè)表，每個(gè)表都有哪些屬性苫纤。單獨(dú)存儲(chǔ)表的屬性就更方便讀取和管理碉钠。?
為了更好得支對(duì)表的元數(shù)據(jù)的管理和變更操作，我們從原有的csv文件進(jìn)化出了第一個(gè)特性方面，分離元數(shù)據(jù)和數(shù)據(jù)的存儲(chǔ)放钦。
討論完了元數(shù)據(jù)的管理，我們?cè)賮砜碈SV文件對(duì)于其他常見的數(shù)據(jù)庫操作還有什么做得不夠好的恭金。除了最頻繁的查詢語句操禀，另一類常見的操作就是添加，修改或者刪除表里的數(shù)據(jù)横腿。對(duì)于添加颓屑，我們只需要將新數(shù)據(jù)添加到文件的末尾斤寂。對(duì)于修改，如改變某一行的某一個(gè)屬性或刪除某一行揪惦，就需要在數(shù)據(jù)文件中進(jìn)行修改遍搞。相較于在文件末尾添加，文件中的修改會(huì)低效很多器腋，尤其是當(dāng)數(shù)據(jù)文件特別大的時(shí)候溪猿。
有什么思路來改進(jìn)呢？那些數(shù)據(jù)庫先賢就想了一招纫塌，分開管理的思路也可以用在數(shù)據(jù)本身呢诊县。設(shè)想一下，除了CSV存放每一行數(shù)據(jù)外措左，我們?cè)賳为?dú)維護(hù)一個(gè)slot_table的文件依痊，這個(gè)文件存啥呢，就存對(duì)應(yīng)CSV數(shù)據(jù)文件每一行的標(biāo)注信息怎披，比如對(duì)應(yīng)原始的CSV文件胸嘁，我們先生成對(duì)應(yīng)的slot_table如下：
對(duì)應(yīng)每一行，我們標(biāo)注V表示(valid)凉逛。對(duì)應(yīng)于新增數(shù)據(jù)操作性宏，我們只要同時(shí)append數(shù)據(jù)行和slot_table行即可。如果我們現(xiàn)在執(zhí)行了一個(gè)更新語句鱼炒，刪除姓名起始為"Cumings"的數(shù)據(jù)衔沼，那第二行的數(shù)據(jù)就要被刪除。對(duì)應(yīng)的昔瞧，我們可以不用修改CSV文件指蚁，只是把slot_table中的2:V改為2:D(deleted)。如果要執(zhí)行更新語句呢自晰，比如把姓名為"Braund, Mr. Owen Harris"年齡紀(jì)錄更新成37歲凝化，這又應(yīng)該怎么操作呢？我們可以在數(shù)據(jù)文件中添加一行新數(shù)據(jù)(第9行)酬荞，這行數(shù)據(jù)復(fù)制了第一行但是把年齡改成37搓劫。在slot_table文件中把1改為D,然后添加9:V。修改后的slot_table和數(shù)據(jù)文件如下：
讀者可能會(huì)發(fā)問混巧，雖然保證了數(shù)據(jù)文件的append only枪向，但是slot_table還是會(huì)在文件中進(jìn)行修改，如果數(shù)據(jù)量一大咧党，依然會(huì)增加讀寫負(fù)擔(dān)秘蛔。還能不能進(jìn)一步優(yōu)化？答案是可以的。我們其實(shí)可以把標(biāo)注信息也以append only的形式添加到slot_table中深员，比如上述的刪除和修改操作完成后负蠕，slot_table如下：
然后在讀取數(shù)據(jù)的時(shí)候，先讀取slot_table倦畅，然后逆序讀取所有行的標(biāo)注信息(讀取到2D后就忽略第二行)遮糖，就能知道哪些行是有效的，哪些行可以略過不用讀取了叠赐。
對(duì)于數(shù)據(jù)的增刪改欲账，我們已經(jīng)可以對(duì)數(shù)據(jù)文件和slot_table都實(shí)現(xiàn)append_only。還有什么問題嗎燎悍？對(duì)于一個(gè)數(shù)據(jù)表敬惦，每次操作都會(huì)添加新信息，久而久之谈山，數(shù)據(jù)文件越來越大，而且無效的行越來越多宏怔，豈不是很浪費(fèi)空間奏路。有什么辦法可以優(yōu)化呢？有臊诊。數(shù)據(jù)庫都會(huì)支持vacuum操作(或者叫compact)鸽粉，這個(gè)操作所做的就是讀取數(shù)據(jù)文件和slot_table，然后根據(jù)標(biāo)注把有效的數(shù)據(jù)行寫回新的文件抓艳。比如触机，對(duì)我們的示例進(jìn)行vacuum操作，新的數(shù)據(jù)文件和slot_table如下所示:
為了更高效地實(shí)現(xiàn)增刪改數(shù)據(jù)玷或，我們引入了第二個(gè)特性儡首，slot_table以及標(biāo)注信息來紀(jì)錄對(duì)數(shù)據(jù)的增刪改，并且引入vacuum操作定期清理無用的行數(shù)據(jù)偏友。
對(duì)于CSV蔬胯，還有什么能改進(jìn)的嗎？你可能已經(jīng)發(fā)現(xiàn)了位他，CSV是用明文來存儲(chǔ)數(shù)據(jù)氛濒，太低效了。比如對(duì)應(yīng)一個(gè)boolean的類型鹅髓，明文存成true或者false舞竿，如果用ascii編碼就是32或者40個(gè)bit(按照8bit的extended ascii編碼)。但如果用byte存儲(chǔ)窿冯，只要1個(gè)bit即可(即便是用0,1明文來存儲(chǔ)boolean也還是沒有byte高效)骗奖。CSV為了方便用戶直接能夠理解，所以犧牲了效率。但是數(shù)據(jù)文件完全由數(shù)據(jù)庫系統(tǒng)管理和讀取重归，可以存儲(chǔ)raw byte配上高效的編碼和解碼算法來進(jìn)一步優(yōu)化米愿。那如何才能更高效得存儲(chǔ)呢？這里我就不給出具體的實(shí)現(xiàn)了鼻吮，可以參考現(xiàn)在流行的RPC框架比如Thrift(https://thrift.apache.org/)和Protocol Buffers(https://developers.google.com/protocol-buffers/)育苟，這些網(wǎng)絡(luò)端傳輸數(shù)據(jù)的協(xié)議，為了追求效率對(duì)數(shù)據(jù)的編碼和解碼有很多優(yōu)化椎木。相對(duì)應(yīng)的违柏，slot_table里存儲(chǔ)的不再只是行號(hào)，而應(yīng)該是該條數(shù)據(jù)對(duì)應(yīng)在文件中的byte offset香椎。
為了更高效得存儲(chǔ)數(shù)據(jù)漱竖，我們引入了第三個(gè)特性，用raw byte來存儲(chǔ)數(shù)據(jù)配合高效的編碼和解碼算法來加速讀取和寫入畜伐。
還有什么能再進(jìn)一步優(yōu)化嗎馍惹？說下一步優(yōu)化前，我們先來了解這樣一類數(shù)據(jù)庫玛界。這類數(shù)據(jù)庫并不進(jìn)行修改和添加操作万矾，但是存儲(chǔ)了大量的數(shù)據(jù)，并且要運(yùn)行大量非常復(fù)雜的分析語句慎框。沒錯(cuò)良狈，這類數(shù)據(jù)庫是數(shù)據(jù)倉(cāng)庫(Data warehouse)。區(qū)別于普通的Online transactional processing(OLTP)的數(shù)據(jù)庫笨枯，通過抓取薪丁，清洗和變化OLTP數(shù)據(jù)庫的數(shù)據(jù)然后導(dǎo)入到數(shù)據(jù)倉(cāng)庫負(fù)責(zé)分析報(bào)表等需要查詢大量歷史數(shù)據(jù)的復(fù)雜語句。這類數(shù)據(jù)庫的表結(jié)構(gòu)稱之為雪花模型(snowflake schema)馅精，由一張或者多張的實(shí)體數(shù)據(jù)表(entity table)严嗜，配合一些輔助表(英文里稱dimension table)。實(shí)體數(shù)據(jù)表通常是交易記錄等存有大量數(shù)據(jù)(億甚至千億級(jí)別)硫嘶，輔助表則只有少量的相關(guān)信息比如國(guó)家阻问，商戶等的具體信息。下圖引用了TPC-H(非常有名的數(shù)據(jù)庫基準(zhǔn)測(cè)試)的雪花模型(from?https://www.researchgate.net/figure/Snowflake-Schema-based-on-TPC-H_fig1_37684343)沦疾，其中表lineitem_orders就是一個(gè)包含所有交易紀(jì)錄的實(shí)體表称近。
實(shí)體表不僅有大量數(shù)據(jù)行，屬性也很多(100到200都很常見)哮塞∨俑眩可是，大部分的分析報(bào)表語句僅需要讀取相關(guān)的幾個(gè)屬性(列)忆畅。為了運(yùn)行該語句衡未，就需要把整個(gè)實(shí)體表的數(shù)據(jù)讀到內(nèi)存中來抽取需要的屬性列。設(shè)想一個(gè)實(shí)體表有100個(gè)屬性，10億條數(shù)據(jù)缓醋，但某個(gè)語句只需要用到3個(gè)屬性如失。按照CSV方式讀取數(shù)據(jù)，97%的數(shù)據(jù)是沒有用處的送粱。貪得無厭的數(shù)據(jù)庫的大牛想褪贵，有什么辦法可以優(yōu)化需要讀取的數(shù)據(jù)嗎？于是列存(column-oriented store)就這樣出現(xiàn)了抗俄。
類似于CSV這樣把每一個(gè)tuple的數(shù)據(jù)存放在一起的存儲(chǔ)方式叫行存(row-oriented store)脆丁。相對(duì)應(yīng)的列存，就是指把一個(gè)表的每個(gè)屬性动雹， 單獨(dú)存在一個(gè)數(shù)據(jù)文件中槽卫。還是沿用上面titanic的例子，我們會(huì)有單獨(dú)的數(shù)據(jù)文件(還有slot_table文件)來存儲(chǔ)姓名胰蝠，船票價(jià)格歼培，登船碼頭，等等茸塞。在讀取的時(shí)候丐怯，根據(jù)查詢語句需求，需要用到哪個(gè)屬性就讀取哪個(gè)屬性的數(shù)據(jù)文件翔横。按照前面的例子，我們只需要讀取原來的3個(gè)屬性的數(shù)據(jù)文件梗搅，讀取速度自然就提高了禾唁。
除了可以避免讀取不必要的數(shù)據(jù)，列存還能帶來什么優(yōu)勢(shì)无切？因?yàn)槊恳涣械念愋褪窍嗤牡炊蹋热缍际钦位蛘呤亲址Ｔ诖鎯?chǔ)同類型的數(shù)據(jù)時(shí)哆键，壓縮算法能夠更有效地進(jìn)行壓縮掘托，使得數(shù)據(jù)量更近一步減少，來加快讀取速度籍嘹。舉個(gè)簡(jiǎn)單的例子闪盔，上述titanic的例子中有一列Cabin紀(jì)錄了倉(cāng)位信息(假設(shè)值分為A1，A2辱士，A3泪掀，B1，...等)颂碘，相較于對(duì)于每一行都直接用字符串來存儲(chǔ)异赫，我們可以采用下面enum的壓縮方式。因?yàn)閭}(cāng)位類型不多，所以對(duì)于每一行塔拳，只需要用tiny就能存下是哪個(gè)倉(cāng)位了鼠证。只需要數(shù)據(jù)庫系統(tǒng)在讀取數(shù)據(jù)的時(shí)候根據(jù)meta把對(duì)應(yīng)數(shù)據(jù)換出即可。
為了應(yīng)對(duì)數(shù)據(jù)倉(cāng)庫中復(fù)雜報(bào)表的查詢語句和超大量的數(shù)據(jù)讀取靠抑，我們引入了第四個(gè)優(yōu)化量九，把行存轉(zhuǎn)換為列存，并且由于存儲(chǔ)的數(shù)據(jù)是一個(gè)類型的孕荠，可以進(jìn)一步用壓縮算法來優(yōu)化數(shù)據(jù)量娩鹉。
小結(jié)
至此，我們從最原始的使用CSV文件格式來存儲(chǔ)數(shù)據(jù)稚伍，一步一步根據(jù)數(shù)據(jù)庫的操作需要弯予，"進(jìn)化"出了下面這些優(yōu)化方法:?
1) 為了更好得支持對(duì)表的元數(shù)據(jù)的管理和變更操作, 分離元數(shù)據(jù)和數(shù)據(jù)的存儲(chǔ)
2) 為了更高效地實(shí)現(xiàn)增刪改數(shù)據(jù)，引入slot_table以及標(biāo)注信息來紀(jì)錄對(duì)數(shù)據(jù)的增刪改个曙，并且引入vacuum操作定期清理無用的行數(shù)據(jù)
3) 為了更高效得存儲(chǔ)數(shù)據(jù)锈嫩，用byte來存儲(chǔ)數(shù)據(jù)配合高效的編碼和解碼算法來加速讀取和寫入
4) 為了應(yīng)對(duì)數(shù)據(jù)倉(cāng)庫中復(fù)雜報(bào)表的查詢語句和超大量的數(shù)據(jù)讀取，引入列存概念垦搬，并且用壓縮算法來進(jìn)一步優(yōu)化數(shù)據(jù)量
具體到真正數(shù)據(jù)庫的實(shí)現(xiàn)呼寸，還有無數(shù)各個(gè)方面的工程優(yōu)化。比如猴贰，為了提高從文件系統(tǒng)讀取數(shù)據(jù)到內(nèi)存的速度对雪，把文件塊的大小設(shè)置得和內(nèi)存頁一致，用內(nèi)置的緩存機(jī)制來提前換進(jìn)和換出數(shù)據(jù)頁(相對(duì)于操作系統(tǒng)的默認(rèn)緩存機(jī)制米绕，數(shù)據(jù)庫系統(tǒng)更清楚哪些數(shù)據(jù)會(huì)一起被使用從而可以提前做好準(zhǔn)備)瑟捣。但是各種優(yōu)化，也并不是數(shù)據(jù)庫大牛拍腦袋想出來的栅干。而是針對(duì)問題迈套，提出思路和解決方案，一步一步實(shí)踐出來的碱鳞。所以面對(duì)工作中的工程問題桑李，我們也應(yīng)該本著這種心態(tài)去處理和解決。
最后留個(gè)坑窿给，雖然列存的實(shí)現(xiàn)贵白，使得我們不用讀取無用列的數(shù)據(jù)，但針對(duì)某些點(diǎn)查詢的語句(point query)填大，比如"select col2 from table1 where col1 = 10", 我們依然需要讀取col1和col2兩列的全部數(shù)據(jù)戒洼。有什么辦法可以優(yōu)化這類查詢嗎？下一期允华，我們接著聊這類優(yōu)化-索引(indexing)圈浇。
