두 컴퓨터에 거의 같은 목록이 있다고 생각해 보자. 목록 전체를 주고받으면 이미 공유하는 항목까지 다시 전송하게 된다. 각 목록을 작은 표로 요약하고 두 표를 비교해 차이를 복원할 수 있다면, 서로 다른 항목만 알아내는 데 필요한 전송량을 줄일 수 있다.
여기에 쓰이는 자료구조 중 하나가 IBLT(invertible Bloom lookup table)다. 항목의 정보를 요약표의 여러 칸에 나누어 반영한 뒤, 두 표를 비교해 같은 항목의 기여를 상쇄한다. 그러고 나면 남은 정보에서 서로 다른 항목을 찾아낼 수 있다.
다만 이 복원에 필요한 공간은 충분히 확보해야 한다. Self-sizing 연구는 서로 다른 항목 수를 먼저 추정해 다음 비교에 쓸 공간을 정한다. 그 추정식은 요약표를 만들 때 항목을 어느 칸에 배치하는지에 따라 달라진다.
Self-sizing IBLT를 확인하려고 만든 작은 재현 사례에서는 두 목록이 정확히 한 항목만 달랐다. 코드는 그 항목을 찾아내는 데 성공했지만, 서로 다른 항목이 몇 개인지 추정한 값은 약 0.678이었다.
이 숫자가 나온 이유는 칸을 고르는 규칙에 있었다. 추정식은 항목 하나의 정보가 서로 다른 세 칸에 들어간다고 가정했다. 그런데 위치를 고르는 코드인 매퍼는 세 번 뽑은 뒤 중복을 지웠다. 이 입력에서는 처음 고른 위치가 [0, 16, 16]이었고, 중복을 지우자 [0, 16]만 남았다. 위치 하나가 겹치면서 추정식과 매퍼가 사용하는 조건이 달라진 것이다.
이 불일치를 재현한 근거를 전달한 뒤 원 프로젝트가 매퍼를 수정하고, 공개 저장소에 내 기여를 기록했다.
검토한 버전에서는 항목마다 서로 다른 세 칸을 써야 했다. 위치를 세 번 고르는 것만으로는 이 조건을 보장할 수 없다.
한 항목의 계산을 따라가 보면
보존한 사례는 64칸짜리 표와 시드 0을 사용한다. 시드는 위치 계산을 같은 조건으로 반복할 수 있게 하는 입력값이다. 항목을 배치할 때 쓰는 숫자 표현인 지문값(fingerprint)은 0xa4712c74562914다.
중복을 지우면 항목의 정보는 0번과 16번 칸에만 들어가고, 각 칸에는 개수 1이 남는다. 추정식의 분자는 칸별 개수의 제곱합에서 전체 합에 따른 보정항을 빼서 구한다.
2 − 4/64 = 1.9375.
분모는 여전히 서로 다른 세 칸을 쓴다고 가정한다.
3 × (1 − 3/64) = 2.859375.
두 값을 나누면 약 0.677596이다. 처음부터 서로 다른 세 칸에 들어갔다면 이 한 항목 사례의 분자는 분모와 같아지고, 추정값은 1이 된다.
큰 벤치마크 없이도 이 작은 사례에서 조건의 불일치를 확인할 수 있었다. 항목 복원에는 성공했으므로 데이터를 잃은 사례로 설명해서는 안 된다. 구현이 지키지 않은 세 칸 조건을 전제로 한 수학적 정리를 반박한 것도 아니다. 당시 버전은 고정된 매퍼 코드에서 확인할 수 있다.
테스트는 통과했는데 왜 달랐을까
보존한 실행 기록에서는 기존 테스트와 논문의 표 수치를 확인하는 검사가 통과했다. 하지만 추정식을 보정하는 시뮬레이션은 위치가 겹치면 다시 뽑아 서로 다른 세 칸을 채웠고, 실제 목록 비교 경로의 매퍼는 중복을 지우는 데서 멈췄다.
시뮬레이션은 추정식의 조건을 지켰지만, 다른 실행 경로는 같은 규칙을 쓰지 않았다. 두 코드를 나란히 보니 통과한 검사들이 무엇을 확인했는지 이해할 수 있었다. 검사에서는 정해진 배치 규칙 아래의 계산을 확인했지만, 그 규칙이 모든 경로에 적용되지는 않았던 것이다.
원 프로젝트는 이번 수정에서 겹친 위치를 다시 뽑도록 매퍼를 고치고, 매퍼 버전 확인도 추가했다. 두 컴퓨터의 요약표를 호환되게 비교하려면 항목을 배치하는 방식도 같아야 하므로 버전 확인이 필요하다. 수정 코드를 작성하고 공개한 주체는 원 프로젝트이며, 내 기여는 불일치를 찾아 재현 근거를 제공한 것이다.
README의 감사 표시에는 Byungwoong Yoo, Independent Researcher라는 이름과 역할이 남아 있다. 재현 사례와 후속 변경을 연결한 내용은 자세한 작업 기록에 정리했다.