Bakverk (DHT)

Den här artikeln beskriver tabellen för bakverksdistribuerade hash. För maten, se Bakverk .

Pastry är ett överläggsnätverk och routingnätverk för implementering av en distribuerad hashtabell (DHT) som liknar Chord . Nyckel -värdeparen lagras i ett redundant peer-to-peer- nätverk av anslutna internetvärdar . Protokollet bootstrappas genom att förse det med IP-adressen till en peer som redan finns i nätverket och därefter via routingtabellen som är dynamiskt byggd och reparerad. Det hävdas att på grund av dess redundanta och decentraliserade karaktär finns det ingen enda punkt för fel och vilken enskild nod som helst kan lämna nätverket när som helst utan förvarning och med liten eller ingen risk för dataförlust. Protokollet kan också använda ett routingmått som tillhandahålls av ett externt program, såsom ping eller traceroute , för att bestämma de bästa rutterna att lagra i dess routingtabell.

Översikt

Även om den distribuerade hashtabellsfunktionaliteten i Pastry är nästan identisk med andra DHT:er , är det som skiljer den från routing-överlagringsnätverket som är byggt ovanpå DHT -konceptet. Detta gör att Pastry kan inse skalbarheten och feltoleransen för andra nätverk, samtidigt som den minskar den totala kostnaden för att dirigera ett paket från en nod till en annan genom att undvika behovet av att översvämma paket. Eftersom routingmåttet tillhandahålls av ett externt program baserat på IP-adressen för målnoden, kan mätvärdet enkelt växlas till det kortaste hoppantal, lägsta latens, högsta bandbredd eller till och med en allmän kombination av mätvärden.

Hash-tabellens tangentmellanrum anses vara cirkulär, som tangentutrymmet i Chord- systemet, och nod-ID:n är 128-bitars heltal utan tecken som representerar positionen i det cirkulära tangentutrymmet. Nod-ID:n väljs slumpmässigt och enhetligt så att kamrater som är intill varandra i nod-ID är geografiskt olika. Routningsöverlagringsnätverket bildas ovanpå hashtabellen genom att varje peer upptäcker och utbyter tillståndsinformation bestående av en lista med lövnoder, en grannskapslista och en routingtabell. Bladnodlistan består av de L /2 närmaste peers efter nod-ID i varje riktning runt cirkeln.

Utöver lövnoderna finns även grannskapslistan. Detta representerar de M närmaste peers i termer av routingmåttet. Även om den inte används direkt i routingalgoritmen, används grannskapslistan för att upprätthålla lokalitetsprinciper i routingtabellen.

Slutligen finns själva routingtabellen. Den innehåller en post för varje adressblock som tilldelats den. För att bilda adressblocken delas 128-bitars nyckeln upp i siffror där varje siffra är b bitar lång, vilket ger ett numreringssystem med bas ^2b . Detta delar upp adresserna i distinkta nivåer från klientens synvinkel, där nivå 0 representerar ett nollsiffrigt gemensamt prefix mellan två adresser, nivå 1 ett ensiffrigt gemensamt prefix och så vidare. Routingtabellen innehåller adressen för den närmaste kända peeren för varje möjlig siffra på varje adressnivå, förutom siffran som tillhör peeren själv på den specifika nivån. Detta resulterar i lagring av $2^{b}-1$ kontakter per nivå, med antalet nivåer som skalas som $(\log _{2} {N})/b$ . Värden på $b\approx 4,L\approx 2^{b}$ och $M\approx 2^{b}$ representerar driftvärden på en typisk nätverk.

Routing

Ett paket kan dirigeras till vilken adress som helst i tangentutrymmet oavsett om det finns en peer med det nod-ID eller inte. Paketet dirigeras mot sin rätta plats på den cirkulära ringen och den peer vars nod-ID är närmast den önskade destinationen kommer att ta emot paketet. Närhelst en peer tar emot ett paket att dirigera eller vill skicka ett paket undersöker den först dess bladuppsättning och dirigerar direkt till rätt nod om en hittas. Om detta misslyckas, konsulterar peeren sin dirigeringstabell med målet att hitta adressen till en nod som delar ett längre prefix med destinationsadressen än peeren själv. Om peer inte har några kontakter med ett längre prefix eller kontakten har dött kommer den att välja en peer från sin kontaktlista med samma längd prefix vars nod-ID är numeriskt närmare destinationen och skicka paketet till den peer. Eftersom antalet korrekta siffror i adressen alltid antingen ökar eller förblir detsamma – och om det förblir detsamma blir avståndet mellan paketet och dess destination mindre – konvergerar routingprotokollet.

Applikationer byggda på Pastry

Pastry själv anger hur nycklar fördelas mellan noderna och hur noden som ansvarar för att hålla en nyckel kan hittas. Att använda detta som ett substrat för ett högre protokoll gör det möjligt för Pastry att implementera funktionalitet som ett distribuerat filsystem, ett prenumerations- och publiceringssystem eller vilket annat system som helst som kan reduceras till att lagra värden och hämta dem senare.

DÅTID

