【摘要】：鍵值存儲(chǔ)是現(xiàn)代存儲(chǔ)系統(tǒng)的重要組成部分,由于LSM-tree數(shù)據(jù)結(jié)構(gòu)針對(duì)磁盤的隨機(jī)寫做了優(yōu)化,大幅度提升了鍵值存儲(chǔ)系統(tǒng)的寫性能,因此基于LSM-tree的鍵值存儲(chǔ)成為主流。為了克服LSM-tree在讀寫操作中仍然產(chǎn)生較高的讀寫放大現(xiàn)象,進(jìn)一步發(fā)展成為采用鍵值分離的鍵值存儲(chǔ)系統(tǒng)。然而,采用鍵值分離的鍵值存儲(chǔ)系統(tǒng)在更新密集型工作負(fù)載下會(huì)頻繁的觸發(fā)垃圾回收(GC)操作,導(dǎo)致其無(wú)法實(shí)現(xiàn)較高性能。針對(duì)上述問(wèn)題,設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)無(wú)需GC的鍵值分離存儲(chǔ)系統(tǒng),該系統(tǒng)通過(guò)對(duì)失效數(shù)據(jù)的有效管理,實(shí)現(xiàn)就地更新,從而消除存儲(chǔ)過(guò)程中的垃圾回收操作,避免存儲(chǔ)系統(tǒng)中有效數(shù)據(jù)的頻繁重寫,減少系統(tǒng)的寫放大,提升系統(tǒng)的性能。首先,通過(guò)收集、管理和復(fù)用失效數(shù)據(jù)索引對(duì)失效數(shù)據(jù)實(shí)現(xiàn)就地更新、覆蓋回收,去除GC過(guò)程,避免了由于GC而產(chǎn)生的開銷。其次,實(shí)現(xiàn)失效索引管理模塊,并通過(guò)構(gòu)建生產(chǎn)者-消費(fèi)者模型,對(duì)該模塊進(jìn)行優(yōu)化,使其在系統(tǒng)中能夠靈活高效的實(shí)現(xiàn)失效數(shù)據(jù)的管理、復(fù)用,為系統(tǒng)去除GC操作提供了基礎(chǔ)保障。最后,通過(guò)邏輯設(shè)計(jì)為數(shù)據(jù)的就地更新寫入方式提供了更新一致性的保證,同時(shí)通過(guò)增加、管理操作日志,實(shí)現(xiàn)了系統(tǒng)崩潰后的數(shù)據(jù)恢復(fù),避免了數(shù)據(jù)丟失。測(cè)試表明,無(wú)需GC的鍵值分離存儲(chǔ)系統(tǒng)可以有效減少系統(tǒng)寫入量,在更新密集型工作負(fù)載下,相比于現(xiàn)有的鍵值分離的鍵值存儲(chǔ)系統(tǒng)WiscKey和HashKV,本系統(tǒng)可以減少30%~50%的寫入量,從而減小系統(tǒng)寫放大。本系統(tǒng)去除了GC過(guò)程,使寫性能得到了提升,同時(shí),系統(tǒng)性能也不會(huì)受到預(yù)留空間大小和鍵值對(duì)數(shù)據(jù)大小的影響。
【圖文】：

隨機(jī)訪問(wèn)未排序的 value。第三，WiscKey 特別設(shè)計(jì)了崩潰一致性和垃圾回收技術(shù)，能夠有效管理 value 的保存日志文件，增強(qiáng)系統(tǒng)的可靠性。第四，WiscKey 在不犧牲一致性的條件下通過(guò)刪除 LSM-tree 日志來(lái)優(yōu)化性能，從而減少寫入帶來(lái)的系統(tǒng)調(diào)用開銷。在現(xiàn)代鍵值存儲(chǔ)工作負(fù)載中，key 通常很小（例如，16B），但是 value 的大小遠(yuǎn)大于 key 的大�。ɡ�，100B 到大于 4KB），而 WiscKey 旨在為此類工作負(fù)載提供更高的讀寫性能。WiscKey 是一個(gè)衍生于 LevelDB 的單機(jī)的持久化鍵值存儲(chǔ)系統(tǒng)，它可以作為關(guān)系型數(shù)據(jù)庫(kù)（如 MySQL）或分布式鍵值存儲(chǔ)（如 MongoDB）的存儲(chǔ)引擎，它提供了與 LevelDB相同的 API，包括Put(key, value)、Get(key)、Delete(key)和 Scan(start, end)。WiscKey 的體系結(jié)構(gòu)如圖 2-1 所示，這個(gè)圖顯示了 WiscKey 在單個(gè) SSD 設(shè)備上的數(shù)據(jù)布局，key 和 value 的地址存儲(chǔ)在 LSM-tree 中，而 value 追加寫入到單獨(dú)的日志文件中。

