Použití mechanizmu MD5 hash k detekci změn v importovaných datech

Jednou z nejčastějších oblastí, ve které data neodpovídají našim potřebám, je jejich velikost (objem dat). Pro protější stranu je zpravidla nejjednodušší posílat opakovaně všechna data, která nám má poslat, bez ohledu na to, zda se změnila nebo ne. Pro nás by naopak bylo jednodušší dostávat pouze změny. Při pomyslném přehazování horké brambory, kterou představuje implementace detekce změn, jsme my, jakožto příjemce dat, odsouzeni k předem prohrané hře - aby o poslání či neposlání rozhodoval protějšek by z principu nebylo dobré: může mít příjemců více a musel by si evidovat, co komu odeslal, tato informace by byla nespolehlivá při případných výpadcích v přenosu apod. Detekovat změny tedy musíme my. Triviální algoritmus by vypadal např. takto (v pseudokódu pro obecnou entitu):

void importEntity(Entity importedEntity) {
	Entity dbEntity = findEntityByAllProperties(importedEntity.property1, importedEntity.property2, ..., importedEntity.propertyN);
	if (dbEntity == null) {
		newEntity(importedEntity);
	} else {
		unchangedEntity(dbEntity);
	}
}

Úkolem metody findEntityByAllProperties je nalézt, zda importovaná entita existuje v databázi. Její identitu na naší straně teprve hledáme, a proto se musíme opřít o její obsah (property1..N jsou properties, které mají vliv na detekci změny, což nutně nemusí být všechny properties z importované entity). Metoda newEntity zajišťuje vložení nové entity, metoda unchangedEntity nemusí dělat nic (v ukázce je pouze její signaturou naznačeno, že může dělat pomocné dodatečné aktualizace, které však úzce nesouvisí s popisovanou problematikou).

Je zřejmé, že kamenem úrazu uvedeného řešení by byla implementace metody findEntityByAllProperties, především sbírání hodnot všech potřebných properties z mnohdy složitého db modelu. Proto je vhodnější řešení vypočítat si z hodnot property1..N MD5 hash. Tento hash je uložen v databázi u entity (ukládá se v metodě newEntity) a je použit při vyhledávání (pravděpodobnost kolize je prakticky nulová a nad sloupcem existuje index, takže vyhledávání je spolehlivé a rychlé).

void importEntity(Entity importedEntity) {
	Hash md5Hash = importedEntity.computeMd5Hash();
	Entity dbEntity = findEntityByHash(md5Hash);
	if (dbEntity == null) {
		newEntity(importedEntity, md5Hash);
	} else {
		unchangedEntity(dbEntity);
	}
}

Toto řešení pokrývá řadu problémů (zejména s výkonem při detekci změn) a značně omezuje objem importovaných dat (tj. převažuje větev volající unchangedEntity). Algoritmus má však nevýhodu, která se projeví v případě potřeby rozšířit hashovací funkci o další properties. Naivní rozšíření by vedlo k jinému hash kódu při stejných vstupních datech a entita by se tvářila jako nová. Tato vlastnost byla v případě tohoto projektu fatální, protože by mohla způsobit jednak neúnosnou zátěž pro korektorky, jednak zahlcení systému. Možné řešení spočívá ve verzování hashí.

Mějme entitu s properties A, B, C a hodnotami A=a, B=b a hashovací funkci H1(A, B), která pro tyto hodnoty dá výsledek h1. Pokud se změní např. property B na hodnotu x, hashovací funkce H1 správně vrátí jiný výsledek h11. Pokud k entitě přibude property C, hashovací funkce nad properties A, B, C bude jiná. (Poznámka: jinakostí se rozumí, že jiná množina vstupních dat má vliv na výsledek. To nemusí nutně znamenat změnu implementace - pokud např. hashovací funkce iteruje přes mapu všech properties, pak se změní hashovací funkce pouhou změnou mapy.) Označme ji H2 - a tato funkce bude dávat zcela jiný výsledek h2. Při případných dalších změnách v datech dává funkce výsledek h22 atd.

Znázorníme výše uvedený slovní popis graficky, protože z obrázku bude IMHO dobře patrné i řešení.

Osa x vyjadřuje, jak se mění data, osa y vyjadřuje, jak se mění hashovací funkce. Život entity je popsán neklesajícím grafem. Příčina problémů dosavadního algoritmu spočívá v tom, že hash se u objektu může změnit ze dvou různých důvodů, přičemž žádoucí je pouze důvod změny dat.

