摘要
kv存儲(chǔ)引擎近些年越來(lái)越受歡迎垫卤，因?yàn)樗梢詮椥缘財(cái)U(kuò)縮容社牲，對(duì)于get/put可以維持高吞吐量甥厦，有更低的延遲纺铭。這些得益于它的簡(jiǎn)單，然而簡(jiǎn)單也帶來(lái)一定的代價(jià)：目前的kv存儲(chǔ)系統(tǒng)不能很好的支持scan性能刀疙， 所以它不適用于處理復(fù)雜舶赔、分析型的query。分析型的query要求更好的數(shù)據(jù)局部性谦秧，然而get/put的高吞吐要求離散的索引竟纳。這篇paper展示了一種折中的方式可以兼具兩者。講述了分布式kv存儲(chǔ)系統(tǒng)TellStore疚鲤，對(duì)于kv锥累、分析型和混合場(chǎng)景都表現(xiàn)了不錯(cuò)的性能。在論文最后的章節(jié)中展示了benchmark的測(cè)試結(jié)果集歇。
1. 介紹
相比于傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)桶略，kv store由于它的彈性、可擴(kuò)展性诲宇、部署和管理簡(jiǎn)單而受到歡迎际歼。而且它的性能也是可預(yù)期的：每條get/put請(qǐng)求花費(fèi)確切的常量級(jí)時(shí)間。這些特性使得一些應(yīng)用可以建立在kvs之上焕窝。
近期的一些工作展示了kvs可以以高效可擴(kuò)展的方式run oltp的負(fù)載蹬挺。這些工作采用了一種"SQL-over-NoSQL"的方式：數(shù)據(jù)持久化存儲(chǔ)在kvs（NoSQL）,應(yīng)用邏輯(with SQL support)放在一個(gè)分隔的處理層。在這個(gè)工作中我們要提出的一個(gè)重要問題是這樣一個(gè)"SQL-overNoSQL"的架構(gòu)使用相同的kvs能否同時(shí)滿足OLAP和OLTP的負(fù)載它掂？
這個(gè)問題是有價(jià)值的巴帮，因?yàn)閛ltp和olap的請(qǐng)求訪問方式是不同的溯泣。大多數(shù)kvs的get/put層是為oltp型負(fù)載所設(shè)計(jì)的，但對(duì)于分析型的請(qǐng)求并不是可行的榕茧，往往要涉及讀全部的數(shù)據(jù)或者大范圍的數(shù)據(jù)垃沦。分析型的系統(tǒng)提供適用于它們的訪問方式：允許一次性訪問到所有的數(shù)據(jù)(full table scan)，下推select條件或者join條件到存儲(chǔ)層用押。大多數(shù)kvs是不具備這樣的能力的肢簿，所以對(duì)于scan的性能是不可接受的。
為了說(shuō)明目前kvs不適合分析型的應(yīng)用蜻拨，table1展示了簡(jiǎn)單的查詢5000wkv對(duì)數(shù)據(jù)的時(shí)間池充，返回了特定字段(YCSB# Query 1 in Section 7.2.1)的最大值(？最大值是什么意思缎讼？)收夸。對(duì)于這個(gè)實(shí)驗(yàn)，論文中用了四種機(jī)型(在7.1章節(jié)中展示了配置)血崭。因?yàn)閞ocksdb是一個(gè)單機(jī)存儲(chǔ)引擎卧惜，測(cè)試它只用了1/4的數(shù)據(jù)量。Cassandra花費(fèi)了大約19m處理這個(gè)簡(jiǎn)單的查詢夹纫。RAMCloud和HBase需要大約半分鐘咽瓷。對(duì)于這三種kvs，使用服務(wù)端聚集數(shù)據(jù)舰讹，因?yàn)閭鬏敂?shù)據(jù)在客戶端聚集會(huì)使得性能更差(???)茅姜。即使將這些數(shù)據(jù)集全部放在內(nèi)存中，性能也是不可接受的跺涤。在這個(gè)實(shí)驗(yàn)中可以接受的系統(tǒng)是rocksdb匈睁，memsql和kudu。rocksdb是一個(gè)適用于oltp系統(tǒng)的開源數(shù)據(jù)庫(kù)存儲(chǔ)引擎桶错，被facebook所使用航唆。MemSQL是分布式的、內(nèi)存關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)院刁，經(jīng)過很好的優(yōu)化(相比與其它的有很快表達(dá)式編譯糯钙？？)退腥。kudu 是一種基于列存的kvs任岸，適用于混合負(fù)載(分析型和get/put)。但是如果有實(shí)時(shí)的延遲的要求狡刘，這7種系統(tǒng)都還遠(yuǎn)達(dá)不到要求享潜。這篇論文將提出TellStore的不同變種，可以實(shí)現(xiàn)更低的延遲嗅蔬，更快的響應(yīng)時(shí)間剑按。
kudu的性能表現(xiàn)說(shuō)明了即使為這種查詢做了特定優(yōu)化的系統(tǒng)也不容易在kvs實(shí)現(xiàn)快速查詢疾就。這里的問題在于同時(shí)支持get/put和scan操作是一個(gè)矛盾的目標(biāo)。有效的scan要求很好的數(shù)據(jù)局部性艺蝴，而get/put要求離散的索引猬腰。多版本和回收機(jī)制的實(shí)現(xiàn)也會(huì)很大的影響性能，是需要考慮的點(diǎn)猜敢。這篇論文展示了一種折中的方式姑荷，說(shuō)明在相同kvs上支持混合負(fù)載是可能的。
這篇論文主要貢獻(xiàn)了以下幾個(gè)點(diǎn)：
第一缩擂，論文提到了Sql-over-NoSql架構(gòu)鼠冕，展示了它如何處理混合負(fù)載的。
第二胯盯，論文提出了開發(fā)一個(gè)同時(shí)支持點(diǎn)查和范圍查詢的kvs的存儲(chǔ)格式設(shè)計(jì)(列存/行存等)供鸠。
第三，論文介紹了TellStore陨闹，一個(gè)分布式的內(nèi)存kvs和兩種不同kvs的實(shí)現(xiàn)（Sections 4 to 6）。
最后薄坏，論文給出了用擴(kuò)展的YCSB benchmark測(cè)試的實(shí)驗(yàn)性能和工業(yè)界（the telecommuni- cations industry ）使用變體實(shí)現(xiàn)kvs支持有效查詢的負(fù)載趋厉。
這個(gè)工作的主要思想是構(gòu)建一個(gè)支持混合型負(fù)載的kvs是可能的，而且性能是可接受的胶坠。相比于從文獻(xiàn)中簡(jiǎn)單提出概念君账，從整體上考慮和羅列這些設(shè)計(jì)問題是比較重要的。
REQUIREMENTS
2.1 SQL-over-NoSQL架構(gòu)
Figure 1 描述了在kvs之上支持OLTP/OLAP混合負(fù)載的SQL-OVER-NOSQL架構(gòu)沈善。在這種架構(gòu)中乡数，數(shù)據(jù)持久化在分布式的包含get/put和scan接口的kvs中，事務(wù)和查詢的邏輯在單獨(dú)的處理層闻牡。處理層也需要處理并發(fā)的查詢和事務(wù)净赴。在整個(gè)過程中，我們使用SI(Snapshot Isolation)作為隔離級(jí)別罩润，使用Figure 1 中展示的Commit Manager來(lái)實(shí)現(xiàn)玖翅。SI(或者多版本并發(fā)控制的其它形式)被作為是默認(rèn)的隔離級(jí)別實(shí)現(xiàn)，尤其是在分布式系統(tǒng)和數(shù)據(jù)庫(kù)混合負(fù)載的場(chǎng)景下割以，因?yàn)閛ltp事務(wù)從來(lái)不會(huì)阻塞或者干擾olap的查詢金度。在SI隔離級(jí)別下，Commit Manager 簡(jiǎn)化設(shè)計(jì)了事務(wù)的時(shí)間戳严沥，保留了對(duì)活躍猜极、已提交和回滾事務(wù)的追蹤，因此幾乎不會(huì)成為系統(tǒng)的瓶頸消玄。
SQL-Over-NoSQL架構(gòu)的一個(gè)主要優(yōu)勢(shì)是elastic(彈性)跟伏。機(jī)器可以獨(dú)立的增加到存儲(chǔ)層或者處理層(計(jì)算層)丢胚。比如，可以新增OLAP節(jié)點(diǎn)放在處理層來(lái)處理復(fù)雜的分析型查詢酬姆。當(dāng)query完成時(shí)嗜桌，這些節(jié)點(diǎn)可以關(guān)閉或者更改屬性來(lái)處理其它任務(wù)。這種結(jié)構(gòu)也能有效地支持混合型的事務(wù)/分析型的負(fù)載:兩種負(fù)載都可以并發(fā)的跑在單獨(dú)的數(shù)據(jù)副本上辞色。
為了高效地實(shí)現(xiàn)SQL-OverNoSQL架構(gòu)骨宠，分布式kvs必須滿足以下的要求：
Scans
除了get/put請(qǐng)求，kvs還必須支持高效地scan操作相满。為了減少網(wǎng)絡(luò)傳輸?shù)拇鷥r(jià)层亿，kvs應(yīng)該支持selections、projections和簡(jiǎn)單的聚合立美，以實(shí)現(xiàn)只有相關(guān)的數(shù)據(jù)從存儲(chǔ)層傳輸?shù)教幚韺幽溆帧Ａ硗猓С謘harded scan對(duì)于許多應(yīng)用來(lái)講是一大優(yōu)勢(shì)建蹄。
Versioning
為了支持多版本的并發(fā)控制碌更，kvs必須要每條記錄的不同版本，根據(jù)事務(wù)的時(shí)間戳來(lái)返回正確的數(shù)據(jù)版本洞慎。Versioning需要有舊版本回收來(lái)釋放舊版本數(shù)據(jù)占用的空間痛单。
Batching and Asynchronous Communication
為了實(shí)現(xiàn)高oltp性能，oltp處理節(jié)點(diǎn)將多個(gè)請(qǐng)求打包發(fā)給存儲(chǔ)層是關(guān)鍵的劲腿。使用這種方式旭绒，從處理層到存儲(chǔ)層傳輸信息的往返代價(jià)就被分?jǐn)偟搅硕鄠€(gè)并發(fā)事務(wù)中。而且焦人，這種打包請(qǐng)求的方式需要異步執(zhí)行挥吵，使得處理層在等待前一次請(qǐng)求被kvs處理完成之前可以收集下一輪的請(qǐng)求。
2.2 實(shí)現(xiàn)的難點(diǎn)
實(shí)現(xiàn)這三個(gè)需求的最大難點(diǎn)在于它們是矛盾的花椭。這也是為什么今天大多數(shù)kvs只支持get/put(例如Cassandra 和 HBase)忽匈，有的實(shí)現(xiàn)了多版本（例如RAMCloud 和 HBase），有些實(shí)現(xiàn)了異步傳輸矿辽。所有的這些特征都能很好的支持離散的數(shù)據(jù)結(jié)構(gòu)脉幢，為get/put操作而設(shè)計(jì)。當(dāng)查找一行特定版本的記錄時(shí)嗦锐，是否它是緊湊的存儲(chǔ)是不重要的嫌松。然而對(duì)于scan，要求很高的數(shù)據(jù)局部性和數(shù)據(jù)緊密的存儲(chǔ)使得每一次存儲(chǔ)層的訪問能夠返回盡可能多的相關(guān)數(shù)據(jù)奕污。數(shù)據(jù)局部性對(duì)于磁盤和內(nèi)存中的scan都很重要萎羔。而且，加入scan的特征也帶來(lái)如下的矛盾點(diǎn)：
Scan vs. Get/Put
大多數(shù)的分析型系統(tǒng)使用列向存儲(chǔ)層來(lái)增加數(shù)據(jù)的局部性碳默。然而贾陷，kvs缘眶，不需要物化數(shù)據(jù)，典型的使用行向存儲(chǔ)來(lái)處理get/put請(qǐng)求髓废。
Scan vs. Versioning
不想關(guān)的多版本記錄會(huì)減少數(shù)據(jù)的局部性而降低scan的性能巷懈。而且，scan過程中check記錄的版本相關(guān)慌洪，也會(huì)花費(fèi)高昂的代價(jià)顶燕。
Scan vs. Batching
像get/put請(qǐng)求那樣打包scan請(qǐng)求并不是有利的。OLTP的負(fù)載要求常量級(jí)的返回時(shí)間和對(duì)get/put請(qǐng)求可預(yù)期的返回時(shí)間冈爹。相反涌攻，scan會(huì)帶來(lái)返回時(shí)間的多變性，取決于謂詞的選擇性和需要處理的復(fù)雜query涉及的字段數(shù)量频伤。
幸運(yùn)地恳谎，如我們所描述的，這些矛盾點(diǎn)是可以以一種折中的方式來(lái)解決的憋肖。這篇論文的目的是去研究kvs的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)和通過實(shí)驗(yàn)證明哪種方式最有效因痛。
3. DESIGN SPACE
這部分給出了一個(gè)整體的概括，關(guān)于構(gòu)建一個(gè)支持bulk操作和scan的kvs的大多數(shù)重要的設(shè)計(jì)問題岸更。
3.1 Where to Put Updates?
這里有三種可能的設(shè)計(jì)方式來(lái)實(shí)現(xiàn)updates(put, delete和insert)：update-in-place, log-structured, and delta-main婚肆。
update-in-place是大多數(shù)關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)所采用的方式。新的記錄(insert)存儲(chǔ)在已存在的空閑頁(yè)上坐慰，更新已有記錄(puts or deletes)通過在原有記錄的地方進(jìn)行覆蓋寫來(lái)實(shí)現(xiàn)。如果記錄是fixed用僧，這種方式是很好的结胀，因?yàn)檫@樣幾乎就不會(huì)有碎片產(chǎn)生。然而责循，這種方式對(duì)于多版本維護(hù)是tricker的糟港。如果多版本數(shù)據(jù)是在原地進(jìn)行維護(hù)，則會(huì)引起明顯的存儲(chǔ)空間碎片和失去局部性院仿。這種方式的另一個(gè)問題是限制來(lái)并發(fā)：為了創(chuàng)建一條記錄的新版本秸抚，整個(gè)page都要被latched（與鎖的區(qū)別？歹垫？）（a latch是lock-term的鎖剥汤，一旦page被更新完就可以釋放）。
Log-structured的存儲(chǔ)設(shè)計(jì)第一次被提出是在文件系統(tǒng)的應(yīng)用中【40】排惨。這種方式被一些kvs所使用吭敢，例如RAMCloud。主要想法是通過追加寫的方式實(shí)現(xiàn)所有的update操作暮芭。 Log-structured的存儲(chǔ)有兩個(gè)重要的優(yōu)勢(shì)：(1) 不會(huì)有空間碎片產(chǎn)生鹿驼。(2)不會(huì)有并發(fā)問題欲低，因?yàn)樽芳訉懣梢砸砸环N不阻塞的方式實(shí)現(xiàn)【29】。一個(gè)主要的缺點(diǎn)是如果沒有做優(yōu)化的話畜晰，對(duì)于scan是很費(fèi)的砾莱，scan需要讀舊版本的數(shù)據(jù)。而且凄鼻，如果一個(gè)記錄很少被更新腊瑟，是很難去做舊版本回收的。一個(gè)被稱為L(zhǎng)SM-Tree的數(shù)據(jù)結(jié)構(gòu)被用在LevelDB [23], RocksDB [16], and Kudu [19]中野宜。這種變體會(huì)定期重組數(shù)據(jù)來(lái)提升讀的性能扫步。
第三種方式delta-main，是被SAP Hana所提出的【17】匈子，也被用在幾個(gè)research 工作中河胎，例如AIM【10】。這種方式以一種寫優(yōu)化的數(shù)據(jù)結(jié)構(gòu)來(lái)收集所有的update請(qǐng)求(called delta)虎敦，并且以一種讀優(yōu)化的數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)大部分的數(shù)據(jù)(called main)游岳。這兩種數(shù)據(jù)結(jié)構(gòu)會(huì)定期的進(jìn)行merge，這種方式嘗試將log-structed的優(yōu)點(diǎn)(fast get/put)和update-in-place(fast scan)的優(yōu)點(diǎn)結(jié)合起來(lái)其徙。
3.2 How to Arrange Records?
最流行的兩種設(shè)計(jì)方式是row-major和column-major胚迫。row-major以連續(xù)的字節(jié)流方式將數(shù)據(jù)存儲(chǔ)在頁(yè)中[24]，這種布局通常對(duì)于get/put在整條記錄上很有效唾那。column-major將數(shù)據(jù)垂直分區(qū)访锻，將表的整列存儲(chǔ)為連續(xù)的字節(jié)流。這種column-major組織方式對(duì)于分析型的query是有益的闹获，這種query經(jīng)常會(huì)涉及到scan列的一個(gè)子集[25, 3, 2, 45, 9, 8]期犬。另外，column-major支持向量操作(SIMD)來(lái)加速批量操作和在現(xiàn)代硬件上的scan [47, 49]避诽。一種column-major的變體稱作PAX[5]龟虎，在每個(gè)page中存儲(chǔ)多條記錄，而在頁(yè)內(nèi)沙庐，所有的記錄以一種column-major的方式存儲(chǔ)鲤妥。PAX是一個(gè)在純列向設(shè)計(jì)和行向設(shè)計(jì)之間很好的折中。
Column-major在定長(zhǎng)的value上表現(xiàn)比較好拱雏。這就是state-of-the-art系統(tǒng)避免使用變長(zhǎng)值的原因棉安，要么簡(jiǎn)單的不允許使用它們(as AIM[10)，要么使用在堆上分配內(nèi)存铸抑，存儲(chǔ)對(duì)應(yīng)指針的方式(as in MonetDB [8] and HyPer [33])垂券，或者用一個(gè)字典并存儲(chǔ)固定大小的字典代碼(as e.g. in SAP/HANA [18] and DB2/BLU [39]))。
3.3 How to Handle Versions?
如第二部分所描述的，我們需要支持記錄的多版本來(lái)實(shí)現(xiàn)多版本并發(fā)控制菇爪。這里有兩種主要的實(shí)現(xiàn)方式：(a) 存儲(chǔ)一條記錄的所有版本在相同的位置 (b) 將記錄的多個(gè)版本使用鏈表鏈起來(lái)算芯。第一種變體通常與update-in-place結(jié)合使用，用這種方式創(chuàng)建新版本的成本更低凳宙，但是合并頁(yè)面做垃圾回收時(shí)會(huì)花費(fèi)高昂的代價(jià)熙揍。第二種變體更適合log-structured的存儲(chǔ)，clustering versions in an append-only data structure would require a costly copy of all previous versions to the head.
鏈接記錄的指針會(huì)消耗空間氏涩，遍歷鏈表會(huì)涉及到很多cache miss也會(huì)花費(fèi)很大的代價(jià)届囚。好的一方面，第二種方式簡(jiǎn)化了垃圾回收是尖，因?yàn)樗梢砸砸环N舊版本數(shù)據(jù)日志流截?cái)嗟姆绞絹?lái)實(shí)現(xiàn)意系。而且可以減少空間的碎片化。
3.4 When to do Garbage Collection?
回收舊版本數(shù)據(jù)的方式有兩種：(a) 使用單獨(dú)的線程做周期的回收饺汹。(b) scan的過程中做piggy-back回收蛔添。方法b增加了scan的時(shí)間，但是也換回了垃圾回收的收益：相比其它table兜辞，scan頻繁從垃圾回收中受益的table會(huì)更頻繁的做垃圾回收迎瞧。piggy-back回收的另一個(gè)優(yōu)點(diǎn)是數(shù)據(jù)處理過程中隨時(shí)隨地做回收，也避免了拿取數(shù)據(jù)引起的cache miss逸吵。
3.5 Summary
table 2給出了在存儲(chǔ)效率(碎片)凶硅、并發(fā)、實(shí)現(xiàn)多版本和垃圾回收的花費(fèi)和scan扫皱、get/put操作的效率的前三個(gè)緯度之間權(quán)衡的方式足绅。第四個(gè)緯度垃圾回收正是實(shí)現(xiàn)這些性能特征的基礎(chǔ)。一個(gè)kvs的性能是由這些技術(shù)的組合所決定的韩脑∏饴瑁總而言之，構(gòu)建一個(gè)kvs總共有24種不同的方式：
(update-in-place vs. log-structured vs. delta-main)
×(row-major vs. column-major / PAX)
×(clustered-versions vs. chained-versions)
×(periodic vs. piggy-backed garbage collection)
另外扰才，還有混合的方式，例如periodic和piggy-backed回收方式可以組合實(shí)現(xiàn)厕怜。幸運(yùn)的是衩匣，僅僅只有幾種變體方式是有意義的：Log-structured方式的updates 和 列向的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)是沒有意義的，因?yàn)槊黠@“delta-main & column-major”的組合方式更有效粥航。另外“l(fā)og-structured & chained-version”的方式明顯比"log-structured & clustered-versions"更優(yōu)琅捏。
這其中最有的兩個(gè)組合方式是log- structured with chained-versions in a row-major的方式和使用delta-main的數(shù)據(jù)結(jié)構(gòu)with clustered-versions in a column-major的格式。接下來(lái)的兩個(gè)章節(jié)將會(huì)描述我們使用這兩種方式在TellStore上的實(shí)現(xiàn)递雀，叫做TellStore-Log 和 TellStore-Col柄延。 第六章給出了TellStore的實(shí)現(xiàn)細(xì)節(jié)，對(duì)于所有的TellStore的變體都是很重要的。第七章包含了通過比較不同變體之間的權(quán)衡得出的性能評(píng)估搜吧，使用已存在的一些kvs作為baseline市俊。出了tellstore-log和tellstore-col，第七章節(jié)包含了第三種變體的結(jié)果滤奈，tellstore-row摆昧，與tellstore-col是相似的，但是使用row-major的存儲(chǔ)格式可以更好的研究對(duì)于混合oltp/olap的負(fù)載權(quán)衡行存和列存蜒程。
4. TELLSTORE-LOG
TellStore-Log的實(shí)現(xiàn)由RAMCloud所啟發(fā)绅你，并加入了新的修改以支持有效的scan。
Where to Put Updates?
Figure 2描述了TellStore-Log的主要數(shù)據(jù)結(jié)構(gòu)：詳細(xì)描述了記錄的布局(kv對(duì))以及使用hashtable來(lái)索引日志中的記錄昭躺。日志本身是被分為多個(gè)片段使用鏈表鏈起來(lái)的多個(gè)pages來(lái)存儲(chǔ)所有的kv對(duì)忌锯。
日志是使用追加寫的數(shù)據(jù)結(jié)構(gòu)：內(nèi)存分配以一種無(wú)鎖的方式自動(dòng)增加到page的頭部。一旦記錄追加到日志中领炫，將變?yōu)椴豢勺兊呐伎濉＿@個(gè)屬性使得恢復(fù)和復(fù)制日志變得簡(jiǎn)單，因?yàn)閺?fù)制過程只需要監(jiān)視頭部驹吮。因?yàn)闊o(wú)鎖的特性针史，相同key的記錄可以并發(fā)的追加到日志中。哈希表始終是同步點(diǎn)碟狞，一條記錄只有等指向它的指針成功地插入或者更新到哈希表中才認(rèn)為生效啄枕。以防沖突，數(shù)據(jù)變?yōu)閕mmutable之前在日志中是無(wú)效的狀態(tài)族沃。delete以一種特殊標(biāo)記的沒有數(shù)據(jù)的update的形式被寫入频祝。
hashtable使用鎖實(shí)現(xiàn)會(huì)變成性能點(diǎn)。并發(fā)無(wú)鎖的hashtable設(shè)計(jì)對(duì)于特定的路徑是一種常用的優(yōu)化手段脆淹。尤其常空，在實(shí)現(xiàn)擴(kuò)容時(shí)面臨點(diǎn)查和update性能的權(quán)衡。TellStore預(yù)先分配一個(gè)定長(zhǎng)大小的hashtable盖溺，為所有在存儲(chǔ)節(jié)點(diǎn)上的表共同使用漓糙。實(shí)現(xiàn)上采用線性探測(cè)的開放尋址算法以解決數(shù)據(jù)沖突的問題。不利的是烘嘱，開放尋址在高負(fù)載下往往表現(xiàn)不佳昆禽。為了節(jié)省內(nèi)存以使得可以使用較小的內(nèi)存保存更大的表，哈希表只記錄表的id蝇庭、記錄的key和指向記錄的指針醉鳖。
How to Arrange Records?
追加寫的方式本質(zhì)上與行向存儲(chǔ)結(jié)構(gòu)相關(guān)聯(lián)。為了支持有效的scan哮内，日志中的記錄必須是完全獨(dú)立的盗棵。我們尤其想要避免去哈希表中查找來(lái)確定一條記錄是否有效(沒有被delete或者覆蓋寫)。這個(gè)約束對(duì)版本控制有一些影響，將在下一節(jié)中提到纹因。
TellStore-Log在存儲(chǔ)節(jié)點(diǎn)上為每個(gè)表分配一段單獨(dú)的log喷屋。這使得scan可以只處理相關(guān)的pages，提高了數(shù)據(jù)的局部性辐怕。sca對(duì)有效的記錄的數(shù)量是敏感的逼蒙，這對(duì)局部性的要求有影響，4.4節(jié)將會(huì)提到寄疏。
4.3 How to Handle Versions?
日志的不可變性使得一條記錄的新版本只能追加到日志的頭部是牢。為了能夠定位到舊版本的數(shù)據(jù)，我們?cè)诿總€(gè)記錄旁邊存儲(chǔ)指向前一個(gè)版本的指針來(lái)形成多版本鏈陕截。另外事務(wù)為每條記錄分配一個(gè)時(shí)間戳保存在元信息中驳棱，多版本的鏈表總是根據(jù)snapshot由新到舊嚴(yán)格排序的，哈希表總是指向最新的記錄农曲。給定一個(gè)snapshot社搅，get請(qǐng)求會(huì)沿著鏈表查找直到遇到第一個(gè)滿足條件的記錄。遍歷鏈表涉及到cache miss的代價(jià)乳规，與fast put是一種權(quán)衡形葬。
這種設(shè)計(jì)看起來(lái)是與所有數(shù)據(jù)都必須獨(dú)立的要求是矛盾的：當(dāng)scan日中中記錄時(shí)，只有記錄的時(shí)間戳可以拿到暮的，不能判斷是否數(shù)據(jù)是過期了的笙以。為了避免哈希表的查找，我們?yōu)槊織l記錄在元信息中增加了過期的時(shí)間戳((valid-to)作為不可變字段冻辩。一條記錄被成功寫之后猖腕，舊版本的記錄的valid-to將會(huì)更新（lazily updated）為新版本的valid-to。給定一個(gè)snapshot, scan 可以通過比較兩個(gè)時(shí)間戳來(lái)確定記錄是否滿足條件恨闪。
哈希表仍然是唯一的同步點(diǎn)倘感，始終指向最新的元素。更新哈希表和設(shè)置valid to字段之間沒有競(jìng)爭(zhēng)條件咙咽，TellStore的SI實(shí)現(xiàn)不能確保在線事務(wù)的可見性(???)老玛。
When to do Garbage Collection?
scan的性能被不再被任何活躍事務(wù)所看見的過期數(shù)據(jù)的數(shù)量所影響。為了更頻繁合并那些經(jīng)常被scan的table钧敞，垃圾回收放在正常scan的一部分中蜡豹。掃描一個(gè)頁(yè)面時(shí)，其運(yùn)行狀況按照頁(yè)面中有效記錄的數(shù)量與總記錄數(shù)量的比率來(lái)計(jì)算犁享，一旦該值降到某個(gè)閥值以下余素，頁(yè)面將會(huì)被標(biāo)記為垃圾回收豹休。被標(biāo)記的頁(yè)面將在下一次scan時(shí)將剩余有效數(shù)據(jù)copy到log的頭部并將回收后的頁(yè)面放入空閑頁(yè)面的池子中炊昆。一條記錄被copy到日志頭部之后，該鍵的多版本鏈的指針需要重新調(diào)整。為此凤巨，我們需要查找哈希表视乐，沿著版本鏈找到正確的位置。這個(gè)操作由于很差的緩存局部性而成本高昂敢茁。為了從非頻繁掃描的表中回收空間佑淀，由后臺(tái)線程定期去掃描回收。
Summary
盡管Ramcloud是日志結(jié)構(gòu)kvs的典型實(shí)現(xiàn)彰檬，但其scan性能較差伸刃。同時(shí)構(gòu)建一個(gè)支持快速get/put請(qǐng)求、版本控制和scan的log-structed kvs是可能的逢倍。主要的要點(diǎn)是日志中多版本的仔細(xì)組織捧颅、有效的垃圾回收策略、延遲的元信息/時(shí)間戳實(shí)現(xiàn)來(lái)使得記錄獨(dú)立较雕，無(wú)鎖算法和良好的工程設(shè)計(jì)碉哑。
TELLSTORE-COL
TellStore-Col采用delta-main方式的核心理念，維護(hù)兩種數(shù)據(jù)結(jié)構(gòu)：main for read, delta for update亮蒋。如Figure3所示扣典，我們的實(shí)現(xiàn)實(shí)際涉及到4種數(shù)據(jù)結(jié)構(gòu)：page list用來(lái)維護(hù)主要的數(shù)據(jù)，兩個(gè)log存儲(chǔ)delta(一個(gè)for insert, 一個(gè)for update)和一個(gè)哈希表來(lái)索引數(shù)據(jù)慎玖。
5.1 Where to Put Updates?
除了查詢?cè)畔⒆侄沃猓趍ain中的數(shù)據(jù)只用于read，所有update都被寫入一個(gè)追加寫的存儲(chǔ)中凄吏。與TellStore-Log不同远舅，delta被分成兩個(gè)獨(dú)立的log:update已存在的記錄被寫到update-log中，update不存在的記錄被寫到insert-log中痕钢。如第5.4節(jié)所示图柏，這種分離使得從delta構(gòu)建main更容易。索引中保留了一個(gè)標(biāo)志位來(lái)標(biāo)示指針指向delta或者main任连。除了這個(gè)標(biāo)志位瘟檩，索引表使用與TellStore-Log相同的哈希表。
