Cet article vous guidera dans la compréhension du Log-Structured Merge-Tree (LSM-Tree), y compris ses concepts de base et sa structure. À la fin, vous serez en mesure de créer votre propre moteur de stockage basé sur LSM-Tree à partir de zéro.
Le Log-Structured Merge-Tree (LSM-Tree) est une structure de données optimisée pour les opérations d'écriture à haut débit. Il est largement utilisé dans les bases de données et les systèmes de stockage, tels que Cassandra, RocksDB et LevelDB.
L'idée clé de LSM-Tree est d'abord d'écrire les opérations dans une structure de données en mémoire (généralement une structure ordonnée comme une liste de sauts ou un arbre AVL). Plus tard, ces écritures sont regroupées et écrites séquentiellement sur le disque sous forme de SSTables, minimisant ainsi les E/S aléatoires.
Le LSM-Tree est divisé en deux composants principaux :
En général, la structure d'un SSTable comprend plus qu'une simple série de paires clé-valeur ordonnées (blocs de données). Il contient également un bloc d'index, un bloc de métadonnées et d'autres composants. Ces détails seront discutés en profondeur lors de la section de mise en œuvre.
L'écriture de données implique l'ajout d'une nouvelle paire clé-valeur ou la mise à jour d'une paire existante. Les mises à jour écrasent les anciennes paires clé-valeur, qui sont ensuite supprimées pendant le processus de compactage.
Lorsque les données sont écrites, elles vont d'abord dans la Memtable, où la paire clé-valeur est ajoutée à la structure de données ordonnée en mémoire. Simultanément, l'opération d'écriture est enregistrée dans le WAL et conservée sur le disque pour éviter la perte de données en cas de panne de la base de données.
La Memtable a un seuil défini (généralement basé sur la taille). Lorsque la Memtable dépasse ce seuil, elle passe en mode lecture seule et est convertie en une nouvelle SSTable, qui est ensuite conservée au Niveau 0 sur le disque.
Une fois la Memtable vidée en tant que SSTable, le fichier WAL correspondant peut être supprimé en toute sécurité. Les opérations d'écriture ultérieures se dérouleront sur une nouvelle Memtable (et un nouveau WAL).
Dans LSM-Tree, les données ne sont pas immédiatement supprimées. Au lieu de cela, les suppressions sont gérées à l'aide d'un mécanisme appelé tombstones (similaire aux suppressions logicielles). Lorsqu'une paire clé-valeur est supprimée, une nouvelle entrée marquée d'une « pierre tombale » est écrite, indiquant la suppression de la paire clé-valeur correspondante. L'enlèvement proprement dit a lieu pendant le processus de compactage.
Cette suppression basée sur la pierre tombale garantit la propriété ajout uniquement de LSM-Tree, évitant les E/S aléatoires et conservant les écritures séquentielles sur le disque.
Le processus d'interrogation des données commence par une recherche dans la Memtable. Si la paire clé-valeur est trouvée, elle est renvoyée au client. Si une paire clé-valeur marquée par une pierre tombale est trouvée, cela indique que les données demandées ont été supprimées et ces informations sont également renvoyées. Si la clé n'est pas trouvée dans la Memtable, la requête procède à la recherche dans les SSTables du Niveau 0 au Niveau N.
Étant donné que l'interrogation de données peut impliquer la recherche de plusieurs fichiers SSTable et peut conduire à des E/S aléatoires sur le disque, LSM-Tree est généralement mieux adapté aux charges de travail à forte écriture qu'à celles à forte intensité de lecture.
Une optimisation courante des performances des requêtes consiste à utiliser un filtre Bloom. Un filtre Bloom peut déterminer rapidement si une paire clé-valeur existe dans une SSTable spécifique, réduisant ainsi les E/S disque inutiles. De plus, la nature triée des SSTables permet d'utiliser des algorithmes de recherche efficaces, tels que la recherche binaire, pour des recherches plus rapides.
Ici, nous présentons la Stratégie de compactage par niveaux, qui est utilisée par LevelDB et RocksDB.
Une autre stratégie courante est la Stratégie de compactage par niveaux de taille, dans laquelle des SSTables plus récentes et plus petites sont successivement fusionnées en SSTables plus anciennes et plus grandes.
Comme mentionné précédemment, une SSTable stocke une série d'entrées triées par clé. Dans la stratégie de compactage par niveaux, les SSTables sont organisées en plusieurs niveaux (Niveau 0 au niveau N).
Au niveau 0, les SSTables peuvent avoir des plages de clés qui se chevauchent, car elles sont directement vidées de la Memtable. Cependant, aux niveaux 1 à N, les SSTables d'un même niveau n'ont pas de plages de clés qui se chevauchent, bien que les chevauchements de plages de clés soient autorisés entre les SSTables de différents niveaux.
Un exemple illustratif (bien que pas entièrement précis) est présenté ci-dessous. Au Niveau 0, les plages de clés des première et deuxième SSTables se chevauchent, tandis qu'au Niveau 1 et au Niveau 2, les SSTables de chaque niveau ont des plages de clés disjointes. . Cependant, les SSTables entre différents niveaux (par exemple, niveau 0 et niveau 1, ou niveau 1 et niveau 2) peuvent avoir des plages de clés qui se chevauchent.
Explorons maintenant comment la stratégie de compactage nivelé maintient cette structure organisationnelle.
Le niveau 0 étant un cas particulier, la discussion sur la stratégie de compactage est divisée en deux parties :
La principale différence entre le compactage Niveau 0 au niveau 1 et le Niveau N au niveau N 1 (N > 0) réside dans la sélection des SSTables aux niveaux inférieurs (Niveau 0 ou Niveau N).
Le processus de compactage et de fusion multi-SSTable est illustré ci-dessous. Lors de la fusion, seule la dernière valeur de chaque clé est conservée. Si la dernière valeur comporte un marqueur « tombstone », la clé est supprimée. Dans l'implémentation, nous utilisons l'algorithme de fusion k-way pour effectuer ce processus.
Il est important de noter que la description ci-dessus du processus de compactage ne fournit qu'un aperçu de haut niveau. De nombreux détails doivent être abordés lors de la mise en œuvre réelle.
Par exemple, dans LevelDB, lors de la construction de nouvelles SSTables pour le niveau N 1 pendant le compactage, si la nouvelle SSTable chevauche plus de 10 SSTables au niveau N 2, le processus passe à la construction d'une autre SSTable. Cela limite la taille des données impliquées dans un seul compactage.
Sur la base de l'aperçu de LSM-Tree ci-dessus, je pense que vous avez maintenant une compréhension de base de LSM-Tree et quelques idées sur sa mise en œuvre. Ensuite, nous allons construire un moteur de stockage basé sur LSM-Tree à partir de zéro. Ci-dessous, nous présenterons uniquement le code principal ; pour le code complet, veuillez vous référer à https://github.com/B1NARY-GR0UP/originium.
Nous décomposerons la mise en œuvre de LSM-Tree en composants de base suivants et les implémenterons un par un :
Dans le processus d'introduction de l'écriture de données, nous avons mentionné que le LSM-Tree écrit d'abord les données dans une structure de données ordonnée en mémoire. Certaines structures de données ordonnées courantes et la complexité temporelle de leurs opérations sont les suivantes :
| 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) |
Nous avons choisi la Skip List pour deux raisons principales : elle est plus simple à mettre en œuvre et à maintenir (principe KISS), et la structure de liste chaînée sous-jacente facilite le parcours séquentiel, ce qui facilite la conservation des données en mémoire sur le disque.
La mise en œuvre complète de la Skip List est disponible sur https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go .
Une liste de sauts se compose d'une liste chaînée de base et de plusieurs niveaux d'index construits dessus. Pour les grands ensembles de données, les couches d'index raccourcissent considérablement le chemin de recherche.
Dans notre implémentation, la structure de base de la Skip List est définie comme suit :
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
La structure des éléments stockés dans la Skip List est définie comme suit :
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
}
types.Entry représente une paire clé-valeur dans le moteur de stockage, comprenant la clé, la valeur et un indicateur de pierre tombale pour la suppression.
suivant : contient des pointeurs vers l'élément suivant à chaque niveau.
Cette structure peut paraître abstraite, alors illustrons-la avec un exemple :
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 ]
Dans cette liste de sauts à trois niveaux, les pointeurs suivants du nœud principal font référence au premier nœud de chaque niveau. Les éléments 3 et 6 stockent l'élément suivant pour chacun de leurs niveaux.
Par exemple, si nous voulons trouver le nœud suivant de l'élément 19 au niveau 2, nous utilisons e19.next[2-1].
func (s *SkipList) Set(entry types.Entry)
Le LSM-Tree utilise des pierres tombales pour effectuer des suppressions, nous n'avons donc pas besoin d'une méthode Supprimer dans l'implémentation de la liste de sauts. Pour supprimer un élément, définissez simplement le Tombstone de l'entrée sur true. Ainsi, la méthode Set gère l'insertion de nouvelles paires clé-valeur, la mise à jour de celles existantes et la suppression d'éléments.
Explorons l'implémentation de la méthode Set. En parcourant les nœuds de chaque niveau depuis le plus haut, le dernier élément plus petit que la clé à définir est enregistré dans la tranche de mise à jour.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
À la fin de ce parcours, curr pointe vers le dernier élément plus petit que la clé à définir dans la liste chaînée de niveau inférieur. Il nous suffit donc de vérifier si l’élément suivant de curr est égal à la clé que nous voulons définir. S'il correspond, l'élément a déjà été inséré ; nous mettons à jour l'élément existant et revenons.
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
}
Si l'élément n'est pas trouvé, il est inséré comme nouvel élément. En utilisant randomLevel, nous calculons le niveau d'index de cet élément. S'il dépasse le nombre actuel de niveaux dans la liste à ignorer, nous ajoutons le nœud principal à la tranche de mise à jour et mettons à jour s.level avec le nouveau nombre de niveaux.
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 ]
Ensuite, construisez l'élément à insérer et les pointeurs suivants de chaque niveau sont mis à jour pour terminer l'insertion.
func (s *SkipList) Set(entry types.Entry)
La liste de sauts peut effectuer des opérations de recherche rapides en s'appuyant sur plusieurs couches d'index. Les boucles for imbriquées dans l'implémentation représentent l'opération de recherche basée sur l'index. Si l'élément correspondant est finalement trouvé dans la liste chaînée de niveau inférieur, il sera renvoyé.
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
}
L'une des raisons pour lesquelles nous avons choisi la liste de sauts est son parcours séquentiel pratique, qui est rendu possible en parcourant simplement la liste chaînée de niveau inférieur.
// 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
}
La mise en œuvre complète de WAL peut être trouvée sur https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go.
Comme mentionné précédemment, le but de WAL (Write-Ahead Logging) est d'éviter la perte de données dans la Memtable causée par des pannes de base de données. Par conséquent, WAL doit enregistrer les opérations sur la Memtable et récupérer la Memtable à partir du fichier WAL au redémarrage de la base de données.
La structure de base de WAL est la suivante, où fd stocke le descripteur de fichier du fichier WAL :
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Puisque nous devons enregistrer les opérations sur la Memtable, cela implique essentiellement d'écrire chaque opération (Set, Supprimer) en tant qu'entrée dans le WAL. La définition de la méthode Write est la suivante :
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)))
Lors de l'écriture de ces entrées dans le fichier, nous devons standardiser le format de fichier WAL. Le format que nous utilisons ici est données de longueur. Tout d'abord, nous sérialisons l'entrée, puis calculons la longueur des données sérialisées et enfin écrivons la longueur et les données sérialisées séquentiellement dans le fichier WAL.
Le code de base est le suivant :
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
}
Puisque nous utilisons le format de fichier WAL longueur des données, lors de la lecture, nous lisons d'abord 8 octets (int64) pour obtenir la longueur des données, puis lisons les données en fonction de cette longueur et les désérialisons pour récupérer l'entrée.
Le code de base est le suivant :
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
L'implémentation complète de Memtable peut être trouvée sur https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go.
La Memtable est chargée d'écrire les opérations du client dans la liste de sauts et de les enregistrer dans le WAL. Il peut également récupérer les données du WAL au démarrage de la base de données.
La structure de base de Memtable est la suivante, qui comprend deux composants principaux skiplist et 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
}
Lors de l'exécution d'une opération Set, la liste de sauts et le WAL doivent être mis à jour simultanément.
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 ]
Pour récupérer une valeur, retournez simplement le résultat de l'opération Get de la liste à sauter.
func (s *SkipList) Set(entry types.Entry)
La récupération de la Memtable à partir du fichier WAL implique d'abord de lire le fichier WAL, puis d'appliquer séquentiellement les enregistrements d'entrée du fichier WAL à la Memtable, et enfin de supprimer le fichier WAL récupéré.
Récupérer la liste des fichiers 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
}
Lire le WAL et récupérer la 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
}
Dans l'introduction précédente, nous avons seulement mentionné que "SSTable (Sorted String Table) est un format de stockage de données qui maintient une série de paires clé-valeur ordonnées." Ici, nous fournirons une explication plus détaillée de la structure de SSTable.
Dans LevelDB, une SSTable se compose de plusieurs blocs ayant des objectifs différents. Un diagramme schématique est présenté ci-dessous :
Les informations d'index sont essentiellement une structure de pointeur appelée BlockHandle, qui comprend deux attributs : offset et size, utilisés pour localiser le bloc correspondant.
Dans notre implémentation de SSTable, nous avons simplifié la structure LevelDB SSTable. Un diagramme schématique est présenté ci-dessous :
L'implémentation complète de SSTable peut être trouvée sur https://github.com/B1NARY-GR0UP/originium/tree/main/sstable.
La structure du bloc de données est définie comme suit, stockant une séquence ordonnée d'entrées.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Nous avons implémenté trois méthodes principales pour le bloc de données :
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
}
Nous utilisons la compression de préfixe pour encoder la séquence clé-valeur. Dans le tampon, nous écrivons séquentiellement la longueur du préfixe commun, la longueur du suffixe, le suffixe lui-même, la longueur de la valeur, la valeur et le marqueur « pierre tombale ».
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 ]
Enfin, nous compressons les données en utilisant s2.
S2 est une extension hautes performances de l'algorithme de compression 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
}
Lors du décodage, le processus est simplement inversé. La paire clé-valeur complète est reconstruite à l'aide du préfixe et du suffixe.
// 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
}
La structure du bloc d'index est définie comme suit. Il stocke la première et la dernière clé de chaque bloc de données, ainsi que le BlockHandle du bloc de données correspondant.
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)))
De même, le Index Block implémente trois méthodes principales : Encode, Decode et Search. Les idées d'implémentation pour les méthodes Encode et Decode sont essentiellement les mêmes, nous allons donc nous concentrer sur la méthode Search.
La méthode de recherche du bloc de données est conçue pour localiser une paire clé-valeur spécifique dans la séquence clé-valeur ordonnée stockée dans un seul bloc de données. En revanche, la méthode de recherche du bloc d'index est utilisée pour localiser le bloc de données contenant la clé donnée dans l'ensemble de la 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
}
Les implémentations de ces deux blocs sont assez simples, les deux ne nécessitant que les méthodes Encode et Decode.
Après avoir introduit tous les blocs de notre SSTable, construire une SSTable implique simplement de construire chaque bloc étape par étape en fonction des paires clé-valeur. Enfin, l'index en mémoire et le SSTable encodé sont renvoyés.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
L'implémentation complète de K-Way Merge est disponible sur https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway.
Dans la section conceptuelle, nous illustrons le processus de compression et de fusion de plusieurs SSTables à travers des diagrammes. Ce processus est accompli à l'aide de l'algorithme k-way merge.
L'algorithme de fusion k-way est une méthode pour fusionner k séquences triées en une seule séquence triée, avec une complexité temporelle de O(knlogk).
Une implémentation de cet algorithme utilise un min-heap comme structure auxiliaire :
La bibliothèque standard fournit une implémentation de tas en conteneur/heap. En implémentant l'interface heap.Interface, nous pouvons créer un min-heap.
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)
La définition de la fonction de la méthode Merge :
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
}
Suit le processus de l'algorithme de fusion 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
}
Enfin, parcourez la carte pour ajouter des éléments à la file d'attente des résultats, en supprimant toutes les paires clé-valeur marquées comme « pierres tombales ». Étant donné que la carte n'est pas ordonnée, la file d'attente des résultats doit être triée avant d'être renvoyée.
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 ]
La mise en œuvre complète du filtre Bloom peut être trouvée sur https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go.
Un filtre Bloom est une structure de données qui vérifie efficacement si un élément est membre d'un ensemble.
La complexité temporelle des opérations d'insertion et de requête est O(k), où k est le nombre de fonctions de hachage. Des faux positifs peuvent se produire (le filtre Bloom prédit qu'un élément est dans l'ensemble, mais il ne l'est pas), mais des faux négatifs ne peuvent pas se produire (le filtre Bloom prédit qu'un élément n'est pas dans l'ensemble, mais c'est effectivement le cas).
Vrai positif (TP) : Le système prédit un événement comme « positif », et il est effectivement positif.
Faux positif (FP) : Le système prédit un événement comme « positif », mais il est en réalité négatif.
Vrai Négatif (TN) : Le système prédit un événement comme « négatif », et il est effectivement négatif.
Faux Négatif (FN) :Le système prédit un événement comme « négatif », mais il est en réalité positif.
La structure de base d'un filtre Bloom comprend le tableau de bits (qui peut être optimisé pour utiliser uint8) et plusieurs fonctions de hachage.
func (s *SkipList) Set(entry types.Entry)
La méthode pour créer une instance de Bloom Filter accepte deux paramètres : n (le nombre d'éléments attendu) et p (le taux de faux positifs souhaité).
Tout d'abord, les paramètres sont validés. Ensuite, la taille du tableau de bits (m) et le nombre de fonctions de hachage (k) sont calculés à l'aide de formules spécifiques. Enfin, les fonctions de tableau de bits et de hachage sont initialisées en fonction de m et k.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Lors de l'ajout d'un élément, toutes les fonctions de hachage sont utilisées pour calculer les valeurs de hachage de la clé. Ces valeurs sont ensuite mappées sur des indices dans le tableau de bits et les positions correspondantes sont définies sur true.
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
}
Pour vérifier si une clé est dans l'ensemble, les fonctions de hachage calculent les valeurs de hachage et les mappent aux indices du tableau de bits. Si l'une de ces positions n'est pas vraie, l'élément n'est pas dans l'ensemble et false est renvoyé.
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 ]
La mise en œuvre complète de Leveled Compaction peut être trouvée sur https://github.com/B1NARY-GR0UP/originium/blob/main/level.go.
Après avoir implémenté des composants tels que K-Way Merge et Bloom Filter, nous pouvons terminer la dernière partie de notre implémentation, le processus de compactage SSTable le plus crucial dans le moteur de stockage LSM-Tree. Cette mise en œuvre suit la Stratégie de compactage par niveaux décrite dans la section « Compactage des données ».
Dans la stratégie de compactage par niveaux, les SSTables sont organisées en plusieurs niveaux (Niveau 0 - Niveau N). Nous avons besoin d'une structure pour stocker ces informations et gérer les SSTables à différents niveaux.
Ainsi, nous avons implémenté une structure appelée levelManager. Nous utilisons un []*list.List pour stocker les informations SSTable pour chaque niveau, où l'index de la tranche correspond au niveau. Chaque élément de la tranche est une liste.List, une liste à double lien qui contient des informations sur tous les SSTables d'un niveau spécifique.
func (s *SkipList) Set(entry types.Entry)
La méthode compactLN est responsable du compactage du niveau N au niveau N 1 (N > 0). Il sélectionne la SSTable la plus ancienne de LN et toutes les SSTables de LN 1 dont les plages de clés se chevauchent avec cette SSTable.
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
}
Les SSTables sélectionnées sont traitées du plus ancien au plus récent. Les paires clé-valeur de leurs blocs de données sont ajoutées à une tranche bidimensionnelle puis fusionnées à l'aide de l'algorithme K-Way Merge.
// 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
}
Avec les paires clé-valeur fusionnées, nous construisons un nouveau filtre Bloom et un nouveau SSTable. Les informations pertinentes sur la nouvelle SSTable sont annexées à la fin du niveau 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
}
Enfin, les anciennes SSTables sont supprimées et la SSTable nouvellement construite est écrite sur le disque.
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)))
La méthode compactL0 gère le compactage du niveau 0 au niveau 1. Contrairement à compactLN, il sélectionne non seulement une SSTable de L0, mais également toutes les SSTables qui se chevauchent dans L0. Le reste du processus est identique à compactLN.
La méthode de recherche localise les paires clé-valeur correspondantes dans toutes les SSTables. Il commence à partir de L0 et parcourt chaque niveau jusqu'à LN. En tirant parti du filtre Bloom et de la structure ordonnée des SSTables, les SSTables qui ne contiennent pas les paires clé-valeur souhaitées peuvent être ignorées efficacement.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Grâce à cela, nous avons implémenté tous les composants principaux du moteur de stockage basé sur LSM-Tree. En assemblant ces composants comme décrit dans l'introduction de LSM-Tree, nous pouvons finaliser l'interface de la base de données.
Code complet : https://github.com/B1NARY-GR0UP/originium/blob/main/db.go
Documentation : https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage
Nous avons commencé par comprendre LSM-Tree, en nous familiarisant avec ses composants principaux et le processus de traitement des demandes des clients. En fin de compte, nous avons construit notre propre moteur de stockage LSM-Tree à partir de zéro.
Bien sûr, cette implémentation n'est qu'un prototype. Un moteur de stockage de niveau production nécessite de prendre en compte bien plus de détails. ORIGINIUM continuera de recevoir des optimisations et des améliorations à l'avenir. J'espère que cet article et ORIGINIUM vous aideront à approfondir votre compréhension de LSM-Tree.
Cela conclut tout ce qui est couvert dans cet article. S'il y a des erreurs ou des questions, n'hésitez pas à nous contacter par message privé ou à laisser un commentaire. Merci !
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Tutoriel de récupération des icônes de mon ordinateur Win10
Pourquoi Webstorm ne peut pas exécuter le fichier
À quel point Dimensity 9000 équivaut-il à Snapdragon ?
Comment résoudre l'erreur de restauration du site Web
largeur de décalage
code d'activation de la clé Vista
Que faire si une erreur normal.dotm se produit
touches de raccourci de remplacement wps
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
