https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/ Click here to return to Amazon Web Services homepage Contact Us Support English My Account Create an AWS Account * Products * Solutions * Pricing * Documentation * Learn * Partner Network * AWS Marketplace * Customer Enablement * Events * Explore More [ ] * `rby * Bahasa Indonesia * Deutsch * English * Espanol * Francais * Italiano * Portugues * Tieng Viet * Turkce * Russkii * aithy * Ri Ben Yu * hangugeo * Zhong Wen (Jian Ti ) * Zhong Wen (Fan Ti ) * AWS Management Console * Account Settings * Billing & Cost Management * Security Credentials * AWS Personal Health Dashboard * Support Center * Knowledge Center * AWS Support Overview Click here to return to Amazon Web Services homepage [ ] * Products * Solutions * Pricing * Introduction to AWS * Getting Started * Documentation * Training and Certification * Developer Center * Customer Success * Partner Network * AWS Marketplace * Support * Log into Console * Download the Mobile App Blog Home Category Edition Follow [ ] Architecture AWS Cost Management AWS Partner Network AWS Podcast AWS Marketplace AWS News Big Data Business Productivity Compute Contact Center Containers Database Desktop & Application Streaming Developer DevOps Enterprise Strategy Front-End Web & Mobile Game Tech HPC Infrastructure & Automation Industries Internet of Things Machine Learning Management & Governance Media Messaging & Targeting Modernizing with AWS Networking & Content Delivery Open Source Public Sector Quantum Computing Robotics SAP Security, Identity, & Compliance Startups Storage Training & Certification Zhong Guo Ban Edition Francaise Deutsche Edition Ri Ben Ban hangug edisyeon Edicao em Portugues Edicion en Espanol English Edition Versiia na russkom Edisi Bahasa Indonesia Mailing List RSS Feed AWS Architecture Blog Exponential Backoff And Jitter by Marc Brooker | on 04 MAR 2015 | in Architecture | Permalink | Share * * * * * [https://aws.amazon.c] Introducing OCC Optimistic concurrency control (OCC) is a time-honored way for multiple writers to safely modify a single object without losing writes. OCC has three nice properties: it will always make progress as long as the underlying store is available, it's easy to understand, and it's easy to implement. DynamoDB's conditional writes make OCC a natural fit for DynamoDB users, and it's natively supported by the DynamoDBMapper client. While OCC is guaranteed to make progress, it can still perform quite poorly under high contention. The simplest of these contention cases is when a whole lot of clients start at the same time, and try to update the same database row. With one client guaranteed to succeed every round, the time to complete all the updates grows linearly with contention. For the graphs in this post, I used a small simulator to model the behavior of OCC on a network with delay (and variance in delay), against a remote database. In this simulation, the network introduces delay with a mean of 10ms and variance of 4ms. The first simulation shows how completion time grows linearly with contention. This linear growth is because one client succeeds every round, so it takes N rounds for all N clients to succeed. [exponential-backoff-and-jitter-blog-figure-1] Unfortunately, that's not the whole picture. With N clients contending, the total amount of work done by the system increases with N2. [exponential-backoff-and-jitter-blog-figure-2] Adding Backoff The problem here is that N clients compete in the first round, N-1 in the second round, and so on. Having every client compete in every round is wasteful. Slowing clients down may help, and the classic way to slow clients down is capped exponential backoff. Capped exponential backoff means that clients multiply their backoff by a constant after each attempt, up to some maximum value. In our case, after each unsuccessful attempt, clients sleep for: [exponential-backoff-and-jitter-blog-figure-3] Running the simulation again shows that backoff helps a small amount, but doesn't solve the problem. Client work has only been reduced slightly. [exponential-backoff-and-jitter-blog-figure-4] The best way to see the problem is to look at the times these exponentially backed-off calls happen. [exponential-backoff-and-jitter-blog-figure-5] It's obvious that the exponential backoff is working, in that the calls are happening less and less frequently. The problem also stands out: there are still clusters of calls. Instead of reducing the number of clients competing in every round, we've just introduced times when no client is competing. Contention hasn't been reduced much, although the natural variance in network delay has introduced some spreading. Adding Jitter The solution isn't to remove backoff. It's to add jitter. Initially, jitter may appear to be a counter-intuitive idea: trying to improve the performance of a system by adding randomness. The time series above makes a great case for jitter - we want to spread out the spikes to an approximately constant rate. Adding jitter is a small change to the sleep function: [exponential-backoff-and-jitter-blog-figure-6] [exponential-backoff-and-jitter-blog-figure-7] That time series looks a whole lot better. The gaps are gone, and beyond the initial spike, there's an approximately constant rate of calls. It's also had a great effect on the total number of calls. [exponential-backoff-and-jitter-blog-figure-8] In the case with 100 contending clients, we've reduced our call count by more than half. We've also significantly improved the time to completion, when compared to un-jittered exponential backoff. [exponential-backoff-and-jitter-blog-figure-9] There are a few ways to implement these timed backoff loops. Let's call the algorithm above "Full Jitter", and consider two alternatives. The first alternative is "Equal Jitter", where we always keep some of the backoff and jitter by a smaller amount: [exponential-backoff-and-jitter-blog-figure-10] The intuition behind this one is that it prevents very short sleeps, always keeping some of the slow down from the backoff. A second alternative is "Decorrelated Jitter", which is similar to "Full Jitter", but we also increase the maximum jitter based on the last random value. [exponential-backoff-and-jitter-blog-figure-11] Which approach do you think is best? Looking at the amount of client work, the number of calls is approximately the same for "Full" and "Equal" jitter, and higher for "Decorrelated". Both cut down work substantially relative to both the no-jitter approaches. [exponential-backoff-and-jitter-blog-figure-12] The no-jitter exponential backoff approach is the clear loser. It not only takes more work, but also takes more time than the jittered approaches. In fact, it takes so much more time we have to leave it off the graph to get a good comparison of the other methods. [exponential-backoff-and-jitter-blog-figure-13] Of the jittered approaches, "Equal Jitter" is the loser. It does slightly more work than "Full Jitter", and takes much longer. The decision between "Decorrelated Jitter" and "Full Jitter" is less clear. The "Full Jitter" approach uses less work, but slightly more time. Both approaches, though, present a substantial decrease in client work and server load. It's worth noting that none of these approaches fundamentally change the N2 nature of the work to be done, but do substantially reduce work at reasonable levels of contention. The return on implementation complexity of using jittered backoff is huge, and it should be considered a standard approach for remote clients. All of the graphs and numbers from this post were generated using a simple simulation of OCC behavior. You can get our simulator code on GitHub, in the aws-arch-backoff-simulator project. TAGS: Scalability Marc Brooker Marc Brooker Marc Brooker is Senior Principal Engineer for AWS Serverless Applications. Resources AWS Architecture Center AWS Well-Architected AWS Architecture Monthly AWS Whitepapers AWS Training and Certification This Is My Architecture --------------------------------------------------------------------- Follow Twitter Facebook LinkedIn Twitch Email Updates Sign In to the Console Learn About AWS * What Is AWS? * What Is Cloud Computing? * AWS Inclusion, Diversity & Equity * What Is DevOps? * What Is a Container? * What Is a Data Lake? * AWS Cloud Security * What's New * Blogs * Press Releases Resources for AWS * Getting Started * Training and Certification * AWS Solutions Portfolio * Architecture Center * Product and Technical FAQs * Analyst Reports * AWS Partner Network Developers on AWS * Developer Center * SDKs & Tools * .NET on AWS * Python on AWS * Java on AWS * PHP on AWS * Javascript on AWS Help * Contact Us * AWS Careers * File a Support Ticket * Knowledge Center * AWS Support Overview * Legal Create an AWS Account Amazon is an Equal Opportunity Employer: Minority / Women / Disability / Veteran / Gender Identity / Sexual Orientation / Age. * Language * `rby * Bahasa Indonesia * Deutsch * English * Espanol * Francais * Italiano * Portugues * Tieng Viet * Turkce * Russkii * aithy * Ri Ben Yu * hangugeo * Zhong Wen (Jian Ti ) * Zhong Wen (Fan Ti ) * Privacy * | * Site Terms * | * Cookie Preferences * | * (c) 2021, Amazon Web Services, Inc. or its affiliates. All rights reserved.