folly::FBString 분석 — SSO + COW 구현

#한 줄 요약

folly::fbstring은 23-byte SSO와 medium 영역 eager copy, large 영역 copy-on-write를 결합한 3-tier 문자열이다. std::string보다 단편화가 적고 jemalloc 친화적이며 ABI는 호환된다.

#동기

std::string은 구현체마다 다르다. libstdc++ 5 이전은 COW, 이후는 SSO 15-byte, libc++/MSVC는 SSO 22-byte. 데이터 센터 규모에서 이 차이는 무시할 수 없다.

Meta는 두 가지 요구가 있었다. 첫째, 짧은 문자열(URL path 조각, key, log tag)의 힙 할당을 없애야 한다. 둘째, 큰 페이로드(HTML, JSON blob)는 함수 인자로 자주 복사되는데 매번 복사하면 throughput이 떨어진다. SSO와 COW를 한 타입에 합쳐 둘 다 해결한다.

1
folly::fbstring small = "hello";          // SSO: 힙 할당 0회
2
folly::fbstring large = ReadFile("doc");  // 큰 데이터
3
folly::fbstring copy  = large;            // COW: refcount만 증가
4
copy.push_back('!');                      // 이때 분리(unshare)

핵심은 세 영역을 한 24-byte 객체에 우겨넣는다는 점이다.

#API & 사용법

fbstring은 std::string의 거의 모든 멤버를 제공한다. c_str(), data(), size(), operator[], append, replace, iterator 모두 동일하다. 추가로 다음이 있다.

1
#include <folly/FBString.h>
2

3
folly::fbstring s = "abc";
4
s.reserve(1000);            // capacity 확장
5
s += "def";
6

7
// std::string과 zero-copy 변환
8
std::string std_s = s.toStdString();         // 새 복사
9
folly::fbstring back(std_s.data(), std_s.size());
10

11
// StringPiece와 호환
12
folly::StringPiece sp = s;

-DFOLLY_USE_FBSTRING_FOR_STD_STRING을 정의하면 std::string을 매크로로 fbstring으로 치환할 수 있다. fbcode 내부에서 쓰는 트릭이지만 외부에서는 ABI 충돌 위험이 있어 권장하지 않는다.

#내부 구현

fbstring의 24-byte 객체는 마지막 byte로 카테고리를 식별한다.

1
// folly/FBString.h 의 약식
2
struct MediumLarge {
3
  char*   data_;       // 8 bytes
4
  size_t  size_;       // 8 bytes
5
  size_t  capacity_;   // 8 bytes — 상위 2-bit이 카테고리
6
};
7

8
struct Small {
9
  char    data_[23];   // 23 bytes
10
  uint8_t lastChar_;   // 상위 2-bit + (23 - size)
11
};

capacity_의 상위 2-bit은 little-endian 머신에서 Small.lastChar_의 상위 2-bit과 같은 byte에 위치한다. 이 2-bit이 카테고리다.

Small 모드에서 size()는 23 - lastChar_(상위 2-bit 마스킹 후)로 계산한다. 빈 문자열이면 lastChar_ = 23이고 data_[0] = '\0'이라 c_str()이 그대로 동작한다.

#Medium — eager copy

23 < size ≤ 254 구간은 힙에 할당하되 복사 시 즉시 deep copy 한다. refcount overhead 없이 단순하다. malloc은 goodMallocSize()로 jemalloc class에 맞춰 올림한다.

1
// 약식
2
static size_t goodMallocSize(size_t n) {
3
  if (n <= 64) return ((n + 7) / 8) * 8;
4
  // 그 외 jemalloc size class
5
}

#Large — Copy-on-Write

255 byte 이상이면 다음 레이아웃이다.

1
[ refcount (8B) | char[] ... | '\0' ]
2
       ↑
3
   heap pointer 의 -8 위치

data_는 char 시작점을 가리키고, data_ - sizeof(size_t) 위치에 atomic refcount가 있다. 복사 생성자는 __atomic_fetch_add(refcount, 1, RELAXED)만 호출하고 반환한다.

수정 시 분리(unshare):

