folly::EvictingCacheMap — LRU 구현 분석

1
folly::EvictingCacheMap<int, std::string> cache(1000);  // max 1000
2
cache.set(1, "a");
3
cache.get(1);                  // hit → LRU 앞으로
4
auto* p = cache.get_or_null(2);  // miss → nullptr
5
// 1001번째 set 시 LRU 항목 자동 제거

1
#include <folly/container/EvictingCacheMap.h>
2

3
// 1. 생성 — max size, 옵션 nclear
4
folly::EvictingCacheMap<int, std::string> c(1024);
5

6
// 2. set — insert/update + LRU 앞으로
7
c.set(1, "a");
8

9
// 3. get — hit이면 LRU 앞으로
10
const std::string& v = c.get(1);   // throws if miss
11

12
// 4. get_or_null — miss 시 nullptr
13
const std::string* p = c.get_or_null(2);
14

15
// 5. peek — LRU 갱신 안 함
16
const std::string* p2 = c.peek(1);
17

18
// 6. erase / clear
19
c.erase(1);
20
c.clear();
21

22
// 7. size / capacity
23
c.size();    c.getMaxSize();
24

25
// 8. 통계 — hit / miss / eviction
26
c.getStats();
27

28
// 9. eviction callback
29
c.setPruneHook([](const auto& k, auto&& v) {
30
  LOG(INFO) << "evicted: " << k;
31
});

1
// 약식
2
template <typename K, typename V>
3
class EvictingCacheMap {
4
  struct Node {
5
    K          key;
6
    V          value;
7
    Node*      prev;
8
    Node*      next;
9
  };
10

11
  folly::F14FastMap<K, Node*> index_;     // key → node 빠른 lookup
12
  Node*       head_;                      // LRU front (most recent)
13
  Node*       tail_;                      // LRU back  (least recent)
14
  size_t      size_;
15
  size_t      maxSize_;
16
  std::function<void(K&&, V&&)> pruneHook_;
17
};

1
// 약식
2
void set(K k, V v) {
3
  if (auto it = index_.find(k); it != index_.end()) {
4
    // 이미 있음 — value 갱신 + LRU 앞으로
5
    Node* n = it->second;
6
    n->value = std::move(v);
7
    moveToFront(n);
8
    return;
9
  }
10
  // 새 entry
11
  if (size_ >= maxSize_) evictOne();   // 한 개 제거
12
  Node* n = newNode(std::move(k), std::move(v));
13
  pushFront(n);
14
  index_.emplace(n->key, n);
15
  ++size_;
16
}
17

18
void evictOne() {
19
  Node* victim = tail_;
20
  unlink(victim);
21
  index_.erase(victim->key);
22
  if (pruneHook_) pruneHook_(std::move(victim->key), std::move(victim->value));
23
  delete victim;
24
  --size_;
25
}

1
const V& get(const K& k) {
2
  auto it = index_.find(k);
3
  if (it == index_.end()) throw std::out_of_range{};
4
  Node* n = it->second;
5
  moveToFront(n);
6
  ++stats_.hits;
7
  return n->value;
8
}

1
folly::EvictingCacheMap<std::string, Response> http_cache(10'000);
2

3
auto* cached = http_cache.get_or_null(url);
4
if (cached) return *cached;
5

6
auto resp = FetchAndProcess(url);
7
http_cache.set(url, std::move(resp));
8
return http_cache.get(url);

1
thread_local folly::EvictingCacheMap<std::string, std::regex>
2
    regex_cache(128);
3

4
const std::regex& compile(const std::string& pattern) {
5
  if (auto* r = regex_cache.get_or_null(pattern)) return *r;
6
  regex_cache.set(pattern, std::regex{pattern});
7
  return regex_cache.get(pattern);
8
}

1
folly::EvictingCacheMap<int, BigObject> c(1024);
2
c.setPruneHook([](int k, BigObject&& v) {
3
  metrics_.evicted.increment();
4
  v.OnEvict();   // resource 해제 hook
5
});

1
// Bad — multi-thread 사용
2
folly::EvictingCacheMap<int, std::string> shared_cache(1024);
3
// thread 여럿이 get/set → race
4

5
// Good — thread_local 또는 외부 mutex
6
thread_local folly::EvictingCacheMap<int, std::string> tls_cache(1024);
7
// 또는 folly::Synchronized<EvictingCacheMap<...>>

1
// 위험 — get으로 LRU 갱신, 의도 외 eviction 변경
2
const auto& v = cache.get(k);   // LRU 앞으로
3
// 의도가 단순 확인이면 peek
4

5
// Good
6
if (auto* p = cache.peek(k)) Inspect(*p);   // LRU 안 건드림

1
// 주의 — max size를 너무 작게
2
folly::EvictingCacheMap<K, V> tiny(10);
3
// thrashing → hit rate 낮음 → cache 무용