Re: Index ueber Dateipool erzeugen

[Raphael Eiselstein <rabe@xxxxxxxxx>]

On Mon, Nov 18, 2013 at 02:39:34PM +0100, Juergen Roethig wrote:
> dann muss er, wenn er als Datenbank einen Primaerschluessel erzeugt,
> auch fuer dessen Eindeutigkeit sorgen! Wenn er dafuer eine (wie auch
> immer geartete) Hash-Funktion verwendet, dann ist das Ergebnis nicht
> eindeutig, also ist der sogenannte Primaerschluessel kein
> Primaerschluessel! Ich verkaufe einen Rolls-Royce Silver Shadow

Das Ergebnis einer konkreten Hashfunktion ist fuer einen bestimmten 
Eingabewert immer eindeutig. In dieser Richtung sollte es keine 
Abweichung zwischen Theorie und Praxis geben.

Bleiben wir mal bei der Praxis: In der Praxis wird zB sha256 (oder 
vergleichbare Hashfunktionen) zum Beispiel zur Deduplikation von 
Datenbloecken auf Storage verwendet: Die Speicherung eines Datenblocks 
erfolgt nur dann, wenn nicht bereits ein Datenblock mit identischer 
Checksumme existiert, falls doch, wird  nur eine Referenz auf den 
bereits geschriebenen Datenblock gepeichert, da man annimmt, dass 
ein bereits gespeicherter Datenblock mit einer identischen Checksumme 
auch inhaltlich identisch ist.

Deduplikation ist allerdings relativ teuer, weshalb man zum Speichern zur
Vermeidung von Performanceproblemen zunaechst einen schnelleren 
Algorithmus anwendet und mit einer optionalen Verifikation beim *Auffinden* 
dann nochmal mit einem teureren Algorithmus verifiziert, ob wirklich 
eine Kollision vorliegt.

Die Empfehlung[1] fuer ZFS-dedup ist, den default sha256 zu verwenden
anstelle von zB "fletcher4,verify".

| However, if you are willing to make the investment to 
| experiment with different checksum/verify options on 
| your data, the payoff may be substantial. Otherwise, 
| just stick with the default provided by setting dedup=on; 
| it's cryptograhically strong and it's still pretty fast. 

In der *Praxis* wird also eine Checksumme eines (oftmal sehr viel
groesseren) Datenblocks als eineindeutig angenommen, auch wenn die Theorie 
freilich ein kalkulierbares Restrisiko einer Kollision kennt und man 
dieses Restrisiko mit Hilfe von Mathematik sicher auch formal korrekt 
ausdruecken kann. 

Ob man das nun Primaerschluessel nennen darf oder nicht werden wir hier
sicher nicht abschliessend klaeren koennen oder wenn dann mal offline, zB
UUGRN Stammtisch. 

Ich *definiere* (gemeint damit ist das 2. "D" aus "DDL") fuer mein Projekt, 
dass die sha256-Checksumme des Inhalts einer Datei ein geeigneter 
"Primaerschluessel" ist. 

Aber.

Wenn ich mein Restwissen ueber Datenbanken noch dazunehme, dann *muesste*  
ich mit ETL-Methoden zunaechst eine Dimension ueber die bereits bekannten 
sha256-Summen ("natural key") bilden und den Primaerschluessel dieser 
Dimension als Surrogatschluessel fuer alle weiteren relationalen Beziehungen 
verwenden, da die Nutzung eines sehr grossen Datenfeldes (zB char64 oder 
int(256)) fuer die Nutzung als Primaerschluessel normalerweise ungeeignet ist.

Da ich hier mit einem *endlichen* Pool (unterschiedlicher) Checksummen 
rechne, duerfte die Groesse dieses Surrogatschluessels mit 32Bit mehr als 
ausreichend dimensioniert sein. Die Dimension koennte theoretisch 2^256
verschiedene Werte enthalten, der aus Performancegruenden auf 32Bit 
reduzierte Datentyp fuer den intern genutzten Primaerschluessel sollte auch
hier kein Problem drstellen.

Der *Einfachheit* halber bleibe ich allerdings *dennoch* dabei, direkt ueber
sha256-Wert zu joinen (d.h. char(64) =hexadezimale Darstellung
eines 256Bit Wertes als String). Da ich diesen Wert im DDL bereits als
Primaerschluessel definiert habe, muss ich auch nicht befuerchten, dass bei
einer relationalen Abfrage eine Checksumme versehentlich mehrfach vorkommt. 

Falls doch, werden keine schlimmeren Dinge passieren als dass mein 
Script (als Abnehmer der Datenbank) sich nicht wie vorgesehen verhaelt.
Es ist reale Software auf realer Hardware und somit ohnehin fehlerbehaftet.

EoD.

Gruss
Raphael
PS: https://blogs.oracle.com/bonwick/entry/zfs_dedup
-- 
Raphael Eiselstein <rabe@xxxxxxxxx>               http://rabe.uugrn.org/
xmpp:freibyter@xxxxxx  | https://www.xing.com/profile/Raphael_Eiselstein   
PGP (alt):            E7B2 1D66 3AF2 EDC7 9828  6D7A 9CDA 3E7B 10CA 9F2D
PGP (neu):            4E63 5307 6F6A 036D 518D  3C4F 75EE EA14 F625 DB4E
.........|.........|.........|.........|.........|.........|.........|..




-- 
UUGRN e.V. http://www.uugrn.org/
http://mailman.uugrn.org/mailman/listinfo/uugrn
Wiki: https://wiki.uugrn.org/UUGRN:Mailingliste
Archiv: http://lists.uugrn.org/