2014-04-03 19 views
5

czy to prawda, że ​​e-mail może być deduplikowane używając tylko niektóre z ich nagłówków jak zgodnie z RFC ich message-id powinno być wyjątkowe?email deduplikacji

Czy istnieje jakiś sposób, aby obliczyć prawdopodobieństwo 1 pojedynczy email beeing pominięte w tej metodzie deduplikacji poniżej (SHA512 hash tych 3 nagłówki)?

// $email is a parsed array containing 3 keys (mime headers) -> message_id, subject and date. $hashStr = $email['message_id']; $hashStr .= $email['subject']; $hashStr .= $email['date']; $uniqueEmailId = hash('sha512', $hashStr);

Jest to rodzaj misji krytycznej że żaden pojedynczy email zostaną pominięte, są szanse, że jesteśmy konieczności deduplikuj na kilka (> 2) mld pliki MIME.

Odpowiedz

4

SHA512 mieszania wytwarza wartość skrótu z 512 bitów danych. Przyjmując losowy rozkład bitów, działa to ponad 1.34e + 154 możliwych wartości. Nawet przy ponad 2e + 9 próbek szanse na przypadkową kolizję są bardzo bliskie zeru.

Jednak Twój wkład do mieszania nie jest całkiem to przypadkowa. message_id to globally unique identifier, który "tylko" ma 5.3e + 36 możliwych wartości, a losowość zależy od implementacji. Zgodnie z linkiem wiki, prawdopodobieństwo kolizji wynosi około 50% na poziomie 4,2e + 18 próbek. Adresy e-mail i daty są prawdopodobnie znacznie wyższe.

Powiedział, że bez faktycznie robi matematyki prawdopodobieństwa, powiedziałbym, że szanse są znikome.

+0

Message-ID nie jest identyfikatorem GUID w tym znaczeniu. Jest globalnie wyjątkowy, ale skonstruowany w sposób specyficzny dla implementacji. Zwykłą techniką jest połączenie heks timestamp_seq # po lewej stronie z nazwą hosta po prawej stronie znaku @. Zobacz RFC 2822 pp22-24 –

2

Jeśli message-id jest już wyjątkowy, nie ma większego sensu mieszaja (a zatem wprowadzenie wprawdzie znikome prawdopodobieństwo kolizji).
Wydaje się, że bardziej zdecydowanym podejściem byłoby wykorzystanie samego identyfikatora komunikatu jako podstawy porównania.

+0

Czy ta kombinacja messageid, tematu i daty nie zmniejszyłaby szansy na kolizję hash? – Floris

+0

@Floris nie, w pierwszej kolejności wprowadzi szansę kolizji. Nie mówię o hashu msgid, ale biorąc to dosłownie, ponieważ już ma być unikalnym identyfikatorem – fstd

+0

Wiem, ale muszę obsłużyć (bardzo duże) ilości danych e-mail (ponad 10k kont z 20k wiadomościami każdy), więc potrzebuję 1 klucza, aby otrzymać unikalną wiadomość. Niestety w moich testach okazało się, że nagłówek Message-ID nie jest naprawdę "wyjątkowy". – Floris