처리율 제한 장치 설계 면접 퀴즈

처리율 제한 장치는 요구사항이 짧아 보여서 바로 알고리즘 이야기로 넘어가기 쉽습니다. 그런데 무엇을 기준으로 세는지와 얼마나 정확해야 하는지를 정하지 않으면 어떤 알고리즘도 고를 수 없습니다.

기능 요구사항과 범위 밖

범위 밖을 말하는 것이 중요합니다. 대규모 공격 방어를 여기서 하려 하면 판정 하나에 붙는 비용이 커지고, 정작 정상 사용자의 한도 판정이 느려집니다. 공격 방어는 더 앞단에서 값싸게 자르는 별개의 일입니다.

어디서 세고 어디서 자르나

세는 자리가 여러 곳이면 한도가 그만큼 늘어납니다. 서비스 3개가 각자 분당 1,000회 를 센다면 사용자는 실제로 분당 3,000회를 쓸 수 있습니다.

숫자가 정하는 것

무엇을 기준으로 세는가

한도의 기준은 셋 중 하나입니다. 이 선택이 나머지 설계보다 먼저입니다.

접속 주소 기준은 정상 사용자를 무더기로 자릅니다. 다만 키가 없는 요청에는 다른 방법이 없으므로, 인증 전 구간에만 넉넉한 한도로 함께 두는 경우가 많습니다.

정확도를 요구사항으로 적는다

"정확하게" 라고 쓰면 게이트웨이 20대가 매 요청마다 합계를 맞춰야 합니다. 그러면 판정이 저장소 속도에 묶입니다.

오차 5퍼센트 를 허용한다고 적어 두면 근사 계산과 지역 캐시를 쓸 수 있습니다. 분당 1,000회 한도에서 1,050회가 지나가는 것은 아무 문제가 아닙니다. 반대로 2,000회가 지나가는 것은 문제입니다. 허용 오차는 어떤 알고리즘이 탈락하는지를 정하는 기준이 됩니다.

앞 단계에서 API 키 기준으로 세고, 게이트웨이에서 자르고, 오차 5퍼센트 까지 허용한다고 정했습니다. 이제 어떻게 셀지를 고릅니다. 가장 값싼 방법부터 봅니다.

시각으로 창을 자른다

키와 분을 붙여 만든 이름 하나에 숫자를 올립니다.

키 abc 의 10시 01분 창: 값을 1 올리고 1,000 을 넘었는지 본다
창이 바뀌면 이름이 바뀌므로 값도 새로 시작한다

키마다 정수 하나만 쓰므로 메모리가 거의 들지 않고, 판정도 값 하나 올리는 것으로 끝납니다. 1ms 예산에 여유가 큽니다.

그런데 경계에서 두 배가 지나간다

두 창은 각자 한도를 지켰습니다. 규칙은 어긋나지 않았는데 결과가 어긋납니다. 서버가 실제로 받은 부하는 2초에 2,000회이고, 이것은 한도가 막으려던 것입니다.

허용 오차 5퍼센트 는 1,050회를 허용하려고 적은 값입니다. 2,000회는 그 범위 밖이므로 이 방법은 탈락합니다. 요구사항에 오차를 숫자로 적어 둔 덕분에 취향이 아니라 근거로 자를 수 있습니다.

그래도 이 방법이 맞는 경우가 있다

경계 버스트가 문제가 되는 것은 한도가 곧 용량 한계에 가까울 때입니다. 한도를 넉넉하게 잡아 두었고 두 배가 와도 서버가 견딘다면, 정수 하나로 끝나는 이 방법이 가장 좋은 선택입니다.

"정확한 방법이 늘 낫다" 가 아닙니다. 무엇을 막으려는 한도인지에 따라 답이 갈립니다.

창 이름을 언제 지우나

창이 지나면 그 이름의 값은 다시 쓰이지 않습니다. 남겨 두면 키 수만큼 쓰레기가 쌓이므로 만료를 창 길이보다 조금 길게 걸어 둡니다. 지우는 코드를 따로 만들지 않고 저장소가 치우게 합니다.

시계가 어긋나면 창도 어긋난다

창 이름을 각 게이트웨이가 자기 시계로 만들면, 시계가 몇 초 다른 두 대가 서로 다른 창에 값을 올립니다. 그러면 같은 시점의 요청이 두 창에 나뉘어 한도가 느슨해집니다. 창 이름은 저장소 쪽 시각으로 만들거나, 게이트웨이 시계를 맞춰 두는 것이 전제입니다.

앞 단계에서 고정 윈도우가 경계에서 두 배를 통과시키는 것을 봤습니다. 원인은 자르는 기준이 고정된 시각이라는 것이었습니다. 기준을 요청 시점으로 바꾸면 경계가 사라집니다.

통과한 요청의 시각을 모아 둔다

판정은 두 단계입니다. 60초보다 오래된 항목을 버리고, 남은 개수를 한도와 비교합니다. 언제 보든 뒤로 60초를 보므로 경계 버스트가 원리적으로 없습니다.

비용은 들고 있는 양이다

한 키가 들고 있는 항목은 최대 한도만큼입니다. 한도가 분당 1,000회 이면 키마다 최대 1,000개입니다.

항목 하나가 수십 바이트라도 1억 개면 수 기가바이트입니다. 그리고 이 메모리는 한도를 다 쓰는 키가 많을수록 늘어납니다.

거절한 요청은 저장하지 않는다

한도를 넘어 거절한 요청까지 저장하면 이상한 일이 생깁니다. 한도를 넘긴 뒤에도 계속 요청을 보내는 쪽이 저장소를 계속 키웁니다. 막으려던 상대가 비용을 늘리는 구조가 됩니다.

통과시킨 요청만 기록한다
거절은 세지 않고 응답만 돌려준다

이 규칙은 남용을 막는 장치에서 일반적으로 성립합니다. 거절 자체가 비싸면 거절이 공격 수단이 됩니다.

판정 비용도 요청마다 든다

버리기와 세기가 매 요청에 붙습니다. 피크 초당 5만 요청이면 그만큼 반복됩니다. 저장소가 정렬된 집합을 다뤄 준다면 한 번에 처리할 수 있지만, 버릴 항목이 많이 쌓인 키에서는 그 한 번이 길어집니다.

1ms 예산에서 이 방식은 여유가 없습니다. 그래서 선택은 둘 중 하나입니다.

정확한 방법이 늘 정답은 아니다

이 방식은 오차가 0입니다. 그런데 요구사항은 오차 5퍼센트 를 허용한다고 적었습니다. 허용된 오차를 쓰지 않으면 그만큼을 비용으로 내는 것입니다.

요구사항에 적힌 여유는 쓰라고 있는 것입니다. 정확도를 공짜로 얻을 수 있을 때만 정확한 쪽을 고릅니다.