Unikátní klíč nad dlouhým řetězcem
Školení, která pořádám 
Tabulky typu InnoDB umožňují maximální délku sloupce v indexu jen 767 bytů (255 UTF-8 znaků + délka). U normálních indexů to nevadí, protože můžeme pomocí sloupec(255) index vytvořit jen nad začátkem sloupce. Problém nastává u unikátních indexů, kde se řetězec může lišit až za délkou zachycenou v indexu. Tento problém nastává např. u URL nebo u cest k souborům, které mohou být dlouhé, mohou se lišit až na konci a které můžeme potřebovat unikátní.
Řešit se to dá přidáním sloupce, do kterého uložíme haš sloupce a unikátní index vytvoříme nad ním. Sloupec můžeme naplňovat triggerem, abychom na to třeba při importu nezapomněli.
CREATE TABLE `feed` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`url` varchar(2047) NOT NULL,
`url_md5` binary(16) NOT NULL DEFAULT '',
PRIMARY KEY (`id`),
UNIQUE KEY `url_md5` (`url_md5`)
);
CREATE TRIGGER `feed_bi` BEFORE INSERT ON `feed` FOR EACH ROW
SET NEW.`url_md5` = UNHEX(MD5(NEW.`url`));
CREATE TRIGGER `feed_bu` BEFORE UPDATE ON `feed` FOR EACH ROW
SET NEW.`url_md5` = UNHEX(MD5(NEW.`url`));
Sloupec můžeme použít i při vyhledávání, jen musíme podmínku ručně zkonstruovat. Pro třídění řazení index samozřejmě použít nemůžeme, to ale u URL obvykle není potřeba.
Diskuse
Pawouk:
Super, díky za typ.Bram:
Otázka je, zda je vhodné spoléhat na to, že nevzniknou kolize vygenerovaných hashů i pro různé řetězce. Pravděpodobnost toho je velmi malá, ale přesto toto riziko existuje.Franta:
Zvlášť když se použije algoritmus MD5…
Jakub Vrána 
:
http://stackoverflow.com/questions/1999824/…#answer-4371834 ukazuje kolizi na 16 bajtech. Ale připravit ji tak, aby řetězce splňovaly formát URL, by byl oříšek.
Jakub Vrána : Jakub Vrána :
U hašovacích funkcí kolize samozřejmě nastat můžou, ale v praxi s tím není potřeba bojovat, obzvlášť u krátkých řetězců. Pravděpodobnost, že by kolize vznikla jen tak náhodou, je nula na mnoho desetinných míst.
Jakub Vrána : Petr:
Já bych si tím nevzniknutím kolize nebyl tak jistý. Chtěl jsem tuto metodu použít pro tabulku s asi 1M záznamů a kolizí bylo hodně. Jednalo se o řetězce o délkách od 4 do 8 znaků. MD5 mi na to přijde nepoužitelné.Jirka:
Chci ten soubor ke stažení. Tohle je totiž šílená pitomost.Kdybyste našel dva kolizní řetězce o čtyřech až osmi znacích, tak by to bylo na publikaci v nějakém prestižním vědeckém časopise.
Všechny známé md5 kolize jsou totiž obskurní BINÁRNÍ a DLOUHÉ kusy nesmyslných dat. Nevím o tom, že by byly známy dva ascii texty, generující totožný md5 hash.
Vojta:
Souhlas. Tipoval bych spíš na nějakou chybu při volání MD5 (nějaký NULL mohl třeba vynulovat celý vstupní řetězec). Kromě toho lze pro klid duše hashovaný řetězec osolit třeba IDčkem záznamu, tím vznikne unikátní řetězec v rámci celé tabulky.Franta:
Což by bylo na nic, protože 1http://example.com/ by mělo jiný hash než 2http://example.com/, zatímco ty chceš, aby URL bylo unikátní tzn. nešlo zadat dvě stejná. BTW: co vede lidi v roce 2013 k používání MD5? To musí být asi nějaké opravdu silné citové pouto :-)
David Grudl:
A proč ne? Je to rychlé a generuje to dostatečně rozdílné hashe. Že lze dnes snadno dohledávat kolize naprosto ničemu nevadí.
David Grudl: Vojta:
Jde o reakci na příspěvek výše, ne na článek. To osolení je pro případ rizika duplicit vstupu do MD5, které je při řetězci o 4-8 znacích a milionu záznamů značné, viz příspěvek od "kb".Pokud potřebuji jedinečnost URL, tak samozřejmě IDčkem solit nemůžu :-)
kb:
Při délce 4-8 znaků a 1M záznamech je hodně slušná pravděpodobnost, že x z nich jsou stejné. Pak mají stejný i hash (pokud se nesolí). Vysvětloval bych si ty kolize spíš takhle :-). Vzniká tu kolem md5 hrozná paranoia.Vojta:
Přesně. Lidé neošetří vstupy, pak z toho viní MD5 a ještě snad doufají, že to za ně vyřeší SHA512 :-) David Grudl:
Pokud je délka MD5 2^128 (což je asi 3e38) a ty operuješ s 1e6 záznamů a kolize ti vznikaly často, tak myslím, že bys tu mohl tak ze tři-čtyři uvést, jinak prostě děsně kecáš ;)
David Grudl: P.:
No myslím že tady je to pěkně spočítáno :)http://stackoverflow.com/questions/201705/…-collisions
baghira:
Hash se ale za unikátní klíč považovat nedá, ne?Michal:
Ja osobne pouzivam php funkci crc32 na url a tu pak ukladam jako index typu int, resp bigint. Zcela spolehlive a funkci...Jen pozor na to co crc32 funkce vraci na 32 a 64 bit platforme. Na 32 bit platforme vraci "signed" cislo a tak je s tim potreba pocitat.
socan:
No... zajimavy tip, ale pokud to pujde, budu se snazit mu za kazdou cenu vyhnout.Jinak si myslim, ze pravdepodobnost kolize, ze dva zaznamy by mely stejny hash, je zanedbatelna, pokud zrovna nepisu aplikaci pro rizeni jaderneho reaktoru.
snk:
Já si myslím, že ta pravděpodobnost je stále stejná. Ať píšeš web pro frantu 123 nebo jaderný reaktor :)Patrik Šíma:
URL bych asi řešil rozparsováním na jednotlivé komponenty (doména, cesta, query). Do 767 bytů (u url nemá smysl operovat s unicode) by se měla vlézt jakákoli část. A pokud ne, můžeme to ještě pojistit hashem každé z nich a na ně dát unique index.
Jan Kahoun:
Vyhledavani zaznamu bude vzdycky rychlejsi pokud se pouzije zminovany hash, protoze porovnavani je binarni. U tabulek s miliony zaznamu to muze znamenat vyrazny rozdil. Jakub Vrána :
Ani cesta (část od /), ani dotaz (část od ?) ani fragment (část od #) se vejít nemusí. Tohle řešení je tedy k ničemu.
Jakub Vrána : Patrik Šíma:
Nemusí. To můžeš stejně tak napsat, že se do longtextu nevleze každý článek. Nebo, že ID bigint(32) nebude někdy stačit, takže je to taky k ničemu. Jenže do databáze se neukládá teorie. Na 95 % případů se to v pohodě vleze. U ostatních bych použil něco úplně jiného. Pole taky nebudeš orat Fiatem 600.
Patrik Šíma:
Stejně tak můžu napsat, že použití hashe, který již z principu nemůže být unikátní, je vlastně stejně k ničemu jako 3500 bajtový klíč :)
Jakub Vrána :
95% případů je žalostně málo. Použití hašovací funkce bude v pořádku asi tak v 99.9 a za tím mnoho dalších devítek procentech případů, takže je v praxi na rozdíl od rozkládání URL na části použitelné.
Jakub Vrána : Patrik Šíma:
Žádná taková "praxe" mě nenapadá. 95 % jsem si vycucal z prstu. Ve skutečnosti jsem se nikdy z tak dlouhým url nesetkal, takže v "praxi" to může být tvých 99.9 a mnoho devítek (já se z mysql skutečně nechystám indexovat celý internet).
Rozdělení je právě naopak mnohem užitečnější kvůli dotazování. Můžu si tak například snadněji vyfiltrovat url dle domény a nemusím provádět obskurní string dotazy nad sloupcem.
Dále silně pochybuji o efektivitě tak dlouhého klíče (když vezmu v úvahu jak se staví).
Hash prostě je špatné řešení. A unikátní klíč nad dlouhým řetězcem je v praxi zřejmě utopie. Ať se přihlásí někdo, kdo to kdy za svou praxi řešil a použil k tomu MySQL.
Jakub Vrána :
Rozdělení URL na části skutečně může řešit nějaké problémy. Ale neřeší to problém, který je popsaný v článku. Já ve své databázi URL delší než 255 znaků mám, i jednotlivé části (hlavně query string) jsou delší než 255 znaků. Stejně tak cesty můžou být delší. Jde o reálný problém, který jsem řešil.
Jakub Vrána : Patrik Šíma:
Takhle. Hash je pro unique index řešením jen tehdy, počítáme-li s tím, že může přijít kolize (byť je nepravděpodobná). A pak je třeba mít scénář i pro tu kolizi. A to v článku není.
Jakub Vrána :
Pokud aplikace generuje 6 miliard URL za sekundu, tak za sto let skutečně nejspíš dojde ke kolizi (http://stackoverflow.com/questions/201705/…-collisions). Ale řekl bych, že dřív dojde místo na disku, kam ta URL ukládáš.
Ne, některé situace se nevyplatí v aplikaci ošetřovat a tohle je přesně jedna z nich.
Jakub Vrána : Patrik Šíma:
Pravděpodobnost přece neříká, že ke kolizi dojde až ZA x záznamu. Klidně může dojít ke kolizi již u druhého. Nebo ne?
Jakub Vrána :
No jasně, ale musel bych mít smůlu, která nenastává ani za miliardy let.
Jakub Vrána : Vojta:
Jinými slovy, simulovat část funkčnosti velice rychlého MD5 nějakými vlastními už z principu pomalými algoritmy (a ještě na každou část dávat z hlediska rychlosti riskantní unique index)? Proč, abych vyhrál záznam v Guinessově knize rekordů o nejpomalejší uložení záznamu v dějinách? :-)Patrik Šíma:
O simulování MD5 jsem nikde nepsal.
Vojta:
Psal jsem "část funkčnosti MD5", protože všechno to pracné, pomalé a zbytečné parsování řetězce normálně nahradí MD5 svým o několik řádů rychlejším algoritmem.Patrik Šíma:
Jinak lze limit u InnoDB zvýšit. Předpokládám, že u takových projektů si člověk může dovolit alespoň vlastní VPS.
"The InnoDB internal maximum key length is 3500 bytes, but MySQL itself restricts this to 3072 bytes. This limit applies to the length of the combined index key in a multi-column index."
Vojta:
Poznámka sice užitečná, ale principielně ukazující nesprávným směrem. Dokud je limit délky textového pole (typ TEXT, BLOB apod.) v databázi o několik řádů vyšší než možná délka indexu, je jediným rozumným rešením používání hashe.Patrik Šíma:
Není to ani jediné řešení, ani rozumné.
Vojta:
Použití hashe že není rozumné řešení? Vždyť přesně pro tyto případy byly hashe vynalezeny! :-DPatrik Šíma:
Skutečně byly hashe vynalezeny pro unikátní indexy? To je mi novinka.
Vojta:
Tady má někdo problém se čtením. Tvrdíš, že použití hashe pro indexaci dlouhých řetězců není rozumné řešení, což je nesmysl, na který tě tady upozornili prakticky všichni čtenáři.Hashe byly vynalezeny právě pro získání krátkého digestu z dlouhého řetězce tak, aby pro běžně používané řetězce nebo binární data dávaly téměř unikátní výsledky. Takový digest se dá báječně a rychle indexovat a v praxi se toto řešení široce využívá i na obrovských komerčních/bankovních aplikacích právě pro svoji jednoduchost a rychlost.
Ale jestli někoho baví místo jednoho zavolání MD5 provádět magii se serverem a do minimálních požadavků psát věty jako "Tato aplikace funguje jen na MySQL 5.6.123 patch 12 a výše po nastavení max_index_length = 3700 a nezaručuje správnou funkčnost pro řetězce >3700 bajtů", prosím. Jen nechci vědět, kolik takových podmínek by minimální požadavky obsahovaly pro středně velkou aplikaci navrženou s podobným přístupem.
Taco:
Nesouhlasím.
Hash byl vynalezen za tím účelem, aby se dalo jednosměrně zjistit, zda ve zdroji došlo ke změně.
To, že někdo používá hash na to, aby zjistil, zda dva zdroje, které se nám nechce z nějakého důvodu číst celé, nejsou shodné, je zkrátka a dobře zneužití nástroje na něco jiného, než k čemu byl určen.
Zda je takové zneužití dobrý, pragmatický, nebo naopak nedobrý a riskantní nápad je námětem diskuse.
Taco:
Ještě se doplním:
Pokud se v něčem ošklivě nemýlím, tak platí:
- Vezmu-li blob, a v něm změním jeden bit, tak výsledný hash z takového blobu budu výrazně jiný proti originálu.
- Zatímco když vezmu blob, a v něm změním "úplně všechno" (toto tak docela nevím jak lépe vyjádřit), tak výsledný hash se proti originálu může lišit třeba jen v jednom bitu.
Jakub Vrána :
Jaký je zdroj tohoto tvrzení? Mám o něm značné pochybnosti, protože hashe byly podle mně vynalezeny právě proto, aby se daly snadno a rychle odlišit dvě různé zprávy. Jestli tyto zprávy vychází ze stejného originálu nebo ne, je úplně jedno.
Jakub Vrána : Taco:
Přesný zdroj ti už neposkytnu. Ale třeba namátkou wiki říká hezkou formulaci: "... porovnáme signaturu k s (předpočítanými) signaturami dat a pokud se neshoduje, můžeme data vyloučit jako určitě nerelevantní. Při shodě máme potenciální kandidáty, které musíme otestovat podrobněji."
Logicky to lze odvodit z chování hashovací funkce, viz můj druhý příspěvek.
PS: Podezření je hezká věc, ale jaksy málo pádné.
Jakub Vrána :
To je limit celé délky klíče. Pak je ještě limit jednoho sloupce (767 bajtů), který bohužel zvýšit nejde. Navíc ani nevidím, jak lze zvýšit těch 3072 bajtů.
Nevím, co myslíš „takovými projekty“, ale unikátní URL nebo cestu se hodí ukládat u všemožných projektů, třeba i takových, kde instalaci nemám pod kontrolou.
Jakub Vrána : Patrik Šíma:
http://dev.mysql.com/doc/refman/5.5/en/innodb-…_large_prefix
Nevím co myslíš "všemožné projekty", protože mě nenapadá ani jeden, kde bych musel použít tak prasácky dlouhý klíč a ještě použil mysql. Tebe jo?
Jakub Vrána :
Např.:
Aplikace, která jakkoliv pracuje s cestami na disku, třeba indexace cest v repozitáři.
Aplikace, která jakkoliv pracuje s URL, např. čtečka feedů.
Žádný prasácky dlouhý klíč se nevytváří, klíč v příkladu má 16 bajtů. Unikátní klíč je velmi pohodlný způsob, jak zajistit, že daný záznam bude v tabulce jen jednou. Neexistuje jediný důvod, proč pro to nepoužít MySQL.
Jakub Vrána : Patrik Šíma:
Souhlasím s tím, že se šance limitně blíží k nule. Taky souhlasím s tím, že v praxi zřejmě nelze použít nic jiného než hash. Ale je dost blbé nezmínit, že hash není unikátní a může dojít ke kolizi. Tedy, že používám něco co není unikátní pro unikátní klíč. To v článku není.
Jak ukládat url je asi irelevatní, protože nevíme co chceme s daty dělat.
Vojta:
Jen nevím, proč se volá ten UNHEX, vždyť jde přeci ukládat rovnou MD5, ne?kb:
Nejspíš úspora místa. Možná i lepší efektivita při porovnávání ale to nemám podložené.Patrik Šíma:
Protože sloupec je BINARY
Patrik Šíma:
Takže test proveden. Povedlo se mi udělat duplicitu již při 212tis. řádcích. Tolik k použití hashe.
Patrik Šíma:
Tak beru zpět, protože se mi nepodařilo ověřit, zda nebyl vygenerován náhodou stejný řetězec.
Tomáš Fejfar:
Jakube, oprav si "třídění" na "řazení" v poslední větě. Třídíme do tříd podle společných znaků (např. zbytkové třídy po celočíselném dělení) a řadíme do řady (např podle velikosti).
Jakub Vrána :
Díky za upozornění, opravil jsem to. Snad si to do budoucna zapamatuji.
Jakub Vrána : Stanislav Nechutný:
Pokud se obávám, že by mohlo dojít k duplicitě hashe, tak mohu použít konstrukciCREATE TRIGGER `feed_bi` BEFORE INSERT ON `feed` FOR EACH ROW
SET NEW.`url_md5` = UNHEX(CONCAT(MD5(NEW.`url`),SHA1(NEW.`url`)));
dojde tím sice k zvětšení porovnávaného sloupce, ale měl by se stále vejít do indexu a pravděpodobnost kolize se extrémně sníží.
Jan Kahoun:
Jakube, místo UNHEX() můžeš použít hexadecimální literál "x" http://dev.mysql.com/doc/refman/5.5/en/hexadecimal-literals.htmlJe to o něco rychlejší :-)
Jan Kahoun:
Omlouvám se, v tomhle případě to vlastně nejde :(Michal Prynych:
Myslím, že přesně toto jsem už jednou řešil a použil jsem velmi podobné řešení. Kolize jsem vyřešil tak, že v select dotazu jsem se ptal na hash i konkrétní hodnotu url. Databáze pak použila klíč nad hashem a pak jen porovnala konkrétní hodnotu s výsledky vybranými podle klíče (shodou okolností jsem nikdy kolizi neměl, ikdyž jsem použil jednodušší hash než md5). Jakub Vrána :
Pak ale nelze použít unikátní klíč.
Jakub Vrána : Michal Prynych:
To je pravda, je to spíše alternativní řešení problému rychlého vyhledávání dlouhých řetězců než unikátní klíč. Nicméně je to poměrně jednoduché a výkonné.Ivan Dlugos:
Nesiel by cely problem riesit trochu inak ako unikatnym klucom? Konkretne napr. spravit ON BEFORE UPDATE/INSERT trigger ktory skontroluje ci sa tento retazec uz v databze nenachadza. Rychlost vyhladavania riesit bud standardnym indexom na danom stlpci ALEBO na hashi a naslednym presnym porovnanim pozadovanych retazcov s retazcami s rovnakym hashom. Jakub Vrána :
Taky by to šlo, ale v tom případě by bohužel nešly použít obraty jako ON DUPLICATE KEY UPDATE.
Jakub Vrána : Diskuse je zrušena z důvodu spamu.
© 2005-2024 