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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 王林穎 陳佳佳;一鍵值守48小時[N];中國航天報;2019年

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

3 山東 郭忠勇;注冊表禁用30項[N];電腦報;2001年

4 上海 SNSN;自由操控MSN Messanger的啟動[N];電腦報;2002年

5 章海峰;排名新方法：無比排序[N];電腦報;2001年

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

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

8 福建 柳堅;讓“我的電腦”不再受“壓迫”[N];電腦報;2002年

9 陳彪;設(shè)置自動刷新窗口[N];中國電腦教育報;2000年

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

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

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

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

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

4 趙楠楠;分布式鍵值存儲系統(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)換層的研究與實現(xiàn)[D];國防科技大學(xué);2017年

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

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

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

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

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

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

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

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

本文編號：2696319