# Give Your Tail a Nudge

DevFeed: [Give Your Tail a Nudge](<https://devfeed.tech/articles/give-your-tail-a-nudge-12526.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2022/10/21/nudge.html>)

Author: Marc Brooker

Published: 2022-10-21T00:00:00Z

Content type: article

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [Latency](<https://devfeed.tech/topics/latency.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [systems](<https://devfeed.tech/topics/systems.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [latency](<https://devfeed.tech/tags/latency.md>), [systems](<https://devfeed.tech/tags/systems.md>)

## AI overview

The article examines Nudge, a scheduling mechanism intended to improve tail latency while retaining the benefits of First-Come First-Served (FCFS). Nudge swaps a newly arrived small job with a large job immediately ahead of it, while preventing jobs that have already swapped from swapping again. The author discusses the mechanism and evaluates it through simulation.

## Source excerpt

Give Your Tail a Nudge Tricks are fun. We all care about tail latency (also called high percentile latency, also called those times when your system is weirdly slow). Simple changes that can bring it down are valuable, especially if they don't come with difficult tradeoffs. Nudge: Stochastically Improving upon FCFS presents one such trick. The Nudge paper interests itself in tail latency compared to First Come First Served (FCFS)1, for a good reason: While advanced scheduling algorithms are a popular topic in theory papers, it is unequivocal that the most popular scheduling policy used in practice is still First-Come First-Served (FCFS). This is all true. Lots of proposed mechanisms, pretty much everybody still uses FCFS (except for some systems using LIFO2, and things like CPU and IO schedulers which often use more complex heuristics and priority levels3). But this simplicity is good: However, there are also theoretical arguments for why one should use FCFS. For one thing, FCFS minimizes the maximum response time across jobs for any finite arrival sequence of jobs. The paper then goes on to question whether, despite this optimality result, we can do better than FCFS. After all, minimizing the maximum doesn't mean doing better across the whole tail. They suggest a mechanism that does that, which they call Nudge. Starting with some intuition: The intuition behind the Nudge algorithm is that we'd like to basically stick to FCFS, which we know is great for handling the extreme tail (high 𝑡), while at the same time incorporating a little bit of prioritization of small jobs, which we know can be helpful for the mean and lower 𝑡. And going on to the algorithm itself: However, when a "small" job arrives and finds a "large" job immediately ahead of it in the queue, we swap the positions of the small and large job in the queue. The one caveat is that a job which has already swapped is ineligible for further swaps. Wow, that really is a simple little trick! If you prefer to t