Comment fonctionnent les internals de stockage DynamoDB

DynamoDB est une hash table dont les values sont des arbres triés, étalés entre machines dans trois Availability Zones. Deux structures de données font presque tout le travail : un hash sur la partition key choisit une machine, un B-tree sur la sort key ordonne les items dedans.

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

DynamoDB stocke tes données comme une géante hash table distribuée dont les values sont des B-trees triés. Un hash sur la partition key choisit un storage node ; un B-tree ordonne les items par sort key dedans. Chaque écriture va à un leader qui réplique vers deux peers à travers trois Availability Zones, acknowledging une fois qu'un quorum (deux des trois replicas) l'a.

• La partition key est hashée, pas recherchée. DynamoDB lance une fonction de hash sur ton PK pour trouver le storage node (ou les nodes, une fois qu'une grande collection split) tenant cette partition — un jump O(1), quelle que soit la taille du table.
• La sort key vit dans un B-tree. Dans une partition, les items sont stockés dans un B-tree ordonné par sort key — ordre d'octets UTF-8 pour les strings, ordre numérique pour les Number keys — c'est pourquoi les lectures de plage (begins_with, between) sont bon marché et Scan ne l'est pas.
• Chaque écriture commit sur un quorum avant d'ack. Une écriture va à un leader, qui réplique vers deux peers dans d'autres AZs et acknowledge une fois qu'un quorum (deux des trois replicas) l'a — la durabilité est achetée avant que ton PutItem renvoie.
• C'est pourquoi les règles de modèles d'accès existent. Hash-then-tree n'est rapide que quand tu lis par clé. Pas de clé, pas de fast path — tu retombes sur le scanning de l'arbre.

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

Venant de SQL, tu imagines un table comme des lignes sur le disque avec un query planner qui choisit des indexes. DynamoDB n'a pas de planner. Le layout de stockage est le contrat — ce qui est rapide et ce qui est un footgun tombent tous deux droit de deux structures.

Imagine une géante map distribuée. La clé est un hash de ta partition key. La value est tout un B-tree d'items qui partagent cette partition key, ordonnés par sort key.

Tout le reste — sémantiques de query, les warnings 10 GB, pourquoi une clé manquante force un Scan — est une conséquence de cette seule phrase.

Hashe la partition key pour trouver le nœud

Quand une requête arrive, DynamoDB applique une fonction de hash interne à la valeur de partition key. Le hash mappe déterministiquement vers un storage node — la partition physique qui possède ces items. AWS documente ça comme le mécanisme derrière les lookups de clé à temps constant quelle que soit la taille du table.

C'est l'étape O(1). Un table de 10 TB et un table de 10 KB coûtent la même chose à localiser : hash, jump, done. Pas de scan d'index pour trouver le nœud, pas de statistiques, pas de plan.

Le catch est le flip side. Si tu ne fournis pas la partition key, DynamoDB n'a pas de nœud vers lequel jumper — il doit marcher chaque partition. C'est un Scan, et c'est la différence entre O(1) et lire tout le table.

La requête hashe vers exactement une partition, puis descend le B-tree de sort key de cette partition jusqu'à l'item — deux étapes bon marché au lieu d'une marche de table.

Ordonne les items dans un B-tree per-partition

Dans une seule partition, les items ne sont pas un heap. Ils sont tenus dans un B-tree keyed par la sort key, ordonné lexicographiquement. Une recherche B-tree est O(log n), et crucialement ce n est les items dans une partition, pas tout le table.

C'est toute la raison pour laquelle les lectures de plage de sort key sont bon marché. Prends un table de télémétrie de flotte où les readings de chaque device vivent sous une partition key :

Parce que le B-tree est trié, « toutes les readings entre 08:00 et 09:00 » est une descente d'arbre jusqu'à la valeur de départ plus une marche séquentielle — pas un filter sur chaque reading que le device a jamais envoyée. Tu ne lis que la plage matchée.

Cet ordre est aussi pourquoi un query begins_with(SK, "READING#2026-06-23") est rapide tandis que filter sur un attribut non-clé ne l'est pas. L'arbre peut seek par SK ; il ne peut seek par rien d'autre. Pour composer ces key conditions en sécurité, construis-les dans le DynamoDB Expression Builder plutôt que de concaténer des strings à la main :

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

Réplique chaque écriture vers trois AZs

Une partition n'est pas une machine. Chacune est répliquée à travers trois nœuds dans trois Availability Zones — le design quorum leader-based détaillé dans le papier DynamoDB USENIX ATC 2022 (le papier Amazon Dynamo 2007 est l'ancêtre de naming et de philosophie, pas ce modèle de réplication).

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

Les lectures ont un choix. Une lecture strongly consistent va au leader et voit la dernière écriture commitée. Une lecture eventually consistent peut être servie par n'importe lequel des trois nœuds, dont un peut être quelques millisecondes derrière — c'est le lag que tu trades pour des lectures moins chères et plus disponibles.

En facturation on-demand, une lecture strongly d'un item 2 KB coûte 1 RCU ; la même lecture eventually-consistent coûte 0.5 RCU. Line-rate tes hot paths dans le calculateur de pricing.

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

Lis les règles depuis la structure

Presque chaque « règle » DynamoDB est juste de la physique de stockage :

• Fournis toujours la partition key. Pas de clé, pas de cible de hash — tu scanne toute la map. C'est le cœur de Query vs Scan.
• Co-localise ce que tu lis ensemble sous une partition key, pour qu'un seul hash + tree-walk renvoie toute l'item collection. C'est le fondement du single-table design.
• Garde les partitions bornées. Une partition est un B-tree sur un set fini de nœuds ; une hot key runaway ou le plafond LSI de 10 GB sont tous deux des limites de cette partition physique.

Une fois que tu vois la forme hash-then-B-tree, la discipline des modèles d'accès arrête de sembler arbitraire — tu gardes juste chaque lecture sur le fast path.

Étapes suivantes

Modélise tes clés pour matcher la structure avec stratégies de sort key et single-table design, puis assemble les expressions réelles dans le DynamoDB Expression Builder. Essaie DynoTable pour regarder ces lectures tourner contre tes propres tables et voir exactement quels items une key condition tire.