Hacker News Reader

Comment by riobard | Hacker News Reader

A side question: what's the best way to build an email message store which stores millions of messages (and adding tens of thousands on average each day) on disk so that it can support:

1) Fast looking up messages sent/received by a particular email address, time, tag, priority, and a handful other properties

and

2) Appending thousands of new messages per second at peak?

View on HN

Maildir (or a very similar one-message-per-file store) plus an index of some kind.

If not for the continuous addition of messages, I'd suggest notmuch (http://notmuchmail.org/), which does a great job of indexing in any way you could want. Unfortunately, as far as I know notmuch does not have an "online" indexing mechanism; someone wrote a notmuch-deliver that adds a message and indexes it, but I doubt it would meet your performance requirements. You could probably make notmuch do what you want, but you might want a new indexing mechanism instead.

I still think you want something very similar to Maildir underneath though.

I was using the one-message-per-file approach, but keeping millions of small files in a filesystem is quite a challenge: I have to worry about available inodes, and listing/manipulating these files takes minutes!

On a relatively small ext4 filesystem here, I have tens of millions of inodes available, and I haven't done anything to tweak that. On a larger filesystem, with a slightly bumped number of inodes, I'd expect several hundred million inodes, more than enough to store all the messages that'll fit in the available space.

As for listing and manipulating, I'd suggest not ever listing all the files. Access them by name only, which should require near-constant time no matter how many files you have. Manipulating the files should take similarly little time. On the occasions that you do need to list all the files, you might find https://www.olark.com/spw/2011/08/you-can-list-a-directory-w... interesting.

A pile of RAM helps, to keep as many directory entries in the dcache as possible.

Email can use up inodes quickly. A thousand users with a thousand emails each is a million files in Maildir. Plus three directories (cur/new/tmp) for each mail folder.

Folders seem unlikely to use up a significant number of inodes compared to the messages. As for messages, how many users do you expect to serve from each mail server? I think you'll hit the limits of whatever service you want to provide before you hit the limit of inodes in your mail store.

(Or you could always encrypt each email and throw it at an object storage system similar to S3. ;) )

I think the best system would be one inbetween mbox and maildir. You specify a filesize limit of say "10MB". Emails are repeatedly added to the same file, until it hits 10MB, then a new file is created. Emails larger than 10MB would not be split over multiple files. An index is kept of all of the messages. When a message is deleted, rather than immediately removing it from the file and blocking like most mbox implementations work, it should just be flagged as deleted in the index. A background process can clean up these messages when the file is not in use.

What you describe is essentially a database for email. You might have a look at http://www.dbmail.org/

This is true. Maildir and mbox are also essentially databases for email.

OK. Maybe I should have said DBMS? I'm speaking specifically about the management of the back-end storage files, e.g. splitting storage over multiple size-limited files, tracking and re-using free space, etc. are all things that DBMSs provide, without a need to reinvent such things for the purposes of storing email.

If there's a better term to describe this I'd be glad to learn it.

Seems like in such a system you've gone to a lot of work to recreate the purpose of a filesystem: to keep the data of different files separate from each other. Why do you want to keep emails together in 10MB chunks?

To address the limited inode issue

I did millions upon millions of small e-mails using Maildir in a filesystem in 2000 (accounts for 1.7 million users on a single filesystem). It's only a challenge if you pick a filesystem with pathological behaviour for directories with many files and/or with small and hard limits for number of inodes (in our case we used ReiserFS 3).

The biggest problem is read bandwidth for your disks. Write IO is likely to be constrained by available network bandwidth unless you do something stupid. Read bandwidth constraints for e-mail are generally easily mitigated by creating an index (so you only need to open or stat the message files when opening individual messages, not to, say, list message sizes in a POP3 server or present an index view on a web interface).

If you need to list/manipulate those files other than writing them once and reading them when a user actually opens that specific message, or deleting them when the user actually deletes the message, then you're doing something wrong (e.g. you didn't create a sufficiently flexible index).

There are some systems based on the Xapian full-text indexer, including my own 'mu'[1] which might be able to do this. It expects the messages in a Maildir, and it can handle > 150 messages per sec, on fairly slow hardware - so after a peak of thousands of new messages, it would take a few seconds to catch up. Tens-of-thousands per day would be no problem. There have been people using [1] for a few million of messages without any problem, but I'm not sure how well it scales beyond that.

[1] http://www.djcbsoftware.nl/code/mu, or 'maildir-utils' in debian/ubuntu

If you only ever want to append messages, and never want to mutate or remove them, I would do this scheme in two parts: 1) an append-only message store; 2) a set of indices stored alongside (1). To append thousands of messages per second, I would probably want a system with multiple writers appending to multiple files (mbox) or directories (maildir), and cycling/archiving the mailboxes as they get large.

As for (2), I know a lot less about indexing messages than I do about storing them, but I would try out an off the shelf SQL or noSQL system and measure the performance, before trying to build anything fancy.

You could look at http://notmuchmail.org/ which builds on top of maildir.

Reply on news.ycombinator.com