Händde för några dagar sedan . Killarna från JUG.ru Group bjöd in drömföreläsare (Leslie Lamport! Cliff Click! Martin Kleppmann!) och ägnade två dagar åt distribuerade system och datoranvändning. Kontur var en av konferensens tre partner. Vi pratade i montern, pratade om våra utdelade förråd, spelade bingo och löste pussel.
Det här är ett inlägg med en analys av uppgifter i Konturs monter från författaren till deras text. Vem var på Hydra - det här är din anledning att minnas den trevliga upplevelsen, vem var inte - en chans att sträcka ut din hjärna stor O-notation.
Det var till och med deltagare som demonterade blädderblocket till bilder för att skriva ner sitt beslut. Jag skämtar inte - de överlämnade den här pappersbunten för verifiering:
Det var tre uppgifter totalt:
- om att välja repliker efter vikter för lastbalansering
- om att sortera frågeresultat mot en databas i minnet
- på tillståndsöverföring i ett distribuerat system med ringtopologi
Uppgift 1. ClusterClient
Det var nödvändigt att föreslå en algoritm för effektivt urval av K från N viktade kopior av ett distribuerat system:
Ditt team har till uppgift att utveckla ett klientbibliotek för ett massivt distribuerat kluster av N noder. Biblioteket skulle hålla reda på olika metadata associerade med noder (t.ex. deras latenser, 4xx/5xx svarsfrekvenser, etc.) och tilldela flyttalvikter W1..WN till dem. För att stödja strategin för samtidig exekvering bör biblioteket kunna välja K av N noder slumpmässigt – chansen att väljas bör vara proportionell mot en nods vikt.
Föreslå en algoritm för att välja noder effektivt. Uppskatta dess beräkningskomplexitet med hjälp av stor O-notation.
Varför är allt på engelska?
För att i denna form kämpade konferensdeltagarna med dem och för att engelska var det officiella språket för Hydra. Arbetsuppgifterna såg ut så här:
Ta papper och penna, tänk, skynda inte att öppna spoilers direkt 🙂
Analys av lösningen (video)
Börjar 5:53, bara 4 minuter:
Och här är hur killarna med blädderblocket presenterade sin lösning:
Analys av lösningen (text)
Följande lösning ligger på ytan: summera vikterna för alla repliker, generera ett slumpmässigt tal från 0 till summan av alla vikter, välj sedan en i-replika så att summan av kopians vikter från 0 till (i-1) är mindre än ett slumpmässigt tal, och summan av repliken väger från 0 till i:te - mer än den. Så det kommer att vara möjligt att välja en replik, och för att välja nästa måste du upprepa hela proceduren utan att ta hänsyn till den valda repliken. Med en sådan algoritm är komplexiteten för att välja en replik O(N), komplexiteten för att välja K-repliker är O(N K) ~ O(N2).
Kvadratisk komplexitet är dålig, men den kan förbättras. För att göra detta kommer vi att bygga för summor av vikter. Ett träd med djup lg N kommer att erhållas, i vars löv det kommer att finnas replikvikter, och i de återstående noderna - delsummor, upp till summan av alla vikter vid roten av trädet. Därefter genererar vi ett slumptal från 0 till summan av alla vikter, hittar den i:te repliken, tar bort den från trädet och upprepar proceduren för att hitta de återstående replikerna. Med den här algoritmen är komplexiteten för att bygga ett träd O(N), komplexiteten i att hitta den i-te repliken och ta bort den från trädet är O(lg N), komplexiteten i att välja K-kopior är O(N + K Ig N) ~ O(N Ig N) .
Linjär-log-komplexitet är trevligare än kvadratisk komplexitet, särskilt för stora K.
Det är denna algoritm ClusterClient-bibliotek från projektet "". (Där är trädet byggt i O(N lg N), men detta påverkar inte algoritmens slutliga komplexitet.)
Uppgift 2. Zebra
Det var nödvändigt att föreslå en algoritm för effektiv sortering av dokument i minnet genom ett godtyckligt icke-indexerat fält:
Ditt team har till uppgift att utveckla en fragmenterad databas för dokument i minnet. En vanlig arbetsbelastning skulle vara att välja topp N dokument sorterade efter ett godtyckligt (icke-indexerat) numeriskt fält från en samling av storlek M (vanligtvis N < 100 << M). En något mindre vanlig arbetsbelastning skulle vara att välja topp N efter att ha hoppat över topp S-dokument (S ~ N).
Föreslå en algoritm för att utföra sådana frågor effektivt. Uppskatta dess beräkningskomplexitet med hjälp av big O-notation i genomsnittsfallet och de värsta scenarierna.
Analys av lösningen (video)
Från 34:50, endast 6 minuter:
Analys av lösningen (text)
Ytlösning: sortera alla dokument (till exempel med ), ta sedan N+S-dokument. I detta fall är sorteringens komplexitet i genomsnitt O(M lg M), i värsta fall O(M2).
Det är uppenbart att det är ineffektivt att sortera alla M dokument och sedan ta bara en liten del av dem. För att inte sortera alla dokument är en algoritm lämplig , vilket kommer att välja N + S av de önskade dokumenten (de kan sorteras med valfri algoritm). I detta fall kommer komplexiteten att minska till O(M) i genomsnitt, medan det värsta fallet förblir detsamma.
Du kan dock göra det ännu mer effektivt – använd algoritmen . I det här fallet läggs de första N+S-dokumenten till min- eller max-högen (beroende på sorteringsriktningen), och sedan jämförs varje nästa dokument med roten på trädet, som innehåller det aktuella minimum- eller maxdokumentet, och läggs till i trädet vid behov. . I det här fallet är komplexiteten i värsta fall, när man hela tiden måste bygga om trädet, O(M lg M), komplexiteten i genomsnitt O(M), som med quickselect.
Heapstreaming visar sig dock vara effektivare på grund av det faktum att de flesta dokumenten i praktiken kan kasseras utan att bygga om högen efter en enda jämförelse med dess rotelement. Sådan sortering är implementerad i Zebra in-memory dokumentdatabas som utvecklats och används i Kontur.
Uppgift 3. Statsbyten
Det var nödvändigt att föreslå den mest effektiva algoritmen för skiftande tillstånd:
Ditt team har till uppgift att utveckla en fancy tillståndsutbytesmekanism för ett distribuerat kluster av N noder. Den i:te nodens tillstånd bör överföras till den (i+1)-te noden, den N:te nodens tillstånd bör överföras till den första noden. Den enda operationen som stöds är tillståndsbytet när två noder utbyter sina tillstånd atomärt. Det är känt att ett tillståndsbyte tar M millisekunder. Varje nod kan delta i ett enda tillståndsbyte när som helst.
Hur lång tid tar det att överföra tillstånden för alla noder i ett kluster?
Analys av lösningen (text)
Ytlösning: byt tillstånden för det första och andra elementet, sedan det första och tredje, sedan det första och fjärde, och så vidare. Efter varje utbyte kommer tillståndet för ett element att vara i önskad position. Du måste göra O(N) permutationer och spendera O(N M) tid.
Linjär tid är lång, så du kan byta tillstånd för element i par: den första med den andra, den tredje med den fjärde, och så vidare. Efter varje tillståndsutbyte kommer vartannat element att vara i rätt position. Du måste göra O(lg N) permutationer och spendera O(M lg N) tid.
Det är dock möjligt att göra växlingen ännu mer effektiv – inte linjärt utan i konstant tid. För att göra detta, i det första steget, måste du byta tillståndet för det första elementet med det sista, det andra med det näst sista, och så vidare. Tillståndet för det sista elementet kommer att vara i rätt position. Och nu måste vi byta tillståndet för det andra elementet med det sista, det tredje med det näst sista, och så vidare. Efter denna omgång av utbyten kommer tillstånden för alla element att vara i rätt position. Det kommer att finnas O(2M) ~ O(1) permutationer totalt.
En sådan lösning kommer inte alls att förvåna en matematiker som fortfarande minns att en rotation är en sammansättning av två axiella symmetrier. Förresten, det är trivialt generaliserat för ett skifte inte med en, utan med K < N positioner. (Skriv i kommentarerna hur exakt.)
Gillade du pussel? Vet du andra lösningar? Dela i kommentarerna.
Och här är några användbara länkar till slut:
- lära sig mer om i kontur
- se register över interna om distribuerade system
- titta på serien med videoföreläsningar»
- prenumerera på vår
Källa: will.com