Partitionnement et Réplication des Données

Le partitionnement des données divise une base de données sur plusieurs nœuds pour l'évolutivité, tandis que la réplication maintient des copies des données sur plusieurs nœuds pour la disponibilité et la performance en lecture ; ensemble, ils déterminent comment une base de données distribuée s'adapte et tolère les pannes.

Definition

Le partitionnement (fragmentation ou sharding) divise les lignes ou les colonnes d'une relation sur plusieurs nœuds afin que chacun détienne une portion des données ; la réplication stocke des copies des mêmes données sur plusieurs nœuds ; les politiques de placement et de réplication régissent conjointement l'évolutivité, la disponibilité et l'équilibrage de charge.

Scope

Ce sujet couvre la manière dont les données sont placées sur les nœuds : le partitionnement horizontal (fragmentation ou sharding) par plage, hachage ou liste, et le partitionnement vertical par colonne ; les stratégies de partitionnement, y compris le hachage cohérent ; et les modèles de réplication — synchrone versus asynchrone, primaire-secondaire versus multi-primaire — ainsi que les compromis entre cohérence et disponibilité qu'ils impliquent. Il traite de la façon dont le partitionnement permet le parallélisme et la réplication la tolérance aux pannes. Il exclut les protocoles de validation et de consensus qui maintiennent la cohérence des répliques, qui constituent un sujet connexe.

Core questions

• Comment le partitionnement par plage, hachage et liste distribue-t-il les lignes entre les nœuds ?
• Quand le partitionnement vertical est-il préférable au partitionnement horizontal ?
• Comment le hachage cohérent limite-t-il le mouvement des données lorsque des nœuds sont ajoutés ou supprimés ?
• Quels sont les compromis entre la réplication synchrone et asynchrone ?
• Comment la réplication primaire-secondaire et multi-primaire diffèrent-elles en termes de cohérence et de disponibilité ?

Key concepts

• partitionnement horizontal (fragmentation ou sharding)
• partitionnement vertical
• partitionnement par plage, hachage et liste
• hachage cohérent
• réplication synchrone versus asynchrone
• réplication primaire-secondaire
• réplication multi-primaire
• clé de partitionnement et équilibrage de charge

Key theories

Partitionnement horizontal et vertical

Le partitionnement horizontal (fragmentation ou sharding) distribue les lignes d'une table entre les nœuds via une clé de partitionnement pour répartir la charge et permettre le traitement parallèle, tandis que le partitionnement vertical divise une table par colonnes ; la fonction de partitionnement affecte de manière critique l'équilibrage de charge et la localité des requêtes.

Hachage cohérent

Le hachage cohérent mappe les clés et les nœuds sur un anneau de sorte que l'ajout ou la suppression d'un nœud ne déplace qu'une petite fraction bornée de clés, ce qui en fait une technique fondamentale pour le partitionnement dans les magasins de données distribués élastiques.

Modèles de réplication et compromis

La réplication synchrone maintient des copies identiques au prix de la latence et de la disponibilité en cas de partitions, tandis que la réplication asynchrone est plus rapide mais peut servir des données périmées ; la réplication primaire-secondaire centralise les écritures tandis que la réplication multi-primaire permet des écritures n'importe où au prix de la résolution des conflits.

Clinical relevance

Le partitionnement et la réplication sont les leviers qui permettent aux systèmes de données de s'adapter et de rester disponibles : la fragmentation permet à une seule base de données logique de gérer des charges de travail qu'aucune machine seule ne pourrait supporter, et la réplication maintient les services opérationnels et rapides malgré les pannes et à travers les régions, rendant ces techniques essentielles à toute plateforme de données à grande échelle.

History

La fragmentation et la réplication ont été étudiées dans les premiers systèmes de bases de données distribuées de la fin des années 1970 et des années 1980. Le hachage cohérent, introduit par Karger et ses collègues en 1997 pour la mise en cache web, a ensuite été adopté par les magasins clé-valeur évolutifs comme schéma de partitionnement, et les grands services internet ont popularisé la fragmentation et la réplication agressives pour l'élasticité et la disponibilité.

Key figures

• M. Tamer Özsu
• Patrick Valduriez
• David Karger

Seminal works

• ozsu2011
• karger1997

Frequently asked questions

Quelle est la différence entre le partitionnement et la réplication ?

Le partitionnement divise les données de sorte que chaque nœud détienne un sous-ensemble différent, ce qui répartit le stockage et la charge pour l'évolutivité. La réplication maintient des copies des mêmes données sur plusieurs nœuds pour la disponibilité et des lectures plus rapides. La plupart des grands systèmes font les deux : les données sont fragmentées entre les nœuds, et chaque fragment est répliqué plusieurs fois.

Pourquoi utiliser le hachage cohérent plutôt qu'un partitionnement par hachage simple ?

Avec un partitionnement par hachage basé sur le modulo ordinaire, changer le nombre de nœuds re-mappe presque toutes les clés, forçant un mouvement massif de données. Le hachage cohérent organise les clés et les nœuds sur un anneau de sorte que l'ajout ou la suppression d'un nœud ne réaffecte que les clés proches de ce nœud, rendant le rééquilibrage peu coûteux à mesure que le cluster s'agrandit ou se réduit.