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

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

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

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

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

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

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

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

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

Или, может быть, у вас есть лучшие идеи по всему проекту?

Ответы

Ответ 1

Как насчет

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 позволит вам "вычитать" документы, но использование хэша для каждого документа позволяет сохранить хэш-подобное качество обнаружения небольших изменений.