체크섬 알고리즘을 사용하여 "빼기"데이터를 지원합니까?

Question

대략 1 억 개의 문서가있는 시스템이 있으며 미러 사이의 수정 사항을 추적하고 싶습니다. 수정에 대한 정보를 효과적으로 교환하기 위해 수정 된 문서에 대한 정보를 각각의 별도 문서가 아닌 며칠까지 보내려고합니다. 이런 식으로 뭔가 : 각 CS이 의 체크섬이다

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

이 특정 날짜에 생성 된 모든 문서의 타임 스탬프.

이제 내가 겪고있는 문제는 문서를 삭제할 때 체크섬에서 데이터를 "빼는"알고리즘을 모른다는 것입니다. 명확한 이유 때문에 암호화 해시는 필요에 맞지 않으며 CRC를 수행 할 수있는 알고리즘을 찾을 수 없습니다.

내가 고려한 한 가지 옵션은 해시에 추가 정보를 추가하는 것이었지만 노드가 다른 순서로 삭제 요청을받을 수 있기 때문에 더 많은 문제가 발생했으며 노드가 다시 시작되면 모든 노드를 다시 읽습니다. 문서의 타임 스탬프 및 삭제에 대한 정보가 손실됩니다.

또한 메모리가 8 기가를 사용하므로 모든 문서 해시가 포함 된 해시 트리를 사용하는 것을 좋아하지 않을 것입니다. 이러한 필요성 때문에 과도한 부담이 될 것 같습니다.

지금까지는 가장 좋은 옵션은 백그라운드에서 이러한 해시를 완전히 재생성하는 것으로 보이지만 이는 불필요한 오버 헤드 일뿐만 아니라 변경 사항에 대한 즉각적인 정보를 제공하지 않습니다.

그래서 체크섬에서 일부 데이터를 "제거"할 수있는 체크섬 알고리즘을 알고 있습니까? 알고리즘은 다소 빠르며 체크섬은 변경 사항이 가장 적음을 강력하게 나타낼 필요가 있습니다 (그래서 일반 XOR을 사용할 수 없습니다).

아니면 전체 디자인에 대해 더 좋은 아이디어가 있습니까?

Answer 1

어떻

X 집계 XOR (자바 스크립트 Y 의사 코드는 이하)이다

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

:

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

이고, f()는 각각의 문서 정보의 해시가? (타임 스탬프, 파일 이름 또는 ID 등)

XOR을 사용하면 문서를 "제외"할 수 있지만 문서 단위로 해시를 사용하면 작은 크기의 검색과 같이 해시 같은 품질을 유지할 수 있습니다 변경.