Rullande hash

En rullande hash (även känd som rekursiv hash eller rullande kontrollsumma) är en hashfunktion där indata hashas i ett fönster som rör sig genom ingången.

Ett fåtal hashfunktioner gör att en rullande hash kan beräknas mycket snabbt – det nya hashvärdet beräknas snabbt givet endast det gamla hashvärdet, det gamla värdet borttaget från fönstret och det nya värdet som läggs till i fönstret – på samma sätt som en funktionen för glidande medelvärde kan beräknas mycket snabbare än andra lågpassfilter.

En av huvudapplikationerna är Rabin–Karps strängsökningsalgoritm , som använder den rullande hash som beskrivs nedan. En annan populär applikation är rsync , som använder en kontrollsumma baserad på Mark Adlers adler-32 som sin rullande hash. Low Bandwidth Network Filesystem (LBFS) använder ett Rabin-fingeravtryck som sin rullande hash. FastCDC (Fast Content-Defined Chunking) använder ett beräkningseffektivt Gear-fingeravtryck som sin rullande hash.

I bästa fall är rullande hashvärden parvis oberoende eller starkt universella . De kan till exempel inte vara 3-vis oberoende .

Polynom rullande hash

Rabin –Karps strängsökningsalgoritm förklaras ofta med en rullande hashfunktion som bara använder multiplikationer och additioner:

$H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_ {k}a^{0}$ ,

där $a$ är en konstant, och $c_{1},...,c_{k}$ är inmatningstecknen (men den här funktionen är inte ett Rabin-fingeravtryck , se nedan).

För att undvika att manipulera stora $H$ -värden görs all matematik modulo $n$ . Valet av $a$ och $n$ är avgörande för att få bra hash; i synnerhet är modulen $n$ typiskt ett primtal. Se linjär kongruentialgenerator för mer diskussion.

Att ta bort och lägga till tecken innebär helt enkelt att lägga till eller subtrahera den första eller sista termen. Att flytta alla tecken med en position åt vänster kräver att hela summan ${\displaystyle H} multipliceras$ med $a$ . Att flytta alla tecken med en position åt höger kräver att man dividerar hela summan $H$ med $a$ . Observera att i modularitmetik $a$ väljas för att ha en multiplikativ invers $a^{-1}$ med vilken $H$ kan multipliceras för att få resultatet av division utan att faktiskt utföra en division.

Rabin fingeravtryck

Rabins fingeravtryck är en annan hash, som också tolkar inmatningen som ett polynom, men över Galois-fältet GF(2) . Istället för att se inmatningen som ett polynom av bytes, ses det som ett polynom av bitar, och all aritmetik görs i GF(2) (på samma sätt som CRC32 ). Hash är resultatet av divisionen av det polynomet med ett irreducerbart polynom över GF(2). Det är möjligt att uppdatera ett Rabin-fingeravtryck genom att bara använda ingångs- och utgående byte, vilket gör det effektivt till en rullande hash.

Eftersom den har samma författare som Rabin–Karps strängsökningsalgoritm, som ofta förklaras med en annan, enklare rullande hash, och eftersom denna enklare rullande hash också är ett polynom, misstas båda rullande hasharna ofta för varandra. Säkerhetskopieringsprogramvaran använder ett Rabin-fingeravtryck för att dela filer, med blobstorlekar som varierar mellan 512 KiB och 8 MiB .

Cyklisk polynom

Hashing med cykliskt polynom – ibland kallat Buzhash – är också enkelt, men det har fördelen att man undviker multiplikationer, istället för att använda fatskift . Det är en form av tabuleringshashning : den förutsätter att det finns någon hashfunktion $h$ från tecken till heltal i intervallet $[0,2^{L})$ . Denna hashfunktion kan helt enkelt vara en array eller en hashtabell som mappar tecken till slumpmässiga heltal. Låt funktionen $s$ vara en cyklisk binär rotation (eller cirkulär skiftning ): den roterar bitarna med 1 åt vänster och trycker den senaste biten i den första positionen. T.ex. $s(101)=011$ . Låt $\oplus$ vara den bitvis exklusiva eller . Hashvärdena definieras som

$H= s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1} ))\oplus h(c_{k}),$

där multiplikationerna med två potenser kan implementeras genom binära skift. Resultatet är ett tal i $[0,2^{L})$ .

Att beräkna hash-värdena på ett rullande sätt görs enligt följande. Låt $H$ vara det föregående hashvärdet. Rotera $H$ en gång: $H\leftarrow s(H)$ . Om $c_{1}$ är tecknet som ska tas bort, rotera det $k$ gånger: $s^{k}(h(c_{ 1}))$ . Sedan är det bara att ställa in

$H\leftarrow s(H)\oplus s^{k}(h(c_{1}) )\oplus h(c_{k+1}),$

där $c_{k+1}$ är det nya tecknet.

Hashing med cykliska polynom är starkt universellt eller parvis oberoende: behåll helt enkelt de första $L-k+1$ bitarna. Det vill säga, ta resultatet $H$ och ta bort alla $k-1$ på varandra följande bitar. I praktiken kan detta uppnås genom en heltalsdivision $H\rightarrow H\div 2^{k-1}$ .

Innehållsbaserad skivning med en rullande hash

Ett av de intressanta användningsfallen för den rullande hashfunktionen är att den kan skapa dynamiska, innehållsbaserade bitar av en ström eller fil. Detta är särskilt användbart när det krävs att bara skicka de ändrade bitarna av en stor fil över ett nätverk: ett enkelt bytetillägg längst fram i filen skulle normalt göra att alla fönster med fast storlek uppdateras, medan det i verkligheten bara är det första "chunk" har ändrats.

