Is een paar dagen geleden gebeurd . De jongens van de JUG.ru Group nodigden droomsprekers uit (Leslie Lamport! Cliff Click! Martin Kleppmann!) en besteedden twee dagen aan gedistribueerde systemen en computers. Kontur was een van de drie partners van de conferentie. We praatten bij de stand, spraken over onze gedistribueerde opslag, speelden bingo en losten puzzels op.
Dit is een post met een analyse van taken op de stand van Kontur van de auteur van hun tekst. Wie was er op de Hydra - dit is je reden om je de prettige ervaring te herinneren, wie niet - een kans om je hersens te strekken grote O-notatie.
Er waren zelfs deelnemers die de flipover in dia's uit elkaar haalden om hun beslissing op te schrijven. Ik maak geen grapje - ze hebben deze stapel papier ter verificatie overhandigd:
In totaal waren er drie taken:
- over het selecteren van replica's op gewicht voor taakverdeling
- over het sorteren van queryresultaten tegen een in-memory database
- op toestandsoverdracht in een gedistribueerd systeem met een ringtopologie
Taak 1. ClusterClient
Het was nodig om een algoritme voor te stellen voor de efficiënte selectie van K uit N gewogen replica's van een gedistribueerd systeem:
Uw team heeft de taak om een clientbibliotheek te ontwikkelen voor een massaal gedistribueerd cluster van N-nodes. De bibliotheek zou verschillende metagegevens bijhouden die zijn gekoppeld aan knooppunten (bijv. hun latentie, 4xx/5xx responspercentages, enz.) en zou drijvende-kommagewichten W1..WN aan hen toewijzen. Om de gelijktijdige uitvoeringsstrategie te ondersteunen, moet de bibliotheek K van N knooppunten willekeurig kunnen kiezen - de kans om geselecteerd te worden moet evenredig zijn met het gewicht van een knooppunt.
Stel een algoritme voor om knooppunten efficiënt te selecteren. Schat de computationele complexiteit ervan met behulp van de grote O-notatie.
Waarom is alles in het Engels?
Omdat in deze vorm de conferentiedeelnemers met hen vochten en omdat Engels de officiële taal van Hydra was. De taken zagen er als volgt uit:
Neem papier en potlood, denk na, haast je niet om meteen spoilers te openen 🙂
Analyse van de oplossing (video)
Vanaf 5:53, slechts 4 minuten:
En hier is hoe de jongens met de flipover hun oplossing presenteerden:
Analyse van de oplossing (tekst)
De volgende oplossing ligt aan de oppervlakte: som de gewichten van alle replica's op, genereer een willekeurig getal van 0 tot de som van alle gewichten, kies dan een i-replica zodanig dat de som van replicagewichten van 0 tot (i-1)de is minder dan een willekeurig getal, en de som van replicagewichten van 0 tot i-de - meer dan dat. Het is dus mogelijk om één replica te selecteren en om de volgende te selecteren, moet u de hele procedure herhalen zonder rekening te houden met de geselecteerde replica. Met zo'n algoritme is de complexiteit van het kiezen van één replica O(N), de complexiteit van het kiezen van K replica's is O(NK) ~ O(N2).
Kwadratische complexiteit is slecht, maar kan worden verbeterd. Om dit te doen, gaan we bouwen voor sommen van gewichten. Er zal een boom met een diepte van lg N worden verkregen, in de bladeren waarvan replicagewichten zullen zijn, en in de resterende knooppunten - gedeeltelijke sommen, tot de som van alle gewichten aan de wortel van de boom. Vervolgens genereren we een willekeurig getal van 0 tot de som van alle gewichten, vinden de i-de replica, verwijderen deze uit de boomstructuur en herhalen de procedure om de resterende replica's te vinden. Met dit algoritme is de complexiteit van het bouwen van een boom O(N), de complexiteit van het vinden van de i-de replica en het verwijderen uit de boom is O(lg N), de complexiteit van het kiezen van K replica's is O(N + K lg N) ~ O(N lg N) .
Lineair-log-complexiteit is leuker dan kwadratische complexiteit, vooral voor grote K.
Het is dit algoritme ClusterClient-bibliotheken van het project "". (Daar is de boom gebouwd in O(N lg N), maar dit heeft geen invloed op de uiteindelijke complexiteit van het algoritme.)
Taak 2. Zebra
Het was nodig om een algoritme voor te stellen voor het efficiënt sorteren van documenten in het geheugen door een willekeurig niet-geïndexeerd veld:
Uw team heeft de taak om een gesharde in-memory documentdatabase te ontwikkelen. Een gebruikelijke werklast zou zijn om de top N documenten te selecteren, gesorteerd op een willekeurig (niet-geïndexeerd) numeriek veld uit een verzameling van grootte M (meestal N < 100 << M). Een iets minder gebruikelijke werklast zou zijn om top N te selecteren na het overslaan van top S-documenten (S ~ N).
Stel een algoritme voor om dergelijke query's efficiënt uit te voeren. Schat de computationele complexiteit met behulp van de grote O-notatie in het gemiddelde geval en de worstcasescenario's.
Analyse van de oplossing (video)
Vanaf 34:50, slechts 6 minuten:
Analyse van de oplossing (tekst)
Oppervlak oplossing: sorteer alle documenten (bijvoorbeeld met ), neem dan N+S-documenten. In dit geval is de complexiteit van het sorteren gemiddeld O(M lg M), in het slechtste geval O(M2).
Het is duidelijk dat het inefficiënt is om alle M-documenten te sorteren en er vervolgens maar een klein deel van mee te nemen. Om niet alle documenten te sorteren, is een algoritme geschikt , waarmee N + S van de gewenste documenten wordt geselecteerd (ze kunnen worden gesorteerd op elk algoritme). In dit geval zal de complexiteit afnemen tot gemiddeld O(M), terwijl het slechtste geval gelijk blijft.
U kunt het echter nog efficiënter doen - gebruik het algoritme . In dit geval worden de eerste N+S-documenten toegevoegd aan de min- of max-heap (afhankelijk van de sorteerrichting), en vervolgens wordt elk volgend document vergeleken met de hoofdmap van de boom, die het huidige minimum- of maximumdocument bevat, en wordt indien nodig aan de boom toegevoegd. . In dit geval is de complexiteit in het slechtste geval, wanneer u de boom constant moet herbouwen, O(M lg M), de gemiddelde complexiteit is O(M), zoals bij quickselect.
Heap-streaming blijkt echter efficiënter te zijn omdat in de praktijk de meeste documenten kunnen worden weggegooid zonder de heap opnieuw op te bouwen na een enkele vergelijking met het root-element. Een dergelijke sortering is geïmplementeerd in de Zebra in-memory documentdatabase die is ontwikkeld en gebruikt in Kontur.
Taak 3. Staatsswaps
Het was nodig om het meest efficiënte algoritme voor het verschuiven van toestanden voor te stellen:
Jouw team heeft de taak om een fancy state exchange mechanisme te ontwikkelen voor een gedistribueerd cluster van N nodes. De status van het i-de knooppunt moet worden overgedragen naar het (i+1)-de knooppunt, de status van het N-de knooppunt moet worden overgedragen naar het eerste knooppunt. De enige ondersteunde bewerking is de toestandswisseling wanneer twee knooppunten hun toestanden atomair uitwisselen. Het is bekend dat een toestandswisseling M milliseconden duurt. Elk knooppunt kan op elk moment deelnemen aan een enkele toestandswissel.
Hoe lang duurt het om de toestanden van alle knooppunten in een cluster over te dragen?
Analyse van de oplossing (tekst)
Oppervlakte-oplossing: verwissel de toestanden van het eerste en tweede element, dan het eerste en derde, dan het eerste en vierde, enzovoort. Na elke uitwisseling bevindt de toestand van één element zich in de gewenste positie. Je moet O(N) permutaties maken en O(N M) tijd besteden.
Lineaire tijd is lang, dus je kunt de toestanden van elementen in paren uitwisselen: de eerste met de tweede, de derde met de vierde, enzovoort. Na elke toestandswisseling staat elk tweede element op de juiste plaats. Je moet O(lg N) permutaties maken en O(M lg N) tijd besteden.
Het is echter mogelijk om de verschuiving nog efficiënter te maken - niet in lineaire, maar in constante tijd. Om dit te doen, moet u bij de eerste stap de toestand van het eerste element uitwisselen met het laatste, het tweede met het voorlaatste, enzovoort. De toestand van het laatste element bevindt zich in de juiste positie. En nu moeten we de toestand van het tweede element verwisselen met het laatste, het derde met het voorlaatste, enzovoort. Na deze uitwisselingsronde zullen de toestanden van alle elementen in de juiste stand staan. Er zullen in totaal O(2M) ~ O(1) permutaties zijn.
Een dergelijke oplossing zal een wiskundige niet verbazen die zich nog herinnert dat een rotatie een samenstelling is van twee axiale symmetrieën. Overigens is het triviaal gegeneraliseerd voor een verschuiving, niet met één, maar met K < N posities. (Schrijf in de reacties hoe precies.)
Hield je van puzzelen? Weet jij andere oplossingen? Deel in de reacties.
En hier zijn uiteindelijk enkele nuttige links:
- leer meer over in omtrek
- zie verslagen van intern over gedistribueerde systemen
- bekijk de serie videocolleges»
- abonneer je op onze
Bron: www.habr.com