Hacker News new | past | comments | ask | show | jobs | submit login

LIFO queues with a timeout, and a retry after an exponential backoff with jitter is/was kind of standard for implementing queues at Google. More info in the Google SRE book: https://sre.google/sre-book/addressing-cascading-failures/#x...



The parent comment is asking why LIFO, and you’re responding “because Google does it.” I don’t think this response is helpful.


Alongside a link to Google's explanation of why they do it, that's a very reasonable and helpful reply. "Changing the queuing method from the standard first-in, first-out (FIFO) to last-in, first-out (LIFO) [...] can reduce load by removing requests that are unlikely to be worth processing"

For more detail, the document cites an article from Facebook (https://dl.acm.org/doi/10.1145/2838344.2839461):

> Most services process queues in FIFO (first-in first-out) order. During periods of high queuing, however, the first-in request has often been sitting around for so long that the user may have aborted the action that generated the request. Processing the first-in request first expends resources on a request that is less likely to benefit a user than a request that has just arrived. Our services process requests using adaptive LIFO. During normal operating conditions, requests are processed in FIFO order, but when a queue is starting to form, the server switches to LIFO mode. Adaptive LIFO and CoDel play nicely together, as shown in figure 2. CoDel sets short timeouts, preventing long queues from building up, and adaptive LIFO places new requests at the front of the queue, maximizing the chance that they will meet the deadline set by CoDel. HHVM3, Facebook’s PHP runtime, includes an implementation of the Adaptive LIFO algorithm.


Why is jitter important in a queue?


To avoid something called the thundering herd problem: https://en.m.wikipedia.org/wiki/Thundering_herd_problem

For instance, a bunch of clients all make a request to a server at the same time, briefly saturating the server. If all the clients have the same timeout without jitter, they will all try again together at the same time once the timeout expires, saturating the server again and again. Jitter helps by « spreading » those clients in time, thus « diluting » the server load. The server can then process these requests without saturating.


The basic idea behind that is also used in all sorts of networks where you have multiple stations sharing the same medium with everyone being able to freely send stuff. To solve this, if a "collision" is detected, stations then use a random timeout before they send again in the hope that the next time there won't be another collision.

https://en.wikipedia.org/wiki/Carrier-sense_multiple_access_...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: