▲

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

 (blog.cloudflare.com)
2P by neo 3달전 | favorite | 댓글 1개

동기

  • 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 등이 있음
▲
neo 3달전  [-]
Hacker News 의견

  • 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 자동자로 컴파일해야 함
답변달기