??前篇文章對LSM的基本原理，演算法流程做了簡單的介紹，這篇文章將實作一個簡單的基于LSM演算法的迷你Key-Value資料庫，結合上篇文章的理論與本篇文章的實踐使之對LSM演算法有更好的理解，當然此版本還有很大問題只是Demo模型，后面也會指出；
??此LSMDB有支持常見的資料庫四大功能：CURD（增刪查改），從前篇文章可知要實作基于LSM的資料庫此程式中需存在這么幾種資料結構：memTable、immutable、SSTable、WAL，分別為記憶體表、只讀記憶體表、排序字串表、預寫式日志，將這幾種資料結構組合起來即可實作一個簡單的Key-Value資料庫；
結構介紹
??MemTable： 記憶體表，此結構為一個有序的記憶體結構此處是一個紅黑樹，當資料達到指定的閾值時會發出刷盤操作，將MemTable拷貝到Immutable生成SSTable，MemTable開始新的周期；
??Immutable： 只讀記憶體表，為避免MemTable在刷盤操作時繼續有新的入庫操作導致出現資料例外情況，引入了此結構使之簡單化，在觸發刷盤操作時將MemTable資料拷貝到此只讀結構，清空MemTable，將Immutable資料生成SSTable，清空Immutable；
??SSTable： 為immutable持久化到磁盤后的排序字串表；
??WAL： 為避免MemTable資料還未持久化SSTable到磁盤程式崩潰導致資料丟失的情況引入的，WAL為順序寫入日志，在接收到資料時添加到MemTable的同時將資料寫入到WAL檔案中，資料刷盤持久化的同時將WAL檔案洗掉，新創建WAL檔案，本篇文章暫未實作；
??觸發SSTable持久化到磁盤時會生成兩個檔案，一個為SSTable檔案由兩部分組成資料區與元資料，資料區為所存盤的值，元資料為資料與索引的開始Offset、長度組成；另一個為索引檔案：索引檔案記錄了每個Key的起始Offset與長度；
SSTable檔案結構：
SSTable索引檔案結構：
具體實作
加載SSTable檔案
??在程式啟動時會初始化上面提到到LSM相關結構，同時檢查目錄是否存在SSTable檔案，存在則從新到舊掃描加載每個SSTable檔案的元資料，根據其元資料加載SSTable索引檔案到記憶體中，
/**
還原索引
*/
func (s *SSTable) restoreIndex() {
s.meta.readFormFile(s.dataFile)
len := s.meta.indexLen
offset := s.meta.indexStart
s.indexFile.Seek(int64(offset), 0)
b := make([]byte, len)
s.indexFile.Read(b)
s.indexTree.FromJSON(b)
}
寫入操作
??LSMDB在執行寫操作時會先寫入到記憶體表memoryTable，當memoryTable大小超過某個閾值時會執行切換記憶體表，將memoryTable資料拷貝到immuTable，清空memoryTable，執行持久化寫入SSTable，清空immuTable；
/**
設定鍵值
*/
func (l *LSMStore) Set(key string, value string) {
var cmd = &SetCommand{Command{1}, key, value}
//todo 寫入wal
//寫入記憶體表
l.memoryTable.Put(key, cmd)
if l.memoryTable.Size() > storeThreshold {
l.switchTable()
l.toSSTable()
}
}
洗掉資料
??LSMDB資料庫中的洗掉并不是真正的洗掉，只是追加一條相同Key標志位為洗掉的資料，在讀取時再做相應的處理，其他流程與添加類似；
/**
洗掉資料
*/
func (l *LSMStore) Del(key string) {
var cmd = &RMCommand{Command{2}, key}
//todo 寫入wal
//寫入記憶體表
l.memoryTable.Put(key, cmd)
if l.memoryTable.Size() > storeThreshold {
l.switchTable()
l.toSSTable()
}
}
讀取資料
??讀取資料時會先檢查memoryTable是否有資料，沒有則檢查immuTable是否存在，最后會依次檢查所加載的SSTable索引是否存在，如存在則根據索引執行的Offset、len從SSTable檔案讀取相對應的內容資料；
/**
獲取資料
*/
func (l *LSMStore) Get(key string) interface{} {
cmd, found := l.memoryTable.Get(key)
log.Println("memory：", found, cmd)
if found {
if v, ok := cmd.(*SetCommand); ok {
return v.Value
}
}
if l.immuTable != nil && l.immuTable.Size() > 0 {
cmd, found := l.immuTable.Get(key)
if found {
if v, ok := cmd.(*SetCommand); ok {
return v.Value
}
}
} else {
for _, t := range l.sstableList.Values() {
table := t.(*SSTable)
v := table.query(key)
return v
}
}
return nil
}
WebApi
開放用于查詢、添加、洗掉的RESTFUL格式api：
查詢： http://localhost:8080/lsmdb/{key}
添加： http://localhost:8080/lsmdb/{key}
{"key":"211213","value":"aaaaaaaa"}
洗掉： DELETE http://localhost:8080/lsmdb/{key}
目前存在的問題
??目前此版本的實作還有多處都有問題，也是后續版本需改進的地方：
??1、此處的索引檔案為全量索引，為每個key都記錄相應的資料，此處的索引檔案大小是非常大的，對性能影響很大；
??2、此版本沒有實作WAL功能程式崩潰時資料丟失；
??3、此版本并沒有后臺執行SSTable合并功能，沒有對修改、洗掉操作做任何處理，只是在查詢時做了相應的忽略操作，影響性能；
??4、單機版本不是分布式程式
文章首發地址：https://mp.weixin.qq.com/s/HoRjSMYumG4A40kHn5UKvQ
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/387680.html
標籤：Go
上一篇：中國象棋程式設計（五）置換表