앞 단계에서 두 가지를 봤습니다. 고정 윈도우는 값싸지만 경계에서 두 배를 통과시키고, 시각을 다 들고 있는 방식은 정확하지만 항목이 쌓입니다. 이 사이에 값싸면서 경계가 없는 방법이 있습니다.
이전 창을 겹치는 비율만큼 섞는다
최근 60초는 이전 창의 뒷부분과 현재 창의 앞부분에 걸쳐 있습니다. 이전 창의 값에 겹치는 비율을 곱해 현재 창의 값과 더합니다.
어림한 값 = 이전 창 값 x 겹치는 비율 + 현재 창 값
정수 두 개만 쓰므로 항목이 쌓이지 않고, 계산도 곱셈 하나와 덧셈 하나입니다. 1ms 예산에 여유가 큽니다. 그리고 기준이 요청 시점이라 경계 버스트가 없습니다.
어림한다는 것은 가정을 두는 것이다
이 계산은 이전 창 안에서 요청이 고르게 왔다고 가정합니다. 실제로 고르면 매우 정확합니다. 몰려 있으면 어긋납니다.
| 이전 창의 실제 분포 | 어림값 |
|---|---|
| 고르게 왔다 | 거의 정확하다 |
| 창의 앞쪽에 몰렸다 | 실제보다 크게 본다. 더 엄격해진다 |
| 창의 뒤쪽에 몰렸다 | 실제보다 작게 본다. 더 느슨해진다 |
느슨해지는 쪽이 위험합니다. 이전 창의 요청이 모두 마지막 순간에 몰렸다면, 그 요청들은 지금도 최근 60초 안에 있는데 어림값은 비율만큼만 셉니다.
최악의 오차를 계산해 본다
현재 창의 절반 지점에서 겹치는 비율은 0.5입니다. 이전 창 1,000회가 모두 그 창의 끝에 몰렸다고 하면,
실제 최근 60초 = 1,000회
어림값 = 1,000 x 0.5 = 500회
남은 여유로 500회를 더 통과시킨다
최악에는 한도의 절반만큼 더 지나갈 수 있습니다. 오차 5퍼센트 는 이 최악을 덮지 못합니다.
잘게 나누면 가정이 약해진다
이 방식이 거친 이유는 창을 두 덩어리로만 보기 때문입니다. 덩어리를 잘게 나누면 가정이 닿는 범위가 줄어듭니다.
| 나눈 단위 | 저장 | 최악 오차 |
|---|---|---|
| 창 2개 | 정수 2개 | 한도의 절반 |
| 1초 버킷 60개 | 정수 60개 | 1초분 |
| 요청 시각 전부 | 통과 요청 수만큼 | 없다 |
같은 계열의 세 방식이고, 얼마나 잘게 나눌지가 정확도와 비용을 함께 정하는 손잡이입니다. 1초 버킷이면 어림하는 부분이 가장 오래된 1초뿐이라 오차가 실질적으로 사라집니다. 정수 60개는 키 10만 개에도 수십 메가바이트입니다.
그래서 실제 선택은 대개 버킷을 몇 개로 둘지입니다. 판정할 때 60개 값을 한 번의 왕복으로 받아올 수 있으면 1ms 예산에 들어옵니다. 값을 하나의 묶음 자료로 두고 필드를 나눠 쓰면 왕복이 늘지 않습니다.
그래서 요구사항을 다시 읽는다
여기서 판단이 갈립니다. 오차 5퍼센트 가 평균적으로 지켜야 하는 값인지, 최악에도 넘지 말아야 하는 값인지 요구사항이 말하지 않았습니다.
| 해석 | 결론 |
|---|---|
| 평균 기준 | 창 2개로도 충분하다. 실제 트래픽은 대개 고르다 |
| 최악 기준 | 창 2개는 탈락한다. 잘게 나눠야 한다 |
면접에서 이 질문을 되돌려 묻는 것이 좋은 신호입니다. 숫자가 적혀 있어도 그 숫자가 평균인지 최악인지에 따라 답이 바뀝니다.
이 요구사항에서는 최악에도 오차 5퍼센트 를 지키기로 보고 1초 버킷 60개를 고릅니다. 창 2개보다 저장이 30배지만 절대량이 작고, 어림하는 부분이 가장 오래된 1초로 줄어듭니다.
창 하나만 저장소에 남기면 된다
현재 창의 값을 올리면서 이전 창의 값을 함께 읽습니다. 이름이 규칙적이라 두 이름을 한 번에 요청할 수 있고, 이전 창은 다음 창이 시작될 때까지만 필요하므로 만료가 두 창 길이면 충분합니다.