Dotaz: Porovnání většího množství dat - hashe, ...?

[dc]

Ahoj, potřeboval bych pravidelně porovnávat větší množství dat. Pro zjednodušení řekněme že se jedná o 2 relační databáze na různých serverech, v každé jedna tabulka, v tabulce miliony řádků, sloupce s daty o 1 či tisíci znacích.

Nechci přenášet takto objemná data mezi servery a pak porovnávat celé hodnoty "řádek po řádku/sloupec po sloupci/znak po znaku". Napadlo mě udělat v obou tabulkách pro každou hodnotu v tabulce hash a z jednoho serveru přenést místo čistých dat tyto hashe a pak je porovnávat. Určitě to bude rychlejší (i datově méně náročně) než přenášet a porovnávat originální data. Nicméně mám několik otázek:

• Jakou hashovací funkci použít abych "vždy" detekoval, že jsou data rozdílná? SHA512 co se týče pravděpodobnosti kolizí?
• Použít jen jeden hash nebo více různých naráz pro vyhnutí se kolizím?
• Nějaký lepší způsob (trochu se bojím kolizí u hashů)? Každopádně jsem koukal, že některé zálohovací SW i například souborové systémy s deduplikací hledají stejné bloky jen podle hashe ... takže se spoléhají jen na pravděpodobnost že ke kolizi nedojde ...

Díky moc za nápady.

Odpovědi

[Kit]

Běžně se používá SHA-1 (160 b) a stačí to.

[Jendа]

https://en.wikipedia.org/wiki/Birthday_problem (tl;dr běžná SHA je v pohodě)

Pokud ale máš sloupec s méně než 32 znaky („sloupce s daty o 1 či tisíci znacích“), tak se to jaksi nevyplatí.

[chrono]

Nějaký lepší způsob (trochu se bojím kolizí u hashů)? Každopádně jsem koukal, že některé zálohovací SW i například souborové systémy s deduplikací hledají stejné bloky jen podle hashe ... takže se spoléhají jen na pravděpodobnost že ke kolizi nedojde ...

Zvyčajne sa to robí tak, že ak je hash rovnaký, tak sa porovnajú dáta (inak tie dáta porovnávať netreba, pretože sú určite iné).

PS: A ak sú tie riadky krátke, pravdepodobne bude stačiť aj MD5 (pretože je to rýchlejšie ako SHA a hash zaberá menej).

[RADEK]

Pokud použiješ hash, pak nemůžeš zjistit jestli jsou data rodílná. Pokud je rodílný hash, pak jsou data rodílná. Pokud je ale hash stejný, pak není možné řící jestli jsou data stejná. Platí pro většinu hash funkcí. Určitě pro sha

[rastos]

Radek: Mám pocit, že tam máš nejaké preklepy.

Každopádne - aby nastala kolízia (zhoda hash-u pri rozdielnom vstupe) pre SHA (či MD5), tak sa treba snažiť. Pri SHA celkom dosť. Pri MD5 menej, ale stále celkom dosť. Pravdepodobnosť, že by sa to podarilo náhodou, je mizivá - to skôr vyhráš v lotérii.

[dc]

No právě. Proto chci, aby dalo alespoň říci, že data jsou na "99,999999999 procent" stejná. Jinou možností je asi jen porovnávat znak po znaku (respektive bajt po bajtu), ale vzhledem k tomu, že některé "sloupce" obsahují binární data (malé obrázky, občas PDFka) v base64, pak je docela náročné už jen tato data přenést na jiný server.

[Kit]

V případě SHA-1 je těch devítek asi 50. Bude ti to stačit nebo jich potřebuješ víc?

[Jendа]

Neznáme jeho aplikaci, pokud mu tam data nahrávají uživatelé a útočník může mít nějaký zájem na tom, aby měl nekonzistentní data, pak by bylo lepší použít hashovací funkci, která není nalomená. Třeba SHA-2.

[Jendа]

A přečetl sis tu stránku o birthday paradoxu, kterou jsem odkazoval?

[dc]

S tím jsem seznámen. Je jasné, že pravděpodobnost toho, sha1(data1) = sha1(data2) je mnohem větší než, že sha1(data1) = nejakyhash. Pročítal jsem různé články a počítal jsem i různé pravděpodobnosti i u docela "exotických" nekryptograficky bezpečných hashů a právě mi i ta malá (někde) pravděpodobnost přijde dost vysoká.

