Существует ли алгоритм контрольной суммы, который также поддерживает «вычитание» данных из него? - PullRequest
Новая
       34

Существует ли алгоритм контрольной суммы, который также поддерживает «вычитание» данных из него?

10 голосов
/ 26 марта 2012

У меня есть система с примерно 100 миллионами документов, и я хотел бы отслеживать их изменения между зеркалами. Чтобы эффективно обмениваться информацией об изменениях, я хочу отправлять информацию об измененных документах по дням, а не по каждому отдельному документу. Примерно так: 

[ 2012/03/26, cs26],
[ 2012/03/25, cs25],
[ 2012/03/24, cs24],
...

, где каждый cs является контрольной суммой отметок времени всех документов, созданных в определенный день.

Теперь проблема, с которой я сталкиваюсь, заключается в том, что я не знаю алгоритма, который мог бы «вычесть» данные из контрольной суммы при удалении документа. По понятным причинам ни один из криптографических хэшей не отвечает этим требованиям, и я не смог найти никаких алгоритмов для CRC, которые бы это делали.

Одним из вариантов, который я рассмотрел, было удаление, добавление дополнительной информации к хешу, но это привело бы к еще большим проблемам, так как узлы могут получать запросы на удаление в другом порядке, и когда узел перезапускается, он перечитывает все метки времени из документов, и, таким образом, информация об удалениях будет потеряна.

Мне также не хотелось бы использовать дерево хешей со всеми хешами документов в памяти, поскольку для этого потребовалось бы примерно 8 гигабайт памяти, и я думаю, что это немного излишне только для этой необходимости.

На данный момент лучший вариант, кажется, время от времени полностью регенерирует эти хэши в фоновом режиме, но это также много ненужных накладных расходов и не даст немедленной информации об изменениях.

Итак, вы, ребята, знаете об алгоритме контрольной суммы, который позволил бы мне "удалить" некоторые данные из контрольной суммы? Мне нужно, чтобы алгоритм был несколько быстрым и контрольная сумма, которая бы четко указывала наименьшие изменения (вот почему я не могу использовать обычный XOR).

Или, может быть, у вас есть лучшие идеи по поводу всего дизайна?

1 Ответ

5 голосов
/ 26 марта 2012

Как насчет 

hash = X(documents, 0, function(document) { ... })

где X - совокупный XOR (псевдокод javascript-y следует): 

function X(documents, x, f)
{
   for each (var document in documents)
   {
      x ^= f(document);
   }
   return x;
}

и f () - это хеш информации отдельного документа? (отметка времени, имя файла, идентификатор или что-то еще)

Использование XOR позволит вам «вычитать» документы, но использование хеш-функции для каждого документа позволяет вам сохранить хеш-подобное качество обнаружения небольших изменений.

...