1
// 약식
2
char* mutableData() {
3
  if (category() == isLarge && refCount() > 1) {
4
    // deep copy 후 자기만의 buffer 보유
5
    unshare();
6
  }
7
  return data_;
8
}

이 unshare는 operator[]의 non-const 오버로드, data() non-const, iterator 시작에서 호출된다. const 접근은 분리하지 않는다.

#Copy-on-Write 동작 그림

Large 영역에서 vs1 = vs2가 일어나면 ptr만 복사 + refcount++. 둘 중 하나가 수정 시에 비로소 새 버퍼를 떼낸다.

이 lazy split이 큰 페이로드의 함수 인자 전달을 사실상 무료로 만든다. 다만 멀티스레드에서 atomic refcount의 contention 비용이 있어 large가 read-heavy일 때 가장 잘 동작한다.

#Why 254, not 255?

254 + 1('\0')이 jemalloc 256 class와 정확히 맞는다. 한 byte 더 쓰면 다음 class(384)로 올라가 단편이 생긴다. 이런 byte 단위 튜닝이 Folly다.

#std::string 비교

23-byte SSO는 24-byte 객체에 마지막 1-byte로 size까지 인코딩한 결과다. libstdc++/libc++가 15 또는 22-byte에 멈춘 이유는 별도의 size 필드를 두기 때문이다.

abseil은 absl::Cord로 다른 방향을 택했다. Cord는 작은 조각의 트리로 큰 문자열을 표현해 substring·append를 O(log n)으로 만든다. fbstring은 contiguous를 유지한다(C API 호환을 위해).

#코드 리뷰 포인트

1
// Bad — std::string으로 받았다가 fbstring으로 복사
2
void Process(const std::string& s) {
3
  folly::fbstring fs(s);  // deep copy
4
  // ...
5
}
6

7
// Good — StringPiece로 받으면 양쪽 다 view 만 잡는다
8
void Process(folly::StringPiece s) {
9
  // ...
10
}

API boundary에서 타입을 어떻게 받느냐가 가장 큰 비용이다. 함수가 소유권을 가지지 않는다면 항상 StringPiece(또는 std::string_view)로 받는다.

1
// 위험 — large fbstring을 비-const iterator로 순회
2
for (auto& c : large_fb_str) {  // unshare 발생!
3
  Sanitize(c);
4
}
5

6
// 안전 — 의도가 read-only면 const
7
for (const auto& c : large_fb_str) {
8
  Inspect(c);
9
}

auto&는 non-const reference라 large mode에서 분리를 강제한다. 의도와 다르면 silent overhead가 생긴다.

#안티패턴

• fbstring을 STL 컨테이너 key로 ABI 경계에서 노출: 다른 라이브러리와 컨테이너 타입이 갈리면 변환 비용이 매번 든다. boundary는 std::string 또는 StringPiece로 통일.
• reserve(0)으로 SSO 강제 시도: 일단 medium/large로 올라간 buffer는 shrink_to_fit()을 호출해도 SSO로 다시 내려오지 않을 수 있다. 짧다고 알면 처음부터 짧게.
• multi-thread에서 mutable iterator 공유: large mode COW는 atomic refcount지만 동일 객체의 mutable 작업은 여전히 race다. 공유하려면 const로 read, 수정 전에 deep copy.

#정리

• fbstring은 23-byte SSO, eager-copy medium, COW large의 3-tier 설계.
• 24-byte 객체에 상위 2-bit 카테고리 인코딩으로 별도 size 필드 없이 SSO 23-byte 달성.
• Large mode COW는 atomic refcount로 multi-thread const 접근 안전.
• jemalloc size class에 맞춘 goodMallocSize()로 단편 최소화.
• API boundary는 StringPiece로 받아 타입 변환 비용 회피.

#다음 편

다음은 Folly가 표준 <format> 대신 {fmt} 라이브러리를 채택한 이유와 통합 방식을 본다.

#관련 항목

• Part 5-03: StringPiece — fbstring의 view 짝
• Part 5-04: Join / split utilities — StringPiece 기반 split
• Part 1-02: Folly vs Abseil 철학 — Cord vs fbstring 설계 차이
• 원문 — folly/FBString.h