Folly Code Review · 74/89

folly Fingerprint64·128 — 분산 hash

2026년 6월 8일 · Hawk · 4분 읽기

한 줄 요약: Fingerprint64/128은 polynomial Rabin-Karp 기반 fixed-size hash다. std::hash가 in-process container용이라면 fingerprint는 서로 다른 프로세스/머신에서 같은 입력에 같은 결과를 보장해 sharding과 dedup의 키가 된다.

#동기

std::hash는 다음을 보장하지 않는다.

같은 입력에 같은 출력 (다른 컴파일러 / 다른 실행 사이).
분포가 좋다는 것.
충돌 attack 저항.

이것들이 in-process hash container에서는 큰 문제가 아니다. 같은 process가 끝나면 hash 결과는 무관. 그러나 다음 경우는 결정적이다.

sharding — hash(key) % N으로 어느 서버로 보낼지 결정. 모든 client가 같은 hash 함수를 써야.
content addressing — Git blob, IPFS CID. 같은 내용이면 같은 hash.
dedup — log dedup, dataset dedup. 다른 머신에서 같은 hash.

이 자리에 std::hash는 부적합. Fingerprint64/128이 답이다.

1
#include <folly/Fingerprint.h>
2

3
folly::Fingerprint64 fp;
4
fp.update(data, len);
5
uint64_t h = fp.value();
6

7
// 또는 one-shot
8
uint64_t h2 = folly::Fingerprint64{}.update(data, len).value();

#알고리즘 — Rabin-Karp polynomial hash

1
입력: byte stream b[0], b[1], ..., b[n-1]
2
다항식: H(x) = b[0]*x^(n-1) + b[1]*x^(n-2) + ... + b[n-1]
3
       mod P(x)
4

5
P(x) = 64-bit irreducible polynomial over GF(2)
6
       (Folly가 고른 specific polynomial)
7

8
연산: GF(2) 다항식 산술 (XOR + shift)

핵심 특성:

분포 균등 — 좋은 polynomial에서 거의 균등.
incremental computable — update(chunk) 반복 가능.
다른 머신에서 같은 결과 — polynomial이 hardcoded.

1
// folly/Fingerprint.h 약식
2
class Fingerprint64 {
3
 public:
4
  Fingerprint64& update(const uint8_t* data, size_t len) noexcept {
5
    for (size_t i = 0; i < len; ++i) {
6
      // GF(2)^64 다항식 mul + xor
7
      val_ = mulPoly(val_) ^ data[i];
8
    }
9
    return *this;
10
  }
11
  uint64_t value() const noexcept { return val_; }
12

13
 private:
14
  uint64_t val_ = 0;
15

16
  static uint64_t mulPoly(uint64_t x) noexcept {
17
    // hardcoded irreducible polynomial과 GF(2) multiply
18
    // 보통 lookup table로 가속
19
    return /* ... */;
20
  }
21
};

실제 구현은 8-byte chunk 단위 처리 + lookup table로 SWAR 가속. 그래도 SpookyHash나 xxhash보다 느리다. 결정적이고 sharding-safe하다는 게 가치.

#Fingerprint128 — 128-bit variant

1
folly::Fingerprint128 fp;
2
fp.update(data, len);
3
auto [hi, lo] = fp.value();
4
// hi, lo: uint64_t 두 개

64-bit가 충분치 않을 때 (예: 수억 객체 dedup, birthday paradox로 충돌 우려) 128-bit 사용. 두 개의 독립된 polynomial 결과를 (hi, lo)에 담는다.

birthday bound 계산:

1
64-bit : ~2^32 객체에서 50% 충돌 확률
2
128-bit: ~2^64 객체에서 50% 충돌 확률

수억 객체면 64-bit도 안전하지만 완전 안전이 필요하면 128.

#API 패턴

1
// streaming
2
folly::Fingerprint64 fp;
3
fp.update(part1, len1);
4
fp.update(part2, len2);
5
auto h = fp.value();
6

7
// one-shot from StringPiece
8
auto h2 = folly::Fingerprint64{}
9
  .update(reinterpret_cast<const uint8_t*>(s.data()), s.size())
10
  .value();
11

12
// content-defined chunking 같은 곳에서 sliding window도 가능
13
// (별도 RollingFingerprint 클래스 — Folly에는 없고 직접 구현)

#std::hash 비교

1
struct Key { std::string s; };
2

3
// in-process container
4
std::unordered_map<Key, V, std::hash<Key>> m;   // OK
5

6
// sharding
7
size_t shard = std::hash<Key>{}(k) % N;          // BAD — 다른 process에서 다른 결과 가능
8
size_t shard = folly::Fingerprint64{}.update(
9
  reinterpret_cast<const uint8_t*>(k.s.data()), k.s.size()).value() % N;   // OK

항목	std::hash	folly::Fingerprint64	xxhash / WyHash	SpookyHash
결정성	보장 안 함	보장	보장 (seed 고정)	보장
분포	구현체 의존	좋음	매우 좋음	매우 좋음
속도	빠름	보통	매우 빠름 (SIMD)	매우 빠름
64/128	64	64/128	64/128	64/128
사용처	in-process	sharding/dedup	general fast	general fast
표준	C++	folly	외부	외부

xxhash나 WyHash가 더 빠르지만 folly 내부에서 sharding 키로는 Fingerprint가 역사적 표준. 새 코드라면 SpookyHashV2(다음 절) 또는 외부 xxhash도 검토.

#absl::Hash와의 비교

absl::Hash<T>는 in-process hash다. 같은 binary 안에서는 결정적이지만 binary 사이엔 다를 수 있다. std::hash의 더 일관된 버전.

1
absl::Hash<Key> h;
2
size_t v = h(k);

sharding에는 부적합 — fingerprint류가 옳다.

#코드 리뷰 포인트

sharding 코드에 std::hash — 즉시 Fingerprint64로 교체.
fingerprint를 unordered_map 키로 — 의도가 고정 키가 아니면 over-engineering. std::hash가 빠르다.
64-bit fingerprint로 수십억 객체 dedup — 128-bit 검토.
같은 데이터에 다른 alignment로 update — fingerprint는 byte stream 단위라 영향 없지만 byte order는 영향 있음. portable한 byte 순서로 input 만들어야.

#자주 보는 안티패턴

1
// 1. struct를 raw bytes로 fingerprint
2
struct K { int a; int b; };
3
K k{1, 2};
4
fp.update(reinterpret_cast<const uint8_t*>(&k), sizeof(K));
5
// → padding/endianness/struct layout 의존 — 다른 머신에서 다른 결과
6

7
// 2. fingerprint를 cryptographic hash로 오해
8
// → 의도적 충돌 만들 수 있음. Adversarial 입력엔 BLAKE3 / SHA-2.
9

10
// 3. fingerprint을 32-bit으로 잘라 sharding
11
size_t shard = (fp.value() & 0xFFFFFFFF) % N;
12
// → lower bit의 분포가 떨어질 수 있음. fp 전체로 modulo.

#실전 — log dedup

1
folly::F14FastSet<uint64_t> seenFingerprints;
2

3
void IngestLog(folly::StringPiece line) {
4
  auto fp = folly::Fingerprint64{}
5
    .update(reinterpret_cast<const uint8_t*>(line.data()), line.size())
6
    .value();
7
  if (!seenFingerprints.insert(fp).second) {
8
    return;   // 중복 — drop
9
  }
10
  Persist(line);
11
}