將類似于 tuple(key size, value size, key, value)這樣的結(jié)構(gòu)存儲(chǔ)在 Value Log 中，，如2 所示，這個(gè)圖顯示了 WiscKey 的新數(shù)據(jù)布局，以支持有效的垃圾回收。Wisc垃圾回收旨在將有效值（不對(duì)應(yīng)于已刪除的鍵）保存在 Value Log 的連續(xù)范圍圖 2-2 所示，這個(gè)范圍的一端用 head 指針標(biāo)記，總是與 Value Log 的末尾相對(duì)新的數(shù)據(jù)值添加到 Value Log 的末尾時(shí)，都會(huì)追加寫入到 head 指針的位置，而范圍的另一端是 tail 指針，每當(dāng)觸發(fā)垃圾回收時(shí)，它就開始釋放空間，只有垃圾線程會(huì)更改 tail 指針。所有有效值的地址范圍都處于 head 和 tail 之間，為了查能夠快速搜索，head 和 tail 指針被保存在內(nèi)存中，并持久化存儲(chǔ)到 LSM-tree 中�；厥�?qǐng)?zhí)行時(shí)，WiscKey 首先從 Value Log 的 tail 指針處讀取一系列鍵值對(duì)（例如個(gè) MB），然后通過(guò)查詢 LSM-tree 判斷哪些是還沒(méi)有被重寫或刪除的有效值，有效值追加到 Value Log 的 head 指針處，最后，更新 tail 指針，釋放所讀取鍵值據(jù)的空間。
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP333

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 徐逸文;方鈺;陳閎中;;一種處理B~+樹重復(fù)鍵值的方法[J];計(jì)算機(jī)工程;2009年05期

2 楊小小;;在重啟中被替換的鍵值[J];辦公自動(dòng)化;2007年01期

3 楊小小;;在重啟中被替換的鍵值[J];電腦知識(shí)與技術(shù)(經(jīng)驗(yàn)技巧);2007年01期

4 楊小小;;重啟中被替換的鍵值[J];辦公自動(dòng)化;2007年08期

5 盧僑生;;一個(gè)鍵值讓文件在重啟過(guò)程中替換[J];電腦愛好者;2006年21期

6 史軍絨;Windows2000注冊(cè)表鍵值類型的探索[J];現(xiàn)代情報(bào);2005年06期

7 王祿;;多鍵值字符串鍵樹的原理及實(shí)現(xiàn)[J];電腦知識(shí)與技術(shù)(學(xué)術(shù)交流);2007年02期

8 劉曉;;大數(shù)據(jù)環(huán)境下分布式鍵值系統(tǒng)的架構(gòu)研究[J];中國(guó)金融電腦;2015年06期

9 孫洪秋;刪除相關(guān)鍵值巧裝超級(jí)解霸[J];電腦愛好者;2001年24期

10 蔣天發(fā);蔣巍;王維虎;熊祥光;;基于轉(zhuǎn)換鍵值的非對(duì)稱數(shù)字水印算法[J];信息安全與技術(shù);2010年08期

相關(guān)會(huì)議論文 前3條

1 翁曉毅;劉曉平;程磊;;三維曲面的鍵值函數(shù)定義及計(jì)算研究[A];全國(guó)第十五屆計(jì)算機(jī)科學(xué)與技術(shù)應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2003年

