Artikel ini akan membimbing anda melalui pemahaman Log-Structured Merge-Tree (LSM-Tree), termasuk konsep teras dan strukturnya. Pada akhirnya, anda akan dapat membina enjin storan anda sendiri berdasarkan LSM-Tree dari awal.
Pokok Gabungan Berstruktur Log (LSM-Tree) ialah struktur data yang dioptimumkan untuk operasi tulis throughput tinggi. Ia digunakan secara meluas dalam pangkalan data dan sistem storan, seperti Cassandra, RocksDB dan LevelDB.
Idea utama LSM-Tree ialah menulis operasi terlebih dahulu ke dalam struktur data dalam memori (biasanya struktur tersusun seperti senarai langkau atau pepohon AVL). Kemudian, tulisan ini dikumpulkan dan ditulis secara berurutan ke cakera sebagai SSTables, dengan itu meminimumkan I/O rawak.
LSM-Tree terbahagi kepada dua komponen utama:
Lazimnya, struktur SSTable merangkumi lebih daripada sekadar siri pasangan nilai kunci tersusun (blok data). Ia juga mengandungi blok indeks, blok metadata dan komponen lain. Butiran ini akan dibincangkan secara mendalam semasa bahagian pelaksanaan.
Menulis data melibatkan penambahan pasangan nilai kunci baharu atau mengemas kini pasangan sedia ada. Kemas kini menimpa pasangan nilai kunci lama, yang kemudiannya dialih keluar semasa proses pemadatan.
Apabila data ditulis, ia mula-mula pergi ke Memtable, di mana pasangan nilai kunci ditambahkan pada struktur data tertib dalam memori. Pada masa yang sama, operasi tulis dilog dalam WAL dan diteruskan ke cakera untuk mengelakkan kehilangan data sekiranya berlaku ranap pangkalan data.
Metable mempunyai ambang yang ditentukan (biasanya berdasarkan saiz). Apabila Memtable melebihi ambang ini, ia ditukar kepada mod baca sahaja dan ditukar kepada SSTable baharu, yang kemudiannya dikekalkan ke Tahap 0 pada cakera.
Setelah Memtable disiram sebagai SSTable, fail WAL yang sepadan boleh dipadamkan dengan selamat. Operasi tulis seterusnya akan diteruskan pada Memtable baharu (dan WAL baharu).
Dalam LSM-Tree, data tidak segera dialih keluar. Sebaliknya, pemadaman dikendalikan menggunakan mekanisme yang dipanggil batu nisan (serupa dengan pemadaman lembut). Apabila pasangan nilai kunci dipadamkan, entri baharu yang ditandakan dengan "batu nisan" ditulis, menunjukkan pemadaman pasangan nilai kunci yang sepadan. Penyingkiran sebenar berlaku semasa proses pemadatan.
Pemadaman berasaskan batu nisan ini memastikan sifat tambah sahaja LSM-Tree, mengelakkan I/O rawak dan mengekalkan penulisan berurutan pada cakera.
Proses menanyakan data bermula dengan carian dalam Memtable. Jika pasangan nilai kunci ditemui, ia dikembalikan kepada klien. Jika pasangan nilai kunci bertanda batu nisan ditemui, ini menunjukkan bahawa data yang diminta telah dipadamkan dan maklumat ini juga dikembalikan. Jika kunci tidak ditemui dalam Memtable, pertanyaan diteruskan untuk mencari SSTables dari Tahap 0 hingga Tahap N.
Memandangkan data pertanyaan mungkin melibatkan pencarian berbilang fail SSTable dan boleh membawa kepada I/O cakera rawak, LSM-Tree biasanya lebih sesuai untuk beban kerja berat tulis berbanding beban kerja intensif baca.
Satu pengoptimuman biasa untuk prestasi pertanyaan ialah penggunaan penapis Bloom. Penapis Bloom boleh menentukan dengan cepat sama ada pasangan nilai kunci wujud dalam SSTable tertentu, mengurangkan I/O cakera yang tidak diperlukan. Selain itu, sifat disusun SSTables membolehkan algoritma carian yang cekap, seperti carian binari, digunakan untuk carian yang lebih pantas.
Di sini, kami memperkenalkan Strategi Pemadatan Bertingkat, yang digunakan oleh LevelDB dan RocksDB.
Satu lagi strategi biasa ialah Strategi Pemadatan Berperingkat Saiz, di mana SSTable yang lebih baharu dan lebih kecil digabungkan secara berturut-turut menjadi SSTable yang lebih lama dan lebih besar.
Seperti yang dinyatakan sebelum ini, SSTable menyimpan satu siri entri yang diisih mengikut kekunci. Dalam Strategi Pemadatan Bertingkat, SSTables disusun ke dalam berbilang peringkat (Tahap 0 hingga Tahap N).
Dalam Tahap 0, SSTables boleh mempunyai julat kekunci yang bertindih, kerana ia terus dipadamkan daripada Memtable. Walau bagaimanapun, dalam Tahap 1 hingga N, SSTables dalam tahap yang sama tidak mempunyai julat kekunci bertindih, walaupun julat kekunci bertindih dibenarkan antara SSTable dalam tahap yang berbeza.
Contoh ilustrasi (walaupun tidak sepenuhnya tepat) ditunjukkan di bawah. Dalam Tahap 0, julat utama SSTable pertama dan kedua bertindih, manakala dalam Tahap 1 dan Tahap 2, SSTables dalam setiap tahap mempunyai julat kunci terputus . Walau bagaimanapun, SSTable antara tahap yang berbeza (cth., Tahap 0 dan Tahap 1, atau Tahap 1 dan Tahap 2) mungkin mempunyai julat utama yang bertindih.
Sekarang mari kita terokai cara Strategi Pemadatan Bertingkat mengekalkan struktur organisasi ini.
Memandangkan Tahap 0 ialah kes khas, perbincangan strategi pemadatan dibahagikan kepada dua bahagian:
Perbezaan utama antara pemadatan Tahap 0 hingga Tahap 1 dan pemadatan Tahap N hingga Tahap N 1 (N > 0) terletak pada pemilihan SSTables pada tahap yang lebih rendah (Tahap 0 atau Tahap N).
Proses pemadatan dan penggabungan berbilang SST boleh digambarkan di bawah. Semasa penggabungan, hanya nilai terkini untuk setiap kunci dikekalkan. Jika nilai terkini mempunyai penanda "batu nisan", kunci dipadamkan. Dalam pelaksanaan, kami menggunakan algoritma gabungan k-way untuk melaksanakan proses ini.
Adalah penting untuk ambil perhatian bahawa perihalan proses pemadatan di atas hanya memberikan gambaran keseluruhan peringkat tinggi. Banyak butiran perlu ditangani semasa pelaksanaan sebenar.
Sebagai contoh, dalam LevelDB, apabila membina SSTable baharu untuk Tahap N 1 semasa pemadatan, jika SSTable baharu bertindih dengan lebih daripada 10 SSTable dalam Tahap N 2, proses bertukar kepada membina SSTable lain. Ini mengehadkan saiz data yang terlibat dalam satu pemadatan.
Berdasarkan gambaran keseluruhan LSM-Tree di atas, saya percaya anda kini mempunyai pemahaman asas tentang LSM-Tree dan beberapa idea tentang pelaksanaannya. Seterusnya, kami akan membina enjin storan berasaskan LSM-Tree dari awal. Di bawah, kami akan memperkenalkan hanya kod teras; untuk kod lengkap, sila rujuk https://github.com/B1NARY-GR0UP/originium.
Kami akan memecahkan pelaksanaan LSM-Tree kepada komponen teras berikut dan melaksanakannya satu demi satu:
Dalam proses memperkenalkan penulisan data, kami menyebut bahawa LSM-Tree mula-mula menulis data ke dalam struktur data tertib dalam memori. Beberapa struktur data tertib biasa dan kerumitan masa operasinya adalah seperti berikut:
| Data Structure | Insert | Delete | Search | Traverse |
|---|---|---|---|---|
| Skip List | O(logn) | O(logn) | O(logn) | O(n) |
| AVL Tree | O(logn) | O(logn) | O(logn) | O(n) |
| Red-Black Tree | O(logn) | O(logn) | O(logn) | O(n) |
Kami memilih Senarai Langkau untuk dua sebab utama: ia lebih mudah untuk dilaksanakan dan diselenggara (prinsip KISS), dan struktur senarai terpaut asas memudahkan traversal berjujukan, menjadikannya lebih mudah untuk mengekalkan data dalam memori ke cakera.
Pelaksanaan lengkap Senarai Langkau tersedia di https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go .
Senarai Langkau terdiri daripada senarai terpaut asas dan berbilang peringkat indeks yang dibina di atasnya. Untuk set data yang besar, lapisan indeks memendekkan laluan carian dengan ketara.
Dalam pelaksanaan kami, struktur teras Senarai Langkau ditakrifkan seperti berikut:
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Struktur elemen yang disimpan dalam Senarai Langkau ditakrifkan seperti berikut:
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
jenis.Entri mewakili pasangan nilai kunci dalam enjin storan, termasuk kunci, nilai dan bendera batu nisan untuk dipadamkan.
seterusnya: Mengandungi penunjuk ke elemen seterusnya pada setiap peringkat.
Struktur ini mungkin kelihatan abstrak, jadi mari kita gambarkan dengan contoh:
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Dalam Senarai Langkau tiga peringkat ini, penunjuk seterusnya nod kepala merujuk nod pertama pada setiap peringkat. Elemen 3 dan 6 menyimpan elemen seterusnya untuk setiap tahapnya.
Sebagai contoh, jika kita ingin mencari nod seterusnya bagi elemen 19 pada Tahap 2, kita menggunakan e19.next[2-1].
func (s *SkipList) Set(entry types.Entry)
LSM-Tree menggunakan batu nisan untuk melakukan pemadaman, jadi kami tidak memerlukan kaedah Padam dalam pelaksanaan senarai langkau. Untuk memadamkan elemen, hanya tetapkan Batu Nisan entri kepada benar. Oleh itu, kaedah Set mengendalikan memasukkan pasangan nilai kunci baharu, mengemas kini yang sedia ada dan memadamkan elemen.
Mari kita terokai pelaksanaan kaedah Set. Dengan merentasi nod dalam setiap tahap dari yang tertinggi, elemen terakhir yang lebih kecil daripada kunci yang akan ditetapkan disimpan dalam kepingan kemas kini.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Pada penghujung traversal ini, curr menghala ke elemen terakhir yang lebih kecil daripada kekunci yang akan ditetapkan dalam senarai terpaut peringkat bawah. Jadi, kita hanya perlu menyemak sama ada elemen curr seterusnya sama dengan kunci yang ingin kita tetapkan. Jika ia sepadan, elemen telah dimasukkan; kami mengemas kini elemen sedia ada dan mengembalikan.
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Jika elemen tidak ditemui, ia dimasukkan sebagai elemen baharu. Menggunakan randomLevel, kami mengira tahap indeks elemen ini. Jika ia melebihi bilangan tahap semasa dalam senarai langkau, kami menambah nod kepala pada kepingan kemas kini dan mengemas kini s.level kepada kiraan tahap baharu.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Seterusnya, bina elemen yang hendak disisipkan dan penunjuk seterusnya bagi setiap peringkat dikemas kini untuk melengkapkan sisipan.
func (s *SkipList) Set(entry types.Entry)
Senarai langkau boleh melakukan operasi carian pantas dengan bergantung pada berbilang lapisan indeks. Gelung bersarang dalam pelaksanaan mewakili operasi carian berasaskan indeks. Jika elemen yang sepadan akhirnya ditemui dalam senarai terpaut peringkat bawah, ia akan dikembalikan.
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Salah satu sebab kami memilih senarai langkau adalah laluan berurutan yang mudah, yang dimungkinkan dengan hanya melintasi senarai terpaut peringkat bawah.
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
Pelaksanaan lengkap WAL boleh didapati di https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go.
Seperti yang dinyatakan sebelum ini, tujuan WAL (Write-Ahead Logging) adalah untuk mengelakkan kehilangan data dalam Memtable yang disebabkan oleh ranap pangkalan data. Oleh itu, WAL perlu merekodkan operasi pada Memtable dan memulihkan Memtable daripada fail WAL apabila pangkalan data dimulakan semula.
Struktur teras WAL adalah seperti berikut, di mana fd menyimpan deskriptor fail fail WAL:
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Memandangkan kita perlu merekodkan operasi pada Memtable, ini pada asasnya melibatkan penulisan setiap operasi (Tetapkan, Padam) sebagai Kemasukan ke dalam WAL. Takrif kaedah Tulis adalah seperti berikut:
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
Apabila menulis entri ini pada fail, kami perlu menyeragamkan format fail WAL. Format yang kami gunakan di sini ialah data panjang. Mula-mula, kami menyerikan Entri, kemudian mengira panjang data bersiri, dan akhirnya menulis panjang dan data bersiri secara berurutan ke dalam fail WAL.
Kod teras adalah seperti berikut:
func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
curr := s.head
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < key {
curr = curr.next[i]
}
}
curr = curr.next[0]
if curr != nil && curr.Key == key {
return types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
}, true
}
return types.Entry{}, false
}
Memandangkan kami menggunakan format fail WAL data panjang, semasa membaca, kami mula-mula membaca 8 bait (int64) untuk mendapatkan panjang data, dan kemudian membaca data berdasarkan panjang ini dan nyahserikannya untuk mendapatkan semula Entri.
Kod teras adalah seperti berikut:
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Pelaksanaan lengkap Memtable boleh didapati di https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go.
Metable bertanggungjawab untuk menulis operasi klien ke dalam senarai langkau dan merekodkannya dalam WAL. Ia juga boleh memulihkan data daripada WAL apabila pangkalan data bermula.
Struktur teras Memtable adalah seperti berikut, yang merangkumi dua komponen utama skiplist dan wal:
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Apabila melakukan operasi Set, kedua-dua senarai langkau dan WAL perlu dikemas kini secara serentak.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Untuk mendapatkan semula nilai, hanya kembalikan hasil operasi Dapatkan senarai langkau.
func (s *SkipList) Set(entry types.Entry)
Memulihkan Memtable daripada fail WAL melibatkan pembacaan fail WAL dahulu, kemudian secara berurutan menggunakan rekod Kemasukan daripada fail WAL ke Memtable, dan akhirnya memadamkan fail WAL yang dipulihkan.
Dapatkan semula senarai fail WAL:
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Baca WAL dan dapatkan semula Memtable:
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
Dalam pengenalan sebelumnya, kami hanya menyebut bahawa "SSTable (Sorted String Table) ialah format storan data yang mengekalkan satu siri pasangan nilai kunci tersusun." Di sini, kami akan memberikan penjelasan yang lebih terperinci tentang struktur SSTable.
Dalam LevelDB, SSTable terdiri daripada berbilang blok dengan tujuan yang berbeza. Gambarajah skematik ditunjukkan di bawah:
Maklumat indeks pada asasnya ialah struktur penunjuk yang dipanggil BlockHandle, yang merangkumi dua atribut: offset dan saiz, digunakan untuk mencari Blok yang sepadan.
Dalam pelaksanaan SSTable kami, kami telah memudahkan struktur LevelDB SSTable. Gambarajah skematik ditunjukkan di bawah:
Pelaksanaan lengkap SSTable boleh didapati di https://github.com/B1NARY-GR0UP/originium/tree/main/sstable.
Struktur Blok Data ditakrifkan seperti berikut, menyimpan urutan entri yang tersusun.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Kami melaksanakan tiga kaedah utama untuk Blok Data:
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Kami menggunakan mampatan awalan untuk mengekod jujukan nilai kunci. Dalam penimbal, kami menulis secara berurutan panjang awalan biasa, panjang akhiran, akhiran itu sendiri, panjang nilai, nilai dan penanda "batu nisan".
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Akhir sekali, kami memampatkan data menggunakan s2.
S2 ialah sambungan berprestasi tinggi bagi algoritma mampatan Snappy.
func (s *SkipList) Set(entry types.Entry)
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Semasa penyahkodan, proses hanya diterbalikkan. Pasangan nilai kunci penuh dibina semula menggunakan awalan dan akhiran.
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Struktur Blok Indeks ditakrifkan seperti berikut. Ia menyimpan kunci pertama dan terakhir setiap Blok Data, bersama-sama dengan BlockHandle bagi Blok Data yang sepadan.
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
Begitu juga, Blok Indeks melaksanakan tiga kaedah utama: Enkod, Nyahkod dan Cari. Idea pelaksanaan untuk kaedah Encode dan Decode pada asasnya adalah sama, jadi kami akan menumpukan pada kaedah Cari.
Kaedah Carian Blok Data direka bentuk untuk mencari pasangan nilai kunci tertentu dalam jujukan nilai kunci tersusun yang disimpan dalam Blok Data tunggal. Sebaliknya, kaedah Carian Blok Indeks digunakan untuk mencari Blok Data yang mengandungi kunci yang diberikan dalam keseluruhan SSTable.
func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
curr := s.head
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < key {
curr = curr.next[i]
}
}
curr = curr.next[0]
if curr != nil && curr.Key == key {
return types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
}, true
}
return types.Entry{}, false
}
func (s *SkipList) All() []types.Entry {
var all []types.Entry
for curr := s.head.next[0]; curr != nil; curr = curr.next[0] {
all = append(all, types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
})
}
return all
}
Pelaksanaan kedua-dua Blok ini agak mudah, dengan kedua-duanya hanya memerlukan kaedah Pengekodan dan Nyahkod.
Selepas memperkenalkan semua Blok dalam SSTable kami, membina SSTable hanya melibatkan membina setiap Blok langkah demi langkah berdasarkan pasangan nilai kunci. Akhirnya, indeks dalam memori dan SSTable yang dikodkan dikembalikan.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Pelaksanaan lengkap K-Way Merge boleh didapati di https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway.
Dalam bahagian konseptual, kami menggambarkan proses memampatkan dan menggabungkan berbilang SSTable melalui rajah. Proses ini dicapai menggunakan algoritma k-way merge.
Algoritma cantuman k-way ialah kaedah untuk menggabungkan k jujukan yang diisih ke dalam satu jujukan tersusun, dengan kerumitan masa O(knlogk).
Satu pelaksanaan algoritma ini menggunakan timbunan min sebagai struktur tambahan:
Pustaka standard menyediakan pelaksanaan timbunan dalam bekas/timbunan. Dengan melaksanakan timbunan.Antaramuka, kita boleh membina timbunan min.
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
func (s *SkipList) Set(entry types.Entry)
Takrifan fungsi kaedah Gabung:
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Mengikuti proses algoritma cantuman k-way.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Akhir sekali, rentas peta untuk menambahkan elemen pada baris gilir hasil, mengalih keluar sebarang pasangan nilai kunci yang ditandakan sebagai "batu nisan." Memandangkan peta tidak tersusun, baris gilir hasil perlu diisih sebelum dikembalikan.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Pelaksanaan lengkap Penapis Bloom boleh didapati di https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go.
Penapis Bloom ialah struktur data yang memeriksa dengan cekap sama ada sesuatu elemen ialah ahli set.
Kerumitan masa untuk kedua-dua operasi sisipan dan pertanyaan ialah O(k), dengan k ialah bilangan fungsi cincang. Positif palsu mungkin berlaku (Penapis Bloom meramalkan bahawa elemen berada dalam set, tetapi tidak), tetapi negatif palsu tidak boleh berlaku (Penapis Bloom meramalkan bahawa elemen tidak dalam set, tetapi sebenarnya ada).
Positif Benar (TP): Sistem meramalkan peristiwa sebagai "positif", dan ia sememangnya positif.
Positif Palsu (FP): Sistem meramalkan peristiwa sebagai "positif", tetapi ia sebenarnya negatif.
True Negatif (TN): Sistem meramalkan peristiwa sebagai "negatif", dan ia sememangnya negatif.
Negatif Palsu (FN): Sistem meramalkan peristiwa sebagai "negatif", tetapi ia sebenarnya positif.
Struktur teras Penapis Bloom termasuk tatasusunan bit (yang boleh dioptimumkan untuk menggunakan uint8) dan berbilang fungsi cincang.
func (s *SkipList) Set(entry types.Entry)
Kaedah untuk mencipta tika Penapis Bloom menerima dua parameter: n (bilangan unsur yang dijangkakan) dan p (kadar positif palsu yang dikehendaki).
Pertama, parameter disahkan. Kemudian, saiz tatasusunan bit (m) dan bilangan fungsi cincang (k) dikira menggunakan formula khusus. Akhirnya, tatasusunan bit dan fungsi cincang dimulakan berdasarkan m dan k.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Apabila menambah elemen, semua fungsi cincang digunakan untuk mengira nilai cincang untuk kunci. Nilai ini kemudiannya dipetakan kepada indeks dalam tatasusunan bit dan kedudukan yang sepadan ditetapkan kepada benar.
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Untuk menyemak sama ada kunci berada dalam set, fungsi cincang mengira nilai cincang dan memetakannya kepada indeks dalam tatasusunan bit. Jika mana-mana kedudukan ini tidak benar, elemen itu tiada dalam set dan palsu dikembalikan.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Pelaksanaan lengkap Pemadatan Bertingkat boleh didapati di https://github.com/B1NARY-GR0UP/originium/blob/main/level.go.
Selepas melaksanakan komponen seperti K-Way Merge dan Bloom Filter, kami boleh melengkapkan bahagian akhir pelaksanaan kami, proses pemadatan SSTable yang paling penting dalam enjin storan LSM-Tree. Pelaksanaan ini mengikut Strategi Pemadatan Bertingkat yang diterangkan dalam bahagian "Pemadatan Data".
Dalam Strategi Pemadatan Bertingkat, SSTables disusun ke dalam pelbagai peringkat (Tahap 0 - Tahap N). Kami memerlukan struktur untuk menyimpan maklumat ini dan mengurus SSTables merentas tahap yang berbeza.
Oleh itu, kami melaksanakan struktur yang dipanggil levelManager. Kami menggunakan []*list.List untuk menyimpan maklumat SSTable bagi setiap peringkat, di mana indeks hirisan sepadan dengan tahap. Setiap elemen dalam hirisan ialah senarai. Senarai, senarai berganda yang menyimpan maklumat tentang semua SSTable dalam tahap tertentu.
func (s *SkipList) Set(entry types.Entry)
Kaedah compactLN bertanggungjawab untuk pemadatan Tahap N hingga Tahap N 1 (N > 0). Ia memilih SSTable tertua daripada LN dan semua SSTables daripada LN 1 yang mempunyai julat kunci bertindih dengan SSTable ini.
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
SSTables yang dipilih diproses mengikut urutan daripada yang paling lama kepada yang terbaru. Pasangan nilai kunci daripada blok data mereka ditambahkan pada kepingan dua dimensi dan kemudian digabungkan menggunakan algoritma Gabungan K-Way.
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
Dengan pasangan nilai kunci yang digabungkan, kami membina Penapis Bloom dan SSTable baharu. Maklumat berkaitan tentang SSTable baharu dilampirkan pada penghujung Tahap N 1.
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Akhir sekali, SSTables lama dipadamkan dan SSTable yang baru dibina ditulis pada cakera.
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
Kaedah compactL0 mengendalikan pemadatan Tahap 0 hingga Tahap 1. Tidak seperti compactLN, ia memilih bukan sahaja satu SSTable daripada L0 tetapi juga semua SSTables bertindih dalam L0. Proses selebihnya adalah sama dengan compactLN.
Kaedah carian mencari pasangan nilai kunci yang sepadan merentas semua SSTables. Ia bermula dari L0 dan berulang melalui setiap peringkat sehingga LN. Dengan memanfaatkan Penapis Bloom dan struktur tersusun SSTables, SSTables yang tidak mengandungi pasangan nilai kunci yang diingini boleh dilangkau dengan cekap.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Dengan ini, kami telah melaksanakan semua komponen teras enjin storan berasaskan LSM-Tree. Dengan memasang komponen ini seperti yang diterangkan dalam pengenalan LSM-Tree, kami boleh memuktamadkan antara muka pangkalan data.
Kod lengkap: https://github.com/B1NARY-GR0UP/originium/blob/main/db.go
Dokumentasi: https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage
Kami bermula dengan memahami LSM-Tree, membiasakan diri dengan komponen terasnya dan proses mengendalikan permintaan pelanggan. Akhirnya, kami membina enjin storan LSM-Tree kami sendiri dari awal.
Sudah tentu, pelaksanaan ini hanyalah prototaip. Enjin storan gred pengeluaran memerlukan pertimbangan lebih banyak butiran. ORIGINIUM akan terus menerima pengoptimuman dan penambahbaikan pada masa hadapan. Semoga artikel dan ORIGINIUM ini membantu mendalami pemahaman anda tentang LSM-Tree.
Itu menyimpulkan semua yang dibincangkan dalam artikel ini. Jika terdapat sebarang ralat atau soalan, sila hubungi melalui mesej peribadi atau tinggalkan ulasan. Terima kasih!
Atas ialah kandungan terperinci Membina Enjin Penyimpanan Pokok LSM daripada Gores. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Apakah perisian lukisan yang ada?
penggunaan fungsi fungsi
Amaran Panggilan Pusat Anti Penipuan Kebangsaan
Bagaimana untuk membeli dan menjual Bitcoin di okex
Mengapa perkataan selepas menaip perkataan hilang?
Terdapat beberapa fungsi output dan input dalam bahasa C
Apakah perbezaan antara USB-C dan TYPE-C
Bagaimana untuk memusatkan div dalam css
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
