How can something that “just works” be so annoying? situation We live in Cambridge off a little road down a drive in shared ownership between us and our neighbouring houses. All the utilities are buried under this drive, including the phone line. anticipation Over the last few years we have been canvassed repeatedly by CityFibre saying that they can deliver fibre all way to our house. I saw them digging trenches and leaving tails of purple fibre cladding along nearby roads, ready to hook up all the houses. I thought they would need to do something similar to deliver fibre to us. So when they turned up and knocked on our door, I talked to their salesbods and walked them up and down the drive and pointed out where the existing BT line goes. Then they gave up trying to sell to us. This happened about three times. disaffection We were not eager enough for an upgrade to deal with these impediments. notification A few months ago we were told that CityFibre would soon come and do the upgrade, since there’s a nationwide deadline for turning off the copper phone network at the end of the year. We expected that this would force them to actually plan some digging works, so we talked to our neighbours about it. We were all ready for some huge faff to follow the next visit by the CityFibre bods. installation CityFibre turned up on the promised morning bright and early. To our enormous surprise, a brown fibre housing was already poking out of the ground next to our copper phone line. It had been fed through 50 metres of 5cm duct without us being aware they were even working on the street. Within a couple of hours, the technicians had drilled through our wall, installed the ONT, blown fibre through the unexpected pipe, plugged in the CPE (superficially identical to the old one), and left telling us to anticipate that it might not work properly until tomorrow. activation Around lunch time, the copper phone line stopped working completely. Some faff ensued, switching all our devices over to the new WiFi network. For a while we thought this was the death of our land line, but in the course of debugging other issues, I realised that the router has a built-in VoIP adapter (I don’t think we were told it has a built-in VoIP adapter) so I plugged the phone in and it Just Worked: they had ported our phone number across and everything. Flawless. I was seriously impressed. rumination It has been a few weeks since the switchover, and apart from a couple of horrible Clown-afflicted IoT devices, it has been fairly smooth. What prompted me to write this up was realising that we delayed this upgrade for years because the sales people were not given enough technical information about how the installation process works: the fact that houses typically have a 5cm duct containing the copper lines (probably standard for the last 40 years) and the fact that fibre can be shoved through a few tens of metres without difficulty. And worse, the sales people didn’t have an esclation path for difficult cases: they just gave up instead. From a technical point of view, the installation was impeccable. (I guess the loose 24 hour window for the cutover time was because OpenReach and CityFibre don’t have tight requirements on ISP reconfiguration schedules.) From the sales point of view, it was crap. Maybe it would have gone faster if we offered to switch early without asking if the drive would be a problem? But I guess the difference between “yes!” and “yes, but will this be a problem?” is too much to expect from a minimum-wage door-to-door salesbod whose employer didn’t give them enough information or any escalation path.

