🔗 연결된 이슈

• Connected: [refactor] 자료구조 + 알고리즘 도입 #410

📄 작업 내용

• 콜백 대기열 도입
• 디바운싱 매커니즘 추가
• 지수 백오프 알고리즘 사용

기존코드의 코드트리

변경코드 코드트리

💻 주요 코드 설명

주석은 머지시 모두 삭제할 예정이니 리뷰시에만 참고해주세요

기존 코드의 문제

기존 코드는 재귀적 호출 방식을 사용하여 토큰 갱신 요청을 처리하고 있었습니다.

if self.isRefreshing {
    DispatchQueue.global().asyncAfter(deadline: .now() + 0.1) {
        self.refreshToken(completion: completion)
    }
    return
}

이 코드는 토큰 갱신이 진행 중일 때 새로운 요청이 들어오면, 0.1초 지연 후 자기 자신(refreshToken)을 다시 호출하는 재귀적 패턴을 사용중이였습니다. 이렇게 했을때

• O(n) 시간 복잡도: n개의 동시 요청이 들어올 경우, 최악의 시나리오에서 refreshToken 함수는 n번 호출됩니다.(직렬 큐 이기에 무한반복)
• 불필요한 대기 시간: 각 재귀 호출마다 0.1초의 지연이 발생하여, 여러 요청이 있을 경우 마지막 요청은 (n-1) * 0.1초 동안 대기해야 합니다.
• 중복된 네트워크 요청: 특정 시나리오(위에서 언급한 경우)에서는 여러 개의 불필요한 네트워크 요청이 발생할 가능성이 있습니다.
• 깊은 호출 스택: 재귀 호출이 많이 발생하면 호출 스택이 깊어져 메모리 사용량이 증가합니다.

와 같은 문제가 발생했습니다.

매서운 알고리즘+ 자료구조의 도입!!

1. 콜백 대기열 도입

기존 코드는 각 요청마다 재귀적으로 함수를 호출했지만, 지금은 대기열 패턴을 도입했습니다:

// 대기 중인 콜백을 저장하는 배열 추가
private var pendingCompletions: [(Result<String, Error>) -> Void] = []

// 함수 내에서 콜백 저장
self.pendingCompletions.append(completion)

이렇게 변경해서

• 모든 요청이 단일 배열에 저장됩니다.
• 토큰 갱신이 한 번만 수행되어도 모든 요청에 응답할 수 있습니다.
• 호출 스택의 깊이가 일정하게 유지됩니다.

2. 디바운싱 메커니즘 추가

기존 코드는 항상 0.1초 지연 후 다시 시도했지만, 개선된 코드는 더 똑똑한 디바운싱 메커니즘을 도입했습니다:

// 디바운싱 매커니즘을 위한 work item
private var refreshWorkItem: DispatchWorkItem?

// 디바운싱 구현
self.refreshWorkItem?.cancel()
let workItem = DispatchWorkItem { [weak self] in
    guard let self = self else { return }
    self.performTokenRefresh(with: currentRefreshToken)
}
self.refreshWorkItem = workItem
DispatchQueue.global().asyncAfter(deadline: .now() + 0.02, execute: workItem)

이렇게 변경해서

• 짧은 시간(0.02초) 내에 들어오는 모든 요청이 하나의 작업으로 통합됩니다.
• 이전 대기 중인 작업이 취소되고 새 작업으로 대체됩니다.
• 0.1초보다 짧은 0.02초 지연으로 반응성이 향상됩니다.

3. 지수 백오프 알고리즘 도입

네트워크 실패 시 재시도 메커니즘으로 지수 백오프 알고리즘을 도입했습니다!

// 지수 백오프: 2^n * 100ms 대기
let delay = pow(2.0, Double(self.requestCount)) * 0.1
DispatchQueue.global().asyncAfter(deadline: .now() + delay) { [weak self] in
    // 재시도 로직
}

이렇게 변경해서

• 일시적인 네트워크 오류에 대한 복원력(?)을 향상시켯습니다
• 재시도 횟수를 제한하여 무한 루프를 방지합니다.

알고리즘 복잡도 개선

알고리즘 복잡도를 O(n)에서 O(1)로 감소시켰습니다.

기존 코드 (O(n)):

1. n개의 동시 요청이 들어오면
2. 첫 번째 요청이 처리되는 동안 다른 (n-1)개의 요청은 대기합니다.
3. 각 대기 요청은 재귀적으로 refreshToken을 호출합니다.
4. 최악의 경우, 호출 스택 깊이는 n에 비례하여 증가합니다.
5. 총 대기 시간은 0.1 * (n-1)초가 됩니다.

현재 코드 (O(1)):

1. n개의 동시 요청이 들어오면
2. 모든 콜백이 pendingCompletions 배열에 추가됩니다.
3. 디바운싱을 통해 단 한 번의 네트워크 요청만 수행됩니다.
4. 결과가 도착하면 모든 콜백이 한 번에 처리됩니다.
5. 호출 스택 깊이는 상수로 유지됩니다.
6. 총 대기 시간은 0.02초로 고정됩니다.

👀 기타 더 이야기해볼 점

알고리즘을 직접 프로젝트에 넣고 instruement로 직접 확인해보니 너무 재밋네요 여러분들도 해보세요!