I've found a hybrid model to be generically useful. Keep the first ~10 calls in a FIFO queue, and if that queue is full put additional calls into an LIFO stack

I've found a hybrid model to be generically useful. Keep the first ~10 calls in a FIFO queue, and if that queue is full put additional calls into an LIFO stack that functions as overflow storage. You can even reuse the same data structure and just flip the behavior under load, what's important is having FIFO behavior normally and then LIFO behavior when congestion occurs.