Many years ago I wrote about how to convert Gregorian dates to Julian Day numbers or similar counts such as rata die as used in Calendrical Calculations. This algorithm is the core of C’s mktime() function that converts a broken-down date-time into linear time_t. I recently learned from Ben Joffe that I was missing a few tricks, and my old code wasn’t as good as it could have been. Here’s a better version (using conventional not C numbering): if m > 2 { m -= 2; } else { m += 10; y -= 1; } y*365 + y/4 - y/100 + y/400 + m*979/32 + d - 336 the main idea Julian years Gregorian correction the month pattern the epoch domains and ranges leap year test length of month the main idea There’s a helpful coincidence in the Gregorian calendar. Although the month lengths aren’t obviously regular, there’s a repeating 5 month pattern that becomes easier to see when you start from March, as illustrated by the table below. This pattern resets at the end of February, midway through its third repeat, coincidentally at the same point that leap days occur. Thus the first line of the code above adjusts the month and year numbers so that January and February are counted at the end of the previous year, and the coincidental alignment occurs at the boundary between the adjusted year numbers. I’ll explain the details of the adjustment as I discuss the relevant parts of the second line 31 days April 30 days May 31 days June 30 days July 31 days 31 days September 30 days October 31 days November 30 days December 31 days 31 days February 28 or 29 Julian years The first part of the main formula counts the number of days before the start of year y, in terms of normal years and leap days. y * 365 + y / 4 The adjustment subtracts one from the year in January and February. The effect is that the leap day in year 4 is counted as a day before the start of the adjusted beginning of year 4, i.e. before March, i.e. exactly the right place. I previously combined this part of the expression into a single term, y * 1461 / 4 Ben Joffe pointed out that when it is written this way the function is only able to make use of 25% of the range of its output data type, because the multiplication overflows for very large year numbers. And on modern CPUs it isn’t actually faster to eliminate the addition. Gregorian correction The next part corrects the number of leap years before the current year. - y/100 + y/400 It works in basically the same way as the Julian leap year calculation, but whereas y/4 trivially compiles to a simple shift operation, this needs a bit more cleverness. As Hacker’s Delight explains, a modern compiler will turn y/100 into a multiply-and-shift: y * (1<<N) * (1/25) >> (N+2) That is, the compiler uses a fixed-point representation of the reciprocal of the divisor. Then it uses common subexpression elimination to suppress the second multiplication by 1/25. So these two divisions are turned into a wide multiply and two shifts. Neat. the month pattern The next part counts the number of days in this (adjusted) year before the start of month m. m * 979 / 32 I previously wrote it using the number of days in the repeating pattern of 5 months, m * 153 / 5 But this is relatively difficult for compilers to optimize well (clang uses two multiplications instead of one), and they don’t know the range of m is limited, so we can do better by turning it into a multiply-and-shift by hand. 979/32 == 30.59375 which is close enough to the exact value 153/5 == 30.6 Either of these expressions produce the right 5 month long/short pattern, but the pattern doesn’t necessarily line up with the normal month numbering. (The two expressions above need different adjustments.) We move March to number 1, just before the start of the pattern. When counting the days before April, we get 31 more than the count for March; when counting the days before May, we get 30 more than the count for April, etc. January is adjusted to follow December to match the adjusted year numbering. m *979/32 diff -------------------- 1 30 March 2 61 31 April 3 91 30 May 4 122 31 5 152 30 6 183 31 7 214 31 8 244 30 9 275 31 10 305 30 December 11 336 31 January 12 367 31 13 397 30 the epoch Because calendars count from 1, the Gregorian date 0001-01-01 gets numbered rata die 1. The adjustments turn January into month 11, and so (as in the second column in the table above) we count 336 days in the adjusted year 0 before January. We need to subtract those extra days to compensate for the adjustment. We can change the offset to choose a different epoch, e.g. the MJD epoch 1858-11-17 is r.d. 678576, and the Unix epoch 1970-01-01 is r.d. 719163. domains and ranges In my old C code I casually used int, which misleadingly implied that it worked with proleptic Gregorian calendar dates before year 1. However signed division and modulus on common CPUs and low-level programming languages truncates towards zero, but this algorithm needs Euclidean or flooring division (which are equivalent for positive divisors). So it’s better to use u32 for these calculations. (Compilers also do a better job when this code uses unsigned integers.) To support negative years, a multiple of 400 years can be added to move year 0 to the middle of the u32 range, and subtracted from the return value to produce a signed count of days. leap year test Ben Joffe also examined fast leap year tests. My new favourite one is I think the neatest if not the fastest: if y % 25 == 0 { y % 16 == 0 } else { y % 4 == 0 } Note that 25 * 16 == 400, so it’s a leap year if it’s divisible by both 25 and by 16, else if it’s divisible by 4 but not by 25. The classic version of this check first tests divisibility by 100. CPUs that rely on branch prediction will correctly predict it 99% of the time: much better than the 75% you get from testing divisibilty by 4 first! But nowadays this if is compiled into a CMOV or CSEL (so branch prediction doesn’t matter), and divisibility by 25 is easier to compile than divisibility by 100. length of month What prompted me to revisit this code was the idea that it’s possible to work out a simpler multiply-and-shift optimization when the values have limited ranges (as in m*979/32 above) and/or when we don’t depend on the exact result of the multiplication. I previously wrote this code for calculating the length of a month: if m == 2 { 28 + is_leap_year(y) as u32 } else { 30 + (m * 275 % 9 > 3) as u32 } The multiply-and-shift idea led me to this replacement for months other than February: 30 + (m * 7 % 16 < 9) as u32 I found it by writing a brute force program that tries successive bitmask widths and multipliers, until it finds a case where all the long months produce results greater than all the short months, or vice versa (as in the winner). But there’s a neater expression, apparently due to Dr Matthias Kretz: 30 | (m ^ (m >> 3)) This uses two tricks: The 1 bit of the month number matches the odd/even long/short pattern in the months before August (month 8), when the phase flips. The flip is done by using the 8 bit to toggle the 1 bit. Bitwise or with 30 sets bits 2, 4, 8, 16 so the higher bits of the month number don’t matter. It compiles to just two ARM instructions: eor w0, w0, w0, lsr #3 orr w0, w0, #0x1e It’s so sweet I actually love how much better it is than my attempt!

