긱 이코노미 배달 앱에서 어떤 배달원에게 주문을 제안할지 결정하는 서비스는, 매 순간 수많은 경로 추정을 반복해야 한다. 직선거리는 다리가 없는 강 건너편을 10분이면 간다고 말하지만 실제로는 그렇지 않기 때문에, 라우팅 엔진으로 실제 이동 시간을 계산해야 한다. 문제는 이 라우팅 호출이 서비스 지연의 가장 큰 원인이라는 점이다. 정해진 시간 안에 처리량을 소화하지 못하면 '양동이가 넘쳐 모두가 젖는' 구조여서, 지연 목표는 타협 대상이 아니다.
다행히 이 계산에는 반복이 많다. 세 집 건너 사는 사람이 같은 마트에 가는 데 걸리는 시간은 나와 크게 다르지 않고, 식당은 아예 움직이지 않는다. 한 블록 떨어진 두 배달원은 거의 동일한 경로 요청을 만들고, 30초 뒤 새 위치에서 또 비슷한 요청을 만든다. 캐시가 없으면 사실상 같은 거리를 계속 다시 계산하는 셈이다. 게다가 추정을 계산한 프로세스가 그 값을 다시 쓰는 경우는 드물어서, 프로세스 로컬 캐시로는 안 되고 공유 캐시가 필요했다.
좌표 대신 육각형, 그리고 키 설계
원시 좌표를 그대로 캐시 키로 쓰는 것은 불가능하다. 필자는 H3를 써서 좌표를 중복 제거했다. H3는 세계를 크기가 다른 육각형으로 나누고 좌표쌍에서 해당 육각형 ID를 얻게 해준다. 해상도는 하나의 조절 레버다. 육각형이 너무 크면 적중률은 높아지지만 추정이 부정확해지고, 너무 작으면 좌표를 다른 식별자로 바꾼 것에 지나지 않는다. 그래서 키는 '출발지 육각형:도착지 육각형:해상도' 형태가 되었고, 값은 추정치, 쓰기 경로는 MSET이었다. 여기까지는 간단해 보였다.
16,384개의 해시 슬롯
문제는 레디스 클러스터였다. 클러스터는 키와 값을 노드에 고르게 분산해야 하고, 이를 위해 16,384개의 해시 슬롯을 만들어 노드들에 나눠 준다. MSET·MGET처럼 여러 키를 다루는 명령은 모든 키가 같은 슬롯에 들어갈 때만 유효하다. 필자는 트레이스를 보다가 이 사실을 알게 됐다. 단일 읽기가 키 하나짜리 MGET 스팬 수십 개로 쪼개져 있었고, 오텔 수집기가 관련 스팬을 상당수 누락하고 있었는데도 최대 읽기 지연 지표가 예상 최악값을 크게 웃돌았다.
키가 어느 슬롯에 들어갈지는 CRC16(key) mod 16384으로 정해진다. 한 글자만 달라도 완전히 무관한 슬롯에 떨어지므로, 매번 고유한 육각형 ID 쌍을 담은 필자의 키들은 사실상 같은 슬롯에 모일 일이 없었다. 잘 만들어진 클라이언트는 이런 MGET을 슬롯별로 묶어 각각 별도의 회선에 실어 보낸다. 필자가 넘긴 키를 생각하면 그것이 옳은 처리였고, 진짜 해법은 키가 그렇게 많은 슬롯에 흩어지지 않게 만드는 것이었다.
해시 태그와 브루트포스
레디스에는 바로 이런 상황을 위한 탈출구인 해시 태그가 있다. 키에 중괄호로 감싼 구간이 있으면 레디스는 그 안의 텍스트만 해싱하고 나머지는 무시한다. 관건은 중괄호 안에 무엇을 넣느냐다. 필자는 정수를 골라, 비트코인 채굴자처럼 브루트포스로 원하는 슬롯에 떨어지는 값을 찾았다. 태그는 사실상 '{routing:v1:}' 같은 템플릿이고, 시작 시점에 0부터 올려가며 각 태그의 해시가 어느 슬롯에 들어가는지 확인해, 모든 노드가 필요한 만큼의 태그를 갖출 때까지 반복한다. 이렇게 하면 수천 개의 키 배치를, 정확히 한 노드를 겨냥한 몇 개의 합법적 다중 키 명령으로 나눌 수 있다.
다만 팬아웃을 줄인 것만으로는 부족했다. 각 레디스 노드는 명령을 단일 스레드로 실행하므로, 같은 노드를 겨눈 20개의 동시 요청은 사실상 하나의 큐다. 청크를 도착지 기준으로 정리하지 않으면 여러 청크가 동시에 같은 노드를 때리고 다른 노드는 놀게 된다. 그래서 회선에 내보내기 전에 모든 키의 슬롯을 로컬에서 계산해 슬롯별로 묶었다. 그러면 팬아웃이 임의의 청크가 아니라 노드 단위로 이뤄지고, 모든 요청이 실제로 일을 하게 된다.
만료 처리와 직렬화, 그리고 교훈
캐시된 경로 추정에는 만료가 있어야 하는데 MSET에는 만료 인자가 없다. 흔한 우회책은 키마다 SET ... EX를 파이프라인으로 보내 명령 하나를 수천 개로 늘리거나, MSET 후 EXPIRE를 두 번째 패스로 돌리는 것이다. 후자는 명령 수가 두 배가 되고, 두 패스 사이에 크래시가 나면 키가 영원히 캐시에 남는 창이 생긴다. 결국 답은 EVAL로 스크립트를 실행하도록 요청하는 것이었다. 마지막으로, 값 직렬화 문제도 있었다. 필자는 습관적으로 JSON을 썼는데 작은 페이로드라 대수롭지 않게 여겼지만, 이 규모에서는 귀한 CPU 시간을 잡아먹었다. 값을 콤마 구분 형식으로 바꾸자 크게 개선됐다.
필자는 이 모든 것이 '이전 단계가 왜 예상과 다르게 실패했는지'를 캐내는 과정이었다고 정리한다. 로버트 파이크의 프로그래밍 규칙 중 측정을 강조한 2번, 그리고 'n은 대개 작으므로 화려한 알고리즘을 함부로 쓰지 말라'는 3번을 인용하며, 자신은 라우팅이 병목임은 측정했지만 정작 자신의 n이 항상 크다는 사실을 간과했다고 말한다. 결국 예상보다 정교한 접근이 필요했던 것이다. 그가 도달한 결론은 벤치마킹 하네스를 나중이 아니라 처음에 만들라는 것이다. 프로덕션을 닮은 입력을 만들어 각 접근을 프로덕션 투입 전에 검증하고, 점점 복잡해지는 코드가 실제로 어떤 성능을 사주는지 정직하게 답하게 해주기 때문이다. 스타트업의 '일단 출시하고 나중에 고친다' 관성 탓에 미뤄왔지만, 스펙만 주면 하네스를 빠르게 만들 수 있는 지금은 그 변명이 더는 통하지 않는다는 것이 그의 실무적 결론이다.