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

29. marts 2019 kl. 05:1112
Dansk forskningsprojekt: Pladsproblemer i skyen skal løses med ny type komprimering
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.
Artiklen er ældre end 30 dage
Manglende links i teksten kan sandsynligvis findes i bunden af artiklen.

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.

Artiklen fortsætter efter annoncen

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.

Om teknikkerne

Deduplikering er en speciel type datakomprimering. Teknikken bruges særligt på store mængder af filer og data. Processen med deduplikering er typisk transpoerant, hvilket vil sige, at brugeren ikke lægger mærke til, at der foregår en komprimeringsproces i baggrunden. Det er ikke nødvendigt at tilbagerulle processen for at få adgang til en deduplikeret fil. Derudover er det muligt at ændre i deduplikerede filer, uden at de skal genkomprimeres. Deduplikering er altid en tabsfri proces (lossless-filer).

Standard datakomprimering omfatter typisk en enkelt fil eller en lille gruppe af filer af gangen. Denne proces er ikke transparent for brugeren. Hvis en gruppe af filer bliver komprimeret, er det ikke muligt at dekomprimere dem en af gangen. Det er nødvendigt for brugeren at dekomprimere alle filerne igen. Hvis indholdet af en komprimeret fil bliver ændret, er det også nødvendigt at genkomprimere hele filen. Standard datakomprimering kan være tabsfri, men det er også muligt at lave en lossy-komprimering, hvor dele af information bliver slettet, uden at det har afgørende betydning for den samlede fil.

Om projektet

Projektet med ny komprimeringsteknik startede i august 2018, og løber fire år frem.

Udover lektor Daniel Lucani Rötter er der tre Ph.d-studerende tilknyttet projektet.

Projektet er en del af det internationale Scale-IoT-projekt.

Budgettet er på 5,9 millioner kroner.

UCLA, University of Neuchatel, Schweiz, Nokia Bell Labs, Kamstrup A/S og Steinwurf Aps er partnere på projektet.

»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.«

12 kommentarer.  Hop til debatten
Denne artikel er gratis...

...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.

Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.

Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.

Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.

Debatten
Log ind eller opret en bruger for at deltage i debatten.
settingsDebatindstillinger
12
24. juni 2019 kl. 13:33

I forhold til denne kontekst ville det vaere muligt at kryptere baade foer og efter deduplikering. Det skal bare goeres til en del a processen. Det ville fungere fint, lige som det allerede goer i "klassisk" deduplikering.

Det lyder dejligt. Har information om hvordan det gøres? Konteksten er to konti hos en cloud udbyder. Data er krypteret på disken og hver konto har sin egen krypteringsnøgle. For mig lyder det umuligt at deduppe. Så hvis du har noget info om hvordan man gør det så del endelig :)

11
24. juni 2019 kl. 12:23

I forhold til denne kontekst ville det vaere muligt at kryptere baade foer og efter deduplikering. Det skal bare goeres til en del a processen. Det ville fungere fint, lige som det allerede goer i "klassisk" deduplikering.

10
2. april 2019 kl. 12:07

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 ;-)

8
2. april 2019 kl. 00:14

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.

7
29. marts 2019 kl. 14:55

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.

5
29. marts 2019 kl. 12:11

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.

Det kommer jo an på hvilken "mode of operation" man bruger: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation Generelt anses det som væsentligt mindre sikkert at bruge Electronic Codebook mode, som er den eneste måde at opnå ens ciphertext ud fra ens plaintext.

4
29. marts 2019 kl. 11:39

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.

3
29. marts 2019 kl. 10:51

Så er det ærgeligt at journalisten ikke spurgte ind til det. For hvordan kan man lave cloud scale deduplikering på block level hvis meget af data er krypteret på disken?

2
29. marts 2019 kl. 09:39

Krypteret data svarer til random data i statistisk fordeling, så det får man nok ikke meget ud af at prøve at deduplikere.

1
29. marts 2019 kl. 06:54

Det er bedst praksis st kryptere data at rest. Det gør alle de cloud projekter jeg har været involveret i. Kan man lave block level dedup på krypteret data?