Des algorithmes efficaces pour gérer les SSD. Des pages victimes à reloger

Les Solid-State Devices remplacent les disques durs, il faut :

Des algorithmes efficaces pour gérer les SSD
Des pages victimes à reloger

Laurent Bloch

Les Solid-State Devices [1] (mémoires persistantes à semiconducteurs, SSD) à base de mémoire flash [2] ont révolutionné le monde des mémoires non-volatiles depuis une dizaine d'années : ils sont plus rapides que les disques durs ; dépourvus de pièces mécaniques, ils sont moins sujets aux pannes ; au fil des ans leur capacité augmente et leur prix diminue, les méthodes d'accès [3] s'améliorent. Dans un article récent des Communications of the Association for Computing Machinery (CACM), Offline and Online Algorithms for SSD Management [4], Tomer Lange, Joseph (Seffi) Naor et Gala Yadgar proposent de nouveaux algorithmes pour optimiser les accès à ces types de mémoire.

Rappel sur les mémoires du passé

La mémoire centrale des ordinateurs, constituée depuis les années 1970 de semi-conducteurs (qui ont succédé aux tores de ferrite), voit son contenu effacé à la mise hors tension. Afin de conserver les données, divers dispositifs d'enregistrement persistant à base de procédés électro-magnétiques ont été mis au point au fil des décennies, principalement bandes et surtout depuis les années 1980 disques magnétiques.

Les disques magnétiques sont des appareils électromécaniques, les disques proprement dits sont en rotation et les têtes de lecture sont fixées sur des bras mobiles qui se déplacent pour atteindre la piste où se trouve la donnée voulue (les données sont enregistrées le long de pistes circulaires concentriques). Les algorithmes d'accès aux données dépendent de ces caractéristiques physiques, le temps d'accès se décompose en temps de positionnement de la tête (déplacement physique du bras) et délai rotationnel (attendre que la donnée passe sous la tête de lecture), on ne peut lire ou écrire qu'un seul bloc de données à la fois. Les performances restent acceptables pour des accès séquentiels (peu de déplacements de bras), elles s'effondrent en cas d'accès aléatoires. On conçoit que les stratégies d'accès aux données avec de tels appareils soient très différentes de celles pour la mémoire centrale, qui assure en théorie des accès à l'ensemble de l'espace de mémoire en temps constant (modulo les problèmes de correspondance entre mémoire virtuelle et mémoire réelle, et de mémoire cache [5]...).

Ascension et avantages des SSD

Les Solid-State Devices (SSD) [6] sont des mémoires à base de semi-conducteurs, comme la mémoire centrale, mais persistantes, comme celles des clés USB ou des cartes SD des appareils photo. L'article Wikipédia [7] donne le détail des procédés utilisés. La documentation AWS [8] est bien faite et introduit un vocabulaire (français) cohérent, le site de l'université Gustave Eiffel explique le fonctionnement des transistors à grille flottante [9] et comment ils peuvent conserver leur état quand ils ne sont plus alimentés.

La technologie à semi-conducteurs, affranchie des contraintes mécaniques inhérentes aux disques durs, permet des accès simultanés à plusieurs données de la mémoire SSD, avec un temps d'accès uniforme, typiquement moins de 0,1 milliseconde, alors que pour un disque dur on ne peut guère espérer moins de 3 millisecondes dans le meilleur des cas (pas de déplacement du bras de lecture), et plutôt 15 millisecondes dans le cas général. À l'heure actuelle la plupart des mémoires SSD sont connectées par l'interface physique PCI-Express [10], ce qui autorise des débits de données bien supérieurs (au moins un ordre de grandeur) à ceux de l'interface Serial ATA [11] des disques durs, et selon les spécifications logiques NVM Express [12].

Aujourd'hui (en 2023) les mémoires SSD sont encore sensiblement plus chères que les disques durs, dans un rapport de 1 à 3, et elles n'atteignent pas encore les mêmes capacités, mais les écarts ne cessent de se réduire. Sauf cas particuliers il n'y a aujourd'hui plus guère de raison d'utiliser les disques durs. En outre les mémoires SSD sont silencieuses et consomment moins d'électricité...

Contraintes d'utilisation des mémoires SSD

Selon la documentation Amazon AWS [13], un SSD comporte des transistors à grille flottante [14] disposés en quadrillage. Chaque ligne de ces quadrillages est appelée page, une collection de pages adjacentes [typiquement 128] constitue un bloc.

Un SSD stocke des informations au sein de ces blocs. Les différentes charges sur les transistors à grille flottante représentent des uns et des zéros binaires. Ce modèle binaire est la façon dont un SSD communique les données. Le contrôleur du SSD enregistre l'emplacement de stockage de données spécifiques dans le lecteur, ce qui vous permet d'y accéder sur votre ordinateur.

L'accès en lecture à la mémoire SSD obéit aux mêmes principes que les accès à la mémoire centrale : le système d'exploitation détermine l'adresse de la page et permet au programme de la lire. Cette identité des modes d'accès laisse espérer la fin de la distinction entre mémoire centrale et fichiers [15], instaurée dans les années 1950 pour des raisons contingentes, et qui n'a vraiment plus lieu d'être depuis les années 1980.