A few weeks ago I was enjoying a couple of boiled eggs (in the shell, with plenty of salt and pepper, and buttery fingers of toast to dunk into the runny yolk) and pondering how fiddly it is to cut off one end of the shell after boiling compared to eating a poached egg. And I was annoyed because (I thought) I didn’t know how to poach eggs. misconceptions For decades I have been under the impression that poached eggs are difficult, because cheffy bods on the telly make such a fuss over cooking them. They led me to believe two falsehoods, both of which have a grain of truth, but it turns out they are not the overwhelming obstacles I thought. I decided to see what happens if I just don’t do any of the chef tricks. How bad could it be? If the poached eggs turned out to be a disaster, I would at least have confirmed what I believed. If not, I have added some delicious food to my repertoire. What did I believe? And what did I learn… If you just break an egg into boiling water, it’ll dissolve into a soupy mess? Yes the egg will spread out and the water will get messy, but almost all of the egg will hold together neatly by itself. If you don’t do the cheffy faff, your poached eggs will be inedible? In fact the fuss is mostly about levelling up from basic to restaurant-standard presentation. A no-fuss but frilly egg is still nice to eat. basic tricks The key trick for boiling an egg is to have plenty of boiling water in the pan before adding the eggs. That gives you a stable temperature and therefore predictable cooking times. To boil large hen eggs from room temperature, I aim for about 4 minutes for a runny yolk, or 8 minutes for a slightly fudgy hard-boiled yolk. For poached eggs, the water should be at a gentle simmer to avoid agitating the wispy white more than necessary. I add plenty of salt for seasoning. A cooking time of 3 minutes is about right. The key trick for poaching eggs is not to worry about the wispy whites in the water. It might be messy but it’ll be fine. Break the eggs near the surface of the water so they aren’t agitated too much from plunging in. When the surface of the white has started coagulating, give them a nudge to make sure they are moving enough to cook evenly and aren’t stuck to the bottom of the pan. Unlike a boiled egg, I can lift the poached egg out of the water with a slotted spoon and jiggle it to judge when it is ready, which is better than relying on my oven timer that can only be set in increments of a whole minute, and handy when I forget to set it… cheffy faff There are about half a dozen ways to improve the presentation of poached eggs. Use very fresh eggs, because they hold their shape better with less wispy white. I only have supermarket eggs, so egg age is not something I can control. Use a fine mesh strainer to separate the loose wispy white from the firm inner white. I think watching this trick taught me that raw eggs are a lot more cohesive and robust than I thought, and they don’t just dissolve into water. Get the water spinning like a vortex before adding the egg. Helen Rennie has a video on poaching eggs in which she discusses why this method is better in a restaurant (after about 6m10s). It requires a very large pot so it isn’t ideal for cooking a few portions at home. Break the egg into a small dish or ladle, so it can be introduced to the water more gently. This is worth doing but nevertheless I don’t bother :-) Add a little vinegar to the water. I don’t believe this has any effect on how the whites spread. It’s possible to use vinegar to coagulate the whites before poaching, but this requires a lot of vinegar and takes a long time, and harms the flavour of the eggs. Most of the spreading of a poached egg is due to turbulence when it plunges into the water, and it happens far too fast to be affected by a little vinegar. Wrap the egg in cling film. I don’t care enough about how neat my eggs are to fiddle with throwaway plastic and risk spilling egg in a clumsy mess. We have some reusable silicone things that cook eggs in a style somewhere between poached and coddled. We almost never use them because they are fiddly and tend to undercook the tops of the eggs even with a lid to keep the steam in. Trim the egg with a knife after cooking. Almost as wasteful as the strainer method! Or… don’t! thoughts In retrospect it’s curious that I was discouraged from even trying to poach eggs for such a long time, and that it took so little to discourage me. I suppose it illustrates how offputting extra steps can be to a beginner. It wasn’t clear to me which steps were optional and what were the consequences of omitting them. It’s something to keep in mind when writing documentation, I guess :-)