[pavlix]

Nekryptograficky bezpečných? :)

[Filip Jirsák]

právě mi i ta malá (někde) pravděpodobnost přijde dost vysoká

V tom případě doporučuju sázení. Až k té kolizi dojde, budete mít už dávno vyhráno neuvěřitelné množství prvních cen, takže z toho jednak snadno zaplatíte škody způsobené tou kolizí hashů, jednak už vás to vůbec nebude zajímat, protože si budete jako multimiliardář užívat na nějakém exotickém ostrově.

[Radovan]

Když ti z milionů souborů vyjde stovka dvojic/trojic se stejnými hashi a stejnou velikostí(!), je potom tak velký problém tuhle hrstku porovnat znak po znaku, do prvního rozdílu?

Nebo použij dva různé hashe současně, to tě také nezabije.

[dc]

To by bylo supr, ale ty soubory jsou většinou stejně veliké (počet znaků base64, alespoň ty obrázky).

[Kit]

Když z miliónu souborů vyjde byť i jedna jediná dvojice s různým obsahem, ale se stejnými hashi, bude to událost tisíciletí.

Zkus si to pro CRC32, u toho nějakou šanci máš.

[krocan]

Dotaz nedava prilis smysl. Co ma znamenat "vzdy" - vadi chyba nebo nevadi? Co znamena porovnani dat - podle PK, podle neceho jineho? Porovnavaji se vzdy vsechny sloupce, nebo jen nektere? Co ma byt vystupem - hodnota ano/ne, seznam rozdilnych radku, neco jineho?

[dc]

Ano, chyba vadí. Nicméně u hashů moc na výběr není, takže jde o to aby to bylo co nejméně pravděpodobné. Porovnávají se řádky hodnota po hodnotě.

[Sten]

Neuvádíte, o jaká data jde, u obecných (náhodných) dat platí: pravděpodobnost kolize je nepřímo úměrná podílu délky hashe k délce vstupních dat. Je jedno, jaký algoritmus použijete (klidně můžete použít CRC), rozhodující je jen jeho délka. Pokud byste měl obecný text, pak je vhodný algoritmus, který má avalanche effect (tj. bude mít uniformní distribuci nad ASCII), ale pak už je opět jedno, který konkrétně to bude. Smysl složitých hashů je pouze to, že je složité vyvolat kolizi úmyslně, pravděpodobnost náhodné kolize je opět jen nepřímo úměrná délce hashe.

[Tomas]

Pokud by vás zajímá shoda (join) nikoli rozdíly (antijoin) tak vám doporučím Bloom filtr.

Mám vnitřní tušení, že vás budou zajímat primárně rozdíly (antijoin), takže vás žádný hash nebo Bloom filter nespasí.

[Tomas]

Asi jsem se nevyjádřil dost srozumitelně.

Pokud vás budou zajímat jen rozdíly mezi dvěma přibližně stejnými množinami, tak z převážné většiny bude porovnání vypadat takto:

1. Zjisti shodu hashů. Ve většině případů najdeme shodu, protože množiny jsou skoro stejné. Jdeme na krok 2
2. Protože nevíme zda jde o kolizi nebo opravdovou shodu, tak musíme dotáhnout plné záznamy k hashům abychom případ kolize ošetřili.

Z postupu vyplývá, že pro drtivou většinu případů v antijoinu musíte dotáhnout tak jako tak celé záznamy a porovnání pomocí hashe vám v rozhodovacím procesu pomůže jen minimálně. Přesněji vám pomůže pouze v tom případě, že nenajdete shodu při porovnání hashe. Ale těchto případů budou pro přibližně stejné množiny jen zlomky procent.

[Kit]

Pokud mě zajímají jen rozdíly, vypustím 2. krok, který by byl zbytečně náročný a stejně by nic neřešil.

[Filip Jirsák]

Každá hashovací funkce má kolize, je to jejich princip. Zároveň platí, že čím delší hash, tím menší pravděpodobnost kolize. A do třetice, pokud nejste banka a nemáte v té tabulce transakce klientů, nebo tam nemáte stažené soubory z celého internetu, tak se kolizí nebojte. Hashovací funkce se používají pro mnohem kritičtější věci, než je nejspíš vaše databáze, a pravděpodobnost kolize je extrémně malá. Pravděpodobnost, že vám pro miliardu řádků vyjde stejný SHA-1 hash, je 10^(-10^65.50155362143924).