L'accès en écriture obéit par contre à des contraintes supplémentaires : « Lorsque vous modifiez ou réécrivez une partie des données d'un SSD, celui-ci doit mettre à jour l'intégralité du bloc flash. Tout d'abord, le SSD copie les anciennes données dans un bloc disponible. Ensuite, il efface le bloc d'origine et réécrit les données avec les modifications apportées au nouveau bloc. Les SSD disposent d'un espace interne supplémentaire pour déplacer et dupliquer temporairement des données. En tant qu'utilisateur, vous ne pouvez pas accéder à ce stockage supplémentaire. ». Ces opérations sont effectuées par le micrologiciel (firmware) du contrôleur du SSD, sans autre intervention du système d'exploitation que l'invocation de la commande TRIM [16], destinée à éviter que les performances ne se dégradent avec le temps et le remplissage de chaque partition, en optimisant le placement des données à écrire, et en effectuant les opérations physiques les plus lourdes pendant les périodes de faible activité de l'appareil. Les données échangées entre le système d'exploitation et la mémoire SSD transitent par une mémoire tampon (buffer), une fonction de traduction (flash translation layer, FTL) assure la correspondance entre l'adresse logique d'une page et l'adresse physique de l'emplacement qu'elle occupe.

Pour écrire une donnée dans une page, il faut donc en définitive réécrire deux fois toutes les pages actives du bloc : c'est le facteur d'amplification d'écriture (Write Amplification Factor, WAF). Et, pour citer les auteurs de notre article, « l'effacement d'un bloc prend typiquement quelques millisecondes, plusieurs ordres de grandeur de plus qu'une lecture ou une écriture ».

L'écriture sur SSD soulève un autre problème : après un certain nombre de cycles écriture-effacement (également appelé cycles P/E pour Program / Erase Cycles) l'emplacement correspondant sur le support se dégrade et devient inutilisable, typiquement après quelques dizaines de milliers d'écritures. Il importe donc de concevoir les programmes d'application, les pilotes de périphériques SSD et le micrologiciel de façon à réduire au minimum le nombre d'opérations d'écriture physique à chaque endroit. C'est à quoi se sont attaqués Tomer Lange, Joseph (Seffi) Naor et Gala Yadgar dans leur article des CACM [17].

Des algorithmes moins myopes et plus efficaces

La plupart des algorithmes d'écriture actuels sont qualifiés par nos auteurs de myopes, parce qu'ils n'ont accès à aucune information sur les écritures à venir dans le futur. C'est cette myopie qu'ils vont tenter de corriger. Mais en attendant, dans cette situation, il est intuitivement avantageux d'effacer le bloc qui contient le moins de pages valides, ce qui réduira le nombre de pages à réécrire et libérera le plus d'emplacements (slots) vides. En l'absence d'information supplémentaire, nos auteurs montrent que cette intuition est correcte.

Parmi les algorithmes myopes, le plus simple est l'algorithme glouton (greedy), sur lequel sont basés la plupart des autres : il attend que le SSD soit plein, et alors il efface le bloc qui contient le moins de pages valides, désigné comme le bloc victime.

L'article commence par poser quelques idées pour clarifier le problème : la version la plus récente d'une page est considérée valide ; toutes les autres versions sont invalides. À un instant t, tout emplacement (slot) du SSD est de façon déterministe dans un des états suivants : valide, invalide ou propre (clean). Un emplacement est valide s'il contient la version valide d'une page. Un emplacement valide qui contient la page p devient invalide en cas de modification de la page p. Et après un effacement du bloc b tous les emplacements de b sont propres (clean).

Toutes les recherches sur ce sujet ont pour objectif de réduire le nombre de réécritures de blocs pour une séquence donnée d'écritures ou de modifications de pages.

Nos auteur appuient leur démarche sur l'idée de date d'expiration (death time) d'une page, c'est-à-dire l'instant où elle sera invalidée : si l'on peut estimer les dates d'expiration des pages, il est avantageux de regrouper dans un même bloc les pages qui ont des dates d'expiration voisines : ainsi, « quand toutes les pages d'un bloc sont invalidées approximativement en même temps, l'amplification d'écriture peut être minimisée en choisissant comme bloc victime celui dont toutes les pages ont été invalidées ».

Partant de cette idée, tout le problème va être de trouver une méthode de prédiction des dates d'expiration des pages. Après que les tentatives d'utilisation de l'apprentissage automatique (machine learning) n'aient pas donné les résultats espérés, nos auteurs ont connu des algorithmes qui tiennent compte du caractère imparfait de l'oracle de prédiction des dates d'expiration utilisé, susceptible d'erreurs. Au fil de ce travail il leur est apparu que la proportion de capacité excédentaire, c'est-à-dire le rapport entre la capacité physique de l'appareil et sa capacité logique (accessible à l'utilisateur) était un facteur clé pour le calcul de l'efficacité des algorithmes (le fait qu'ils soient ou non plus efficaces que l'algorithme glouton, dans la cas général ou dans le pire des cas).

