Newsgroup: it.comp.os.linux.sys
Titolo: hash e collisioni

Ho la necessità di ricavare un intero *positivo* univoco partendo da
una stringa.
un crc32 è soggetto a troppe collisioni (ne ho viste almeno un paio e
non è tollerabile).
 
Un md5 convertito in decimale sarebbe paurosamente lungo:
 
hexdec(md5('ciao mondo')) = 7.2536685476193E+37
 
qualche altra idea? Ho la necessità di codificare delle stringhe in
modo da poterle richiamare per la loro controparte numerica.
 
Ad esempio:
 
"ciao mondo" = 1243423544
"Ciao mondo" = 4565423424
 
Pensavo di concatenare due crc32 per la versione "corta" (un crc32
fatto sulle posizioni pari, un crc32 fatto sulle dispari) e non so
quale algoritmo per la versione a 64bit.
 
Che probabilità ci sono di trovare una collisione calcolando solo i
primi 8 o 16 caratteri di un md5 o sha1?

 stringa.
 
Prova a vedere qui
 
http://www.cse.yorku.ca/~oz/hash.html
 
Ci sono sempre collisioni, ma questi algoritmi presentano una 
distribuzione decente (e un calcolo molto veloce)
 
PSK

 distribuzione decente (e un calcolo molto veloce)
 
Grazie, ci guardo.
 
Comunque dovrei essere riuscito, modificando un po di codice, a
bypassare
la necessità di calcolar l'hash sulla stringa.
Salvo la stringa as-is in un db, associandola ad un id generato usando
lo
unix timestamp in millisecondi, 2 numeri random (da 00 a 99) ed il pid
che
ha eseguito la richiesta. Non possono sussistere doppioni, il
timestamp può
solo aumentare (quindi esclude matematicamente i doppioni), il pid mi
aggiunge sicurezza nel caso arrivassero due richieste nello stesso
millisecondo
ed un numero random di due cifre rende matematicamente impossibile un
doppione.
 
Si verificherebbe una collisione solo con 99 inserimenti nello stesso
millisecondo
gestiti dallo stesso pid. non dico impossibile ma poco ci manca.
 
Dove non posso ricavare il pid (ad esempio in javascript), uso due
numeri random
come prefisso, il timestamp in millisecondi ed altri due numeri random
come suffisso.
1/9999 di possibilità di collisione in caso di richieste nello stesso
millisecondo.
Vien fuori un numerone di 18 cifre.
 
L'unica cosa che non mi convince è l'uso dei numeri random, riducono
drasticamente
le probabilità di collisione (1/9999esimo) ma preferirei avere un
qualche numero più
"affidabile", che so, nanosecondi o cose simili ma con maggiore
entropia.
 
Tutto 'sto casino perchè:
1) ho una struttura dati non modificabile da me e che non permette il
rilevamento delle collisioni
2) devo fare degli inserimenti senza poter prima verifica la presenza
o meno dei dati su db (anche per questioni di performance)

che
 
Se hai un db, perché non usare un contatore archiviato in quello stesso
DB entro una transazione?
 
	BEGIN
	INSERT INTO TABLE SELECT <DATI>, COUNTER FROM COUNTERS
	UPDATE COUNTERS SET COUNTER = COUNTER + 1
	COMMIT
 
Leonardo
 
-- 
Tell us whether you spy, in the light of the morn,
what saluted was fiercely at the fall of the past day:
whose pips and whose bands in the very heart of the fray
bravely floated from the bulwarks to which we were sworn?

 DB entro una transazione?
 
Non è così semplice.
Ho più punti di inserimento, uno dei quali è un javascript.
Lato javascript devo generare un ID univoco e numerico (sarà salvato
in un campo BIGINT(20)) senza possibilità di verifica, sia per le
performance (dimezzo le query), sia per come è strutturato il codice e
l'accesso al db.
 
Quindi, lato javascript genero un codice pseudo casuale come scritto
nel post precedente, il server lo riceve e lo inserisce lato DB. Se
usassi una transazione, una storeprocedure o cose simili, avrei un ID
univoco ma lato javascript non riuscirei ad accedervi. E visto che il
javascript deve eseguire due o tre operazioni in successione, tutte lo
con lo stesso ID, non posso far generare ad "esterni" il codice,
altrimenti mi sarebbe bastato un campo auto increment.
 
Controllando bene il codice, però, in un punto non posso generare ID
casuali ma devo generare un hash numerico, bigint20 partendo da una
stringa ed il CRC32 genera troppe collisioni.
Visto che un campo bigint da 20 cifre tiene perfettamente un numero a
64bit, potrei azzardare un CRC64 unsigned.
 
Non ho altre idee su come generare un hash intero positivo a 64bit (in
modo da avere bassissime collisioni, quasi nulle) partendo da una
stringa.
 

 l'accesso al db.
 
si, ma non puoi lasciar fare tutto al db?
 
ad esempio:
http://archives.postgresql.org/pgsql-sql/2006-09/msg00157.php
 
 
Ciao Jack
-- 
Yoda of Borg am I! Assimilated shall you be! Futile resistance is, hmm?

 
http://archives.postgresql.org/pgsql-sql/2006-09/msg00157.php
 
 
Come ho già scritto, no.
Perchè l'id che sarà salvato su DB mi serve in più punti del programma
PRIMA che l'inserimento avvenga (e quindi prima che il db mi generi un id)
 
Inoltre, io posso solo fare inserimenti, non ho alcun modo di eseguire
delle letture, che oltre ad essere impossibili, raddoppierebbero di
fatto il numero di query.
 
-- 
Tu non puoi passare!
Sono un servitore del fuoco segreto e reggo la fiamma di Anor!
Il fuoco oscuro non ti servirà a nulla, fiamma di Udur!
Ritorna nell'ombra! TU NON PUOI PASSARE!

 altrimenti mi sarebbe bastato un campo auto increment.
 
Questa non mi e' chiara cioe' hai tre insert ad esempio e non riesci a ragrupparle nella stessa transazione ?
 
