Darabokra törted a stream-em
Rövid bepillantás az adatszeletelés nem mindennapi világába
Az idők során annyi absztrakciós réteget húztunk fel magunk és a gép közé, hogy már fel se tűnik, hogy valójában mást se csinálunk, mint adatokat darabolunk szét és fűzünk össze újra. Adatszilánkok száguldoznak rézvezetékekben és repkednek mindenfelé a levegőben.
A legegyszerűbb szeletelt adat, amivel találkozhatunk a fix méret alapján feldarabolt. Ilyen például, amikor TCP csomagokra bontjuk a küldendő adatot a hálózati kommunikáció során vagy amikor egy fájlt fix méretű darabokban olvasunk fel.
Megfűszerezhetjük HTTP kéréseinket egy kis Range header-rel, aminek segítségével a válasz egy darabkáját kérhetjük el a webszervertől, ha esetleg megszakadt volna a letöltésünk vagy egyszerre több szálon is el akarjuk kezdeni a fájlt letölteni, ahogy azt a régi letöltésvezérlők tették. De például akkor is darabokra szakítjuk fájljainkat, amikor átpasszírozzuk őket a BitTorrent protokollon. Ezek a fix darabok remekül szolgálnak minket, ha jól használjuk őket, de megvannak a maguk korlátai, szó szerint és átvitt értelemben is.
A probléma
Tegyük fel, hogy egy backup szoftveren dolgozunk. A fájlokat feldaraboljuk, hogy ha két fájlban megtalálható ugyanaz a darab, akkor az csak egyszer legyen letárolva. Remek ötlet, rengeteg helyet megspórolhatunk. Aztán jön a kedves felhasználó, a fájl elejére ír valamit, ezzel az összes darabka elcsúszik és tárolhatjuk le újra a teljes adatot, pedig a fájl lényegében alig változott. Köszönjük szépen, felhasználó.
Hasonló problémába ütközhetünk ha például két gép között szeretnénk adatokat mozgatni. A betárcsázós internet lassú (vagy lemerülőben van a mobilinternet keretünk), úgyhogy szeretnénk minimalizálni az adatforgalmat. Ennek érdekében a kezdő- és a végponton is feldaraboljuk a fájlt, lehash-eljük a darabokat és csak azokat a darabokat mozgatjuk, ahol a hash nem stimmel. Ha pedig valaki a fájl elejére mer írni, akkor az összes hash rossz lesz és másolhatunk át mindent.
Mivel fix méretű darabkáink vannak ezért ha az adat bármely ponton változik, az az összes darabkára kihatással van, ami utána következik. Okosabban kellene vágni. Nem fix méret mentén, hanem valahogy az adattól függővé tenni a vágási pontokat. Mondjuk ha van egy CSV fájlunk, akkor lehetne például soronként vágni. Így kisebb-nagyobb darabkákat kapunk és a felhasználói módosítások se fognak rengeteg új darabkát eredményezni.
Minden szép és jó, amíg kedves felhasználó el nem kezdi bináris fájlokkal használni a rendszert. Bár egy bináris fájlban is előfordulhatnak új sor karakterek, azért érezzük, hogy ez a megoldás nem az igazi. Valami olyasmire lenne szükségünk, ami bár függ a fájl tartalmától, mégsem támaszkodik a fájl - esetlegesen nem létező - belső szerkezetére.
Tartalomfüggő szeletelés
Vehetnénk mondjuk az első 8 bájtot és összeadhatnánk őket. Ha az eredmény osztható 64-gyel, akkor megvan az első darabkánk. Ha nem, akkor odébb mozgatjuk a kis ablakunkat és megnézzük a 2. karaktertől a 9. karakterig az összeget és így tovább. Az osztó módosításával növelhetjük vagy csökkenthetjük a szeletek méretét. Ezt a megoldást szokták "Content-defined chunking"-ként vagy "Content-based slicing"-ként is emlegetni.
Az alábbi, stratégiailag elhelyezett gombokat megfelelően megkattintva meg is nézheted működés közben.
Összeg és a maradékTalált darabokNem is kell mindig egyesével összeadnunk a mozgó ablakunk minden bájtját. Számolhatunk gördülő összeget is, ha az előző 8 bájt összegéből kivonjuk az ablakból éppen kikerült bájtot és hozzáadjuk az ablakba újonnan bekerültet.
Használhatunk az összeg helyett egy hash-t, az oszthatóság helyett pedig kereshetünk benne valami mintát (mondjuk végződjön két nullára), a minta bonyolultságával szabályozva a szeletek méretét. Teljesítmény szempontjából viszont nem mindegy, hogy milyen hash-t választunk. Nem feltétlen akarunk több milliárd SHA-256-ot kiszámolni egy nagyobb fájl esetén, hacsak nem vagyunk Bitcoin bánya tulajdonosok. Szerencsére a gördülő összeghez hasonlóan léteznek gördülő hash-ek is, amik jobban megfelelnek erre a célra.
Nagyjából erről szól a tartalomfüggő szeletelés, egy érdekes és hasznos megoldás, nem mindennapi problémákra (mint például az inkrementális backup rendszerek vagy fájlok szinkronizálása). Ha részletesebben is belemerülnél a témába az alábbi linkek remek kiindulópontok lehetnek.