2 袁錦繡;錢雪忠;汪錦嶺;;一種基于位置和DHT的移動(dòng)ad hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)方案[A];2006年全國(guó)開放式分布與并行計(jì)算學(xué)術(shù)會(huì)議論文集（一）[C];2006年

3 張智江;王志軍;張尼;;一種可應(yīng)用于大流量環(huán)境下的雙層散列算法研究[A];中國(guó)通信學(xué)會(huì)信息通信網(wǎng)絡(luò)技術(shù)委員會(huì)2011年年會(huì)論文集（下冊(cè)）[C];2011年

相關(guān)重要報(bào)紙文章 前10條

1 王林穎 陳佳佳;一鍵值守48小時(shí)[N];中國(guó)航天報(bào);2019年

2 編譯 沈建苗;鍵值數(shù)據(jù)存儲(chǔ)未來(lái)會(huì)流行嗎?[N];計(jì)算機(jī)世界;2015年

3 山東 郭忠勇;注冊(cè)表禁用30項(xiàng)[N];電腦報(bào);2001年

4 上海 SNSN;自由操控MSN Messanger的啟動(dòng)[N];電腦報(bào);2002年

5 章海峰;排名新方法：無(wú)比排序[N];電腦報(bào);2001年

6 江蘇 飛浪;Windows NT 4.0操作技巧16則[N];電腦報(bào);2001年

7 江蘇 周勇生;Windows NT 4.0應(yīng)用精粹（一）[N];中國(guó)計(jì)算機(jī)報(bào);2001年

8 福建 柳堅(jiān);讓“我的電腦”不再受“壓迫”[N];電腦報(bào);2002年

9 陳彪;設(shè)置自動(dòng)刷新窗口[N];中國(guó)電腦教育報(bào);2000年

10 山西 閆錦鋒;找回失去的登錄窗口[N];電腦報(bào);2002年

相關(guān)博士學(xué)位論文 前4條

1 徐辰;鍵值存儲(chǔ)系統(tǒng)中的質(zhì)量感知調(diào)度[D];華東師范大學(xué);2014年

2 張凱;基于多核/眾核體系結(jié)構(gòu)構(gòu)建高性能網(wǎng)絡(luò)系統(tǒng)的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2016年

3 黃玉龍;基于GPU的查詢技術(shù)并行化研究[D];華南理工大學(xué);2013年

4 趙楠楠;分布式鍵值存儲(chǔ)系統(tǒng)高效能數(shù)據(jù)布局技術(shù)研究[D];華中科技大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 楊李楊;基于分布式流處理系統(tǒng)的分組策略研究[D];哈爾濱工業(yè)大學(xué);2019年

2 李娟;基于Key-Value的大容量SSD閃存轉(zhuǎn)換層的研究與實(shí)現(xiàn)[D];國(guó)防科技大學(xué);2017年

3 馮小川;云存儲(chǔ)中鍵值型數(shù)據(jù)庫(kù)訪問(wèn)模式保護(hù)的研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2019年

4 馮淇;基于LSM-Tree的鍵值存儲(chǔ)引擎的優(yōu)化研究與實(shí)現(xiàn)[D];華中科技大學(xué);2019年

5 張大年;面向內(nèi)存分區(qū)的自適應(yīng)鍵值數(shù)據(jù)庫(kù)[D];華中科技大學(xué);2019年

6 吳海源;基于DRAM-NVM混合內(nèi)存的持久化鍵值存儲(chǔ)系統(tǒng)研究[D];華中科技大學(xué);2019年

7 林立亞;無(wú)垃圾回收的鍵值分離存儲(chǔ)系統(tǒng)優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)[D];華中科技大學(xué);2019年

8 胡澤鑫;基于非易失內(nèi)存的混合鍵值存儲(chǔ)系統(tǒng)的研究與實(shí)現(xiàn)[D];華中科技大學(xué);2019年

9 孟嘉豪;一種面向鍵值對(duì)存儲(chǔ)系統(tǒng)的高效數(shù)據(jù)遷移機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)[D];華中科技大學(xué);2019年

10 王成;基于RDMA的鍵值存儲(chǔ)系統(tǒng)性能優(yōu)化[D];南京大學(xué);2019年

本文編號(hào)：2696319