Overview

Part 1: 분산 웹 캐시에서는 카카오의 트래픽을 처리하고 있는 Wcache에 대한 간략한 소개를 하였습니다.이전 버전의 Wcache는 기본적으로 준수한 응답속도를 보이고 있었지만, metadata를 집중된 DB에 저장하는 방식 및 기타 구조상의 문제로 인한 성능 안정성 문제,그리고 기능상의 문제들이 잠재되어 있었습니다. 본 포스트에서는 이전 버전의 Wcache에서 어떠한 구조적 문제가 있었는지, 또한 이를 어떻게 해결하였는지를 다룹니다.

Part 2: Wcache 저장 구조 변경

저장 구조 변경 - 성능 안정화

기존 BigFile 저장방식의 문제점

이전 포스트에 나와있듯이 Wcache는 metadata 정보를 컨텐츠와는 별도로 DB에 저장해 두고 있었습니다. 메모리에올라와 있는 LRU hashtable에 원하는 컨텐츠가 캐싱되어 있지 않다면, SQLite DB에 컨텐츠 키를 가지고 어떤 BigFile에 있는지, 헤더의 길이는 얼마나 되는지 등의 정보들을 조회를 해야 하는 것이죠.

메모리 상의 LRU hashtable에 없을 경우 기존 Wcache의 컨텐츠 조회 방식

위 과정은 평상시 읽는 과정에서는 문제가 없었지만, block 단위로 컨텐츠를 디스크에 저장할 때와 BigFile이 가득 차 오래된 BigFile block들을 replace 할 때 문제가 발생합니다.n개의 컨텐츠가 하나의 block에 있을 경우 BigFile에서의 디스크 write operation은 한 번만 발생하지만 SQLite DB에서의 metadata 관련 정보 업데이트는 n번 발생하게 됩니다.특히, 주기적으로 용량 확보를 위해 오래된 블록 또는 BigFile 전체를 비워야 하는 경우,DB 전체를 스캔해 관련 항목을 삭제하는 작업(ex: “DELETE FROM table WHERE BigFileNo = 1”)으로 인한 부하가 증가하게 되고,결국 이러한 작업이 있을 때마다 Wcache의 성능은 일시적으로 평상시에 비해 최대 80%까지 하락하는 모습을 보이게 됩니다.DB 부하를 줄이기 위해 block 크기를 줄이는 방법을 고려해 보았으나 그만큼 디스크 write operation 횟수가 증가합니다.게다가 구조상 block 크기보다 큰 컨텐츠를 저장할 수 없기 때문에 그만큼 캐시 효율이 감소하게 됩니다.

이러한 중앙 집중적인 SQLite구조에는 한계가 있다고 파악하였고, 근본적으로 저장 구조를 개선해야 된다고 결론 내렸습니다.

Journaling BigFile (JBF)

중앙 집중적인 SQLite대신 각 BigFile에 metadata를 함께 저장하는 방식을 취하기로 하였습니다.이를 위해 SQLite처럼 journaling이 가능하면서 안정적으로 metadata와 컨텐츠를 저장하기 위해 자체적으로 Journaling BigFile, 일명 JBF를 개발해 적용하였습니다.

JBF의 구조도. 포맷을 위해서는 앞부분(전체 파일 크기의 1%)만 리셋해주면 된다.

JBF는 위 그림과 같이 BigFile 내부에 block-level journal(write-ahead log), space map, B-Tree 등을 가지고 있어 BigFile 개별로 복구, 조회, 포맷이 가능합니다.또한, Metadata 정보를 JBF 내부 B-Tree에 적재하고, 컨텐츠 body는 JBF의 일반 영역에 저장합니다.JBF는 BigFile별 포맷이 매우 빠르게 이루어 지기 때문에 기존 버전과는 다르게 가득 찬 BigFile을 비울 때 발생하는 성능 하락 이슈가 없습니다.컨텐츠를 여러 block에 걸쳐 쓰는것이 가능하기 때문에 저장 가능한 컨텐츠의 최대 크기 제한 역시 BigFile 전체 크기로 늘어나게 됩니다.

JBF를 이용한 저장구조

