Comment fonctionnent les internes de stockage DynamoDB

DynamoDB est une table de hachage dont les valeurs sont des arbres triés, répartis sur des machines dans trois zones de disponibilité. Deux structures de données font presque tout le travail : un hash sur la clé de partition choisit une machine, un B-tree sur la clé de tri ordonne les items à l'intérieur.

Comment DynamoDB stocke-t-il les données ?

DynamoDB stocke tes données sous forme d'une gigantesque table de hachage distribuée dont les valeurs sont des B-trees triés. Un hash sur la clé de partition choisit un nœud de stockage ; un B-tree ordonne les items par clé de tri à l'intérieur. Chaque écriture est répliquée de façon synchrone vers trois nœuds dans trois zones de disponibilité avant d'acquitter.

• La clé de partition est hachée, pas cherchée. DynamoDB applique une fonction de hash sur ton PK pour trouver le seul nœud de stockage détenant cette partition — un saut O(1), quelle que soit la taille de la table.
• La clé de tri vit dans un B-tree. À l'intérieur d'une partition, les items sont stockés dans un B-tree ordonné lexicographiquement par SK, c'est pourquoi les lectures par plage (begins_with, between) sont bon marché et un Scan ne l'est pas.
• Chaque écriture touche trois nœuds avant d'acquitter. Une écriture va à un leader, qui réplique de façon synchrone vers deux pairs dans d'autres AZ — la durabilité est payée avant que ton PutItem ne revienne.
• C'est pourquoi les règles d'access pattern existent. Hash-puis-arbre n'est rapide que quand tu lis par clé. Pas de clé, pas de chemin rapide — tu retombes à parcourir l'arbre.

Commence par la structure de données, pas l'API

En venant de SQL, tu imagines une table comme des lignes sur disque avec un planificateur de requêtes qui choisit des index. DynamoDB n'a pas de planificateur. La disposition de stockage est le contrat — ce qui est rapide et ce qui est un piège découlent tous deux directement de deux structures.

Imagine une gigantesque carte distribuée. La clé est un hash de ta clé de partition. La valeur n'est pas un item unique — c'est tout un B-tree d'items qui partagent cette clé de partition, ordonnés par clé de tri.

Tout le reste — la sémantique de requête, les avertissements de 10 Go, pourquoi une clé manquante force un Scan — est une conséquence de cette seule phrase.

Hacher la clé de partition pour trouver le nœud

Quand une requête arrive, DynamoDB applique une fonction de hash interne à la valeur de la clé de partition. Le hash se mappe de façon déterministe à un seul nœud de stockage — la partition physique qui détient ces items. AWS documente ceci comme le mécanisme derrière les recherches par clé à temps constant, quelle que soit la taille de la table.

C'est l'étape O(1). Une table de 10 To et une table de 10 Ko coûtent la même chose à localiser : hacher, sauter, fini. Pas de scan d'index pour trouver le nœud, pas de statistiques, pas de plan.

Le hic est le revers de la médaille. Si tu ne fournis pas la clé de partition, DynamoDB n'a aucun nœud vers lequel sauter — il doit parcourir chaque partition. C'est un Scan, et c'est la différence entre O(1) et lire toute la table.

La requête se hache vers exactement une partition, puis descend le B-tree de clé de tri de cette partition jusqu'à l'item — deux étapes bon marché au lieu d'un parcours de table.

Ordonner les items dans un B-tree par partition

À l'intérieur d'une seule partition, les items ne sont pas un heap. Ils sont tenus dans un B-tree clé sur la clé de tri, ordonnés lexicographiquement. Une recherche dans un B-tree est en O(log n), et crucialement ce n est le nombre d'items dans une partition, pas dans toute la table.

C'est toute la raison pour laquelle les lectures par plage de clé de tri sont bon marché. Prenons une table de télémétrie de flotte où les mesures de chaque appareil vivent sous une seule clé de partition :

Parce que le B-tree est trié, « toutes les mesures entre 08:00 et 09:00 » est une descente d'arbre jusqu'à la valeur de début plus un parcours séquentiel — pas un filtre sur chaque mesure que l'appareil ait jamais envoyée. Tu ne lis que la plage correspondante.

Cet ordonnancement est aussi pourquoi une requête begins_with(SK, "READING#2026-06-23") est rapide alors que filtrer sur un attribut hors clé ne l'est pas. L'arbre peut chercher par SK ; il ne peut chercher par rien d'autre. Pour composer ces conditions de clé en toute sécurité, construis-les dans le constructeur d'expressions DynamoDB plutôt que de concaténer des chaînes à la main :

KeyConditionExpression  PK = :pk AND begins_with(SK, :day)

Répliquer chaque écriture sur trois AZ

Une partition n'est pas une seule machine. Chacune est répliquée sur trois nœuds dans trois zones de disponibilité — une lignée de conception qui remonte au modèle de réplication du papier Amazon Dynamo de 2007.

Un nœud est le leader de la partition. Une écriture va au leader, qui écrit localement et réplique vers ses deux pairs. Le leader acquitte l'écriture une fois qu'un quorum durable de nœuds l'a — donc la durabilité à travers les AZ est payée avant que ton PutItem ne revienne.

Les lectures ont un choix. Une lecture fortement cohérente va au leader et voit la dernière écriture committée. Une lecture à cohérence à terme peut être servie par n'importe lequel des trois nœuds, dont l'un peut être en retard de quelques millisecondes — c'est le décalage que tu échanges contre des lectures moins chères et plus disponibles.

La même idée de propagation asynchrone est pourquoi une lecture de GSI peut être périmée — vois les GSI sont à cohérence à terme.

Lire les règles à même la structure

Presque chaque « règle » DynamoDB n'est que de la physique de stockage :

• Fournis toujours la clé de partition. Pas de clé, pas de cible de hash — tu scannes toute la carte. C'est le cœur de Query vs Scan.
• Co-localise ce que tu lis ensemble sous une seule clé de partition, pour qu'un seul hash + parcours d'arbre renvoie toute la collection d'items. C'est le fondement du single-table design.
• Garde les partitions bornées. Une partition est un B-tree sur un ensemble fini de nœuds ; une clé chaude emballée ou le plafond de 10 Go d'un LSI sont tous deux des limites de cette partition physique.

Une fois que tu vois la forme hash-puis-B-tree, la discipline d'access pattern cesse de sembler arbitraire — tu gardes simplement chaque lecture sur le chemin rapide.

Étapes suivantes

Modélise tes clés pour correspondre à la structure avec les stratégies de clé de tri et le single-table design, puis assemble les vraies expressions dans le constructeur d'expressions DynamoDB. Essaie DynoTable pour regarder ces lectures s'exécuter contre tes propres tables et voir exactement quels items une condition de clé ramène.