[lertimir]

To tve cislo se mi nezda. Nebo je to pravdepodobnost, ze vsechny radky budou mit stejny hash, nicmene to moc zajimava hodnota neni. Ale je zrejme, ze tazatel si neco precetl, ale vubec neumi ve velkych cislech pracovat. Pro tazatele. I nejjednodussi soucasny hash SHA-1 se pohybuje v dimenzi 10^48 coz dava cca 10^34 hashu na kazdy bit, ktery na tom disku muze byt ulozen a take vice nez 10^11 hashu pro kazdou jadernou castici vsech atomu z nichz je disk vyroben. Pravdepodobnost kolize sice existuje, ale pro normalni data je mala. A cileny utok na vytvoreni kolize na jeden hash je mozny, odhadovana cena je cca 100k $. Takze pokud tam nejsou opravdu dulezita data tak ti staci i SHA-1.

[Filip Jirsák]

Klidně to můžete přepočítat. Je to přece varianta narozeninového paradoxu, akorát místo rozdělení n lidí do 365 skupin podle dne v roce rozdělujete miliardu dokumentů do 2¹⁶⁰ skupin podle SHA-1 hashe.

[pavlix]

Tak jestli psal lertemir o hledání ekvivalentního hashe k pevnému a vy o hledání dvojice (birthday paradox), tak to leccos vysvětluje. :D

[Filip Jirsák]

Já jsem psal o tom, co popisuje tazatel. Má dvě tabulky s miliony záznamů, a bojí se kolize hashovací funkce. Já jsem ty dvě tabulky sesypal na jedno místo a předpokládám tam miliardu záznamů – takže ty dvě tabulky s „miliony záznamů“ by mohly mít třeba každá půl miliardy. Narozeninový paradox říká, s jakou pravděpodobností na té hromadě s miliardou záznamů bude dvojice záznamů se stejným hashem. Nerozlišuju, zda by dvojice se stejným hashem byla v jedné původní tabulce nebo každý záznam z dvojice v jedné tabulce – předpokládám, že problém by byl s oběma variantami.

Hledání dokumentu se stejným hashem, jako má jeden předem vybraný dokument, to by byl záměrný útok na jeden konkrétní záznam. Tam je ta pravděpodobnost samozřejmě ještě nižší (na druhou stranu je to úplně jedno, protože v řádech, ve kterých se pohybujeme, neznamená milionkrát nižší pravděpodobnost vůbec nic).

[lertimir]

Jednoduchá triviální úvaha říká, že pravděpodobnost při jakémukoli kombinaci v narozeninovém paradoxu je větší než základní pravděpodobnost. A ta základní je 2^-160 tj cca 10^-48. V kombinaci více hashů v exponentu musí být pravděpodobnost víc než 10^-48. To tvé číslo je absurdní. A opět jednoduchá úvaha říká, že pro 10^9 záznamů mám cca 10^18 kombinací dvojic (n*(n-1)/2). Takže cca pravděpodobnost kolize bude někde v řádu 10^-30.

[Filip Jirsák]

Máte pravdu, někde jsem udělal chybu při zápisu exponenciální aproximace do Wolfram Alpha. A jak jsem počítal s délkou hashe 2¹⁶⁰, nedocvaklo mi, že v tom desítkovém základu je to trochu moc 10^-30 je správně.

[Filip Jirsák]

Ještě k těm jiným způsobům - pokud se mezi dvěma porovnáními nezmění všechna data, pomohlo by přidat do té tabulky triggerem plněný sloupeček s časem poslední změny. Při přenosu pak vezmete jenom ty řádky, které se změnily od posledního přenosu.

[Heron]

Algoritmus, které používají některé programy, na posouzení shody souborů:

1. porovnání velikostí (soubory o různých velikostech jsou různé)
2. porovnání hashů (soubory s různými hashi jsou různé)
3. porovnání dat u souborů se stejnými hash*

Jde o cenu jednotlivých kroků. Jestliže je okamžitě známa velikost dat, je dobré s tím začít, protože je to nejlevnější. Pokud jsou jednotlivé balíky dat stejně velké, nemá tento krok smysl.