기존 SQLite에 의존했던 탐색 로직을 개편하기 위해서는 어떠한 JBF에 컨텐츠가 존재하는지를 캐시 key 만으로 알아내야 합니다.이를 위해 JBF들을 몇 개의 그룹으로 나누고, 캐시 key를 그룹 개수로 modular 연산하여 특정 그룹을 정하고, 해당 그룹 내부의 있는 JBF들에서 순차적으로 탐색하도록 구성하였습니다.

JBF를 적용한 Wcache의 컨텐츠 조회 방식. Read시에는 최근에 write한 JBF부터 조회한다.

전체 JBF들을 동시에 사용하지 않고 그룹으로 묶어 사용하는 이유는 효율적인 디스크 용량 활용이 가능해지기 때문입니다.JBF는 BigFile 단위로 포맷을 하게 되는데, 그룹을 만들지 않고 모든 JBF에 골고루 저장하게 되면 JBF들이 가득 차게 되는 시점이 비슷해지고,이후 오래된 캐시를 비우는 작업 시 전체 JBF들을 비슷한 시기에 비워야 하는 이슈가 생깁니다.그렇게 되면 순간적으로 hit율이 낮아짐은 물론 새롭게 컨텐츠를 캐싱하는 양도 많아져 소스 서버의 부하까지 발생하게 됩니다.반면 그룹을 묶어서 사용하게 되면 그룹 별로 하나씩만 비울 수 있게 되어 순간적인 캐시 hit율 하락을 완화시킬 수 있습니다.

또한 각 그룹별로 write가 이루어지는 JBF들의 순번이 정해져 있고 컨텐츠가 쌓이는 속도도 일정하기 때문에 이점을 활용해 디스크 locality도 증가시킬 수 있습니다.Wcache 초기 세팅 시 각 그룹에서 같은 순번에 있는 JBF들을 물리적 디스크상에서 인접하게 생성시키면(group 1의 1번 JBF, group 2의 1번 JBF, … group 1의 2번 JBF, …)컨텐츠를 디스크에 캐싱할 때 인접한 구역을 쓰기 때문에 HDD를 사용하는 경우 디스크의 seek time을 줄일 수 있는 중요한 요인이 됩니다.

Bloom filter를 통한 JBF 성능 최적화

JBF들의 그룹을 만드는 구조는 한 가지 치명적인 단점이 있습니다. 바로 중복된 JBF 탐색입니다. 위 그림에서 볼 수 있듯이 캐싱된지 오래된 컨텐츠를 읽기위해서는 쓸모없는 JBF 탐색이 들어가야 하는데, 이는 개편 후 초기 테스트 시 Wcache에 쌓이는 컨텐츠가 많아질수록 성능을 저하시키는 주요 원인이 되었습니다.

Bloom filter 도식도. n번의 hash를 돌린 결과값이 전부 bucket에 존재하면 통과, 하나라도 없으면 실패. (출처: Wikipedia)

이를 해결하기 위해 각 JBF 앞단에 bloom filter1를 적용하게 됩니다. Bloom filter는 어떤 원소가 집합에 속하였는지 확률적으로 알 수 있게 하는 함수입니다.약간의 false positive만 가지고 있고 false negative는 없기 때문에 해당 필터를 통과하는 경우에만 JBF 조회를 하도록 변경을 함으로써 기존 대비 2 ~ 5배의 응답속도를 향상시켰습니다.

Bloom filter를 적용한 경우와(주황색) 적용하지 않은 경우(파란색)의 응답속도 차이.

Metadata 저장구조 변경 - Vary Object 관리 개선

HTTP 헤더 중에는 ‘Vary’라는 항목이 있습니다.동일한 URL에 대해 요청을 하더라도 요청한 사용자의 특징(User Agent, Accept Encoding, Origin 등등)에 따라 서로 다른 응답을 해 주기 위해서 존재하는 헤더입니다.따라서 웹 캐시에서는 vary 헤더를 확인하고 해당 헤더에서 명시하는 조건에 따라 동일 URL이라 하더라도 다른 종류의 컨텐츠를 캐싱하고, 제공해야 합니다.

