# 트라이-하드의 좋은 날: 컴퓨팅 1% 절약

> Clean Markdown view of GeekNews topic #16704. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=16704](https://news.hada.io/topic?id=16704)
- GeekNews Markdown: [https://news.hada.io/topic/16704.md](https://news.hada.io/topic/16704.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-09-11T09:42:21+09:00
- Updated: 2024-09-11T09:42:21+09:00
- Original source: [blog.cloudflare.com](https://blog.cloudflare.com/pingora-saving-compute-1-percent-at-a-time/)
- Points: 2
- Comments: 1

## Topic Body

#### 동기

- Cloudflare의 글로벌 네트워크는 초당 6천만 개 이상의 HTTP 요청을 처리함
- 새로운 오픈 소스 Rust crate를 사용하여 CPU 사용량을 줄이고 CDN의 처리 능력을 향상시킴
- Pingora는 Cloudflare의 Rust 기반 프록시 서비스의 핵심이며, 이를 오픈 소스로 공개함
- Pingora-origin 서비스는 사용자의 요청을 실제 목적지로 전달하는 역할을 함
- 요청이 Cloudflare를 떠날 때 내부 정보를 제거하는 작업이 필요함
- 이 작업은 매우 빈번하게 발생하며, CPU 사용량의 1.7%를 차지함

#### 벤치마킹

- Criterion Rust crate를 사용하여 함수의 성능을 나노초 단위로 측정함
- 원래 `clear_internal_headers` 함수는 평균 3.65µs가 소요됨

#### 읽기 작업 줄이기

- 헤더를 제거하는 방향을 반대로 하여 읽기 작업을 줄임
- 이 변경으로 함수의 실행 시간이 3.65µs에서 1.53µs로 개선됨
- CPU 사용량을 1.71%에서 0.717%로 줄임

#### 데이터 구조 검색

- 해시맵을 사용하여 내부 헤더를 저장하고 검색하는 방법을 시도함
- 해시맵의 읽기 시간은 키 길이에 비례하여 선형적임
- 정렬된 집합이나 상태 기계와 같은 다른 데이터 구조를 시도함
- 정규 표현식을 사용한 구현은 해시맵보다 두 배 느림

#### 트라이 사용

- 트라이는 접두사 검색이나 자동 완성 시스템에 사용되는 트리 데이터 구조임
- 트라이는 문자열이 포함되지 않은 경우를 빠르게 식별할 수 있음
- 기존 트라이 구현은 해시맵보다 느림
- Cloudflare는 자체 최적화된 트라이 구현인 trie-hard를 개발함

#### Trie Hard

- trie-hard는 노드 관계를 정수의 비트에 저장하고 메모리를 연속적으로 사용하여 속도를 높임
- `clear_internal_headers` 함수의 실행 시간을 0.93µs로 줄임
- CPU 사용량을 1.71%에서 0.43%로 줄임
- 실제 프로덕션 환경에서 trie-hard의 성능이 벤치마크와 일치함

#### 결론

- 코드의 느린 부분을 파악하고 최적화하는 것이 중요함
- 작은 최적화가 모여 큰 성능 향상을 가져올 수 있음
- Cloudflare의 연결 클라우드는 네트워크 보호, 인터넷 애플리케이션 가속, DDoS 공격 방어 등의 기능을 제공함

### GN⁺의 정리

- Cloudflare는 Rust 기반의 새로운 오픈 소스 crate를 통해 CPU 사용량을 줄이고 CDN의 처리 능력을 향상시킴
- Pingora-origin 서비스의 내부 헤더 제거 작업을 최적화하여 CPU 사용량을 1.28% 줄임
- trie-hard라는 자체 최적화된 트라이 구현을 개발하여 성능을 크게 개선함
- 이 기사는 코드 최적화와 데이터 구조 선택의 중요성을 강조하며, 작은 최적화가 큰 성능 향상을 가져올 수 있음을 보여줌
- 유사한 기능을 가진 프로젝트로는 NGINX, HAProxy 등이 있음

## Comments



### Comment 28802

- Author: neo
- Created: 2024-09-11T09:42:21+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=41501496) 
- Cloudflare의 내부 헤더 저장 및 제거 방식에 대해 여러 가지 추측을 했음
  - 별도의 사전이나 데이터 구조 사용
  - 모든 내부 메타데이터를 포함하는 단일 헤더
  - 모든 헤더에 접두사를 붙여 내부는 'I', 외부는 'E'로 시작
  - 모든 내부 헤더는 "CFInt"로 시작
  - 특정 목록의 헤더가 내부 헤더라는 방식은 예상하지 못했음
  - 웹은 이미 모호한 신호와 헤더 명칭으로 가득 차 있음
  - Cloudflare 같은 대규모 회사가 이런 오류가 발생하기 쉬운 메커니즘을 사용하는 것이 이상함

- UTF-8 문자를 비트마스크로 매핑하는 것에 대해 처음에는 비효율적이라고 생각했음
  - 32비트로 `a-z`와 여섯 개의 특수 문자를 포함할 수 있음
  - 64비트로 대문자 `A-Z`와 여섯 개의 특수 문자를 포함할 수 있음
  - HTTP 헤더에 충분한 공간을 제공하며 빠른 매칭 알고리즘을 가능하게 함
  - 이 기술은 Bloom Filter임
  - 1970년대에 자원이 제한된 시기에 개발된 기술이지만 여전히 유용하게 사용되고 있음

- Cloudflare의 최적화가 가치 있는지에 대한 의문
  - 약 500개의 CPU 코어를 절약했음
  - Cloudflare의 비용을 모르지만, 몇 만 달러 정도의 절약이 예상됨
  - 엔지니어링에 대한 긍정적인 ROI를 기대할 수 있는지 의문
  - 필터를 역직렬화 단계에서 적용하여 헤더가 생성되지 않도록 하는 것이 더 나을 수 있음

- 데이터 구조 최적화에 대해 잘 알지 못하지만 해시 테이블을 빠르게 무시한 것이 놀라움
  - 정적 테이블을 검색할 때 해시 테이블이 더 빠를 것이라고 생각함

- fancy한 데이터 구조를 사용하여 제거할 항목을 구성하고 이를 기반으로 헤더 맵에서 제거함
  - "remove_header" 호출이 관련된 코드 링크를 제공함

- 트라이(Trie)를 사용한 블로그 포스트가 드디어 나옴
  - 트라이 관련 문제들이 헛되지 않았음

- 작은 Bloom Filter를 시도해봤는지 궁금함
  - 헤더 키에 대한 빠른 컨볼루션과 Bloom Filter 테스트가 트라이를 걷는 것을 피할 수 있음

- 정적 항목 집합을 매칭하는 경우 완벽한 해시 테이블을 시도했는지 궁금함
  - 몇 가지 산술 연산과 단일 문자열 비교로 줄일 수 있음

- 최적화가 흥미로움
  - 요청 생성 시 헤더를 내부로 태그하는 것이 가능했는지 궁금함
  - 출력 시 필터링이 간단해짐

- regex crate가 더 잘 작동하지 않은 이유가 궁금함
  - 여러 리터럴 문자열 검색을 Aho-Corasick 자동자로 컴파일해야 함