CDN 및 DDoS 방어 서비스 등을 제공하는 클라우드플레어(Cloudflare)는 평균적으로 초당 6,000만 건이 넘는 대량의 HTTP 요청을 처리하고 있다. 이런 HTTP 요청 처리에 있어 처리 방식을 재검토해 CPU 사용률을 1% 이상 줄일 수 있었다고 공식 블로그에 게시했다.
클라우드플레어 서비스에서 사용되는 핀고라(Pingora) 프레임워크에서는 사용자 요청을 실제 목적지 서버인 오리진(origin)으로 전송할 때 클라우드플레어 내부에서만 사용되는 헤더를 제거해야 한다. 헤더를 제거하기 위해 클라우드플레어는 외부로 향하는 모든 요청에 대해 처리를 수행했다고 한다. “clear_internal_headers” 함수는 외부로 향하는 요청을 처리하는 “pingora-origin” 서비스 CPU 시간 1.7% 이상을 소비하고 있었다. 외부로 향하는 요청은 초당 3,500만 건 발생하고 있어 영향이 크기 때문에 엔지니어링 팀은 이 함수 최적화에 착수하기로 했다고 한다.
엔지니어링 팀은 먼저 평가 라이브러리(Criterion.rs)를 사용해 함수 평균 실행 시간을 측정하고 방법별 실행 시간 차이를 시각화할 수 있도록 했다. 최적화 전 단계에서는 평균 실행 시간이 3.65µs였다고 한다.
초기 코드에서는 내부 헤더 목록을 기반으로 모든 헤더를 순서대로 처리해 헤더를 찾아 삭제하는 작업이 100회 이상 수행되고 있었다.
엔지니어링 팀은 대부분 각 요청에는 10개에서 30개 정도 내부 헤더만 사용된다는 점에 주목했다. 요청 각 헤더를 내부 헤더와 대조해 삭제하는 방식으로 변경해 처리 시간을 1.53µs까지 줄일 수 있었다고 한다. 이것만으로도 함수 속도가 2.39배 향상됐다.
더 나아가 각 헤더를 내부 헤더와 대조하는 부분에 대한 고속화에 착수했다. O-표기법을 사용할 때 해시 테이블의 읽기 시간은 O(1)이므로 더 이상 고속화의 여지가 없어 보이지만 실제로는 키의 길이를 L이라고 할 때 해시 계산에 O(L)의 시간이 걸린다.
엔지니어링 팀은 검토를 거듭한 결과 트라이(Trie) 구조를 채택하기로 했다. 트라이 구조는 문자열 앞에서부터 순서대로 일치를 찾는 구조로 단어 목록에 없는 문자열 탐색을 비교적 빠르게 종료할 수 있다는 특징이 있다. 예를 들어 단어 목록이 and, ant, dad, do, dot으로 구성되어 있을 경우 a나 d로 시작하지 않는 단어는 즉시 단어 목록에 없음으로 판정할 수 있다.
트라이 구조에서는 검색 공간을 빠르게 축소할 수 있기 때문에 단어 목록과 일치하지 않는 경우 검색 시간을 O(log(L))로 줄일 수 있다. 단어 목록과 일치하는 경우 검색 시간은 O(L)로 해시 계산과 다르지 않지만 요청 헤더 중 내부 헤더와 일치하는 헤더는 10% 미만이기 때문에 고속화할 수 있다고 한다.
클라우드플레어 사용 사례에 맞게 트라이 구조를 구현하는 등 노력의 결과 초기 1.71%였던 clear_internal_headers 함수의 CPU 사용률을 0.34%까지 줄일 수 있었다고 설명하고 있다.
글에선 결론은 최적화 방법보다는 코드가 어디서 얼마나 느려지고 있는지 아는 게 더 중요하다는 것이라며 시간을 좀더 내어 프로파일링이나 벤치마크 도구를 활용해 보라고 마무리하고 있다. 관련 내용은 이곳에서 확인할 수 있다.