[awsblog]exponential backoff

OCC 소개

OCC(Optimistic concurrency control)는 여러 작성자가 쓰기 손실 없이 단일 개체를 안전하게 수정할 수 있는 유서 깊은 방법입니다. OCC에는 세 가지 좋은 속성이 있습니다. 기본 저장소를 사용할 수 있는 한 항상 발전하고 이해하기 쉽고 구현하기 쉽습니다. DynamoDB의 조건부 쓰기는 OCC를 DynamoDB 사용자에게 자연스럽게 적합하게 하며 DynamoDBMapper 클라이언트에서 기본적으로 지원합니다.

OCC는 진행 상황이 보장되지만 높은 경합에서는 여전히 성능이 좋지 않을 수 있습니다. 이러한 경합 사례 중 가장 간단한 것은 많은 클라이언트가 동시에 시작하여 동일한 데이터베이스 행을 업데이트하려고 하는 경우입니다. 매 라운드마다 한 클라이언트의 성공이 보장되기 때문에 모든 업데이트를 완료하는 데 걸리는 시간은 경합과 함께 선형적으로 늘어납니다.

이 게시물의 그래프에서는 원격 데이터베이스에 대해 지연(및 지연 편차)이 있는 네트워크의 OCC 동작을 모델링하기 위해 작은 시뮬레이터를 사용했습니다. 이 시뮬레이션에서 네트워크는 평균이 10ms이고 분산이 4ms인 지연을 도입합니다. 첫 번째 시뮬레이션은 완료 시간이 경합과 함께 선형적으로 증가하는 방식을 보여줍니다. 이 선형 성장은 한 클라이언트가 모든 라운드에 성공하므로 N 클라이언트 모두가 성공하려면 N 라운드가 필요하기 때문입니다.

불행히도 그것이 전체 그림이 아닙니다. N 클라이언트가 경합하는 경우 시스템이 수행하는 총 작업량은 N2와 함께 증가합니다.

백오프 추가

여기서 문제는 N 클라이언트가 첫 번째 라운드에서 경쟁하고 N-1이 두 번째 라운드에서 경쟁하는 식이라는 것입니다. 모든 고객이 모든 라운드에서 경쟁하게 하는 것은 낭비입니다. 클라이언트 속도를 늦추는 것이 도움이 될 수 있으며 클라이언트 속도를 늦추는 고전적인 방법은 기하급수적 백오프로 제한됩니다. Capped exponential backoff는 클라이언트가 각 시도 후 최대값까지 백오프를 상수로 곱하는 것을 의미합니다. 우리의 경우 각 시도가 실패한 후 클라이언트는 다음을 위해 잠자기 상태입니다.

시뮬레이션을 다시 실행하면 백오프가 약간 도움이 되지만 문제가 해결되지는 않습니다. 클라이언트 작업은 약간만 줄어들었습니다.

문제를 확인하는 가장 좋은 방법은 이러한 기하급수적으로 중단된 호출이 발생하는 시간을 살펴보는 것입니다.

호출이 점점 덜 자주 발생한다는 점에서 지수 백오프가 작동하고 있음이 분명합니다. 문제는 또한 두드러집니다. 여전히 호출 클러스터가 있습니다. 모든 라운드에서 경쟁하는 클라이언트의 수를 줄이는 대신 경쟁하는 클라이언트가 없는 시간을 도입했습니다. 네트워크 지연의 자연스러운 변화로 인해 약간의 확산이 발생했지만 경합은 많이 줄어들지 않았습니다.

지터 추가

해결책은 백오프를 제거하는 것이 아닙니다. 지터를 추가하는 것입니다. 처음에 지터는 임의성을 추가하여 시스템의 성능을 향상시키려는 직관적이지 않은 아이디어로 보일 수 있습니다. 위의 시계열은 지터에 대한 좋은 사례입니다. 우리는 스파이크를 거의 일정한 속도로 분산시키고자 합니다. 지터를 추가하면 절전 기능이 약간 변경됩니다.

그 시계열이 훨씬 좋아 보입니다. 격차가 사라지고 초기 급증 이후에는 거의 일정한 통화 비율이 있습니다. 총 호출 횟수에도 큰 영향을 미쳤습니다.

100명의 경쟁 클라이언트가 있는 경우 통화 수를 절반 이상 줄였습니다. 또한 지터가 없는 지수 백오프와 비교할 때 완료 시간을 크게 개선했습니다.

이러한 시간 제한 백오프 루프를 구현하는 몇 가지 방법이 있습니다. 위의 알고리즘을 "Full Jitter"라고 부르고 두 가지 대안을 고려해 보겠습니다. 첫 번째 대안은 "Equal Jitter"로, 항상 약간의 백오프와 지터를 유지합니다.

이것의 이면에 있는 직관은 그것이 매우 짧은 수면을 방지하고 항상 백오프로부터 속도 저하를 일부 유지한다는 것입니다. 두 번째 대안은 "Full Jitter"와 유사하지만 마지막 임의 값을 기반으로 최대 지터를 증가시키는 "Decorrelated Jitter"입니다.

어떤 접근 방식이 가장 좋다고 생각합니까?

클라이언트 작업량을 살펴보면 "Full" 및 "Equal" 지터의 경우 호출 수가 거의 같고 "Decorrelated"의 경우 더 많습니다. 두 가지 모두 지터가 없는 접근 방식에 비해 작업을 상당히 줄였습니다.

지터가 없는 지수 백오프 접근 방식은 명백한 패배자입니다. 그것은 더 많은 작업을 필요로 할 뿐만 아니라 지터 방식보다 더 많은 시간을 필요로 합니다. 사실, 다른 방법을 잘 비교하기 위해 그래프에서 벗어나는 데 훨씬 더 많은 시간이 걸립니다.

지터 방식 중 "Equal Jitter"는 패자입니다. "Full Jitter"보다 약간 더 많은 작업을 수행하고 훨씬 더 오래 걸립니다. "Decorrelated Jitter"와 "Full Jitter" 사이의 결정은 덜 명확합니다. "전체 지터" 접근 방식은 작업을 덜 사용하지만 약간 더 많은 시간을 사용합니다. 그러나 두 접근 방식 모두 클라이언트 작업과 서버 부하를 상당히 감소시킵니다.

이러한 접근 방식 중 어느 것도 수행할 작업의 N2 특성을 근본적으로 변경하지 않지만 합리적인 수준의 경합에서 작업을 크게 줄이지는 않습니다. 지터 백오프 사용의 구현 복잡성에 대한 수익은 엄청나며 원격 클라이언트에 대한 표준 접근 방식으로 간주되어야 합니다.

이 게시물의 모든 그래프와 숫자는 OCC 동작의 간단한 시뮬레이션을 사용하여 생성되었습니다. GitHub의 aws -arch-backoff-simulator 프로젝트 에서 시뮬레이터 코드를 얻을 수 있습니다 .

 

 

Reference

 

https://aws.amazon.com/ko/blogs/architecture/exponential-backoff-and-jitter/

Exponential Backoff And Jitter | Amazon Web Services