실전 JS 문제 중, Rate Limiter 구현 문제가 나왔다.
오늘은 해당 문제를 어떻게 풀었는지, 그리고 풀고 난 이후 어떻게 개선했는지 말해보겠다.
결론적으로 말하면 Rate Limiter를 Sliding Window Counter 방식으로 구현하였다.
Rate Limiter가 무엇인지 궁금하다면 이 글을 읽어주길 바란다!
문제 설명
-
/** * [(lv.5)api-요청-제한기.js] * * @param {number} maxRequests - 최대 허용 요청 수 * @param {number} timeWindow - 시간 윈도우 (ms) * @returns {(fn: () => Promise<any>) => Promise<any>} */
- 위의 형식대로 인자를 받고 반환하는 createRateLimiter 함수를 작성한다..
- 주어진 시간(timwWindow) 내에 최대 maxRequests 번까지 요청을 처리한다.
- 요청이 제한을 초과하면, 큐에 대기시켰다가 순차적으로 처리한다.
- 모든 요청은 Promise로 처리한다.
- 예시
-
// 예시: const rateLimitedRequest = createRateLimiter(2, 1000); // 1초에 최대 2개 요청 // 동시에 3개 요청 Promise.all([ rateLimitedRequest(() => fetch('/api/1')), // 즉시 실행 rateLimitedRequest(() => fetch('/api/2')), // 즉시 실행 rateLimitedRequest(() => fetch('/api/3')) // 1초 후 실행 ]);
-
첫 번째 풀이 - 유사 Token Bucket
처음에는 Token Bucket과 유사한 방식으로 createRateLimiter함수를 구현하였다.
어떻게 구현할지 생각하다가 들어온 작업을 모두 queue에 저장한 다음에, 현재 queue에 있는 작업들의 양을 보고 몇번째 timeWindow 뒤에 실행될지 생각하면 되겠다고 생각했다.
즉, 들어온 작업이 언제 처리될지 delay 시간을 구하는 것이다.
먼저, 작업이 들어오면 queue라는 이름의 배열에 저장해주었다.
실제로 queue를 구현하면 좋겠지만, 간단한 문제이므로 여기서는 배열을 사용하였다.
export function createRateLimiter(maxRequests, timeWindow) {
const queue = [];
return async function (task) {
queue.push(task);
};
}
이후 setInterval 메서드를 이용하여,
고정된 크기인 timeWindow 마다 queue에서 maxRequests의 만큼 queue에서 앞에서 부터 제거하였다.
export function createRateLimiter(maxRequests, timeWindow) {
const queue = [];
setInterval(() => {
for (let _ = 0; _ < maxRequests; _++) queue.shift();
}, timeWindow);
return async function (task) {
queue.push(task);
};
}
이렇게 되면 수행된 task는 queue에서 빠져나가게 된다.
이제 작업을 실행한 시간을 구해주면 된다.
queue의 크기에서 maxRequests 만큼 나누어주면 몇 번의 timeWindow 뒤에 해당 task가 수행될 지 알 수 있다.
그럼 해당 dalay 만큼 setTimeout 메서드를 통해 기다린 다음 task를 실행하고 반환하면 된다!
export function createRateLimiter(maxRequests, timeWindow) {
const queue = [];
setInterval(() => {
for (let _ = 0; _ < maxRequests; _++) queue.shift();
}, timeWindow);
return async function (task) {
queue.push(task);
const delay = Math.floor(queue.length / maxRequests) * timeWindow
return new Promise((resolve, reject) => {
setTimeout(() => {
try {
resolve(task());
} catch (e) {
reject(e);
}
}, delay);
});
};
}
현재 코드는 지연시간이 정확하지 않다.
만약에 정확히 setInterval이 이루어지는 시간이 아닌 기다리는 도중에 들어온다면,
지연 시간에서 이미 흐른 시간 만큼은 빼주어야 한다.
그렇게 완성된 코드는 아래와 같다!
export function createRateLimiter(maxRequests, timeWindow) {
const queue = [];
let now = Date.now();
setInterval(() => {
for (let _ = 0; _ < maxRequests; _++) queue.shift();
now = Date.now();
}, timeWindow);
return async function (task) {
queue.push(task);
const delay =
Math.floor(queue.length / maxRequests) * timeWindow +
(timeWindow - Date.now() + now);
return new Promise((resolve, reject) => {
setTimeout(() => {
try {
resolve(task());
} catch (e) {
reject(e);
}
}, delay);
});
};
}
현재 코드의 문제점은 아래와 같다.
- 메모리 관리 문제
- setInterval에 대해서 cleanup 메커니즘이 없어서 메모리 낭비가 된다.
- queue는 계속 커질 수 있는데 제한이 없다.
- 불필요한 shift 연산
- queue가 비어있을 때에도 setInterval 안에서는 계속 shift 연산을 수행한다.
이런 문제점을 가지고 해당 문제를 제출한 튜터님께 찾아갔다.
그리고 내 방식은 이런 문제가 있어서 수정이 필요한데, 튜터님은 어떻게 푸셨는지 여쭈어 봤다.
Rate Limiter를 재귀를 사용해서 구현하면 setInterval을 쓰지 않고도 해결할 수 있어요.
먼저 작업들을 requestQueue에 보관하고, 각 작업이 실행되는 시간은 requestTimes 배열에 기록해요.
requestTimes 배열의 크기를 확인해서 최대 요청 수보다 작다면, queue에서 작업을 하나 꺼내와서 바로 실행을 하죠.
반대로 최대 요청 수만큼 실행 중이라면, timeWindow 만큼의 시간을 기다려야 해요.
timeWindow가 지나고 나면 다시 위의 과정을 반복하는 거예요.
이렇게 재귀 호출로 계속해서 큐를 처리하는 방식이에요.
설명을 들었으니 이제 구현해볼 차례이다!
두 번째 풀이 - Sliding Window Counter
먼저, 지역변수로 requestQueue, requestTimes를 선언하고, 각 작업이 들어오면 requestQueue에 저장해주었다.
그리고 재귀 호출할 함수를 정의하였다.
export function createRateLimiter(maxRequests, timeWindow) {
const requestQueue = [];
const requestTimes = [];
return (taskFn) =>
new Promise((resolve, reject) => {
requestQueue.push({ taskFn, resolve, reject });
processQueue();
});
function processQueue() { }
}
이후 processQueue 함수 안에서 requestTimes의 크기가 maxRequests보다 작다면 queue에서 작업을 가져와 실행해주었다.
반대로 requestTimes의 크기가 maxRequest보다 크다면, setTimeout으로 timeWindow동안 기다리도록 하였다.
export function createRateLimiter(maxRequests, timeWindow) {
const requestQueue = [];
const requestTimes = [];
return (taskFn) =>
new Promise((resolve, reject) => {
requestQueue.push({ taskFn, resolve, reject });
processQueue();
});
function processQueue() {
let timestamp = Date.now();
if (requestTimes.length < maxRequests) {
const { taskFn, resolve, reject } = requestQueue.shift();
requestTimes.push(timestamp);
const response = taskFn();
Promise.resolve(response).then(resolve).catch(reject);
} else {
setTimeout(() => {
processQueue();
}, timeWindow);
}
}
}
현재 requestTimes 배열을 비워주고 있지 않아 timeWindow만큼 기다려도 작업이 실행되지 않는다.
이를 requestTimes 배열에서 timestamp보다 작은 값들은 삭제해주도록 하자.
function createRateLimiter(maxRequests, timeWindow) {
const requestQueue = [];
const requestTimes = [];
let timestamp = Date.now();
return (taskFn) =>
new Promise((resolve, reject) => {
requestQueue.push({ taskFn, resolve, reject });
processQueue();
});
function processQueue() {
while (requestTimes.length !== 0 && requestTimes[0] < timestamp)
requestTimes.shift();
if (requestTimes.length < maxRequests) {
const { taskFn, resolve, reject } = requestQueue.shift();
requestTimes.push(timestamp);
const response = taskFn();
Promise.resolve(response).then(resolve).catch(reject);
} else {
setTimeout(() => {
timestamp = Date.now();
processQueue();
}, timeWindow);
}
}
}
setTimeout은 비동기로 일어나는데, timestamp를 해당 부분에서 초기화하니 해당 부분에서 에러가 날 수도 있다.
예를 들어, 5개의 요청이 들어왔는데, maxRequests가 2인 상황을 가정해보자.
그러면 처음 2개는 바로 실행되지만 나머지 3개는 setTimeout 메서드를 통해 기다리게된다.
그리고 timeWindow 만큼 기다렸다가 timestamp를 갱신하고 processQueue를 다시 실행하는데, 이때 3번째 요청이 실행되서 requestTimes에 값이 들어갔는데, 4번째 요청의 기다린 시간이 끝나서 requestTimes로 들어왔다고 하면 3번째 요청을 삭제하게 된다.
이는 maxRequests의 값에 상관없이 task를 계속 실행할 수 있으므로 이를 수정해야한다.
따라서 timerIId라는 변수에 setTimeout의 반환값을 저장하고, setTimeout의 콜백 함수가 실행되면 timerId를 null로 설정하였다.
그리고 timerId의 값이 null이 아닐 때에는 setTimeout을 실행하지 않도록 하였다.
마지막으로 남은 작업에 대한 호출을 task를 실행하고 난 후 processQueue를 재실행하도록 하였다.
function createRateLimiter(maxRequests, timeWindow) {
const requestQueue = [];
const requestTimes = [];
let timeId = null,
timestamp = Date.now();
return (taskFn) =>
new Promise((resolve, reject) => {
requestQueue.push({ taskFn, resolve, reject });
processQueue();
});
function processQueue() {
while (requestTimes.length !== 0 && requestTimes[0] < timestamp)
requestTimes.shift();
if (requestTimes.length < maxRequests) {
const { taskFn, resolve, reject } = requestQueue.shift();
requestTimes.push(timestamp);
const response = taskFn();
Promise.resolve(response)
.then(resolve)
.catch(reject)
.finally(processQueue);
} else {
if (timeId) return;
timeId = setTimeout(() => {
timeId = null;
timestamp = Date.now();
processQueue();
}, timeWindow);
}
}
}
마지막으로 현재 코드는 requestQueue의 값이 없어도 계속 재귀구문을 돌기 때문에 처음에 requestQueue가 비어있으면 밑의 작업을 수행하지 않고 return 하도록 하자.
export function createRateLimiter(maxRequests, timeWindow) {
const requestQueue = [];
const requestTimes = [];
let timeId = null,
timestamp = Date.now();
return (taskFn) =>
new Promise((resolve, reject) => {
requestQueue.push({ taskFn, resolve, reject });
processQueue();
});
function processQueue() {
if (requestQueue.length === 0) return;
while (requestTimes.length !== 0 && requestTimes[0] < timestamp)
requestTimes.shift();
if (requestTimes.length < maxRequests) {
const { taskFn, resolve, reject } = requestQueue.shift();
requestTimes.push(timestamp);
const response = taskFn();
Promise.resolve(response)
.then(resolve)
.catch(reject)
.finally(processQueue);
} else {
if (timeId) return;
timeId = setTimeout(() => {
timeId = null;
timestamp = Date.now();
processQueue();
}, timeWindow);
}
}
}
그럼 완성하였다!
후기
처음 문제를 풀 때는 Rate Limiter에 대해서 알지 못 했고, 그저 주어진 정보로 구현하려고 노력했다.
하지만 블로그를 작성하면서 Rate Limiter에 찾아보게 되었고,
Rate Limiter의 여러 구현 방식들(Fixed Window Counter, Sliding Window Counter, Token Bucket)을 알게되었다.
이를 통해 내가 작성했던 코드가 어떤 설계 방식을 따르고 있었는지 더 명확하게 이해할 수 있어 좋았다!
'💻 개발 > JavaScript' 카테고리의 다른 글
| 바닐라 JS에서 알아보는 useState 동작 원리 및 간단한 구현 (1) | 2025.01.31 |
|---|---|
| ECMAScript와 함께 알아보는 실행 컨텍스트 (0) | 2025.01.23 |
| JavaScript로 구현하는 Rate Limiter : 효율적인 API 요청 (0) | 2025.01.17 |
| [JS] 비동기 처리: 콜백 지옥과 Promise, Async/Await (0) | 2025.01.10 |
| [JS] 구조 분해 할당과 일반 할당 (0) | 2025.01.08 |