Perche le tre insert sicuramente sono nella stessa esecuzione del javascript visto che parli di un id univoco per ogni esecuzione(anche perche javascript perde 
lo stato ad ogni esecuzione).
Io farei una unica insert con tutti i dati che devi inviare alla fine della procedura javascript in una tabella temporanea(anche usando un blob se i dati sono 
tabelle aloro volta) con un trigger(stored procedure) che spachetta quello che ha ricevuto e fa tutte le procedure necessarie.
 
Il javascript non leggerebbe niente visto che non sarebbe necessario (insert unica e non multipla).
 
Giulia
 
 
 
 
 
 
 

 ragrupparle nella stessa transazione ?
 
Io ho un javascript che deve generare un ID, in autonomo, senza chiedere
nulla a fonti esterne.
 
Si genera un ID, sapendo già (con una sufficiente dose di sicurezza) che
tale ID sarà univoco. Una volta generato, fa tutto quello che deve fare,
tutti i suoi calcoli, salva i cookie etc etc poi richiama una API
RESTFul che procede alla insert usando l'ID fornito dal javascript
 
Se usassi una transazione o cose simili (o più in generale facessi
generare l'id al database), il javascript non sarebbe al corrente 
dell'id e non riuscirebbe a fare le sue operazioni.


 generare l'id al database), il javascript non sarebbe al corrente dell'id e non riuscirebbe a fare le sue operazioni.
 
 
Ok via la transazione, la insert unica globale alla fine e' possibile ?
 
Tanto non leggendo il db il javascript se ne impipa dello stato del db direi, o vuoi comunque tenere allineato il client tramite i cookies al db ?
e quindi una seconda esecuzione di quel javascript deve essere riconosciuta da db ?
 
 
Giulia
 
 

 riconosciuta da db ?
 
Ma non capisco.
Quale insert globale? io faccio UNA insert in UNA tabella.
 
I dati che inserisco, però, devono essere generati da JS perchè
poi vengono salvati su cookie.
 
Tra le tante cose, l'ID, univoco, viene usato anche per cifrare un
cookie. In sostanza, non posso far generare l'id al DB, altrimenti
non sarei qui a chiedere lumi su un algoritmo di hashing a basse
collisioni.
 
Al momento ho risolto con il timestamp in millisecondi concatenato
a 4 cifre random.
Diciamo che uso più sistemi, a seconda delle possibilità:
 
- timestamp in millisecondi con 4 cifre random concatenate
- versione decimale a 64bit dei primi 16 caratteri di un hash sha1
   [dove mi serve la possibilità di rigenerare lo stesso hash partendo
    dalla stessa stringa]
- timestamp in ms concatenato a 4 cifre random ed il pid del processo
 
In sostanza concateno numeri a caso o pseudo casuali fino ad arrivare
a 19 cifre, che mi danno una quantità di collisioni talmente basse da
essere trascurabile senza il rischio di generare un numero che
richiederebbe almeno 65bit
 
Sembra funzionare.


RESTFul che procede alla insert usando l'ID fornito dal javascript
 
Potresti usare un "fake ID". Il Javascript fa tutto quello che deve fare
usando il fakeid (puoi concatenare IP, timestamp e random...), ed il DB,
in fase di inserimento, genera un ID sicuramente unico, e tratta il fake
ID come quell'ID.
 
La mappatura fakeid -> ID sta nella sessione.
 
In effetti, potresti allocare un sufficiente spazio per fakeID quando la
sessione si apre, e salvarla nel JS; per es. invii
 
	var BaseFake = 10000
 
dopodiché il DB ad altri client assegna 20000, 30000, eccetera. E quando
ha bisogno di un nuovo fakeid, il javascript prende BaseFake++.
 
Finché quella sessione non crea 10000 ID, sei a posto :-)


 Quale insert globale? io faccio UNA insert in UNA tabella.
 
Il problema come sempre(non riferito a te) e' che hai un problema ma chiedi lumi sulla soluzione.
 
Da quello che capisco tu hai un client che non puo' leggere dal db, ma che deve mantenere un suo stato allineato con il db
anche tra piu' esecuzioni (per questo usi i cookies).
 
Chiamiamo sessioni questa serie di esecuzioni con lo stesso identificativo.
 
Qualsiasi soluzione con numeri causali non puo' essere deterministica, quindi o prendi un contatore anche all'esterno del db che da un ticket univoco o comunque 
sbatterai sempre sul problema (anche se a 18 cifre).
Una istanza separata di db con un php che nasconde nella pagina contente il javascript un contatore sicuramente univoco ?
Sprecherai un sacco di numeri quando l'esecuzione non richiede questo id ma computazionalmente e' irrisorio.
 
Per gli script bash che fanno insert un qualcosa di paragonabile ovviamente.
 
Giulia
 
 

 non è tollerabile).
 
Quello che ti suggeriva Leonardo è l'approccio migliore per la tua 
soluzione "complichiamo le cose facili".
 
Se rimani col suo consiglio, genera via Javascript un UUID (sono 
standardizzati). Io ho trovato una libraria che si attacca a JQuery e 
potrebbe fare al caso tuo. Googolando viene fuori subito
Gli UUID sono fatti per questo, senza farsi seghe mentali sulle 
collisioni.
 
La soluzione migliore invece, visto che usi una interfaccia REST, è farti 
restituire dalla API un oggetto JSON che contenga l'ID generato. E' 
prassi normale e buona norma.
 
Ad ogni buon conto, non è il NG giusto, ma manco lontanamente.

 richiederebbe almeno 65bit
 
Non capisco il ragionamento, se crei un numero a 19 cifre -che presumo 
essere decimali- lo rappresenti con un numero a 64 bit, dov'è il 
vantaggio?

 ha bisogno di un nuovo fakeid, il javascript prende BaseFake++.
 
E no, io in JS ho bisogno del ID esatto, non di un base.
DB e JS devono essere sincronizzati.


 ma computazionalmente e' irrisorio.
 
Chi ha detto che non è deterministico?
Io non genero un ID ad ogni sessione, genero un ID ad ogni browser.
Tale ID viene salvato sia su DB, sia su cookie.
 
Alla sessione successiva, sempre dello stesso browser, se è presente il
cookie leggo l'id da li dentro, altrimenti ne genero uno nuovo.


 Ad ogni buon conto, non è il NG giusto, ma manco lontanamente.
 
