6

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.

Brad Peabody
  • 239
  • 1
  • 7
  • 1
    "*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.*" -> This seems a fairly easy thing to test and benchmark. If you're designing a system to work with that scale of numbers, you shouldn't rely just on "suspect". You may be a victim of [premature optimization](http://wiki.c2.com/?PrematureOptimization). – Machado Jun 01 '17 at 20:52
  • Also, what specifically are you trying to solve ? If you just want a persistent queue, there are already several solutions capable of handling that. Which technology / platforms are you targeting ? – Machado Jun 01 '17 at 20:55
  • @Machado valid point. Just trying to know as much as possible as early as possible. SQLite compaction time is definitely a known and documented issue, e.g.: https://blogs.gnome.org/jnelson/2015/01/06/sqlite-vacuum-and-auto_vacuum/ I'm trying to embed it in a Go application - should run on all platforms Go supports (calling C or C++ code from Go is a workable approach as well). The messages will vary in size from < 1k to maybe 10MB. – Brad Peabody Jun 01 '17 at 20:58
  • Are you able to run with a filesystem as well or are you constrained to a single file for persistence ? I mean, in your algorithm can you span multiple files and delete them as pleased or you have to allocate a single contiguous space (like 2GB) and stick with it ? – Machado Jun 02 '17 at 12:14
  • I'm being annoying asking questions because of the requirements you stated. 4 billion messages, at 10MB each, that would be something like 40 petabytes of data lying around waiting to be processed. That doesn't seem something doable with a -Lite product. You're trying to create a solution that may handle from 4TB (4Gx1k) to 40PB (4Gx10MB) on the same solution, and this is no simple task. – Machado Jun 02 '17 at 12:36
  • @Machado I see. I'm not constrained to a single file, but ideally a single directory. That however is not a strict requirement. The only hard requirement is that it does not require separate installation or system level service management in order to operate. It should run in-process, but theoretically even that is not a 100% strict requirement. You're right, I'm not looking at 40PB of data - primarily because that exceeds the capacity of normal machines. I'm looking at a case of majority disk usage on a machine that might be a node in a cluster e.g. 2-4TB. – Brad Peabody Jun 02 '17 at 15:33
  • That seems more reasonable. But even then, 2TB of data is a lot. Do you have a explicit range of possible message sizes ? I mean, they'll be all over the place (1k, 2MB, 10MB, 527k, etc...) or is it something you can control ? I'm asking because one of the things some DBAs and developers usually discuss is about the "page size", where a single IO could read an entire document or row of data. – Machado Jun 02 '17 at 15:59
  • Unfortunately I do not have control over the message sizes - it's based on user input. There will be some hard cap around 10MB, but also an average message size would probably be more like 5k (think email messages). The max message size is low enough that we can guarantee that there will never be a message that doesn't fit in memory, if that helps. – Brad Peabody Jun 02 '17 at 16:07
  • Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/59753/discussion-between-machado-and-brad-peabody). – Machado Jun 02 '17 at 16:34

3 Answers3

4

I think I have enough information to provide an answer. It may not be what you're looking for, though.

