absl::Cord — 분산 시스템용 대용량 문자열

1
// 회피 — 매 concat마다 전체 복사
2
std::string body;
3
for (auto& chunk : chunks) {
4
  body += chunk;   // O(n^2) 누적 복사
5
}
6

7
// 회피 — substring이 매번 복사
8
std::string head = body.substr(0, 1024);

1
Cord = "Hello, " + 1MB chunk + ", world"
2

3
         CONCAT
4
        /      \
5
     CONCAT    FLAT("...world")
6
    /      \
7
 FLAT      EXTERNAL(1MB)
8
("Hello,") (refcount=2)

1
#include "absl/strings/cord.h"
2

3
absl::Cord c("Hello");
4
c.Append(", world!");        // O(log n), 새 chunk 한 개 추가
5
c.Prepend("Greeting: ");     // O(log n)
6

7
absl::Cord copy = c;         // O(1), refcount 증가
8
absl::Cord sub = c.Subcord(9, 20);  // O(log n), zero-copy
9

10
// 반복
11
for (absl::string_view chunk : c.Chunks()) {
12
  ::write(fd, chunk.data(), chunk.size());
13
}
14

15
// 평탄화 — std::string 필요 시 (alloc)
16
std::string flat(c);
17
absl::string_view view = c.Flatten();  // 내부적으로 평탄화
18

19
// 외부 메모리 흡수
20
absl::Cord c = absl::MakeCordFromExternal(view, [](absl::string_view) {
21
  // releaser — refcount 0 시 호출
22
});

1
class Cord {
2
 public:
3
  Cord() = default;
4
  Cord(absl::string_view src);
5
  Cord(const Cord& src);    // O(1) — refcount 증가
6
  Cord(Cord&& src) noexcept;
7

8
  void Append(absl::string_view src);
9
  void Append(Cord src);
10
  void Prepend(absl::string_view src);
11

12
  Cord Subcord(size_t pos, size_t n) const;  // O(log n)
13

14
  size_t size() const;
15
  bool empty() const;
16

17
  ChunkRange Chunks() const;
18
  CharIterator char_begin() const;
19

20
  std::string ToString() const;
21
  absl::string_view Flatten();
22

23
 private:
24
  // InlineRep — union { inline_buf[15]; CordRep* tree; }
25
  cord_internal::InlineData contents_;
26
};

1
struct InlineData {
2
  // Inline mode — 마지막 byte의 LSB = 0
3
  char inline_buf[15];
4
  uint8_t tagged_size;   // bit0=0 → inline, bits1-7 = size
5

6
  // Tree mode — 마지막 byte의 LSB = 1
7
  // CordRep* tree (8B) + reserved (7B) + tag (1B, LSB=1)
8
};

1
struct CordRep {
2
  std::atomic<int32_t> refcount;
3
  uint8_t tag;       // FLAT / EXTERNAL / SUBSTRING / BTREE
4
  uint8_t storage[3];
5
  size_t length;
6
};

1
Btree root (height=2)
2
├─ Btree (height=1)
3
│  ├─ FLAT [0..4KB]
4
│  ├─ FLAT [4KB..8KB]
5
│  ├─ ...
6
│  └─ FLAT (~64개)
7
├─ Btree (height=1)
8
└─ ...

1
// 가상 RPC 핸들러
2
absl::Status Handle(const Request& req, Response* res) {
3
  absl::Cord body;
4
  body.Append(BuildHeader(req));      // 작은 inline
5
  body.Append(LoadFromDisk(req.key)); // 큰 file mmap을 EXTERNAL chunk로
6
  body.Append(BuildFooter());
7

8
  *res->mutable_payload() = std::move(body);
9
  return absl::OkStatus();
10
}

1
// 회피 — Cord 잘라서 std::string으로
2
std::string head(cord.Subcord(0, 1024));
3

4
// Good — Cord 그대로 처리
5
absl::Cord head = cord.Subcord(0, 1024);

1
// 회피
2
::write(fd, cord.data(), cord.size());   // 컴파일 에러
3

4
// Good — scatter-gather
5
std::vector<iovec> iov;
6
for (absl::string_view ch : cord.Chunks()) {
7
  iov.push_back({const_cast<char*>(ch.data()), ch.size()});
8
}
9
::writev(fd, iov.data(), iov.size());

1
// 회피 — O(n log n)
2
for (size_t i = 0; i < cord.size(); ++i) {
3
  Use(cord[i]);
4
}
5

6
// Good — chunk 순회 O(n)
7
for (absl::string_view ch : cord.Chunks()) {
8
  for (char c : ch) Use(c);
9
}

1
// 회피 — 빈번한 mutation
2
Cord buf;
3
for (int i = 0; i < 1000000; ++i) {
4
  buf.Append(absl::StrCat(i, "\n"));
5
}