Ma infatti il problema non è il JS, il problema è calcolare un hash
intero a 64bit, lato server.


 vantaggio?
 
Non decimale. Un intero a 64bit, da 0 a 18446744073709551615.
Il vantaggio è che mi permette di avere
1 possibilità su 18446744073709551615 di collisione, cosa resa
ancora più improbabile visto che gli interi da me generati contengono
il timestamp in millisecondi (che è univoco per definizione, non si
può ripresentare) concatenando un altro filotto di numeri pseudo casuali
per scongiurare eventuali collisioni nel caso di accessi multipli allo
stesso millesimo di secondo.
 
Mi pare che il timestamp in millisecondi sia 13 cifre, io ne genero 18,
il che genera 1 collisione ogni 99999 inserimenti allo stesso millisecondo.
 
Quello che mi chiedo, tornando in-topic, se converto i primi 16
caratteri di un hash sha1 in un intero unsigned, avrò differenze
rispetto ai primi 16 caratteri di un md5 ?
 
Altri algoritmi di hashing che permettono di generare *interi* a 64bit?
 
Il javascript e la sua archiettura non hanno niente a che vedere con la
questione, il mio problema è calcolare l'hash di una stringa, non
generare numeri casuali a basse probabilità di collisione.


 l'ID deve essere un intero, per un massimo di 64bit.
 
E comunque gli UUIDv4 sono numeri random, in forma esadecimale.
Non cambia *nulla* rispetto la mia soluzione se non la loro lunghezza.


 cookie leggo l'id da li dentro, altrimenti ne genero uno nuovo.
Ribadisco, numera le pagine internamente con un contatore preso da dove ti pare (ma sempre lo stesso)
o anche i server web non possono parlare tra loro/accedere alla base dati ?
D'altronde se ti stai a lambiccare il cervello con hash , tempo e numeri casuali significa che non sei cosi'
ignorante della problematica .......
 
Giulia
 
 

 ignorante della problematica .......
 
Semplicemnete il vecchio sistema calcolava il CRC32 di una stringa
piuttosto complessa (basata su useragent ed altre stupidate). Per
questioni interne ho convertito tutti i CRC32 in unsigned positivi
evitando quindi di avere ID negativi. Le collisioni, comunque, erano
troppo alte. Dopo circa 1 mese di utilizzo ho registrato non meno di
20 collisioni e visto che lo stesso algoritmo era usato in più parti
del software, cambiando il CRC32 in favore di numeri pseudo-random,
ho risolto le collisioni da una lato ma generato un problema di
hashing dall'altro in cui necessito di un algoritmo che mi permetta
di validare una stringa partendo dal suo hash.
 
Esempio:
 
ciao mondo = 36920eb5dd1b993cf73086d2afde23b1 in md5
sapendo che 36920eb5dd1b993cf73086d2afde23b1 è già presente su DB
(qui posso controllare), so già che 'ciao mondo' è stato registrato.
 
Io però devo avere degli ID numerici, quindi calcolo l'sha1, lo taglio
a 16 caratteri e converto in intero unsigned che corrisponde ad un
numerone a 64bit.
 
Tra md5 ed sha1, nei primi 16 caratteri, c'è differenza quanto numero
di collisioni possibili? Volendo posso fare un sha-256 o 512 se,
sempre nei primi 16 caratteri, mi diminuisce il fattore collisione.


 cambia *nulla* rispetto la mia soluzione se non la loro lunghezza.
 
No.
Gli UUID sono di diverse tipologie.
Una dipende anche dal tempo.
Una dipende univocamente dalla macchina che l'ha generata.
Una è una via di mezzo ...
 
Etccc...
 
E comunque non si tratta, come ti avevo specificato, di usare quel valore 
diretto.
Lato client usi l'UUID, lato server usi un ID standard che ti mappi 
biunivocamente con l'UUID.
 
Con gli hash interi stai andando a cercarti rogne.
Se deve essere univoco, lascialo generare dal server ed usa quello. REST 
è fatto apposta.

 è fatto apposta.
 
Il problema è che mi tocca cambiare TUTTO il database, perchè le colonne
sono tutte BIGINT(20).
 
Il passaggio da signed ad un unsigned, fatto da me tempo fa, ha
richiesto tipo 6 (sei) ore. Non oso immaginare migrare in varchar(40).


 è fatto apposta.
 
Comunque, il problema c'è solo lato javascript perchè
l'id univo generato dal server non può avere doppioni:
 
(int)round(microtime(true)*1000).getmypid()
 
e sul server la data non è errata.


E no, io in JS ho bisogno del ID esatto, non di un base.
 
La prima volta hai ESATTAMENTE 10000.
 
Mandi al DB 10000. Il DB sa cosa fare, tu anche.
 
Poi ti serve, lato JS, un altro ID. Generi 10001. Lo mandi al DB e
anche in questo caso il DB sa cosa fare (non l'ha mai visto prima,
cosi' inserisce il record nel DB con ID 12345678; da quel momento,
ogni volta che il JS gli dice "10000", il DB capisce "12345678").
 
