Distribuerade Hash-tabeller

Detta är den första artikeln i en serie som utforskar koncepten bakom moderna decentraliserade system, inklusive Keep-nätverket.
Hur lagrar och hämtar du stora mängder data snabbt och effektivt? Och när jag säger stort menar jag ordningen på exabyte. Detta är en del av en tvådelad serie om lagring och hämtning av data för Keep-nätverket.
Datalagring är ett stort problem och förvärras med mer digitalt genererat innehåll och mer data lagrad i molnet. Lösningen finns i något som kallas distribuerade dispersionstabeller eller DHT: er. I den här första delen av vår serie kommer vi att undersöka vad DHT är och hur de används av välkända enheter, som BitTorrent och Storj, och nya nätverk som IPFS.
DHT är för närvarande ett område med betydande innovation och är ett av de grundläggande elementen i distribuerad teknik. De utgör ryggraden för fillagring och nodupptäckt, vilket är ett väsentligt behov av Keep-klienten. Kunder måste kunna hitta varandra och dela data för att vara produktiva medlemmar i nätverket. Därför är en bra DHT nödvändig för att upprätthålla framgång.
Innan vi dyker in i distribuerade hashtabeller, låt oss snabbt granska vad en hashtabell är och hur den fungerar.
Hash-bord
En hash-tabell, även känd som en hash-karta, är en typ av datastruktur. För att förstå en hash-tabell, låt oss använda en bibliotekshylla som ett exempel. I ett typiskt bibliotek används Dewey-decimalsystemet (DDS) för att skapa ett lagrings-ID som kallas ett samtalsnummer, vilket ger varje bok en specifik placeringsplats för lagring och hämtning. Detta genereras genom att tillämpa reglerna för Dewey-decimalsystemet på en bok baserat på den kategori som den faller i. Bibliotekshyllor har nummer som motsvarar utbudet av samtalsnummer som finns tillgängliga via DDS.

Du kanske kommer ihåg från skoltiden att detta gjorde det väldigt enkelt att hitta böcker. Allt du behövde göra var att söka efter bokens samtalsnummer och sedan bläddra i biblioteket med en karta över var raderna med hyllor med prefix. När du har hittat en rad med rätt prefix kan du sedan hitta boken genom att följa numren på den enskilda hyllan i följd tills du har hittat den bok du vill ha.
Låt oss gå tillbaka till böckernas land till bitens land. Dewey-tilldelningssystemet för decimaltal är på många sätt en mycket enkel hashfunktion och samtalsnumret är ett hashvärde. Böcker kan ses som "data" och hyllorna är analoga med datalagringsplatser med hash-värden för att identifiera dem unikt. Slutligen motsvarar kartläggningskapaciteten i hjärnan och rymden en routningsalgoritm som låter dig använda bokens hashvärde för att hämta den från lagringsplatsen.
Hashfunktionen, hashvärdet och routningsalgoritmen är nyckelelement i en hashtabell. En hash-tabell använder dessa för att lagra och hämta stora mängder data direkt och utan fel. För att uppnå detta måste hashfunktionen, hashvärdet och routningsalgoritmen ha några mycket specifika funktioner.
Hashfunktionen måste vara deterministisk, vilket innebär att det finns en en-till-en-mappning mellan ingång och utgång. Hashvärdet måste tillhöra ett ID-utrymme som är tillräckligt stort för att en stor mängd data ska kunna lagras. För att direkt kunna hämta stora mängder data måste routningsalgoritmen vara effektiv; det vill säga det måste hämta och lagra data från en plats med det lägsta antalet operationer.