PAST är ett distribuerat filsystem som ligger på toppen av Pastry. En fil lagras i systemet genom att beräkna hashen för dess filnamn. Sedan dirigerar Pastry innehållet i filen till noden i det cirkulära tangentutrymmet närmast hashen som erhålls från filnamnet. Denna nod kommer sedan att skicka kopior av filen till de k noder som är närmast den faktiska nyckeln, av vilka de flesta sannolikt är lövnoder för denna nod och därmed direkt nåbara. Hämtning av data åstadkoms genom att omhasha filnamnet och dirigera en begäran om data över Pastry till rätt plats i tangentutrymmet. Begäran kan uppfyllas av vilken som helst av de k noder som har kopior av data. Detta åstadkommer både dataredundans och belastningsfördelning. Eftersom intilliggande noder i tangentutrymmet är geografiskt olika är oddsen att alla k kommer att gå offline samtidigt mycket små. Ännu viktigare, eftersom Pastry-routingprotokollet försöker minimera det tillryggalagda avståndet, är den närmaste noden till maskinen som gjorde begäran (enligt måtten) troligen den som svarar med data.

SKRIVARE

SCRIBE är ett decentraliserat publicerings-/prenumerationssystem som använder Pastry för sin underliggande rutthantering och värdsökning. Användare skapar ämnen som andra användare kan prenumerera på. När ämnet har skapats kan ägaren av ämnet publicera nya poster under ämnet som kommer att distribueras i ett multicastträd till alla SCRIBE-noder som har prenumererat på ämnet. Systemet fungerar genom att beräkna hashen för ämnesnamnet sammanlänkat med namnet på användaren som äger ämnet. Denna hash används sedan som en Pastry-nyckel, och utgivaren dirigerar sedan paket till noden närmast nyckeln med hjälp av Pastrys routningsprotokoll för att skapa rotnoden för ämnet på den noden. Folk prenumererar sedan på ämnet genom att beräkna nyckeln från ämnet och utgivarens namn och sedan använda Pastry för att dirigera ett prenumerationsmeddelande till ämnet mot rotnoden. När rotnoden tar emot prenumerationsmeddelandet från en annan nod lägger den till nod-ID:t till sin lista över barn och börjar agera som vidarebefordrare av ämnet.

Decentralisering åstadkoms genom att alla noder i nätverket snokar efter prenumerationsmeddelanden som går förbi dem på väg till ämnets rotnod. Om ämnet är ett ämne som den aktuella noden prenumererar på, kommer den att sluta vidarebefordra paketet mot rotnoden och lägga till noden som försöker prenumerera som ett av dess underordnade. På detta sätt bildas en trädliknande struktur med rotnoden överst som skickar ut till de första få abonnentnoderna och sedan vidarebefordrar var och en av dessa noder meddelandena till sina barn, och så vidare. Eftersom paket från slumpmässiga noder på Pastry-nätverket som är avsedda för samma nod ofta hamnar på samma väg mycket snart under sin resa, slutar de med att de kopplas till den del av trädet som är närmast dem i Pastry-nätverket. Eftersom varje hopp längs en bakverksrutt representerar det som lokalt är den bästa rutten enligt det ruttmått som används, söker prenumerationsmeddelandet upp den närmaste delen av trädet och fäster sig där.

Slutligen uppnås feltolerans bland medlemmar i distributionsträdet genom användning av timeouts och keepalives med faktiska dataöverföringar som fördubblas som keepalives för att minimera trafiken. Om en underordnad nod inte hör från sin förälder på ett tag, dirigerar den ett nytt prenumerationsmeddelande till trädets rotnod och fäster sig igen vart den än stöter på trädet för det ämnet. Om en förälder inte hör från ett barn under en timeout-period, tar det bort barnet från listan över barn. (Om den här åtgärden gör att dess underordnade lista blir tom, slutar föräldern att fungera som en speditör helt och hållet.) Den enda kvarvarande felpunkten är rotnoden, och Pastry själv övervinner detta automatiskt. Eftersom Pastry duplicerar nycklar bland de få noder som ligger närmast nyckelns faktiska värde, har rotnoden redan speglar inställda, som ligger vilande. Om rotnoden går offline, igen upptäcks genom timeout, kommer den närmast närmaste Pastry-noden att börja fungera som rotnod. När skaparen av ämnet försöker publicera nytt material kommer den gamla rotnoden att vara oåtkomlig. Utgivaren kommer då att falla tillbaka på Pastry-nätverket och använda det för att dirigera sitt publiceringsmeddelande till den nya rotnoden. När detta har gjorts cachar utgivaren en kopia av den nya rotnodens IP-adress för att minska användningen av Pastry-nätverket för framtida överföringar.

Se även

A. Rowstron & P. Druschel (november 2001). "Pastry: Skalbar, decentraliserad objektplacering och routing för storskaliga peer-to-peer-system" ( PDF) . IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Tyskland : 329–350.
A. Rowstron; AM. Kermarrec; M. Castro & P. Druschel (november 2001). "SCRIBE: Designen av en storskalig infrastruktur för händelsemeddelanden" ( PDF) . NGC2001 UCL London .

externa länkar