Folly Code Review · 37/89

folly::AtomicHashMap — lock-free read 분석

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

cpp folly container atomic-hashmap lock-free

#한 줄 요약

folly::AtomicHashMap은 append-only + lock-free read의 hash map이다. erase 불가, value 수정도 제한적. 대신 read는 mutex 없이 atomic load만으로 끝나 contention이 0.

#동기

설정 cache, dictionary lookup, monitoring counter 같이 기록은 가끔, 읽기는 매우 자주인 데이터는 일반 mutex 기반 map이 과한 비용. 16 reader 가 동시에 read 한다면 mutex가 줄을 세우게 된다.

1
typical use case
2
  - feature flags     : startup 시 fill, 그 후 read-only
3
  - id → name table   : 새 id 가끔 추가
4
  - per-thread counter : append, increment, 읽기 위주

AtomicHashMap의 제약:

erase 불가.
key의 in-place 갱신은 atomic value type만.
최대 capacity를 처음에 지정.

대신 얻는 것:

read는 wait-free.
writer 한 명이 들어와도 reader 영향 0.

1
folly::AtomicHashMap<int64_t, std::string> ahm(100'000);  // capacity
2
ahm.insert(1, "alice");
3
// reader thread들
4
auto it = ahm.find(1);
5
if (it != ahm.end()) Use(it->second);

#API & 사용법

1
#include <folly/AtomicHashMap.h>
2

3
// 1. 생성 — 최대 capacity 미리 지정
4
folly::AtomicHashMap<int64_t, std::string> m(1'000'000);
5

6
// 2. insert — concurrent, lock-free
7
auto [it, ok] = m.insert(42, "answer");
8

9
// 3. find — wait-free
10
auto it = m.find(42);
11
if (it != m.end()) {
12
  std::cout << it->second;
13
}
14

15
// 4. operator[] — insert default if absent
16
m[7];   // ""가 들어감
17

18
// 5. erase 없음
19
// m.erase(42);   // 컴파일 에러
20

21
// 6. 통계
22
m.size();
23
m.maxSize();          // 처음 지정한 capacity

AtomicHashMap은 sub-map들의 chain 구조. capacity를 초과하면 새 sub-map을 추가. 단, 더 이상 ScalableAlloc 없이 fixed.

#내부 구현

#AtomicHashArray가 기본 단위

1
AtomicHashMap
2
  └ AtomicHashArray (sub-map 1)
3
  └ AtomicHashArray (sub-map 2, 첫 게 가득 차면 추가)
4
  └ ...

각 AtomicHashArray는 고정 크기 array. open addressing linear probing.

1
// 약식 — folly/AtomicHashArray.h
2
template <class Key, class Value>
3
class AtomicHashArray {
4
  struct Cell {
5
    std::atomic<Key>   key;
6
    Value              value;     // value는 atomic 아닐 수도
7
  };
8
  std::vector<Cell> cells_;       // fixed capacity
9
  std::atomic<size_t> numEntries_;
10
};

key는 std::atomic. Empty sentinel(보통 0 또는 ~0)을 사용. CAS로 key를 lock 후 value 채움.

#Insert — CAS based

1
// 약식
2
std::pair<Iterator, bool> insert(Key k, Value v) {
3
  size_t h = hash(k);
4
  size_t start = h % capacity_;
5
  for (size_t i = 0; i < capacity_; ++i) {
6
    size_t idx = (start + i) % capacity_;
7
    Cell& c = cells_[idx];
8

9
    Key expected = kEmpty;
10
    if (c.key.compare_exchange_strong(expected, k,
11
                                       std::memory_order_release)) {
12
      // empty 였음 → claim 성공
13
      c.value = std::move(v);
14
      numEntries_.fetch_add(1);
15
      return {Iterator{this, idx}, true};
16
    }
17
    if (expected == k) {
18
      // 이미 있음
19
      return {Iterator{this, idx}, false};
20
    }
21
    // 다른 key → 다음 probe
22
  }
23
  // 가득 — sub-map 추가 로직 (AtomicHashMap level)
24
}

CAS 한 번으로 claim. 성공하면 value를 채운다. value 쓰기는 atomic 아님 — reader가 partial value를 볼 가능성. 그래서 value는 POD 또는 immutable이 권장.

#Find — wait-free

1
// 약식
2
Iterator find(const Key& k) const {
3
  size_t h = hash(k);
4
  size_t start = h % capacity_;
5
  for (size_t i = 0; i < capacity_; ++i) {
6
    size_t idx = (start + i) % capacity_;
7
    Key found = cells_[idx].key.load(std::memory_order_acquire);
8
    if (found == k) return Iterator{this, idx};
9
    if (found == kEmpty) return end();
10
  }
11
  return end();
12
}

원자 load 한 번. lock 없음. acquire/release pairing으로 insert side가 write한 value가 reader에 보임.

#Multi sub-map chain

1
// AtomicHashMap level
2
std::pair<Iterator, bool> insert(Key k, Value v) {
3
  // 1. 가장 최근 sub-map에 시도
4
  for (auto& sub : subMaps_) {
5
    auto r = sub.insert(k, v);
6
    if (r.second || r.first != sub.end()) return r;
7
  }
8
  // 2. 가득 → 새 sub-map (mutex로 한 번에 한 명만)
9
  std::lock_guard g(growLock_);
10
  subMaps_.emplace_back(make_unique<AtomicHashArray>(growSize));
11
  return subMaps_.back()->insert(k, v);
12
}

성장은 mutex 보호 하지만 read/insert는 기존 sub-map에서 lock-free.

#제약

항목	AtomicHashMap	일반 hash map
Capacity 미리 지정	필수	reserve로 hint
Erase	X	O
Resize	append-only	full rehash
Value 수정 (in-place)	atomic type만	자유
Iterator 안정	영구 (cell 그대로)	rehash 시 invalid
Reader contention	0	mutex 필요

이런 제약을 받아들일 수 있는 use case에서만.

#std/abseil 비교

1
// std
2
// 직접 대응 없음. std::unordered_map + std::shared_mutex로 구현 필요
3

4
// abseil
5
// flat_hash_map + absl::Mutex
6
// 또는 absl::node_hash_map + node 자체에 lock
7
// concurrent variant은 없음 — Google 내부에는 있으나 미공개
8

9
// folly
10
folly::AtomicHashMap<K, V> ahm(N);          // append-only, lock-free read
11
folly::ConcurrentHashMap<K, V> chm;          // 다음 글 — 전체 thread-safe

abseil은 concurrent hash map을 공개하지 않는다. fbcode는 두 가지(AtomicHashMap / ConcurrentHashMap)로 다른 trade-off를 제공.

#코드 리뷰 포인트

1
// Bad — erase 필요한데 AtomicHashMap
2
folly::AtomicHashMap<int, Conn> conns(N);
3
// disconnect 시 erase 안 됨 — 메모리 누수
4

5
// Good — erase 필요하면 ConcurrentHashMap
6
folly::ConcurrentHashMap<int, Conn> conns;

erase가 의미 있으면 AtomicHashMap을 쓰면 안 된다. 또는 tombstone value 같은 logical delete 패턴.

1
// Bad — 큰 value, partial read 위험
2
folly::AtomicHashMap<int, std::vector<int>> m(N);
3
m.insert(1, {1, 2, 3, 4, 5});
4
// reader가 인덱스만 본 상태에서 size를 다르게 볼 수 있음
5

6
// Good — POD / atomic
7
folly::AtomicHashMap<int, uint64_t> counters(N);

value는 atomic 이거나 immutable after insert. 그렇지 않으면 reader가 깨진 값을 본다.

1
// 잘못된 capacity 추정
2
folly::AtomicHashMap<int, int> m(1000);
3
for (int i = 0; i < 1'000'000; ++i) m.insert(i, i);
4
// sub-map이 계속 추가 — find가 모든 sub-map을 순회, 느려짐

capacity는 최대값에 맞춰 한 번에. sub-map chain이 길어지면 find가 모든 chain을 본다.

#안티패턴

ConcurrentHashMap 대신 AtomicHashMap: erase가 필요하면 ConcurrentHashMap. AtomicHashMap은 단방향 transactional 환경만.
value mutation: in-place update는 value가 std::atomic이어야 안전. 일반 type은 reader가 torn value를 본다.
capacity 부족: chain이 길어지면 read complexity 증가. 처음에 max에 맞춰 reserve.