Repenser les politiques de compactage dans les arbres de fusion structurés par journal (LSM-trees)

Les arbres de fusion structurés par journal (LSM-trees) sont largement utilisés pour construire des magasins de clés-valeurs. Ils compactent périodiquement les séquences triées qui se chevauchent afin de réduire l'amplification des lectures. Les recherches antérieures sur les politiques de compactage se sont concentrées sur le compromis entre l'amplification des écritures (WA) et l'amplification des lectures (RA). Dans cet article, nous proposons de considérer l'opération de compactage dans les LSM-trees comme un investissement en calcul et en bande passante I/O pour améliorer le débit de requêtes future du système, et donc de repenser les conceptions des politiques de compactage. Une application typique d’un LSM-tree gère un flux d'écriture modéré mais constant et privilégie les ressources pour les vidanges de haut niveau de petites séquences triées afin d'éviter la perte de données due aux interruptions d'écriture. L'objectif de la politique de compactage est donc de maintenir un nombre optimal de séquences triées pour maximiser le débit de requêtes moyen. Puisque les opérations de compactage et de lecture se disputent les ressources CPU et I/O du même pool, nous devons effectuer une optimisation conjointe pour déterminer le moment et l'agressivité appropriés du compactage. Nous introduisons un modèle à trois niveaux d'un LSM-tree et proposons EcoTune, un algorithme basé sur la programmation dynamique pour trouver la politique de compactage optimale selon les caractéristiques de charge de travail. Notre évaluation sur RocksDB montre qu'EcoTune améliore le débit moyen des requêtes de 1,5x à 3x par rapport à la politique de nivellement et jusqu'à 2,5x par rapport à la politique de nivellement paresseux sur des charges de travail avec des ratios de requêtes de plage/point.