Inleiding
Stel je een dienst voor die gebruikersprofielen, voorkeuren en accountinstellingen opslaat. Eén database heeft zijn praktische capaciteitsgrens bereikt, dus de dienst verdeelt gebruikers over meerdere databaseshards. Op basis van een gebruikers-ID moet elke applicatie-instantie kunnen bepalen welke shard de gegevens van die gebruiker beheert.
Zolang het aantal shards gelijk blijft, is routering eenvoudig. Een shard toevoegen maakt het interessant: een verzoek naar een andere database sturen verplaatst de benodigde rijen nog niet.
Consistente hashing beperkt hoeveel gebruikers je moet verplaatsen. Een migratieprotocol zorgt ervoor dat die verplaatsingen veilig verlopen.
Waarom modulo duur kan worden
Een eenvoudige routeringsregel is:
shard = hash(userId) % shardCountNeem deze voorbeeldwaarden, met shardnummers die bij nul beginnen:
| Gebruikershash | Drie shards | Vier shards |
|---|---|---|
| 12 | 0 | 0 |
| 13 | 1 | 1 |
| 14 | 2 | 2 |
| 15 | 0 | 3 |
| 16 | 1 | 0 |
| 17 | 2 | 1 |
| 18 | 0 | 2 |
| 19 | 1 | 3 |
De meeste gebruikers in dit voorbeeld krijgen een andere bestemming zodra de vierde shard verschijnt. Bij uniform verdeelde hashwaarden verplaatst een directe overgang van drie naar vier buckets ongeveer driekwart van de sleutels. Vergelijk hiervoor de resten over een volledige cyclus van twaalf waarden: slechts drie behouden hetzelfde bucketnummer.
Schakelt de applicatie over voordat de gegevens zijn gemigreerd, dan belanden verzoeken op shards waar die gebruikers nog niet bestaan. Eerst alles migreren lost het probleem ook niet volledig op: tijdens het kopiëren blijven er wijzigingen binnenkomen.
Modulo is niet per definitie verkeerd. Het probleem is dat de deler rechtstreeks afhangt van het aantal fysieke databases, terwijl dat juist het aantal is dat we willen kunnen veranderen.
Plaats shards op een ring
Consistente hashing plaatst shardposities en gebruikershashes in dezelfde cirkelvormige ruimte. Een gebruiker hoort bij de eerste shardpositie op of na zijn hash. Aan het einde gaat de zoektocht verder vanaf het begin. Deze verdeling via een ring wordt beschreven in het oorspronkelijke Dynamo-artikel, paragraaf 4.2 .
Gebruik voor een klein voorbeeld de posities 0 tot en met 99, met shard A op 20, B op 50 en C op 80. Volg oplopende posities met de klok mee; na 99 begin je weer bij 0.
De volgende posities zijn gekozen om het principe uit te leggen, niet berekend uit echte gebruikers-ID’s.
| Gebruiker | Hashpositie | Eigenaar |
|---|---|---|
| Alice | 10 | A |
| Ben | 35 | B |
| Carmen | 65 | C |
| Dev | 90 | A |
Voeg nu shard D toe op positie 40. De ring wordt:
block-beta
columns 3
space A(("A · 20")) space
C(("C · 80")) space D(("D · 40 · new"))
space B(("B · 50")) space
A --> D
D --> B
B --> C
C -- "99 → 0: wrap" --> AVolg de pijlen met de klok mee, vanaf A bovenaan. De afstanden zijn schematisch en niet evenredig aan de hashbereiken. Zonder D liep de pijl van A rechtstreeks naar B. D vangt nu hashes op die groter zijn dan 20 en hoogstens 40 zijn.
D wordt eigenaar van het interval (20, 40]. Ben verhuist van B naar D. De andere drie gebruikers houden hun eigenaar. Een gebruiker precies op positie 40 hoort ook bij D; een gebruiker op 20 blijft bij A.
Alleen het interval dat de nieuwe positie overneemt, verandert van eigenaar. Bij een evenwichtige plaatsing en uniform verdeelde sleutels verplaatst het toevoegen van een shard met gelijke capaciteit aan N shards naar verwachting ongeveer 1 / (N + 1) van de sleutels. Dat is een verwachting, geen garantie voor een specifieke ring of voor het aantal te verplaatsen bytes.
Een kleine routeringsfunctie
Je kunt de eigenaar opzoeken met binair zoeken in een gesorteerde lijst van posities:
type Token = { position: bigint; shardId: string;};
function ownerForHash(hash: bigint, ring: readonly Token[]): string { if (ring.length === 0) throw new Error("De shardring is leeg");
let low = 0; let high = ring.length;
while (low < high) { const middle = low + Math.floor((high - low) / 2); const token = ring[middle]!;
if (token.position < hash) low = middle + 1; else high = middle; }
return ring[low % ring.length]!.shardId;}
const ring: Token[] = [ { position: 20n, shardId: "A" }, { position: 40n, shardId: "D" }, { position: 50n, shardId: "B" }, { position: 80n, shardId: "C" },];
ownerForHash(35n, ring); // DownerForHash(90n, ring); // A: terug naar het beginDit is een routeringsvoorbeeld, geen volledige databaseclient. Het gaat uit van een onveranderlijke ring met unieke, gesorteerde posities en hashes en tokens binnen hetzelfde niet-negatieve bereik. Bij het opbouwen van de ring moet je tokenbotsingen deterministisch afwijzen of oplossen.
Leg in een echte dienst het hashalgoritme, de seed, de invoercodering en de normalisatie van gebruikers-ID’s vast als onderdeel van het routeringsprotocol. Gebruik niet de standaard objecthash van een programmeertaal: een ander proces of een andere taal kan een ander resultaat opleveren. Gebruik stabiele logische shard-ID’s in plaats van hostnamen, zodat het vervangen van een databasehost niet onbedoeld de verdeling verandert.
Virtuele nodes verbeteren de verdeling
Eén positie per shard kan ertoe leiden dat sommige shards veel grotere intervallen bezitten. Virtuele nodes geven elke fysieke shard meerdere posities verspreid over de ring. Elke positie verwijst nog steeds naar dezelfde shard; het is geen extra database of kopie van de gegevens. Dynamo gebruikt deze techniek om de verdeling te verbeteren en rekening te houden met verschillen in capaciteit. Dynamo-artikel
Een clusterconfiguratie kan bijvoorbeeld tokens toewijzen aan identiteiten als A:0, A:1 en A:2. Houd die identiteiten stabiel wanneer je D toevoegt. Alle tokens opnieuw genereren zou de gewenste stabiliteit juist tenietdoen.
Meer tokens kunnen het eigenaarschap gelijkmatiger verdelen, maar gelijke aantallen sleutels betekenen niet noodzakelijk een gelijke belasting. Meet naast gebruikersaantallen ook bytes, verzoekfrequentie en latentie.
- Een nieuwe shard verandert alleen het eigenaarschap van bepaalde bereiken, in plaats van de meeste gebruikers opnieuw te verdelen.
- Virtuele nodes spreiden het eigenaarschap van elke shard over meerdere bereiken.
- Elke router kan uit dezelfde ringversie de eigenaar berekenen.
Kies wat met een gebruiker meeverhuist
In dit ontwerp is userId de verdeelsleutel voor een groep gerelateerde rijen:
user_profiles(user_id, ...)user_preferences(user_id, ...)user_addresses(user_id, address_id, ...)Een verzoek zoekt eerst de shard voor de gebruikers-ID op en voert daar zijn queries uit. Gerelateerde wijzigingen kunnen binnen één lokale databasetransactie blijven als alle benodigde rijen bij elkaar staan.
Een e-mailadres is meestal geen goede vervanging voor die sleutel, omdat het kan veranderen. Een inlogverzoek dat begint met een e-mailadres heeft een extra zoekstap nodig om de stabiele gebruikers-ID te vinden. Ook moet je bepalen hoe je unieke e-mailadressen over de hele dienst afdwingt; een unieke index op elke afzonderlijke shard is daarvoor niet genoeg.
Bij toepassingen waarin organisaties centraal staan, kan de keuze anders uitvallen. Als de meeste bewerkingen alle gebruikers binnen één organisatie raken, kan verdelen op tenantId meer transacties lokaal houden. Het nadeel is dat een grote organisatie één shard kan domineren. Kies de groepering op basis van de bewerkingen die je samen wilt uitvoeren.
Een nieuwe ring heeft een migratieprotocol nodig
Stel dat versie 7 van de ring Ben aan B toewijst en versie 8 aan D. Alleen de routers aanpassen zorgt ervoor dat Bens profiel onvindbaar lijkt. Het profiel eenmalig kopiëren is ook onvoldoende: een wijziging op B tijdens het kopiëren kan na de omschakeling verloren gaan.
Een mogelijk migratieontwerp gebruikt een snapshot, een wijzigingenstroom en een korte schrijfblokkade voor het te verplaatsen bereik:
- Bereid de bestemming voor. Maak de benodigde tabellen en indexen op D. Leg het bereik, de bron, de bestemming en de beoogde eigenaarschapsversie duurzaam vast in migratiemetadata. B blijft leidend.
- Kopieer een consistente snapshot. Verplaats alle gebruikersgebonden rijen binnen het bereik. Stem het beginpunt van de registratie van wijzigingen af op de snapshot, zodat je wijzigingen en verwijderingen tijdens het kopiëren zonder gaten kunt herhalen.
- Werk de achterstand weg. Pas wijzigingen in volgorde toe op D en zorg dat opnieuw proberen veilig is. Controleer de achterstand en valideer de gekopieerde gegevens terwijl B nog steeds lees- en schrijfverzoeken afhandelt.
- Blokkeer schrijvers en schakel om. Blokkeer schrijfverzoeken voor dat bereik kort of zet ze in een wachtrij. Verwerk de resterende wijzigingen en leg daarna de eigendomsoverdracht vast. Oude eigenaren moeten verzoeken met een verouderde versie weigeren of doorsturen; alleen routers verversen houdt oude schrijvers niet tegen.
- Bewaar en ruim op. Bewaar B’s oude kopie gedurende een vastgestelde herstelperiode en verwijder die pas nadat verkeer en replicatiestatus zijn gecontroleerd. Zodra D nieuwe wijzigingen accepteert, vereist terugdraaien het verwerken van die wijzigingen. Routers simpelweg terugzetten naar B is niet genoeg.
De precieze aanpak hangt af van de database. Een duurzame dienst voor eigenaarschap moet concurrerende migraties in een eenduidige volgorde afhandelen, en het schrijfpad moet die beslissingen afdwingen. Naïef naar beide databases schrijven introduceert een nieuw foutscenario: de ene database kan een wijziging accepteren terwijl de andere die weigert.
Neem ringversies op in operationele logs en de migratiestatus. Daarmee kun je een verouderde router onderscheiden van ontbrekende gegevens of een mislukte kopie.
Uitval is iets anders dan herverdeling
Als B uitvalt, stuurt het onmiddellijk verwijderen van B uit de ring zijn gebruikers naar andere shards. Hun gegevens zijn daar daardoor nog niet beschikbaar.
Behandel failover naar een replica apart van veranderingen in logisch shardeigenaarschap. Een logische shard kan een primaire database en replica’s in verschillende foutdomeinen hebben. Een geschikte replica promoveren behoudt de identiteit en verdeling van de shard; de ring veranderen start een andere operatie.
Een drukke gebruiker kan nog steeds een shard overbelasten
Zelfs een perfect verdeelde ring kan de belasting van één gebruiker niet splitsen als diens gegevens bij elkaar moeten blijven. Een beroemd account, geautomatiseerde client of uitzonderlijk grote organisatie kan zijn shard overbelasten terwijl andere shards ruimte overhouden.
Voor gegevens waaraan vooral wordt toegevoegd, zoals activiteiten, kan een afzonderlijke verdeelstrategie de belasting opdelen in tijdbuckets of deelsleutels. Leesverzoeken moeten dan weten welke partities ze moeten raadplegen. De AWS-handleiding over write sharding laat dezelfde afweging zien: schrijfbewerkingen over achtervoegsels verdelen vereist extra coördinatie bij het lezen.
Profielen en instellingen kunnen bij elkaar blijven op basis van de gebruikers-ID, terwijl activiteiten dat afzonderlijke schema gebruiken. Niet elke tabel in de dienst hoeft dezelfde verdeelstrategie te volgen.
Overweeg ook vaste logische buckets
Voor een SQL-omgeving waarin de applicatie de verdeling beheert, kun je gebruikers ook naar een vaste verzameling logische buckets hashen:
bucket = hash(userId) % 4096shard = placementTable[bucket]Hier is 4096 een voorbeeld van een bucketaantal dat gelijk blijft wanneer je fysieke shards toevoegt. Schalen verandert geselecteerde verwijzingen in de plaatsingstabel, niet de hashberekening voor elke gebruiker. Het bucketaantal later veranderen zou opnieuw een herverdelingsprobleem opleveren.
Dit ontwerp maakt expliciet welke eenheden je migreert. Een ring biedt flexibele tokenplaatsing; een bucketmap biedt een begrensde verzameling partities om bij te houden. Beide vereisen nog steeds gecoördineerde eigendomsoverdrachten en veilige gegevensoverdracht.
Controleer voordat je kiest of de database partitionering en herverdeling al zelf regelt. Een extra ring in de applicatie kan anders een nieuwe bron van routeringsstatus worden zonder een daadwerkelijk probleem op te lossen.
Voor een gebruikersdatabase is het ontwerp pas klaar als het meer kan beantwoorden dan ‘Welke shard bezit deze ID?’. Het moet ook duidelijk maken wie tijdens een migratie de volgende wijziging beheert, hoe verouderde routers worden afgehandeld en hoe het systeem herstelt als de bestemming halverwege uitvalt.