La mia impressione e' che tu stia trovando un sistema per prendere
la colpa TU di una situazione (lentezza, poca scalabilita') che e'
colpa d'altri e comunque va risolta in altra sede.
 
La mia opinione è che se le prestazioni sono cosi' piu' importanti
dell'integrita' dei dati che non si possa fare una rapida getId(),
allora forse si può risparmiare anche l'unica write. Cosi' dopo va
ancora piu' veloce :-D
 
Considera pure che "raddoppiare il numero di query" e' un punto di
vista COMPLETAMENTE FUORVIANTE.
 
Il tuo tempo di transazione non e' solo il tempo di query.
 
E' come dire che se sei sulla spiaggia, se ordini al cameriere "Un
caffè" te lo porta dopo 10 minuti, ma se ne ordini due te li porta
dopo 20. Non è così: te lo porta dopo 10 minuti e 20 secondi, quel
che gli serve per pressare due cialde invece di una.
 
Un'ipotetica funzione reserveUniqueId() puoi metterla in parallelo
al caricamento di ennemila altre cose. Ci sta benissimo che - alla
fine delle operazioni - il tempo totale sia *lo stesso* perche' il
tempo di recupero dell'UID viene assorbito dai tempi morti.
 
Fai una transazione per leggere e incrementare il counter, e cosi'
hai un counter univoco. Sicuramente, dimostrabilmente, ho-seguito-
tutte-le-best-practices-e-ho-il-culo-coperto-e-blindato univoco.
 
Se la pagina che deve usare l'UID è caricata a parte, e di sicuro,
oggigiorno, Web 2.0, la pagina caricherà duemila oggetti, andra' a
caricarne duemila e uno. Si potrà capire il ritardo...
 
===
 
C'e' un giochino che fanno ai corsi per masochisti, in cui hai una
secchiellata di dischetti di metallo e ti viene chiesto di mettere
due blocchi di legno a distanza. E iniziano col dirti "1 cm". Così
d'istinto metti due dischetti uno sull'altro e sei lesto.
 
Poi ti dicono "2 cm". E cosi' via.
 
Alla fine, "faccio questa piccola patch" ("aggiungo un dischetto")
ti mette in una situazione in cui per quanto tu sia bravo ed abbia
la mano ferma, le torri di dischetti crollano.
 
Il punteggio che ottieni è dato da quanto POCO ci metti a renderti
conto della trappola, e per ribellarti o farlo presente :-)
 
Magari mi sbaglio, ma questa cosa dell'UID-SHA1-random mi puzza di
essere nei dintorni del ventesimo dischetto :-D
 
Leonardo mettenteti in guardia


 essere nei dintorni del ventesimo dischetto :-D
 
Il fatto è che non sono una banca, è un normale contatore di click
in cui arrivano diecimila trilioni di richieste in rapida successione
perchè associato ad un circuito di scambio banner che fa (non scherzo)
milioni di impression giornaliere. Dell'integrità dei dati, in una
scala da 1 a 10 mi importa 4. Non me ne frega niente se ogni X di
inserimenti uno non va a buon fine perchè duplicato.


inserimenti uno non va a buon fine perchè duplicato.
 
Sembrerebbe un lavoro per qualcosa come MongoDB.
 
Leonardo


 essere nei dintorni del ventesimo dischetto :-D
 
