I'm looking at building a message queuing library in Go, which will be used as part of a larger application. A doubly-linked-list seems like a sensible approach for an in-memory data structure, but let's say this list grows to be 4 million items and each item is 10k, things no longer are guaranteed to fit in memory, plus I need it to be persistent across restarts.
Most of the activity on the queue will be writing to the end and reading and deleting from the beginning, however there are cases where consuming a message may fail for reasons not related to the queue and the item needs to be moved to the end of the queue.
I'm familiar with some data structures that work well on disk for other specific cases. A log structured merge tree seems to be great for random access data, but not when the reads and writes are localized to the end and beginning of the tree (based on my understanding). B Trees and B+ Trees also seem intended more for random access and traversal.
Curious what algorithms or approaches exist that are already tailored to this problem.
NOTE: Regarding SQLite, one of my concerns is the compaction time. The queue contents are likely to be very high turnover and it's important that any sort of compaction that needs to be done can happen on a fairly large data set without a very large performance impact. I.e. if there are 4G worth of messages sitting the queue I don't want a scenario where things just lock up for 2 minutes while it does compaction, which is what I suspect is going to happen with SQLite.