Neznám strukturu vaší db, já ukládám hash (sha512) vždy společně s daty v db (PostgreSQL datový typ BYTEA). Takže tato možnost je (u mě) zadarmo, všechny hash už jsou dostupné a stačí je jen porovnat.

Co se týče výběru funkce, postupuju jednoduše: jaká je aktuálně nejsilnější dostupná funkce? Lze ji použít? Hotovo. Nevím, proč bych se měl zabývat (jak tady někteří naznačují**) tím, jestli sha1 je nebo není dostatečná. Na 6 let staré plečce běží sha512sum rychlostí přes 200MB/s. Je to singlthread proces, takže si jich pustím 4 současně a dostávám rychlost 1GB/s. Tolik ten storage stejně ani nedá. Takže není vůbec co řešit.

*) Rozčiluje mě, pokud někdo automaticky beze h(d1) == h(d2) => d1 == d2. Tato implikace neplatí. Proto je nutný ten třetí krok, tedy porovnat data (bez ohledu na to, jak moc nepravděpodobné je nalezení kolize). Udělat to můžu, tak proč to neudělat?

**) Možná pracují na speciálním HW s velmi omezenými prostředky. Na PC toto není potřeba vůbec řešit.

[dustin]

Opravdu je rychlejší spočítat z jednotlivých dat hashe a pak porovnávat všechny hashe, než porovnávat rovnou data?

Nevím, kolik těch dat je, ale z hlediska celkové náročnosti bych si tipnul, že obyč. dump do txt (v mysql např. do formátu mysqldump -tab), přenos změn přes rsync na druhou stranu se zapnoutou gzip kompresí (-z) a normální porovnání řádek po řádku s druhým dumpem vyjde v součtu všech operací nejúsporněji. I pro jednotky gigabajtů to musí být řádově minuty, když už se přenášejí jenom změny.

Samozřejmě nevím, kolik těch změn tam je, jak tabulky rostou atd. atd.

[Filip Jirsák]

Ten hash se spočítá jednou v okamžiku změny. Pokud nebude změněné prakticky všechno, vyplatí se to. Rsync nedělá nic jiného, než že počítá hash a přenáší jen změněná data... Akorát ten hash rsyncu je optimalizovaný na rychlý výpočet, ne na kryptografickou bezpečnost - ale zase se musí počítat vždy znovu.

[dustin]

To ale vyžaduje úpravu stávající aplikace, což nevím, zda tazatel může. Jinak by se hashe musely kešovat mimo aplikaci, což je další overhead.

IMO pro taková data (jednotky GB) je nejjednodušší a nejspolehlivější řešení dump, rsync na druhou stranu a normální porovnání s dumpem druhé db. Pokud by šlo řádky rozšířit o sloupeček timestampu, šly by na obou stranách vytahovat jenom řádky se změnou od data posledního porovnávání (s nějakou časovou rezervou), to by mohlo výrazně urychlit.

Nebo v db nastavit replikaci na druhou stranu a porovnávat to v DB. To by mělo minimální overhead při přenosu, db posílá jen změny. Klidně i s využitím těch timestampů.

[dustin]

Jo, vidím, že ten timestamp jsi navrhoval. V mysql používáme přímo typ timestamp, který se automaticky aktualizuje při každém zápisu do libovolného sloupce řádky.

[Filip Jirsák]

To ale vyžaduje úpravu stávající aplikace, což nevím, zda tazatel může.

Ne aplikace, ale databáze.

Vzhledem k tomu, že tazatel nechce přenášet celou databázi, není rada, že má přenést celou databázi, asi přesně to, co chce slyšet…

[dustin]

Někdy bývají nejjednodušší řešení ta správná. A někdy taky ne.

[xkucf03]

Můžeš té databázi věřit? Nebo ti do těch dat může někdo cizí hrabat, falšovat je a ty si to musíš zkontrolovat?

Pokud je to tvoje databáze a věříš jí, tak bych se na nějaké hashe vykašlal a jednoduše si tam dal sloupeček s číslem verze (lepší než datum a čas, protože bude spolehlivě unikátní) a trigger, který bude číslo při každé změně zvyšovat.

Pak budeš porovnávat jen čísla verzí a pokud se budou lišit, tak teprve spočteš hash nebo rovnou přeneseš data a porovnáš/synchronizuješ data.

BTW: koukni na SymmetricDS – to je hotový nástroj na synchronizaci databází.