En enkel metod för att göra dynamiska bitar är att beräkna en rullande hash, och om hashvärdet matchar ett godtyckligt mönster (t.ex. alla nollor) i de lägre N bitarna (med en sannolikhet på ${\textstyle {1 \over 2^ {n}}}$ , förutsatt att hashen har en enhetlig sannolikhetsfördelning) så väljs den till att vara en bitgräns. Varje bit kommer alltså att ha en genomsnittlig storlek på ${\textstyle 2^{n}}$ byte. Detta tillvägagångssätt säkerställer att omodifierade data (mer än en fönsterstorlek bort från ändringarna) kommer att ha samma gränser.

När gränserna väl är kända måste bitarna jämföras med kryptografiskt hashvärde för att upptäcka förändringar. Säkerhetskopieringsmjukvaran Borg använder Buzhash-algoritmen med ett anpassningsbart intervall för chunkstorlekar för att dela upp filströmmar.

Sådan innehållsdefinierad chunking används ofta för datadeduplicering .

Innehållsbaserad skivning med rörlig summa

Flera program, inklusive gzip (med alternativet --rsyncable ) och rsyncrypto, gör innehållsbaserad uppdelning baserat på denna specifika (ovägda) rörliga summa:

$S(n)=\sum _{i=n-8195}^{n}c_{i},$

$H(n)=S(n)\mod 4096,$

var

• $S(n)$ är summan av 8196 på varandra följande byte som slutar med byte $n$ (kräver 21 bitars lagring),
• $c_{i}$ är byte $i$ i filen,
• $H(n)$ är ett "hashvärde" som består av de nedersta 12 bitarna av $S(n)$ .

Att flytta fönstret med en byte innebär helt enkelt att lägga till det nya tecknet till summan och subtrahera det äldsta tecknet (inte längre i fönstret) från summan.

För varje $n$ där $H(n)==0$ klipper dessa program filen mellan $n$ och $n+1$ . Detta tillvägagångssätt kommer att säkerställa att alla ändringar i filen endast kommer att påverka dess nuvarande och möjligen nästa bit, men ingen annan bit.

Gear fingeravtryck och innehållsbaserad chunking-algoritm FastCDC

Chunking är en teknik för att dela upp en dataström i en uppsättning block, även kallade chunks. Content-defined chunking (CDC) är en chunking-teknik där uppdelningen av dataströmmen inte baseras på fast chunkstorlek, som vid chunking med fast storlek, utan på dess innehåll.

Den Content-Defined Chunking-algoritmen måste beräkna hashvärdet för en dataström byte för byte och dela upp dataströmmen i bitar när hashvärdet möter ett fördefinierat värde. Men att jämföra en sträng byte-för-byte kommer att introducera den tunga beräkningsoverheaden. FastCDC föreslår en ny och effektiv Content-Defined Chunking-metod. Den använder en snabbt rullande Gear-hashalgoritm, hoppar över minimilängden, normaliserar chunk-storleksfördelningen och sist men inte minst, rullar två byte varje gång för att påskynda CDC-algoritmen, som kan uppnå cirka 10 gånger högre genomströmning än Rabin- baserad CDC-metod.

Grundversionens pseudokod tillhandahålls enligt följande:

  
         
      
        
    
    
    0
    0  
          
        
             
          algoritm  FastCDC  -ingång:  databuffert  src  , datalängd  n  ,  utdata:  skärpunkt  i  // buffertstorleken är mindre än minsta chunkstorlek  om  n  ≤  MinSize  returnera  sedan  n  om  n  ≥  MaxSize  sedan  n  ←  MaxSize  MinSize  ← 2KB // dela minsta chunk storleken är 2 KB  MaxSize ← 64KB // delad   maximal  chunkstorlek är 64 KB  Mask  ←  0x0000d93003530000LL  fp  ←  i  ←  //  Hoppa över de första  MinSize-  bytena och kickstarta hashen  medan  i  <  MinSize  do  fp  +  ←  [  src  [  i  ]]  i  ←  i  + 1  medan  i  <  n  do  fp  ← (  fp  << 1 ) +  Gear  [  src  [  i  ]]  om  !(  fp  &  Mask  )  returnera  sedan  i  i  ←  i  + 1  return  i 

Där Gear array är en förberäknad hash-array. Här använder FastCDC Gear hashing-algoritm som kan beräkna de rullande hashresultaten snabbt och behålla den enhetliga fördelningen av hashningsresultaten som Rabin. Jämfört med den traditionella Rabin-hash-algoritmen uppnår den en mycket snabbare hastighet. Experiment tyder på att det kan generera nästan samma bitstorleksfördelning på mycket kortare tid (cirka 1/10 av rabin-baserad chunking) när dataströmmen segmenteras.

Beräkningskomplexitet

Alla rullande hash-funktioner kan beräknas i tid linjärt i antal tecken och uppdateras i konstant tid när tecken flyttas med en position. I synnerhet kräver beräkning av Rabin-Karps rullande hash av en sträng med längden $k$$O(k)$ modulära aritmetiska operationer, och hashning med cykliska polynom kräver ${\ displaystyle O(k)}$ bitvis exklusiva ors och cirkulära skift .

programvara

• rollinghashcpp är en gratis C++-implementering av flera rullande hashfunktioner
• rollinghashjava är en Apache-licensierad Java-implementering av rullande hashfunktioner

Se även

• MinHash
• w-shingling

externa länkar

• MIT 6.006: Introduktion till algoritmer 2011 - Recitation 9 - Rolling Hash