Dansk forskningsprojekt: Pladsproblemer i skyen skal løses med ny type komprimering

Daniel Lucani Rötter er lektor på Institut for Ingeniørvidenskab ved Aarhus Universitet. Illustration: Lars Kruse / AU Foto
Forbedret deduplikering er nøglen til fremtidens problemer med begrænset cloud-plads, lyder det fra lektor bag nyt forskningsprojekt fra Aarhus Universitet.

Et godt match behøver ikke at bestå af to helt ens. Tværtimod er der faktisk fordele ved at matche data, der ikke er helt ens, når det drejer sig om komprimering og deduplikering. I hvert fald hvis det står til Daniel Lucani Rötter, som er lektor på Institut for Ingeniørvidenskab ved Aarhus Universitet.

Han er en del af den projektgruppe, som har sat sig for at finde en ny og forbedret metode til at komprimere de store datamængder, der eksempelvis strømmer igennem datacentre. Formålet er at løse de pladsproblemer i skyen, der kan opstå som følge af den stigende brug af Internet of Things (IoT) og Cloud-løsninger.

»Vi tænker først og fremmest det her som et komprimeringsprojekt, der skal fungere i cloud-skala. Normalt foregår komprimering og deduplikering kun med datablokke, som er fuldstændigt identiske med hinanden, men vi prøver at gå længere endnu. Vi forsøger at komprimere data, selvom to datablokke ikke er helt ens,« siger Daniel Lucani Rötter.

Uens datablokke

Projektet tager udgangspunkt i teknikken til deduplikering, som går ud på at undersøge blokke af store datamængder for dubletter eller redundans – altså om der er blokke af data, som er identiske.

Opstår der et match, hvor en datablok er nøjagtig identisk med en allerede gemt blok, bliver den nye kopi slettet, og der oprettes i stedet en henvisning til den allerede gemte og helt ens datablok.

Deduplikering er allerede kendt som en effektiv metode til at forbedre udnyttelsen af lagringsplads, men projektgruppen fra Aarhus Universitet vil også udnytte teknikken til blandt andet at til at reducere antallet af bytes, som sendes ved netværksoverførsler.

Og så vil man heller ikke nøjes med at matche identiske blokke af data i processen med deduplikering.

»Vi prøver at lave et komprimeringsmatch mellem to datablokke, som er ens på mange punkter, men som ikke er helt identiske. Hvis man arbejder med store mængder af data, kan der være eksempler på, at en datablok kan have utrolig mange lighedspunkter med flere tusinde eller ligefrem millioner andre blokke af data, selvom de ikke er ens. Vi forsøger at lave matches og komprimere disse uens datablokke,« siger han.

Han tilføjer, at projektgruppen på nuværende tidspunkt er i gang med at udvikle teknikker, hvor man systematisk og simpelt kan identificere, om der er de såkaldte ”lige ved og næsten”-matches - altså en eller anden form for ligheder i datamængderne, uden at de forskellige bidder behøves at være helt ens – som man kan deduplikere og komprimere.

Registrerer forskelligheder

Ifølge Daniel Lucani Rötter kan man komprimere langt mere effektivt ved ikke kun at have fokus på helt ens datablokke. Det eneste, som behøves for at lave matchet mellem de forskellige blokke, er en hashing af, hvor data stammer fra, eller hvad indholdet er, og hvordan de to databidder adskiller sig fra hinanden, påpeger han.

»For at deduplikere og komprimere datablokke, som ikke er helt identiske, skal der laves registrering af de to blokkes forskelligheder. Vi skal altså også gemme information om, hvordan de to næsten ens datablokke adskiller sig fra hinanden. Med den information kan vi altid gå tilbage til det oprindelige udgangspunkt,« siger Daniel Lucani Rötter.

Han påpeger dog, at der er grænser for, hvor uens de matchede datablokke kan være, hvis teknikken stadig skal være brugbar.

»Der er en balancegang i forhold til, hvor uens data man vil matche. Hvis man parrer meget uens data til en komprimering, vil man kunne komprimere meget data, men det vil samtidig kræve en større registrering af forskellighederne i datamatchet,« siger han og tilføjer, at projektgruppens mest simple model matcher datablokke, som kun adskiller sig med en enkelt bit.