La vera domanda non e` capire se questo giochetto sia simile a quel 
giochetto da te descritto, ma come tu faccia a conoscere quel giochetto da 
te descritto :P
 
Un Enrico e le domande pericolose
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
 
iQEcBAEBAgAGBQJPGejFAAoJED3SMOGZLYdYJ5kH/0LZvxcG5hjFcP6ZAKb4Q3zt
PsImZKsDzNJwYV4hOyCI+6/GSQldsnzB4XXDy5O1yJaHHdZwn42tvI6gBKe5IdbZ
oa77+Oc4jZpfi9W+KUwTGoUEpps9f8WEO4NcfDfFPAVA18y57VG6fTpiqG99wVeR
QXOmlEJuanMsv8kFOTbKcJu4v8DjpWaVdRIOeZKqC1N9D7HqFj4lKTT4QZ+h/TlL
ZUJnMMNez5Bl7VCbQE/HswuYL4HRrbaYKRJ+mNRj6qLV4gOpGxoVqtTTd5K1THiD
R9o8E34w7zoWtRMkjs91L/M0B/MdvaDwzf+WrcgD6TKePJDSm8DWprKvPp9uUXY=
=3SZ4
-----END PGP SIGNATURE-----
 

te descritto :P
 
Eh, sono brutti ricordi :-)
 
Leonardo


 non avere nulla a che fare con alcun database!
 
L'UUID si può creare senza aver necessità di verifica.
Adesso mi ha messo la pulce nell'orecchio: se convertissi tutti i
BIGINT(20)
attuali in VARBINARY(16) e salvassi l'UUID in forma esadecimale
binaria (ovvero
senza i trattini) ? Potrei usarli come chiave primaria senza un
decadimento
prestazionale, senza dover fare un campo autoincrement e senza la
necessità di
dover verificarne l'esistenza su db.
 
(qui si che siamo molto OT, ma la competenza di chi frequenza questo
NG difficilmente
si trova in altri)

 dover verificarne l'esistenza su db.
 
Ho risolto. Ho dimenticato un passaggio fondamentale: il JS viene
caricato
dal server ogni volta, quindi, prima che il JS intervenga con le sue
operazioni, deve passare per il mio server.
 
detto ciò, lato server mi genero un ID temporaneo, presumibilmente con
questa
struttura in MICROsecondi (univoca, non riceverò *mai* due richieste
allo stesso
microsecondo, è tecnicamente impossibile e volendo si può aumentare
l'entropia):
 
(gmdate('U')-1327174467).substr(microtime(),2,6)
 
poi verifico: se è presente un cookie con un ID salvato in precedenza,
uso il cookie
perchè significa che tale browser è già stato schedato, in caso
negativo, quindi primo
accesso, setto l'id generato dal server.
Facendo così, non devo fare alcuna validazione ed ho la certezza di
usare un timestamp
corretto, UTC (quindi niente ora legale) e sicuramente univoco.

l'entropia):
 
E a questo punto, scopri che fra IOSS, caching e tutto il resto, se adotti
un contatore univoco su file, ottieni prestazioni identiche e una certezza
MATEMATICA di non avere collisioni :-)


 MATEMATICA di non avere collisioni :-)
 
IOSS?
 
Con l'algoritmo indicato sopra, ho già una certezza matematica di
assenza
doppioni. Il numero può solo aumentare, e salvo 2 inserimenti nello
stesso
microsecondo (che ricordo essere 1 millionesimo di secondo) l'assenza
di
doppioni è garantita. Già avere due inserimenti nello stesso identico
secondo
è difficile, avere un milione lo escludo tassativamente e come detto
più volte,
nel caso ci fosse un doppione... amen. Non è una transazione bancaria,
una
probabilità di collisione su un milione di inserimenti al secondo è
accettabile.
Non riesco a generare un doppione nemmeno facendo questo:
 
while ( true ) { echo (gmdate('U')-1327174467).substr(microtime(),
2,6)."\n" }
 
sul mio computer, figuriamoci su un server che deve anche processare
dati.
 
L'unica cosa che non riesco a cambiare è l'hash sha1 convertito in
intero.
Io ho una stringa, ad esempio "ciao mondo" e devo calcolarne un hash
(in qualunque
modo) e convertire l'esadecimale in intero a 64bit, pertanto prendo i
primi 16
caratteri del mio hash e converto.
 
Ripropongo la domanda alla quale non ho avuto risposta: i primi 16
caratteri di
un hash md5, sono "identici" in termini di collisioni ai primi 16
caratteri di un hash sha1?

caratteri di un hash sha1?
 
Sostanzialmente, sì.


 caratteri di un hash sha1?
 
A parità di bontà dell'algoritmo di hashing, ciò che differenzia due
algoritmi è solo il numero di bit da cui è composto l'output.
Supponendo di avere funzioni ideali, se prendi solo N bit di un ciascun
algoritmo la probabilità di collisione è sempre e solo funzione di N ed
è la stessa per qualsiasi algoritmo.
Non per nulla esistono SHA1, SHA256, SHA512... tutte praticamente
identiche se non per il numero di bit dell'hash
 
-- 
Flavio Visentin
 
Scientists discovered what's wrong with the female brain: on the left
side, there's nothing right, and on the right side, there's nothing left

 Sostanzialmente, sì.
 
"sostanzialmente" a cosa corrisponde? Tanto vale usare un md5 che è
anche più
leggero dal punto di vista computazionale?
Se invece calcolassi un sha256 o 512, prendendo comunque solo i primi
16 caratteri?
 
Purtroppo questo è un limite non facilmente aggirabile senza mettere
mano a 3/4 del
codice ed a tutto il database con dati già esistenti.

 mano a 3/4 del codice ed a tutto il database con dati già esistenti.
 
Ma perché se hai spazio per 128 bit (16 byte) non usi un UUID??? E' un
metodo universalmente riconosciuto per generare valori casuali univoci
nel tempo. Reinventare la ruota è sempre stupido.


 nel tempo. Reinventare la ruota è sempre stupido.
 
Perchè ho letto da più parti che a lungo andare rallentano, soprattuto
se
usati come chiavi primarie (cosa che io devo necessariamente fare)
Anche convertendoli in forma binaria ho visto dei benchmark poco
incoraggianti,
tutto qui.
 
Non si tratta di reinventare la ruota, si tratta di adottare un
sistema con
una estremamente remota possibilità di collisione ed un timestamp con
concatenato
il numero di microsecondi mi sembra sufficientemente sicuro. Se
proprio vogliamo
star comodi, potrei aggiungere un numerino random 0-9, in modo da
avere 1 probabilità
su 9 nel caso di doppio inserimento nello stesso microsecondo.
 
Il problema deriva dalle dimensioni del DB, io ho milioni e milioni di
record in
tabella, andare a fare select+insert ho paura che prima o poi mi
rallenti un bel po,
oltre a costringermi a riscrivere buona parte di codice (non fatta da
me) senza
avere a disposizione tutti i sorgenti.
 
Il mio problema è un altro: come calcolo l'hash di una stringa in
formato int64
senza dover riscrivere tutto il codice? Un CRC64? Altri algoritmi?

 Beh, in tal caso avrò 5 anni per mettere mano al sistema.
 
Boot failure.
 
 
-- 
Paranoia is a disease unto itself. And may I add: the person standing
next to you may not be who they appear to be, so take precaution.
-----------------------------------------------------------------------------
http://bofhskull.wordpress.com/
 

 Boot failure.
 
ROTFL
 
 
-- 
Tu non puoi passare!
Sono un servitore del fuoco segreto e reggo la fiamma di Anor!
Il fuoco oscuro non ti servirą a nulla, fiamma di Udur!


 identiche se non per il numero di bit dell'hash
 
Come immaginavo.
Quindi tagliando a 16caratteri un md5, avrò 1 collisione ogni 2^64
combinazioni, che detto in maniera diversa, significa poter gestire
al massimo 2^64 stringhe differenti.
 
In alcune sezioni può andare (hash fatto su useragent, su citta, su ip,
su host, su sistema operativo),
in altre probabilmente no, come l'hash fatto sulla URI.


 o meno dei dati su db (anche per questioni di performance)
 
se non puoi gestire le collisioni è semplicemente sbagliato l'uso di 
chiavi hash. Poi da quello che scrivi sembra che tu debba inserire nel 
DB qualsiasi cosa ti venga passata sia che esista già sia che non sia 
presente.

 presente.
 
... son due questioni diverse.
La prima: generare un ID numerico intero (max 64bit) ad ogni visita.
(salvo
la presenza di un cookie con l'ID numerico al suo interno
 
La seconda: generare un hash, sempre intero a 64bit, partendo da una
stringa in
modo da poter richiamare la stringa mediante hash.

 modo da poter richiamare la stringa mediante hash.
 
con questa devi lo stesso poter gestire le collisioni. Tempo fa ho 
implementato l'algoritmo LZW e mi sono trovato ad affrontare gli stessi 
problemi: purtroppo con 32/64-bit (nel mio caso 32) le collisioni sono 
tutt'altro che improbabili.

 tutt'altro che improbabili.
 
Lo so, è questo il mio problema.


Quindi perché non fai come ha detto leo?
Un file con scritto il valore e lo incrementi ad ogni lettura. Dato che
le operazioni sono seguenziali non hai alcunissimo rischio di collisioni
se non dopo 2^64 record.


 collisioni se non dopo 2^64 record.
 
Ora la dico grossa grossa: ma un file da cui pescare gli UUID da
passare al javascript?
Garantito al 100% senza collisioni: il controllo viene fatto prima,
in momenti di sottoutilizzo.
E se qualche hash viene estratto ma non usato lo recuperiamo
al controllo successivo.
 
-- 
ValeRyo 
 
 

passare al javascript?
 
E' superfluo. Il trucchetto con il file contatore gestisce senza traumi
sull'ordine del milione di connessioni al secondo.
 
 
http://www.kegel.com/c10k.html
 
 
Con una piccola modifica a questo, si arriva a un risultato simile e si
fa anche a meno del contatore di appoggio su file (quando parte, fa UNA
interrogazione al DB e chiede MAX(id). Poi va di shm/ipc).
 
 
http://httpd.apache.org/docs/1.3/mod/mod_unique_id.html
 


 se non dopo 2^64 record.
 
Perchè ho bisogno di risalire alla stringa partendo dal suo hash.
Fare come suggerito significa, una volta schedata la stringa, dover
fare una query ogni volta che mi serve l'hash.
 
Mi spiego:
 
io devo schedare "ciao mondo".
Se avessi spazio utilizzerei un sha1 al completo ed il problema non
sussisterebbe.
Ma visto che il campo in cui devo salvare l'hash è un BIGINT(20) e
per di più è una chiave primaria, sarebbe un suicidio usare una stringa.
Usare un BINARY salvando la forma binaria dell'hash sarebbe ugualmente
un suicidio prestazionale.
 
il 'vecchio' sistema usava CRC32, ma son soggetti a *troppe* collisioni.
 
Cercavo quindi alternative.
Fare come mi è stato suggerito significherebbe inserire ogni volta la
stringa associata ad un ID (autoincrement, o altro) ma poi per
richiamarla dovrei fare una SELECT sulla stringa per intero, che è ciò
che voglio evitare per 2 motivi:
 
1) mi renderebbe nulla la chiave primaria fatta su ID, visto che io poi
accederei soltanto tramite la stringa al completo
2) sarebbe lento, molto lento, rispetto ad una ricerca su chiave numerica
3) ma sopratutto: in più parti del codice (molte, molte parti) io ricavo
l'id partendo da sha1('ciao mondo'). Fare come mi è stato suggerito
significherebbe mettere quantomeno una select ad ogni richiamo.


 al controllo successivo.
 
Volendo, ma il problema NON E' IL JS!
Li ho già risolto da un pezzo, e volendo posso aggungere un controllo
pre-invocazione (visto che il javascript viene scaricato dal mio server
prima di essere eseguito. Basta inserirlo dentro un file PHP ed ecco che
posso verificare gli ID prima di darli al JS)
 
Il mio problema è l'hash sulle stringhe.


significherebbe mettere quantomeno una select ad ogni richiamo.
 
Sei alle prese con un problema architetturale a monte. Tu avresti dovuto
generare l'ID e poi portartelo in giro (magari al posto della stringa) e
non rigenerartelo ogni volta.
 
A questo punto, giunti alla ventesima monetina, ti conviene davvero fare
l'unhex di una sottostringa dell'MD5.
 
Non starei a disturbare SHA1, se non per motivi cosmetici.


 query ogni volta che mi serve l'hash.
 
E allora non sono gli hash che ti servono.

 
 
stai ancora postando su un thread aperto la settimana scorsa.
 
anche con un alter da 12 ore ci avresti guadagnato...
 
 
-- 
Paolo opg
 
BE AWARE that this post uses a fake reply-to address
to contact me write to:
janickg ( at ) hotmail ( dot ) com
--

 anche con un alter da 12 ore ci avresti guadagnato...
 
Non hai considerato il refactoring del codice, ne la perdita
di tutti i dati presenti durante la conversione tra i campi,
ne il tempo necessario a cambiare tutti i riferimenti in tutte
le tabelle.


 a cambiare tutti i riferimenti in tutte le tabelle.
 
i riferimenti in tutte le tabelle, se usi correttamente l'integrità 
referenziale, non sono mai un problema.
 
Quanto agli altri punti, quando un oggetto (qualunque cosa sia quella su 
cui stai lavorando) dimostra dei *SERI* problemi architetturali è bene 
affrontare il problema di petto e risolverlo correttamente, non metterci 
l'ennesima pezza.
 
Io ormai la penso così e fortunatamente è ciò che mi consente di andare 
avanti. Sempre più gente si converte dall'agricoltura all'IT. Nessuno 
vuole più lavorare la terra. Tant'è vero che dalla cina importiamo sia i 
pomodori che i router e gli iphone.
 

 l'ennesima pezza.
 
Non lo metto in dubbio, ma il codice NON L'HO FATTO IO e sopratutto ci
sono dati già presenti al suo interno. Molti, molti dati.
(e come ho scritto, non ho i sorgenti di tutto il codice, alcune parti
sono cifrate).
 
Se ti si rompe la macchina, hai due soluzioni:
1) lasciarla 6 mesi dal meccanico in attesa del pezzo di ricambio definitivo
2) rimetterla in funzione con una pezza mentre il meccanico ordina
il pezzo definitivo, ma almeno in questi 6 mesi usi la macchina.
 
Io sono nella seconda situazione. Mi è stato chiesto di mettere una
pezza, perchè se avessi dovuto riprogrettare tutto (come prima o poi
dovrò fare) non avrei nemmeno avuto il problema dei dati al suo interno,
ne il problema delle interminabili ore nell'inserire l'unsigned in
alcuni campi dover aver preventivamente convertito i valori negativi
in positivi.


 positivi.
 
Si ma se la pezza che il meccanico ti mette equivale a trasformare la 
macchina in un trattore, potrebbe essere che pur funzionando non ti serve 
più.
 
Stai andando ad infognarti con hash, binari, bit, troncamenti, catziematzi 
che nemmeno conosci e che, a mio personalissimo avviso, se solo ti 
generano una collisione ti producono un danno mostruoso. 
 
Non è molto saggio: capisco il tuo problema ma l'accanimento terapeutico 
su un oggetto tecnologicamente defunto andrebbe vietato per legge.
 
 
 
 
 

 traumi sull'ordine del milione di connessioni al secondo.
 
Lo so, ma a Gandalf non piace...
 
-- 
ValeRyo 
 
 

 su un oggetto tecnologicamente defunto andrebbe vietato per legge.
 
Non è che mi sto andando ad infognare. Il software era già nelle fogne.
Io ho già hash, id e cose simili, erano già li.
Ho già dei CRC32 usati praticamente ovunque (e già sta cosa mi
fa innervosire), vorrei sostituirli, senza stare a diventare cretino,
con qualcosa che generi meno collisioni, tant'è che inizialmente pensavo
ad un CRC64 o addiritture una concatenazione di due CRC32 (uno fatto sui
caratteri pari, uno sui caratteri dispari)
 
In sostanza, qualcosa di plug&play, senza dover travolgere giga e giga
di database e metter mano a tutto il codice senza sapere dove si andrà
a finire, visto che parti di codice sono codificate. rischio di
stravolgere tutto poi sul più bello, la query di select che devo
aggiungere magari è proprio nel file cifrato.


 (e già sta cosa mi fa innervosire)
 
Io mi chiedo chi è il genio che ha usato i CRC32 (che non sono hash) per 
questi lavori.
 
Il CRC viene usato per controllare la coerenza dei dati (soprattutto nei 
sistemi di comunicazione dopo le trasmissioni) ma arrivare ad usarli come 
hash (che non sono nemmeno loro lo strumento giusto) bisogna essere 
proprio una mente malata...
 
Se sei messo così male con i CRC allora applica una soluzione qualsiasi.
Le collisioni dovresti già averle, se hai tanti dati.

 lo strumento giusto) bisogna essere proprio una mente malata...
 
Altra puttanata: nel contesto presentato dal nostro stregone preferito
le funzioni hash sono lo strumento ideale da usare. Solo che esistono  
miriadi di funzioni hash e centinaia di classi di funzioni hash; nel 
contesto in discussione gli hash crittografici o i controlli di ridondanza 
sono solamente delle funzioni hash poco adatte e bisogna guardare ad 
altre classi di hash come le funzioni di hash perfetto.
 
E simo caduti dalla padella nella brace. Una funzione hash perfetto possono
essere laboriose da trovare per cuil'unico consiglio sensato già è stato 
dato: hai un database? Usalo.
 
in alternativa lascia perdere i CRC ED USA UN BANALE CHECKSUM A 64 BIT
che almeno non è oneroso da calcolare.
 
 
 

 che almeno non è oneroso da calcolare.
 
I CRC sono dei checksum a tutti gli effetti e non due cose distinte come 
vorresti far credere (*) (è una puttanata, no ?)
 
Quello che differenzia i checksum dagli hash è che i primi servono per 
controllare la correttezza dei dati (a scapito delle collisioni) ed i 
secondi servono per quanto possibile a validare univocamente un certo 
dato (evitando collisioni per quanto possibile).
 
Siccome l'OP ha bisogno dell'univocità e non della verifica della 
correttezza, non deve usare i checksum a 64bit come consigli tu.
Semplicemente perchè gli algoritmi di checksum non sono fatti per quello 
scopo.
 
Quindi, ricapitolando, se io affermo che usare un CRC come algoritmo di 
hash è folle, se tu mi dici che io sparo una puttanata e poi giungi alle 
stesse conclusioni (usare un ID univoco) che avevo espresso inizialmente 
e consigliando come alternativa una cosa sbagliata (CRC64), allora sono 
due i casi: o non hai letto o sei colui che ha progettato e realizzato 
l'accrocchio.
 
(*) 
http://it.wikipedia.org/wiki/Cyclic_redundancy_check
 
 

 Le collisioni dovresti già averle, se hai tanti dati.
 
Si, hai centrato il problema.
Ho delle collisioni, ed i dati cominciano ad essere sfalsati.
Per assurdo, tramite l'admin del software, cliccando su un link
per aprire una determinata pagina, vengo indirizzato su quella
errata, proprio perchè c'è una collisione di ID.

 che almeno non è oneroso da calcolare.
 
Del tipo?
Almeno a 64 bit riduco drasticamente le probabilità di collisione e
rimetto
in piedi la baracca.

Addì  martedì 24 gennaio 2012 22:13 Gandalf Mithrandir scrisse:

La checksum più fessa è:
 
x(1)+x(2)+x(3)+...+x(n)
 
Una un po' più veloce è:
 
x(1) xor x(2) xor x(3) xor ... xor x(n)
 
Una più generale è:
 
ck(0)=0
 
ck(i+1) = a(i) x(i) + ck(i) mod n
 
 
Vedi tu quale usare; le funzioni di hash sono moltissime,
una ricerca su i sacri testi o su google ti permetterà di
trovarne intere categorie ma l'unica cosa che conta è: 
tu devi scegliere tra le tante possibili quale va bene nel 
tuo caso.
 
 

 progettato e realizzato l'accrocchio.
 
Lo confesso, quel programma è stato fatto da me e di notte mi immetto 
neri server altrui ed inserisco controlli sul CRC dovunque.
 
 
 

 tuo caso.
 
Questo è proprio il motivo per il quale ho scritto nel gruppo.
non trovo nessun algoritmo utile, generano tutti numeri esadecimali
ben più grossi di 64bit, quindi non convertibili in intero se non
troncandoli.


 di Adler
 
 
Se vai a leggerti la letteratura, come dici tu, i checksum sono proprio 
delle somme e servono per verificare l'INTEGRITA' dei dati.
 
Sempre in letteratura, Adler-32, Flercher e lo stesso CRC sono algoritmi 
di checksum più evoluti perchè non si basano solo sulle somme ma hanno 
anche una componente "posizionale" che rafforza l'algoritmo.
 
Quindi non solo stai consigliando uno strumento (il checksum) che è più 
debole di un CRC (che è una evoluzione migliorativa e più robusta del 
checksum).
Ma torniamo al discorso iniziale perchè questi "oggetti" non sono lo 
strumento giusto che serve all'OP.
 
 
Possiamo discutere quanto vuoi sull'utilità di questi algoritmi ma mi 
pare proprio che oltre ad essere andato OT, stai pure cercando di 
confondere le idee con la teoria che padroneggi sicuramente molto più di 
me in quanto tale e non perchè la hai applicata.
 
Preparo le valigie: destinazione Zanzibar al caldo.
 

 di 64bit, quindi non convertibili in intero se non troncandoli.
 
perchè se devi minimizzare le collisioni hai bisogno di più bit.
 
E' per questo che esistono gli hash "crittografici" che possono essere 
lunghi 128, 256, 512, 1024, XYZ bits e più lunghi sono meglio è.
 
E troncarli non è la scelta giusta.

 Preparo le valigie: destinazione Zanzibar al caldo.
 
Ci sono stato, mi ha fatto schifo e non tornerò mai più.
No, non mi fai invidia. Preferisco fare le ferie a casa.


 E troncarli non è la scelta giusta.
 
Lo so, ma devo trovare mettere una fottuta pezza.


 troncandoli.
 
Premessa: non ho risposo prima poiché sono convinto che la strada
maestra sia sfruttare un ID unico, per cui ho taciuto non potendo  
contribuire in modo costruttivo.
 
 
Strano, con google ho trovato molto materiale sulle funzioni hash
 
http://www.google.it/search?q=hash+function
 
 
A cominciare dalle pagine della wikipedia:
 
http://en.wikipedia.org/wiki/Hash_function
 
http://en.wikipedia.org/wiki/Hash_table
 
 
continuando su pagine più specialistiche:
 
http://www.partow.net/programming/hashfunctions
 
http://www.concentric.net/~ttwang/tech/inthash.htm
 
http://www.cse.yorku.ca/~oz/hash.html
 
 
fino ad arrivare a un vero e proprio generatore di hash pefetti:
 
http://www.gnu.org/software/gperf/
 
 
 

 invidia. Preferisco fare le ferie a casa.
 
A me ne hanno parlato tutti bene.
Mi interessa il tuo parere. Cosa non ti è piaciuto ?

 Mi interessa il tuo parere. Cosa non ti è piaciuto ?
 
Tutto.
Premessa: non fraintendermi.
 
Io prima di andare li son stato a Sharm, Maldive, Seychelles.
Mi restano ben pochi posti da vedere (di quelli con effetto WOW),
tolto il pacifico, quindi forse ho un metro di paragone un tantino alto.
 
Non ho sopportato il fatto che come arrivi in aeroporto una mandria di
persone ti assale chiedendo soldi, ti minacciano (con la polizia accanto
e pienamente concorde) di farti svuotare l'intera valigia in cerca di
non si sa cosa a meno che tu non gli dia una mancia. Ed in effetti, a
molti sfortunati dietro di noi è stata svuotata letteralmente tutta la
valigia con tanto di perquisizione da parte della corrotta polizia.
 
Attraversi un paese che non è povero, di più. Il tragitto da aeroporto
al villaggio è come passare nelle peggiori favelas brasiliane. Ogni
volta che incroci lo sguardo di uno ti chiede una mancia.
Respiri aria? Lascia pure la mancia.
 
Non ho sopportato la spettacolarizzazione dei masai. Hanno un loro
perchè, una loro storia, che rispetto, ma nei villaggi vengono
ridicolizzati come se fossero dei fenomeni da baraccone il giorno
di carnevale.
 
I barconi portano la gente in visita FIN SOPRA LA BARRIERA, a camminare,
sia che tu abbia scarpe che doposci, sopra i coralli, te li fan
prendere, anzi, li staccano loro per dirti: "Guarda che bello"
 
Ora, capisco che essendo poveri ed alla canna del gas tutto fa brodo,
ma a tutto c'è un limite ed ho promesso a me stesso di non andare più
in paesi il cui stipendio minimo delle persone sia inferiore a 100 euro.


 Premessa: non fraintendermi.
 
Concordo con quasi tutto quello che scrivi.
Al mio ritorno ti racconto.
 
Nel frattempo, grazie!
 

 Nel frattempo, grazie!
 
Di niente, figurati.
Quanto stai? Dove? (in privato)
Io ODIO i villaggi con animazione, perchè non possono
stracciarmi le palle ogni volta, ad ogni ora, per chiedermi
se voglio fare il giocagiue. NO, NON LO VOGLIO FARE, VOGLIO
FARE SOLO UNA COSA: IL NIENTE.
 
Mai più in un BravoClub.
 
Fammi sapere se anche te tornerai con la convinzione di
non andare più in nessun posto i cui stipedi siano inferiori
a 100 euro mensili.


 l'ennesima pezza.
 
Comunque, a naso ed OT per OT, potrei risolvere in maniera rapida 
facendo così:
 
1) aggiungo colonna "hash" in tutte le tabelle e la metto come indice 
univoco
2) nel controller che mi gestisce le query, faccio un bel check:
  a) se il campo inserito in WHERE si chiama "id" e
  b) il valore passato non e' un intero e
  c) ha lunghezza pari a 40 caratteri
 
considero la colonna "hash" anzichè la colonna "id"
 
in questo modo, dovrei riuscire a modificare 2 o massimo 3 righe di codice.
 
Parallelamente converto il campo "id" in autoincrement così facendo
i dati saranno ricercabili sia tramite hash, sia tramite id, senza
dover fare un refactoring totale del codice.


 fare un refactoring totale del codice.
 
Non posso darti alcun consiglio sensato in questo caso perchè non conosco 
la struttura del DB.
 
Però io valuterei di utilizzare l'autoincrementante solo nella tabella 
"principale" ed usare l'integrità referenziale per far riferimento allo 
stesso valore nelle altre. Ovviamente se è possibile.
 
L'hash univoco come valore di entrata in una colonna aggiunta, se non mi 
ricordo male, è uno dei consigli che ti aveva dato Leonardo e, come 
soluzione temporanea, probabilmente può funzionare.
 
 

 soluzione temporanea, probabilmente può funzionare.
 
In questo caso la soluzione sarebbe definitiva.
I campi saranno autoincrement, quindi no doppioni, l'hash serve a me per
poter richiamare a livello di codice un dato record senza conoscerne
l'id e per evitare, ovviamente, una ricerca brutale in formato testo.
 
In sostanza
 
SELECT id FROM useragent WHERE hash = UNHEX(SHA1('culo'))
 
(a dire il vero io cerco già il binario, l'unhex e l'sha1 lo
faccio a livello di codice e non di DB)
 
Questa soluzione dovrebbe essere affidabile e con la totale assenza
di duplicati.


  c) ha lunghezza pari a 40 caratteri
 
Niente, ho detto una stupidaggine, non si può fare.
Sto mondezzone prima salva la tabella di relazione (visto che
sa già a priori quali saranno gli ID delle tabelle relazionate,
dato che usa un hash e non un autoincrement), poi inserisce i
dati nelle singole tabelle relazionate.
 
Questo significa che io riesco ad alterare a piacere le tabelle
relazionate, ma non riesco a variare la tabella di relazione perchè
quando faccio l'inserimento li, non ho ancora l'autoincrement.
