Des chercheurs du MIT révolutionnent le stockage de données sur ordinateurs

Le stockage des informations constitue un aspect important et indispensable en informatique. Récemment, un trio de chercheurs du MIT a découvert une stratégie qui pourrait stimuler le stockage de données informatiques avec les tables de hachage à probation linéaire. Depuis plus d’un demi-siècle, ces tables sont des structures de données fréquemment utilisées, mais critiquées pour leur utilisation à faible capacité.

Des ordinateurs autour d'une moitié de la terre

D’après les éléments recueillis de cette découverte, il serait possible dans certains cas d’utiliser les tables de hachage à progression linéaire avec de grandes capacités de stockage. Plus intéressant encore, la vitesse ne serait pas sacrifiée et le stockage de données se ferait de manière plus efficace.

Cette nouvelle stratégie développée a été surnommée « hachage de cimetière ». Elle sera présentée en février 2022 au Symposium Foundations of Computer Science à Boulder, dans le Colorado.

Une idée de génies

Afin de mettre au point cette technique révolutionnaire, le groupe a repensé entièrement la façon traditionnelle dont les tables de hachage stockaient les informations.

Habituellement, les données se conservent dans les tables de façon linéaire, c’est-à-dire que la donnée parcourt le tableau jusqu’à ce qu’elle trouve une case mémoire vide pour s’y loger. Dans le cas de la suppression, le processus est pareil. Cependant, une fois que la donnée est supprimée, un marqueur nommé « pierre tombale » est inséré dans la case vide indiquant l’ancienne présence de l’information retirée.

Avec le « hachage de cimetière », le nombre de pierres tombales placées dans un tableau est augmenté artificiellement au point d’occuper la moitié de l’espace libre. Ainsi, ces pierres servent de réservations pour de futures données qui pourront être insérées.

« L’utilisation bien conçue de pierres tombales peut complètement changer le paysage de la façon dont le sondage linéaire se comporte. »

William Kuszmaul, Doctorant en informatique au MIT

Des travaux à faire avant la révolution

Le collectif de chercheurs soutient fermement que l’utilisation de la nouvelle manière peut conduire à des performances optimales dans les tables de hachage à progression linéaire. Le directeur de thèse de Kuszmaul approuve d’ailleurs cette affirmation.

Cependant, cette avancée théorique n’est pas suffisante pour réformer le stockage de données sur ordinateurs. Des expériences doivent être menées pour valider la découverte et pour connaître dans quelle mesure elle est réalisable.

« La construction d’une table de hachage comporte de nombreuses considérations. Bien que nous ayons considérablement avancé d’un point de vue théorique, nous ne faisons que commencer à explorer le côté expérimental des choses. »

William Kuszmaul, Doctorant en informatique au MIT