Hvordan adskiller projektet sig fra tidligere projekter med komprimering?

»Vi går ikke kun efter nøjagtig ens datablokke. Tidligere kendte metoder til at lave deduplikering er enormt datakrævende, og det er vores ikke. Vores teknik kan bruges med 10.000 gange mindre data, og man kan derfor bruge denne metode mere effektivt allerede på med en mindre datamængde.«

Er der andre, som har forsøgt sig med det her før?

»Nej, der her har ikke været afprøvet før, og derfor er vi også meget spændte på projektet. Vi har det teoretiske potentiale på plads, og vi har et lille system, som vi kan fodre med data. I øjeblikket går processen langsomt, men vi ved at potentialet er der, og jeg er ikke nervøs for, at vi kan nå i mål med en enormt hurtig og effektiv komprimeringsmetode.«

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (10)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Torben Mogensen Blogger

Kryptering fungerer ofte som block cyphers, hvorved data krypteres blok for blok, med blokke helt ned til 64 bit. Så hvis to blokke er identiske før kryptering, vil de også være det efter kryptering, så deduplikering fungerer fint på krypterede blokke.

Sandsynligheden for at to krypterede blokke er næsten ens er til gengæld meget lille -- selv en forskel på et bit i det originale data resulterer i to krypterede blokke, som ikke ligner hinanden mere end to tilfældige blokke. Ellers er krypteringen noget skod. Så hvis man skal genkende næsten ens data, så skal det være før kryptering, og hvis man gemmer differentialinformation, skal det sige noget om forskellen på det ukrypterede data. Det indebærer i sig selv en risiko, fordi en angriber kan gætte noget data og ud fra denne information finde ud af, hvor tæt gættet er på en krypteret blok, og det er noget skidt. Hvis man kun kan se om gættet er helt ens med den angrebne blok, er sandsynligheden meget lille for at få brugbar information, men hvis man får et mål for forskellene, kan man ret hurtigt indsnævre gættene.

Jonas Høgh
Jacob Gorm Hansen

At man kan deduplikere data-blokke som ikke er helt ens, fx https://www.usenix.org/legacy/event/osdi08/tech/full_papers/gupta/gupta.pdf

Den grundlaeggende ide at at lave en LSH-hash, fx Min-hashing, hvis sandsynlighed for at kollidere er proportionel med overlappet mellem to maengder man gerne vil sammenligne. Dette har vaeret kendt siden Broder forskede i det hos Altavista i 1999. Naar man har fundet to blokke med samme hash kan man beregne en diff, fx med xdelta-algoritmen (se Burns and Long, 1998, jeg kan ikke lige finde et link til den).

Jeg har selv tidligere arbejdet paa et kommercielt produkt som bruger lignende teknikker, og som bruges paa millioner af Virtual Machine images hver eneste dag, verden over.

Emil Hempel

Torben, det er ikke helt korrekt at 2 blokke med samme data bliver til det samme ved kryptering - f.eks. ved AES CBC bliver næste blok krypteret med checksummen fra den forrige, så hvis er en ændring et sted i den krypterede datastrøm ændre hele det resterende output fra krypteringen og det vil dermed blive umugeligt at lave dedupe.

Derimod er det korrekt hvis du kryptere 2 filer med samme data og samme kode med AES CBC - så vil output blive identisk.

Hans Nielsen

Er præmissen for diskussionen ikke forkert ?

"Forbedret deduplikering er nøglen til fremtidens problemer med begrænset cloud-plads, "

Hvem siger at der er begrænset cloud-plads ?

Og her synes jeg diskutionen rammer rigtigt. Vi vil vel ikke opgive kryptering og sikkehed, på grund af "dårlige" løsninger på mulige plads problemer ?

Lad os håbe at Moores får løst pladsproblemmerne og at gode kryptografer, så får løst humm - Er der overhovedet så et problem ;-)

Log ind eller Opret konto for at kommentere