Pourquoi LevelDB a besoin de plus de deux niveaux?

Question

Je pense que seuls deux niveaux (niveau 0 et niveau 1) sont corrects, pourquoi LevelDB a-t-il besoin de niveau 2, niveau 3 et plus?

Answer 1

Je vous indiquerai quelques articles sur LevelDB et sa structure de stockage sous-jacente.

Donc dans le documentation for LevelDB il discute des fusions entre les niveaux. Ces fusions ont pour effet de migrer progressivement de nouvelles mises à jour du niveau le plus jeune au plus grand niveau en n'utilisant que des lectures et des écritures en masse (c'est-à-dire en minimisant les recherches coûteuses).

La structure de LevelDB est similaire à Log Structured Merge Trees. Le papier discute les différents niveaux si vous êtes intéressé par l'analyse de celui-ci. Si vous pouvez passer à travers les mathématiques, il semble que votre meilleur pari pour comprendre la structure des données.

Un beaucoup plus facile à lire analysis des pourparlers LevelDB sur la relation du datastore à LSM arbres, mais en termes de vos questions sur les niveaux tout ce qu'il dit est:

Enfin, avoir des centaines de SSTables sur disque est aussi pas une bonne idée, donc périodiquement nous allons lancer un processus pour fusionner les SSTables sur disque. La documentation LevelDB offre probablement la meilleure réponse: (maximiser la taille des écritures et des lectures, puisque LevelDB est un stockage de données sur disque (recherche lente)).

Bonne chance!

Answer 2

Je pense qu'il s'agit principalement de la fusion facile et rapide des niveaux.

En Leveldb, le niveau (i + 1) a env. 10 fois les données comparées au niveau-i. Ceci est plus analogue à une structure de cache à plusieurs niveaux où si la base de données a 1000 enregistrements entre les clés x1 à x2, alors 10 des accès les plus fréquemment utilisés dans cette gamme seraient au niveau 1 et 100 dans la même plage serait au niveau 2 et reste au niveau 3 (ce n'est pas exact mais juste pour donner une idée intuitive des niveaux). Dans cette configuration, pour fusionner un fichier au niveau-i, nous devons regarder au plus 10 fichiers de niveau- (i + 1) et tout peut être mis en mémoire, une fusion rapide effectuée et réécrite. Il en résulte une lecture de blocs de données relativement petits pour chaque opération de compactage/fusion. D'autre part, si vous n'aviez que 2 niveaux, la plage de clés dans un fichier de niveau 0 pourrait potentiellement correspondre à 1000 fichiers de niveau 1 et tous doivent être ouverts pour la fusion qui va être assez lent. Notez qu'une hypothèse importante ici est que nous avons des fichiers de taille fixe (disons 2MB). Avec des fichiers de longueur variable au niveau 1, votre idée pourrait encore fonctionner et je pense qu'une variante de cela est utilisée dans des systèmes comme HBase et Cassandra. Maintenant si vous êtes préoccupé par la recherche de retard avec plusieurs niveaux, encore une fois c'est comme une structure de cache à plusieurs niveaux, les dernières données écrites seraient dans des niveaux plus élevés pour aider avec la localité typique de référence.

Answer 3

Le niveau 0 correspond aux données en mémoire les autres niveaux sont des données de disque. La partie importante est que les données dans les niveaux sont triées. Si level1 est constitué de 3 fichiers de 2Mb, alors dans fichier1, ce sont les touches 0..50 (triées) dans le fichier2 150..200 et dans le fichier3 300..400 (à titre d'exemple). Ainsi, lorsque le niveau de mémoire est plein, nous devons insérer les données sur le disque de la manière la plus efficace, c'est-à-dire en écriture séquentielle (en utilisant le moins de recherche de disque possible).Imaginez en mémoire que nous avons les touches 60-120, cool, nous les écrivons séquentiellement sous forme de fichier qui devient file2 dans level1. Très efficace! Mais maintenant, imaginons que level1 soit beaucoup plus grand que level0 (ce qui est raisonnable puisque le niveau0 est de la mémoire). Dans ce cas, il y a beaucoup de fichiers dans level1. Et maintenant, nos clés en mémoire (60-120) appartiennent à de nombreux fichiers car la gamme clé dans le niveau 1 est très fine. Maintenant, pour fusionner level0 et level1, nous devons lire beaucoup de fichiers et faire beaucoup de recherches aléatoires, créer de nouveaux fichiers en mémoire et les écrire. Donc, c'est là que de nombreux niveaux entrent en jeu, nous aurons beaucoup de couches, chacune plus grande que la précédente (x10), mais pas beaucoup plus grande, donc quand nous devons migrer des données de i-1 à i-ème couche, nous avons bonne chance d'avoir à lire le moins de fichiers. Maintenant, puisque les données peuvent changer, il n'est peut-être pas nécessaire de les propager vers des couches plus coûteuses (elles peuvent être modifiées ou supprimées) et nous évitons ainsi les fusions coûteuses. Les données qui se retrouvent dans le dernier niveau sont statistiquement les moins susceptibles de changer, c'est donc le meilleur ajustement pour la dernière couche la plus coûteuse à fusionner.