From what we discussed and I understood, we have the following scenario:

  • Large number of messages to be processed;
  • Persistence needed to handle clean reboots (I'm not talking about power surges or power outages);
  • Inconsistent size of each message;
  • A need for FIFO structure;
  • Possibility of using the filesystem as storage;
  • Need to be portable, within go supported environments (MacOS, Linux, Windows);
  • Need to be self-hosted, cannot use an external queue provider;

That being said, I'd architect something that would rely 100% on the filesystem.

Store each message as a single file, name them with a timestamp or a counter you can control from a reliable source and leverage the filesystem capabilities for you.

You would be limited by what the filesystem can do for you (number of files per directory, number of directories per disk, maximum size per file, etc.), but it's very flexible, easy to debug and monitor and extremely portable and flexible, allowing you to increase the speed of your IO by just changing hardware around (HD -> SSD -> Raid -> Storage Server, etc.).

You will have to study different filesystems to push each one to the limits, but the most common ones can handle these requirements very well:

Data below copied from the excellent answer on StackOverflow:

FAT32:

  • Maximum number of files: 268,173,300
  • Maximum number of files per directory: 216 - 1 (65,535)
  • Maximum file size: 2 GiB - 1 without LFS, 4 GiB - 1 with

NTFS:

  • Maximum number of files: 232 - 1 (4,294,967,295)
  • Maximum file size
    • Implementation: 244 - 26 bytes (16 TiB - 64 KiB)
    • Theoretical: 264 - 26 bytes (16 EiB - 64 KiB)
  • Maximum volume size
    • Implementation: 232 - 1 clusters (256 TiB - 64 KiB)
    • Theoretical: 264 - 1 clusters

ext2:

  • Maximum number of files: 1018
  • Maximum number of files per directory: ~1.3 × 1020 (performance issues past 10,000)
  • Maximum file size
    • 16 GiB (block size of 1 KiB)
    • 256 GiB (block size of 2 KiB)
    • 2 TiB (block size of 4 KiB)
    • 2 TiB (block size of 8 KiB)
  • Maximum volume size
    • 4 TiB (block size of 1 KiB)
    • 8 TiB (block size of 2 KiB)
    • 16 TiB (block size of 4 KiB)
    • 32 TiB (block size of 8 KiB)

ext3:

  • Maximum number of files: min(volumeSize / 213, numberOfBlocks)
  • Maximum file size: same as ext2
  • Maximum volume size: same as ext2

ext4:

  • Maximum number of files: 232 - 1 (4,294,967,295)
  • Maximum number of files per directory: unlimited
  • Maximum file size: 244 - 1 bytes (16 TiB - 1)
  • Maximum volume size: 248 - 1 bytes (256 TiB - 1)
Machado
  • 4,090
  • 3
  • 25
  • 37
  • With a right choice of a file system, it's a great approach. Many of the advanced algorithms mentioned in the question are already implemented in filesystems, tuned and battle-tested. The choice and maybe tuning of the FS parameters will be _crucial_ for performance. OTOH a large queue important for performance may be provided with its own partition and a tuned FS. – 9000 Jun 02 '17 at 16:49
  • @9000, exactly my thoughts. But at first there isn't the need to provide a queue in another partition, if he follows the suggestion to name the files sequentially. The only problem with the sequential approach is how properly wrap-around the number when near the limit of an int64. – Machado Jun 02 '17 at 17:01
  • Very interesting points and thanks. Might work just fine. My question would be performance around head/tail insertion/deletion - presumably the FSs sorting would be used to determine message sequence, which means meaningful and decently performing "give me the first file" operation must exist along with a means of determining last file name efficiently. That said, may be totally workable. – Brad Peabody Jun 02 '17 at 17:01
  • 1
    @Machado: re proper wrap-around: uint64 is pretty large. Consider a case when we push 1M messages through the queue every second, probably somehow above the practical limits of current FSes and hardware. It will take `(2 ** 64) / (365 * 24 * 3600 * 1e+6)`, or slightly less than _585 thousand years_ to get to the wrap-around event. – 9000 Jun 02 '17 at 17:09
  • 1
    @9000, you're right, I didn't think it through. I hope Brad won't be around to handle the Y585K bug in the system. This will be another unfortunate developer problem. :-) – Machado Jun 02 '17 at 17:19
  • 1
    If I'm still alive in 585000 CE, just shoot me. – Brad Peabody Jun 03 '17 at 02:40
3

Another way of approaching this is to basically just store the messages in blocks of a reasonable size, and each block is stored in a file on disk, and either read in (or possibly mem-mapped) for use in memory when needed.

Blocks could be, for example, 64MB each. Each one is a file, named with timestamp and random number. The purpose of grouping the messages is to avoid a proliferation of small messages from creating a bottleneck at the filesystem level. If the message count reaches into the millions it could prove difficult to efficiently navigate the FS to find the first and last message. Block sizes must be larger than the largest possible message and must be guaranteed to fit in memory at least a few at a time.

Folder prefixing can be used to make navigation simpler. I.e. if the file's timestamp is 201706021852 then it could live in the 20170602/18 folder. The prefixing could be configurable for different predicted message volumes if needed.

When blocks are read into memory, a doubly-linked-list would work as the in-memory representation. The first and the last block should be easily findable on the disk by crawling the folder structure, these blocks are loaded into memory and then the in-memory versions worked on - messages being pushed to the back and popped from the front. Messages in a block when consumed could simply be flagged as such and when all messages in the block are consumed the block is deleted.

At whatever intervals are appropriate, the loaded blocks would flushed to disk and everything fsync()ed. Operations that are guaranteed to be atomic (rename) would be used to reliably know if your write succeeded.

The above structure should work well if you never need to find a message in the middle of the queue (which would required a full scan of all blocks).

Brad Peabody
  • 239
  • 1
  • 7
1

And yet another solution would be to just use a SQLite table. Internally SQLite uses binary trees for both table data and indexes (not specifically optimized for head and tail-heavy reads and writes but also not particularly inefficient). And it will re-use pages which become completely available. It may very well be that SQLite will do the job with reasonable performance and never require compaction (since a queue which is consumed in sequence should theoretically completely remove full pages, since all of the records will be deleted in sequence). Needs to be tested.

Brad Peabody
  • 239
  • 1
  • 7