Approche systématique

Nos auteurs voient deux limitations inhérentes aux algorithmes myopes :

choisir le bloc victime selon le nombre d'emplacements valides qu'il contient n'est pas forcément optimal : il est par exemple raisonnable de retarder l'effacement d'un bloc dont les pages vont être utilisées à brève échéance, même s'il ne contient qu'un petit nombre d'emplacements valides ;
les algorithmes myopes ne possèdent aucune information qui permettrait de choisir judicieusement les emplacements pour les nouvelles pages à écrire.

Pour pallier ces limitations, la démarche de nos auteurs repose sur l'idée de date d'expiration, déjà évoquée ci-dessus.

Définition : la date d'expiration de la page p à l'instant t, notée y(p, t), est l'instant du prochain accès à p après l'instant t.

En groupant dans un même bloc les pages de dates d'expirations voisines, on réduira l'intervalle de temps pendant lequel ce bloc contiendra un mélange de pages valides et invalides, ce qui le rendra plus vite disponible pour un effacement sans réécriture. Mais pour cela encore faudrait-il connaître les dates d'expiration ! Un bloc qui contient un mélange de pages valides et invalides est nommé par nos auteurs un bloc zombie.

L'idée générale de la méthode envisagée est la suivante : on nommera lot (batch) un ensemble de blocs dont les emplacements sont occupés par des pages selon leur date d'expiration prédite ; soit Δ le nombre total de lots. Si les prιdictions d'expiration sont exactes, chaque lot contient au plus un bloc occupé par un mélange de pages valides et invalides (bloc zombie). Δ est donc une mesure du désordre induit par le placement des pages : plus Δ est grand, plus il y a de blocs zombie. L'idιe est de maintenir la valeur de Δ la plus basse possible en rιordonnant les pages quand elle augmente. Et comme une telle opération de réorganisation implique de nombreuses réécritures, il faut en outre s'assurer qu'elle est effectuée rarement.

Dans un premier temps, nos auteurs appliquent leur méthode dans une configuration où toute la séquence des opérations est connue à l'avance, ce qui permet bien sûr de connaître les dates d'expiration des pages. Cette situation expérimentale permet de prouver que l'algorithme ainsi conçu n'effectue qu'un nombre négligeable de réécritures, elle montre l'importance de la méthode de placement (par opposition à une stratégie de sélection de victime) et l'utilité de connaître les dates d'expiration.

Dans un second temps, les auteurs se placent dans une situation plus réaliste, où la séquence des opérations à venir n'est pas connue. Ils postulent l'existence d'un oracle qui pour chaque opération fournit la date d'expiration de la page concernée. Un tel oracle aura pu être obtenu par apprentissage automatique, et on sait qu'il pourra commettre des erreurs. De surcroît il ne donne pas les dates d'expiration des pages concernées par les opérations ultérieures. Compte tenu de ces causes d'erreur et d'incertitude, la réorganisation des pages peut entraîner un nombre excessif de réécritures. Pour faire face à ce risque, ils supposent la disponibilité d'une mémoire auxiliaire attachée au contrôleur, plus petite mais beaucoup plus rapide que le SSD, destinée à accueillir d'une part les nouvelles pages en attente de placement, d'autre part les pages valides à réécrire ailleurs parce qu'elles étaient dans un bloc victime.

Résultats et conclusions

Le lecteur pourra se reporter à l'article pour la description complète des algorithmes et leurs preuves, ainsi que les résultats expérimentaux obtenus par comparaison avec l'algorithme glouton et avec l'algorithme HotCold. Ces résultats montrent, pour toute une série de configurations du matériel et de séquences d'opérations, de bien meilleures performances pour les algorithmes exposés dans l'article de Tomer Lange, Joseph (Seffi) Naor et Gala Yadgar.

Laurent Bloch

Article mis en ligne le 7 septembre 2023 sut le site de Laurent Bloch.
https://laurentbloch.net/MySpip3/Des-algorithmes-efficaces-pour-gerer-les-SSD

Cet article est sous licence Creative Commons Attribution 4.0 International. https://creativecommons.org/licenses/by/4.0/deed.fr

NOTES

[1] https://fr.wikipedia.org/wiki/SSD

[2] https://fr.wikipedia.org/wiki/M%C3%A9moire_flash

[3] https://laurentbloch.net/MySpip3/NVMe-simple-perfectionnement-ou-premice-d-une-revolution

[4] https://cacm.acm.org/magazines/2023/7/274045-offline-and-online-algorithms-for-ssd-management/fulltext

[5] https://laurentbloch.net/MySpip3/Complexite-de-l-analyse-du-cache

[6] https://laurentbloch.net/MySpip3/NVMe-simple-perfectionnement-ou-premice-d-une-revolution

[7] https://fr.wikipedia.org/wiki/SSD#Techniques

[8] https://aws.amazon.com/fr/compare/the-difference-between-ssd-hard-drive/