기존 Wcache에서는 이런 vary object에 대한 고려가 충분하지 않았습니다. 아래 그림처럼 vary object 저장은 가능했지만,리스트 형식으로 원하는 vary object가 나올 때까지 탐색해야 했고 그마저도 vary 헤더가 없는 normal object와 동시에 캐싱을 할 수 없는 이슈가 있었습니다.

Wcache의 기존 metadata 저장구조(a)와 개선된 저장구조(b)

이를 해결하기 위해 저장 구조 설계 시 처음부터 vary object의 존재를 고려하였습니다. Metadata를 두 개의 타입 (Meta / Info)으로 나누어,Meta에는 현재 Wcache에 캐싱되어있는 vary object의 종류와 info의 포인터를, Info에는 실제 컨텐츠의 정보 (offset, header 등)를 담도록 설계하였습니다.이 구조를 통해 여러 개의 vary object가 있어도, normal object와 공존해도 문제없이 사용자가 원하는 컨텐츠를 제공할 수 있게 됩니다.

Lock 구조 개선 - 동일 컨텐츠 접근 시 생기는 병목현상 제거

Wcache는 느슨한 구조의 actor model2을 가지고 있습니다. 사용자의 요청이 들어오면 다수의 actor(HTTP 요청 수신 / 응답 / 컨텐츠 처리 / 소스 서버 통신)를 돌아다니며 처리됩니다.각 actor는 I/O multiplexing 형식으로 동시에 여러 개의 요청을 다룰 수 있게 하여 최대한의 성능을 낼 수 있도록 설계되었습니다.그러나 디스크 I/O를 하는 actor는 내부적으로 blocking read / write를 수행하게 되어 단일 thread로는 원활한 성능을 얻을 수 없기에 내부적으로 multi thread 모델을 채택하였습니다.

그러다보니 해당 구조에서는 캐싱된 컨텐츠를 처리하는 actor에서 컨텐츠를 조회하고 검증하는 동안 불가피하게 캐시 key에 대해 광범위한 lock 처리를 해야 했습니다.이 lock은 컨텐츠가 새로 갱신되거나 삭제(Purge)될 때를 위해 필요하지만, 이전 구조에서는 read / write lock 구분이 없었습니다.이는 동일 컨텐츠를 집중적으로 요청할 때 해당 컨텐츠의 초당 처리수가 제한되는 문제를 야기합니다.일반적으로 특정 이벤트3로 인해 트래픽이 증가하는 경우, 소수의 인기 있는 컨텐츠들이 집중적으로 요청되는 경우가 많으므로 이러한 성능 제한은 급작스런 트래픽 대응 시 잠재적인 문제가 될 수 있습니다.

이를 해결하기 위해 먼저 read / write lock을 분리하여 평시에 컨텐츠가 집중적으로 요청되는 경우 동시에 접근이 가능할 수 있도록 하였습니다.더 나아가 lock의 범위를 줄이고 추후 유지보수를 쉽게 하기 위해 순수하게 디스크 I/O 부분과 캐시 컨텐츠를 검증하는 부분을 별도의 actor로 분리해 조금 더 효율적인 처리를 할 수 있도록 변경하였습니다.이 조치는 동일 컨텐츠 요청에 대해 기존 대비 약 3배의 성능 향상을 이루어냅니다.

결과

이번 개편은 개발부터 성능 안정화까지 약 1년에 걸쳐 진행되었습니다. 기존 Wcache 구조의 핵심 부분들을 전부 뜯어고치는 대 작업이었습니다.이번 개편을 통해 더 안정적인 성능을 이끌어 낼 수 있었고, 기능적인 측면들 - vary object 저장 유연화, 컨텐츠 크기 제한 해제,regular expression 기반 대량 캐시 퍼지 등 - 에서 큰 발전을 이룰 수 있게 되었습니다.

Bloom Filter ↩
Actor Model ↩
다음 앱에서의 뉴스속보 및 날씨알림 등의 푸시, 카카오톡 채널탭 뱃지 등… ↩

분산 웹 캐시 (Wcache)의 개선과정 - Part 2