Změny hashovací funkce budeme označovat jako verze a číslovat 1, 2, … Z výkonových důvodů není vhodné (a často ani potřebné) přegenerovávat hash kódy u všech entit podle nové funkce. Šetrnější algoritmus, který ale přesto zohledňuje verzování hashovacích funkcí, je následující:

SortedSet usedVersions = ...; // serazeno sestupne
void importEntity(Entity importedEntity) {
	SortedMap, Hash> md5Hashes = importedEntity.computeMd5Hashes(usedVersions);
	int newestVersion = usedVersions.first();
	Hash newestMd5Hash = md5Hashes.get(newestVersion);
	for (version, md5Hash : md5Hashes) { // projde hashe od nejnovejsi po nejstarsi
		Entity dbEntity = findEntityByHash(md5Hash);
		if (dbEntity != null) {
			if (version == newestVersion) {
				unchangedEntity(importedEntity);
			} else {
				unchangedEntity(importedEntity, newestVersion);
			}
			return;
		}
	}
	newEntity(importedEntity);
}

Algoritmus předpokládá znalost všech verzí, které jsou v celém systému použity (tj. podle nichž dosud existují v systému platné entity). Tyto verze tvoří množinu seřazenou sestupně. Pro danou entitu vypočte postupně hash kódy pomocí jednotlivých hashovacích funkcí, přičemž jakmile nějaký hash nalezne, považuje entitu za nezměněnou a až po neúspěšném hledání všech hash kódů považuje entitu za novou. Přetížení metody unchangedItem znázorňuje dodatečnou aktualizaci hash kódu za nejnovější verzi, pokud dosavadní není nejnovější. Hash kódy se tedy aktualizují až v okamžiku importu, což nevadí, protože do té doby hash stejně nikdo nepotřebuje.

Přechod na verzované hash kódy musí být transparentní a stejně opatrný jako samotný rutinní provoz. Jednou z možností je:

• zavést verzi 0 a zařadit do usedVersions
• updatnout všechny záznamy na nový formát hash kódů s verzí 0
• upravit metodu computeMd5Hashes tak, aby pro vstup 0 vrátila aktuální hash z databáze (ale pouze pokud je tento hash verze 0, v opačném případě může vrátit null nebo dummy řetězec)

Po čase, kdy zmizí všechny entity s hash kódem 0, lze vrátit zpět původní podobu algoritmu.

Počet naráz používaných verzí by měl být co nejmenší, protože určuje počet průchodů cyklem a v případě nových entit dochází k průchodu celého cyklu. Ideální stav v rutinním provozu je jedna verze, v „přechodovém období“ dvě. V reálném světě mohou vznikat požadavky na novou verzi a přitom v systému stále existovat entity se starými verzemi hash kódů, pak je potřeba průběžně sledovat, zda jsou staré verze ještě používány, případně je hromadně přegenerovat z dat v databázi.

Pokud entita může být změněna i jiným způsobem (např. editací z administrace), je nutné rozmyslet, zda má hash reflektovat pouze stav, ve kterém byla entita importována, nebo jakoukoli změnu entity nezávisle na původci. V prvním případě editace přebije import, protože import nepozná změnu (ovšem pouze do doby, než sám pošle změnu anebo se povýší verze hashovací funkce). Druhý případ znamená, že vždy vyhrává poslední změna, ale je náročnější na aktualizaci.

Z mnoha dobrých důvodů se vyplatí negenerovat hash přímo ze zdroje (importní xml, db), ale vytvořit nejprve řetězcovou podobu ve StringBuilderu a až z ní vytvořit hash:

• užitečné při debugování, jak který hash vznikl
• umožňuje to v nouzovém případě napsat vnitřní formu ručně a vytvořit hash stranou
• při převodu na řetězec je možné doplnit dodatečné konverze pro sjednocení nežádoucích odlišností (např. pokud se seznamy mají považovat za shodné, když se liší jen pořadím prvků, do hashe je seřadíme; hodnoty BigDecimal sjednotíme na stejné scale apod.)

Algoritmus se týká pouze udržení hash kódu, tj. jak šetrně zahrnout do hash kódu property, která dosud nebyla jeho součástí, ale byla součástí importu. Pokud k importované entitě přibyde nová property (ať už je nebo není součástí hashe), algoritmus vyhodnotí entitu jako nezměněnou (a v případě, že nová property je součástí hashe, také aktualizuje hash na vyšší verzi), ale samotný update nové property musí zajistit metoda unchangedEntity.