I’m writing a simulation, or rather, I’m procrastinating, and this blog post is the result of me going off on a side-track from the main quest. The simulation involves a bunch of tasks that go through a series of steps with delays in between, and each step can affect some shared state. I want it to run in fake virtual time so that the delays are just administrative updates to variables without any real sleep()ing, and I want to ensure that the mutations happen in the right order. I thought about doing this by representing each task as an enum State with a big match state to handle each step. But then I thought, isn’t async supposed to be able to write the enum State and match state for me? And then I wondered how much the simulation would be overwhelmed by boilerplate if I wrote it using async. Rather than digging around for a crate that solves my problem, I thought I would use this as an opportunity to learn a little about lower-level async Rust. Turns out, if I strip away as much as possible, the boilerplate can fit on one side of a sheet of paper if it is printed at a normal font size. Not too bad! But I have questions… async fn-damentals pin a task noop context primops, generally primops, minimally contexts and wakers primops, commandingly primops, yieldingly fake sleep in action questions async fn-damentals My starting point was to write: async fn deep_thought() -> u32 { 42 } fn main() { deep_thought(); } playground When I call deep_thought() I immediately get a Future<Output = u32>. As the compiler warns, none of the code in deep_thought() runs, it just constructs a value of an ineffable type which contains the initial state of deep_thought()’s state machine. To actually run it, I need to poll() it. The Future::poll() method has a signature that immediately presents a number of obstacles: fn poll( self: Pin<&mut Self>, ctx: &mut Context<'_>, ) -> Poll<Self::Output> pin a task Unlike normal Rust data structures, a Future can contain references to itself. (In a Rust function, variables can refer to other variables, and a Future contains (roughly speaking) function activation frames, hence it can be self-referential.) So, whereas normal Rust data types can be moved, a Future must stay at the same address even when it is not borrowed. The Pin type is used to immobilize a Future. For my purposes it’s easiest to Pin the Future in a Box on the heap. I’ll define a struct Task to wrap the Pinned Future so that I can define a couple of methods on it. (More elaborate async frameworks usually have more layers between their version of Task and its Future.) This wrapper is generic over the ineffable Fut type and its ultimate return type Out (which for deep_thought() is u32). struct Task<Fut> { future: Pin<Box<Fut>>, } impl<Fut, Out> Task<Fut> where Fut: Future<Output = Out>, { fn spawn(future: Fut) -> Self { let future = Box::pin(future); return Task { future }; } } Constructing a Task looks like, let mut task = Task::spawn(deep_thought()); noop context The second argument to poll() is a Context, which is a wrapper around a Waker. The simplest way to make a Context is by using Waker::noop(), which is enough for us to get deep_thought() to actually run. As in the fake-time simulation that I am procrastinating, 7.5 million years pass in the blink of an eye. let mut ctx = Context::from_waker(Waker::noop()); match task.future.as_mut().poll(&mut ctx) { Poll::Pending => { todo!(); } Poll::Ready(answer) => { println!("the answer is {answer}"); } } playground primops, generally An async function can call another async function, and (in async code just like in normal code) the called async function does nothing but return a Future. To make it do something, the caller needs to .await the Future. Under the covers .await compiles down to poll()ing the Future. A chain of async .await calls bottoms out in a primitive operation that interacts with the outside world. A primitive async operation is an impl Future state machine data structure, written manually instead of relying on compiler trickery. Typically, a primitive Future will be poll()ed twice: The first time, it arranges for the operation to happen then returns Poll::Pending. The async executor suspends this Task while the operation proceeds. After the operation is complete the async executor resumes the Task by poll()ing it, which immediately becomes a second poll() on on the primitive Future. This time it returns Poll::Ready() with the result of the operation, which becomes the value returned by .await. A primitive Future can implement a more complicated state machine that needs to be poll()ed more, but twice is the minimum necessary to actually suspend a Task. primops, minimally Continuing my approach of doing the least possible thing to illustrate a point, here’s a stub Future that pretends to sleep. Its trivial state machine is encoded in the delay value: if it’s zero, the Future continues without suspending; if it’s non-zero, the Future suspends, but first resets the delay so that next time it will continue. struct Sleep(u32); impl Future for Sleep { type Output = (); fn poll( mut self: Pin<&mut Self>, _: &mut Context<'_> ) -> Poll<()> { if self.0 > 0 { self.0 = 0; return Poll::Pending; } else { return Poll::Ready(()); } } } As an example of using it, deep_thought() can pretend to spend a long time by constructing a Sleep() object (which is our minimal state machine) then .await it to invoke poll(). async fn deep_thought() -> u32 { Sleep(7_500_000).await; 42 } And the main loop now needs to poll() the Task twice to run it to completion. loop { match task.future.as_mut().poll(&mut ctx) { Poll::Pending => { println!("sleeping for 7.5 million years..."); } Poll::Ready(answer) => { println!("the answer is {answer}"); return; } } } playground contexts and wakers In that minimal proof-of-concept, the fake Sleep primitive does not actually do anything other than suspend the Task, and the top-level async executor loop blithely assumes it knows why the Task was suspended. The purpose of the Context and its inner Waker is to allow a primitive Future to communicate with the async executor loop: to arrange for the operation to happen, and suspend the Task while the operation proceeds. So for my fake Sleep to account for the passing of fake time, I need to construct my own Waker that does something more useful than Waker::noop(). I believe the design intent is that a Waker is roughly speaking a wrapper round a smart pointer that refers to the current Task. When a primitive Future suspends a task, it stashes the Waker with the operation in progress. When the operation completes, the Waker is told to wake() its Task, which puts it back on the async executor’s loop to be poll()ed. To make a Waker, I need to make a RawWaker: pub const unsafe fn Waker::from_raw( waker: RawWaker ) -> Waker; pub const fn RawWaker::new( data: *const (), vtable: &'static RawWakerVTable ) -> RawWaker; This is dismaying, it’s like hand-rolled object-oriented C. Instead of a type-safe dyn Trait, I have to cruft something together from a raw pointer, a list of functions in a struct, and unsafe code. At this point I got stuck, despondently trying to work out how my Tasks and executor loop should refer to each other, and what kind of smart pointer I can smuggle through a raw *const() pointer. Eventually I realised there’s a simpler way. primops, commandingly There are a couple of ways that a primitive Future can arrange for an operation to happen: It can immediately make system calls and mutate global data structures to fire off the operation, before suspending itself by returning Poll::Pending. This requires that difficult tangle of smart pointers. Or instead it can suspend itself first, returning a command that the async executor will carry out on the Task’s behalf. This is awkward because Poll::Pending cannot carry a payload. However, the Context provides a side-channel that I can use to smuggle out a return value. In imaginary safe Rust, a Task can return a Command roughly as follows: The executor loop prepares a place-holder variable for the command. let mut cmd = Command::Run; It poll()s the Task, passing a mutable borrow of the command. let p = task.future.as_mut().poll(&mut cmd); When a primitive Future wants to perform an operation, it overwrites the command before suspending the Task. fn poll( mut self: Pin<&mut Self>, cmd: &mut Command ) -> Poll<()> { *cmd = Command::Example; return Poll::Pending; } When the async executor loop gets Poll::Pending from poll(), it looks at the command to decide what to do with the Task. In real Rust I need to smuggle the borrowed &mut cmd through the RawWaker’s raw *const() pointer. Since I’m not using the Waker to revive the Task when its operation completes, I can reuse the RawWakerVTable from Waker::noop(). primops, yieldingly I’ll define a Yield type that combines the primitive commands and Poll::Ready() in one enum, and I’ll fix the top-level task’s return type to Future<Output = ()>. (Too much boilerplate is needed to keep the Output type generic.) “Yield” has a dual meaning: the result returned (yielded) from an activity; and the task relinquishing (yielding) the CPU. #[derive(Copy, Clone, Debug)] enum Yield { Run, Sleep(u32), // maybe other commands here Done(), } The async executor loop calls poll() on a Task, which creates a place-holder Yield and stashes a pointer to it in a fresh Context. impl<Fut> Task<Fut> where Fut: Future<Output = ()>, { fn poll(&mut self) -> Yield { let mut yld = Yield::Run; let data = &mut yld as *mut Yield as *const (); let vtable = Waker::noop().vtable(); let waker = unsafe { Waker::new(data, vtable) }; let mut ctx = Context::from_waker(&waker); match self.future.as_mut().poll(&mut ctx) { Poll::Pending => yld, Poll::Ready(()) => Yield::Done(), } } } The Yield type is also used as the direct representation of a primitive Future. An async function constructs a Yeild and .awaits it, which causes the Yield to be returned via the Context to the async executor’s loop. Before suspending, the Future Yield is reset to Yield::Run so that execution continues the next time the Task is poll()ed. (Analogous to resetting the Sleep delay to zero in the previous example.) impl Future for Yield { type Output = (); fn poll( mut self: Pin<&mut Self>, ctx: &mut Context<'_>, ) -> Poll<Self::Output> { if let Yield::Run = *self { return Poll::Ready(()); } else { let yld = ctx.waker().data() as *mut Yield; let yld = unsafe { yld.as_mut().unwrap() }; *yld = *self; *self = Yield::Run; return Poll::Pending; } } } There’s more discussion of the unsafe code below. fake sleep in action The async executor loop needs to carry out the commands Yielded by its tasks. The classic data structure for timers is a min-heap keyed on the wake-up time; fake time is just a normal timer queue without any actual sleeping or delays between wake-up times. After augmenting my Task type with a wake-up time, I can write my main program roughly like this sketch: let mut tasks = BinaryHeap::new(); for i in 1..=TASKS { tasks.push(Task::spawn(activity(i, LIMIT))); } while let Some(mut task) = tasks.pop() { match task.poll() { Yield::Sleep(delay) => { task.wake_up += delay; tasks.push(task); } Yield::Done() => { // drop completed task } yld => panic!("unexpected {yld:?}"), } } The main program spawns some activity()s that sleep in a loop for differing amounts of time. They report their progress to stdout. For this demo I want the tasks to print synchronously (no async IO!) to illustrate the progress of their state machines. This demo is greatly simplified but roughly the same shape as the fake-time simulation that I’m procrastinating. async fn activity(delay: u32, stop: u32) { let mut now = 0; println!("{now} {delay} start"); loop { Yield::Sleep(delay).await; now += delay; if now < stop { println!("{now} {delay} continue"); continue; } else { println!("{now} {delay} return"); return; } } } You can see the complete demo in action at the Rust playground. Task 1 wakes up every tick, task 2 every other tick, etc. questions I don’t know why a Waker isn’t just an abstract generic type parameter with some trait bounds, so that I could define it using safe code. As far as I can tell the language and the standard library don’t depend on its exact shape, so I would expect the details to be punted to async runtime libraries. I guess there’s something I’m missing that requires the standard library to partially restrict the shape of a Waker. There are some weaknesses in my unsafe code. Miri says the code is OK, which agrees with my handwavy correctness argument by analogy with a mutable borrow. However I’m not certain that the compiler is guaranteed to know that yld can be mutated by poll(). An alternative might be to return the mutated Yield from Task::poll() by reconstructing the &mut Yield reference from the Context in the same manner as Yield::poll(). But then I’m not certain the compiler will know that the borrowed yld needs to live all the way to the end of the function. For now I’ve chosen the shorter code. Having learned how to do it myself, I’m curious to hear of crates that already solve this problem.

A while back I wrote about the linear rate limit algorithms leaky bucket and GCRA. Since then I have been vexed by how common it is to implement rate limiting using complicated and wasteful algorithms (for example). But linear (and exponential) rate limiters have a disadvantage: they can be slow to throttle clients whose request rate is above the limit but not super fast. And I just realised that this disadvantage can be unacceptable in some situations, when it’s imperative that no more than some quota of requests is accepted within a window of time. In this article I’ll explore a way to enforce rate limit quotas more precisely, without undue storage costs, and without encouraging clients to oscillate between bursts and pauses. However I’m not sure it’s a good idea. linear reaction time fixed window quota resets hybrid quota-linear algorithm discussion opinion linear reaction time How many requests does a linear rate limiter allow before throttling? The parameters for a rate limiter are: q, the permitted quota of requests w, the accounting time window So the maximum permitted rate is q/w. Let’s consider a client whose rate is some multiple a > 1 of the permitted rate (a for abuse factor) c = a * q/w I’ll model the rate limiter as a token bucket which starts off with q tokens at time 0. The bucket accumulates tokens at the permitted rate and the client consumes them at its request rate. (It is capped at q tokens but we can ignore that detail when a > 1.) b(t) = q + t*q/w - t*a*q/w The time taken for n requests is t(n) = n/c = (n*w) / (a*q) After n requests the bucket contains b(n) = q + n/a - n The rate limter throttles the client when the bucket is empty. b(t) = 0 = q + t * (1 - a) * q/w 0 = 1 - t * (a - 1) / w t = w / (a - 1) b(n) = 0 = q + n * (1/a - 1) 0 = q - n * (a - 1) / a n = q * a / (a - 1) For example, if the client is running at twice the permitted rate, a=2, they will be allowed q*2 requests within w seconds before they are throttled. That’s a bit slow. The problem is that the bucket starts with a full quota of tokens, and during the first window of time another quota-full is added. So a linear rate limiter seems to be more generous in its startup phase than its parameters suggest. fixed window quota resets This is a fairly common rate limit algorithm that enforces quotas more precisely than linear rate limiters. It is similar to a token bucket, but it resets the bucket to the full quota q after each window w. The disadvantage of periodically resetting the bucket is that careless clients are likely to send a fast burst of requests every window. (A linear rate limiter will tend to smooth out requests from careless clients, though it can’t prevent deliberately abusive burstiness.) And a quota-reset rate limiter uses more space than a linear rate limiter: it needs a separate bucket counter as well as a timestamp. each client has the time when its window started and a bucket of tokens if c == NULL c = new Client c.bucket = quota c.time = now reset the bucket when the window has expired if c.time + window <= now c.bucket = quota c.time = now the request is allowed if the client has a token to spend if c.bucket >= 1 c.bucket -= 1 return ALLOW else return DENY hybrid quota-linear algorithm The idea is to have two operating modes: Low-traffic clients are allowed to make bursts of requests, because that’s good for interactive latency. High-traffic clients are required to smooth out their requests to an even rate. The algorithm switches to smooth mode when a client consumes its entire quota and the bucket reaches zero, and switches back to bursty mode when the bucket recovers to a full quota. Bursty mode avoids being too generous by adding at most one quota of tokens to the bucket per window. Smooth mode also avoids being too generous by starting with an empty bucket. I’ve written this pseudocode in a repetitive style because that makes each paragraph more independent of its context, though it is still somewhat stateful and the order of the clauses matters. the rate limit is derived from the quota and window rate = quota / window a client that returns after a long absence is reinitialized like a new client; in bursty mode the time is the start of a fixed window and the bucket contains a whole number of tokens; we subtract one from the quota to account for the current request fn reset() c.bucket = quota - 1 c.time = now c.mode = BURSTY return ALLOW initialize the state of a new client if c == NULL c = new Client return reset() reset the state when a bursty client’s window has expired if c.mode == BURSTY and c.time + window <= now return reset() when a client consumes its last token, switch modes; in smooth mode the time is updated for every request and the bucket can hold fractional tokens; apply a negative penalty so we don’t allow any over-quota requests before the end of the fixed window; add one to allow the next request at the start of the next window if c.mode == BURSTY and c.bucket == 1 remaining = c.time + window - now c.bucket = -remaining * rate + 1 c.time = now c.mode = SMOOTH return ALLOW smooth mode accumulates tokens proportional to the time since the client’s previous request; update the request time so that tokens accumulate at the same rate whether the request is allowed or denied if c.mode == SMOOTH c.bucket += (now - c.time) * rate c.time = now when the bucket has refilled, switch back to bursty mode if c.mode == SMOOTH and c.bucket >= quota return reset() we have dealt with all the special cases; in either mode the request is allowed if the client has a token to spend if c.bucket >= 1 c.bucket -= 1 return ALLOW else return DENY discussion This hybrid algorithm has a similar effect to running both a quota-reset and a linear rate limiter in parallel, but it uses less space. The precision of quota enforcement in smooth mode is maybe arguable: It guarantees that the client remains below the limit on average over the whole time it is in smooth mode. But if it slows down for a while (but not long enough to return to bursty mode) it can speed up again and make more requests than its quota within a window. opinion I think it’s a mistake to try to treat each time window in strict isolation when assessing a client’s request quota. A linear rate limiter only seems to be unduly generous on startup if you ignore the fact that the client was quiet in the previous window. As well as being more expensive than necessary (in some cases disgracefully wasteful), algorithms like sliding-window and quota-reset encourage clients into cyclic burst-pause behaviour which is unhealthy for servers. And I’ve seen developers complaining about how annoying it is to use glut/famine rate limiters. By contrast, rate limiters that measure longer-term average behaviour by keeping state across multiple windows can naturally encourage clients to smooth out their requests. So on balance I think that instead of using this hybrid quota-linear rate limiter, you should reframe your problem so that you can use a simple linear rate limiter like GCRA.