Thundering herd problem

In computer science, the thundering herd problem occurs when a large number of processes or threads waiting for an event are awoken when that event occurs, but only one process is able to handle the event. When the processes wake up, they will each try to handle the event, but only one will win. All processes will compete for resources, possibly freezing the computer, until the herd is calmed down again.[1]

Mitigation

The Linux-kernel will serialize responses for requests to a single file descriptor, so only one thread (process) is woken up.[2] For epoll() in Linux 4.5 kernel version was added flag EPOLLEXCLUSIVE flag, thus several epoll sets (different threads or different processes) may wait on same resource and only one set will be woken up. For certain workloads this flag can given significant processing time reduction[3].

Similarly in Microsoft Windows, I/O completion ports can mitigate the thundering herd problem, as they can be configured such that only one of the threads waiting on the completion port is woken up when an event occurs.[4]

In systems which rely on a backoff mechanism (e.g. exponential backoff), the clients will retry failed calls, by waiting a specific amount of time between consecutive retries. In order to avoid the thundering herd problem, jitter can be purposefully introduced, in order to break the synchronization across the clients thereby avoiding collisions. In this approach, randomness is added to the wait intervals between retries, so that clients are no longer synchronized.

gollark: This isn't well-defined.
gollark: As a temporary solution it all got fed to one of our negative frequency trader machines, which will apply it to all financial markets simultaneously and thus keep it out of the way for a few years.
gollark: We tried feeding the capital into excess letters from the language models but then ran into Unicode concerns.
gollark: By some estimates, 3% of our processing power is spent on accounting.
gollark: No.

See also

References
  1. "Thundering Herd Problem". The Jargon File (version 4.4.7). Retrieved 9 July 2019.
  2. "Does the Thundering Herd Problem exist on Linux anymore". stackoverflow.com. Retrieved 2019-07-09.
  3. Madars, Vitolins (2015-12-05). "EPOLLEXCLUSIVE Linux Kernel patch testing". mvitolin. Retrieved 2020-08-11.
  4. "IO Completion Ports — Matt Godbolt's blog". xania.org. Retrieved 2019-01-23.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.