Från hashtabeller till distribuerade hashtabeller
För att få en hög nivå förståelse för hur DHT fungerar kan vi utöka vår biblioteksanalogi till att omfatta bibliotek i länder och kontinenter. Antag att vi ville ge biblioteksanvändare tillgång till böcker var som helst i världen. För att göra det vill jag presentera dig för vår bibliotekarie Tom.
Som bibliotekarie är Tom ansvarig för att lagra böcker och hitta böcker för biblioteksdeltagare. Han arbetar på ett lokalt bibliotek i Denver, Colorado. Detta bibliotek kan lagra rätt antal böcker, men inte alla böcker som deltagare i det lokala biblioteket kanske vill ha.
Om vårt bibliotekssystem var strukturerat på samma sätt som en distribuerad hash-tabell, skulle Toms bibliotek vara en nätverksnod. För att hitta en bok online skulle Tom ha en lista över närmaste bibliotek som han först kan kontakta för att se om en önskad bok finns tillgänglig. Om ingen av dem hade boken, skulle de gå till närmaste bibliotek och så vidare tills boken hittades eller inget bibliotek återstod.
Dessutom, eftersom inte alla böcker kan lagras i varje bibliotek, kan systemet göra vissa bibliotek ansvariga för vissa böcker och inte andra. Ansvar kan tilldelas baserat på metadata för böckerna, såsom ursprungsland, språk etc.
Återigen, från boklandet till bitlandet, i en typisk distribuerad hashtabell, lagras data i många noder (bibliotek) som går in i och lämnar systemet. DHT-protokollet avgör hur data distribueras mellan dessa noder, vilket säkerställer att de enkelt kan sökas och hämtas.
Utvecklingen av distribuerade hashtabeller
Framväxten av massdistribuerade hashtabeller ägde rum i slutet av 1990-talet och början av 2000-talet, vilket sammanföll med tillkomsten av P2P-system som Gnutella, Freenet, Napster och BitTorrent. Dessa system försökte utnyttja distribuerade lagrings- och datorresurser och utvecklade sina egna protokoll för att möta deras behov.
Följande är några anmärkningsvärda, men inte omfattande, händelser i DHT: s historia:
Napster
Napster använde en central indexeringsserver för att tillhandahålla en "värdlista" över användare som för närvarande är inloggade i systemet. Servern innehöll inte filer, men hade en lista över filer som användarna hade i värdlistan. När en användare sökte efter en fil med Napster-klienten, skulle servern söka igenom värdlistan och deras fillista för att se vem som hade dem och förse den begärande med en lista över värdar som hade sin fil. Användarens Napster-klient initierar sedan en anslutning med den användarvalda värden och initierar en nedladdning. Klienten avslutar anslutningen när nedladdningen är klar
Om vi tillämpar vår biblioteksanalogi på Napster, skulle det vara som att ha ett centralt bibliotek som ansvarar för att lagra platsen för böcker i alla bibliotek som någonsin har interagerat med den. Om en användare ville ha en bok bör de först kontakta Centralbiblioteket, hämta informationen från biblioteket där boken förvarades och sedan kontakta det biblioteket för att få boken.
Napsters största nackdel som DHT var dess centrala indexeringsserver, vilket skapade en enda felpunkt för systemet.

BitTorrent
BitTorrent uppfann modern DHT. Tjänsten lanserades 2005 på DHT Mainline-protokollet. Huvudlinjen DHT är ett mycket bra distribuerat system och en förbättring jämfört med Napster-systemet, eftersom det inte finns någon central felpunkt. Systemet anpassar sig organiskt till de noder som kommer in och ut ur systemet. Detta är viktigt för driften av BitTorrent, eftersom bithastigheten är hög, där användare runt om i världen går med och lämnar systemet vid oförutsägbara tider.
BitTorrent-systemet är mer som en riktig DHT. Det distribuerade bibliotekssystemet som beskrivs ovan är en bra bild på hög nivå av hur BitTorrent-systemet fungerar.
Štorje
Storj ansluter personer med lagringsbehov till leverantörer av smartcontracts-lagring via Storj-protokollet. Storj-protokollet använder en modifierad version av Kademlia-protokollet, som delar många av funktionerna i BitTorrent Mainline DHT.
IPF
I likhet med internet är IPFS (Inter Planetary File System) ett distribuerat filsystem som länkar noder som innehåller specifika filtyper. Till skillnad från internet lagras inte innehåll på enskilda servrar utan distribueras istället över flera noder. För att distribuera detta innehåll använder IPFS en BitTorrent som DHT-protokoll, utvecklat av Protocol Labs. IPFS är öppen källkod och användes senast av det katalanska piratpartiet för att vara värd för webbplatser som blockerats av den spanska konstitutionella domstolen.
Filecoin
Filecoin är ett distribuerat lagringsnätverk som använder element i IPFS-protokollet tillsammans med ett incitamentlager för lagringsleverantörer. Protokollet för Filecoin utvecklas för närvarande av Protocol Labs, samma grupp som utvecklar IPFS.

HA KVAR
DHT är ett viktigt verktyg i Keep-verktygslådan. Precis som ovanstående användningsfall kommer behållande kunder att spridas över hela världen och uppleva lite. Dessutom kan de också uppleva attacker från skadliga enheter, och Keep-protokollet måste utvecklas kontinuerligt för att vara motståndskraftigt.
Keep använder DHT för att skapa ett robust distribuerat protokoll som kan tillgodose dessa behov och vara öppen källkod. Att vara öppen källkod gör det möjligt för ett globalt nätverk av oberoende utvecklare att förnya sig om protokollet. En av de första ansträngningarna för Keep-teamet kommer att vara att använda libp2p-nätverksstacken med öppen källkod för att låta Keep-kunderna upptäcka. Håll koll på den andra delen av vår egen decentraliserade utbildningsserie Keep Nik Grinkevich om libp2p-nätverket.
Få reda på mer
För mer information om Keep-nätverket:

Gå med oss på Reddit.
Kolla in vår whitepaper.
Läs vår business primer.
Prenumerera på email updates.
Följ oss på Twitter.
Gå med oss Slack.
Gå med oss Telegram.
Gå med oss Discord Keep
Gå med oss Discord TBTC