sup talk - Apr 2009 - Possible problem with maildir ID generation

I''ve been studying maildir.rb (and adding some debug code) while
trying to figure out my lost message problem.  I think there may be a
problem with the way the internal message IDs are generated.  The
make_id method glues together the file timestamp and size.  But I
think this could lead to an out-of-order problem in the @ids array.

Consider two messages that arrive in the same second, but the second
message is smaller than the first.  Because the message size makes up
the low seven (decimal) digits of the ID, the second message, even
though it arrived later, will have an ID that is less than the first
message.

Then suppose that sup polls the maildir directory after the first
message arrives, but before the second message arrives, and sets the
cur_offset to the ID of the first message.  Then, the next time it
polls, it will see the second message, but because its ID is less than
that of the first message, it will appear before the first in the @ids
array after it is sorted.  So then the each method will skip the
second message, because cur_offset (the ID of the first message) will
be found in @ids after it.

Does this scenario make sense?  I have seen what appears to be one
instance of this happening, though I''m still watching closely and
adding more debugging code to make sure that it explains all of the
lost messages.

Reformatted excerpts from Mark Alexander''s message of
2009-04-16:
> Consider two messages that arrive in the same second, but the second
> message is smaller than the first.  Because the message size makes up
> the low seven (decimal) digits of the ID, the second message, even
> though it arrived later, will have an ID that is less than the first
> message.
I think you could be right. Using the size as part of the ID was
supposed to differentiate messages with the same timestamp, but it would
result in exactly the behavior you describe when polling.

I think there''s a much simpler scheme we can use that will also fix
this. I''ll post a patch soon and we can see if it addresses the
problem.
-- 
William <wmorgan-sup at masanjin.net>

On Tue, Apr 21, 2009 at 7:00 AM, William Morgan
<wmorgan-sup at masanjin.net> wrote:
> I think you could be right. Using the size as part of the ID was
> supposed to differentiate messages with the same timestamp, but it would
> result in exactly the behavior you describe when polling.
>
> I think there''s a much simpler scheme we can use that will also
fix
> this. I''ll post a patch soon and we can see if it addresses the
> problem.
I''d be very interested in this patch.

In the meantime, I made some minor changes to maildir.rb, without
changing the ID scheme.  One problem was every time a maildir was
polled, the most recent message (i.e., the one at cur_offset) would be
treated as a new message again.  I also changed last_offset to return
an ID that would be one second later than the last message seen.

These changes seem to have mostly fixed the lost message problem I was
having, though I''m not exactly sure why.  I''ve only had one
lost
message over the last couple of days, instead of the expected 10 or
20.  I can''t explain this one lost message, but I think it must be due
to a different problem, unrelated to maildir handling.  I was able to
get sup to see this message again by doing a ''touch'' on both
the
message itself and the containing maildir.

I doubt that my changes would fix the race condition I described
earlier, but I''ve avoided this problem by not running fetchmail
in the background while sup is running.

I''ll send out my patch in a separate email.

On Tue, Apr 28, 2009 at 3:18 PM, Marc Hartstein
<marc.hartstein at alum.vassar.edu> wrote:
> Isn''t part of the maildir scheme that the filenames are guaranteed
to be
> unique? ?It''s been a while since I looked at this part of the sup
> source, but would it be possible to simply use the filename as the ID
> when working with maildir, rather than generating a new ID? ?Or is there
> an additional constraint (like ordering?) that needs to be satisfied and
> isn''t by maildir?
Maildir filenames are unique, but they would need to be ordered
by time, since sup depends on that ordering (look in maildir.rb for
where it uses sort).  I''m not sure if mail delivery programs
(I use procmail) guarantee that the filenames are ordered that way.

I will say that the patch I sent out for maildir.rb has made
my life a lot happier, but it''s still not ideal because of
the race condition I mentioned.

William was talking about using some other scheme to generate IDs.
We should see what he has to say about this.

Reformatted excerpts from Mark Alexander''s message of
2009-04-28:
> Maildir filenames are unique, but they would need to be ordered by
> time, since sup depends on that ordering (look in maildir.rb for where
> it uses sort).  I''m not sure if mail delivery programs (I use
> procmail) guarantee that the filenames are ordered that way.
That''s correct; the name is not sufficient as ids because Sup needs a
single pointer into the Maildir as a marker for what it has already
processed, so we have to use something ordinal.  But it can''t just be
any old ordinal, it has to be something that corresponds with the way
messages are written to the Maildir, in order to be able to divide newer
messages from older ones.

A timestamp is the obvious choice, but messages can have the same
timestamp, so then what do you do? The current approach is to sort by
another arbitrary field (in this cae, message size), which gives a
unique ordering, but doesn''t match up

(All this rigamarole about ordinals and blah blah blah is necessary
because I don''t want Sup to rescan the entire Maildir unless absolutely
necessary. One day I''ll convert my mbox to a Maildir with 250k files in
it, and a rescan will kill me, especially at Ruby speed.)
> I will say that the patch I sent out for maildir.rb has made my life a
> lot happier, but it''s still not ideal because of the race
condition I
> mentioned.
> 
> William was talking about using some other scheme to generate IDs.  We
> should see what he has to say about this.
Well I haven''t quite started on it yet, but my plan is to:

a) Sort files by timestamp, and then by something else (maybe name), and
   use the position in that array instead of the timestamp. This
doesn''t
   solve anything, but it will make the ids prettier, and removes the
   hideous "%7d" thing.
b) When polling, if the current "offset" is N, return all messages
that
   have a timestamp >= the Nth message. So this will mean that we''ll
   rescan messages on occasion, but we shouldn''t miss any.

Any obvious flaws?
-- 
William <wmorgan-sup at masanjin.net>

Reformatted excerpts from William Morgan''s message of
2009-04-29:
> A timestamp is the obvious choice, but messages can have the same
> timestamp, so then what do you do? The current approach is to sort by
> another arbitrary field (in this cae, message size), which gives a
> unique ordering, but doesn''t match up
Sigh.

Doesn''t match up with that procmail, or whatever MUA, is giving us.
-- 
William <wmorgan-sup at masanjin.net>

Reformatted excerpts from Marc Hartstein''s message of
2009-04-29:
> On Wed, Apr 29, 2009 at 03:31:52PM -0700, William Morgan wrote:
> > (All this rigamarole about ordinals and blah blah blah is necessary
> > because I don''t want Sup to rescan the entire Maildir unless
absolutely
> > necessary. One day I''ll convert my mbox to a Maildir with
250k files in
> > it, and a rescan will kill me, especially at Ruby speed.)
> 
> How are we defining ''rescan'' here?  I can think of a
couple of possible
> meanings, and I''m not sure where you are:
> 
> 1. Open every file in the maildir and read from it, every poll.
> 2. Visit every filename in the maildir to consider whether it is a new
> file, every poll.
> 3. Something else I''m not thinking of this instant.
You''re probably confused because what I said was wrong. Here''s
what I
should have said:

Rescanning the entire directory to check for new mail is unavoidable in
Maildir. What I *do* have some control over, i.e. can try to optimize,
is the following operation: given a file in the directory, does it
represent a new message? One way to do this would be to maintain a set
of all filenames representing read messages, and to check for existence
within the set, for every file. Sup doesn''t do this; instead it defines
an ordering on filenames, such that newer filenames are "larger" than
older filenames under that ordering, and maintains a threshold
representing the dividing point between new and old. The idea being that
performing that comparison is quick, and that storing the set of read
messages is also quick.

(And again, I care about the case where you have 500k messages, and so
doing set existence is painful. Although perhaps Bloom filters are the
solution... that would be interesting!)
> So the only way you''re going to get a timestamp collision (on the
> filename timestamp, perhaps not on the actual ctime) is if you have
> multiple processes delivering mail simultaneously, or if you''re
> synchronizing mail delivered on multiple hosts.  In the case of the
> latter, a timestamp-based heuristic for finding new messages isn''t
> going to work.
I think the collisions we are seeing are due to timestamp granularity.
A little research suggests that e.g. ext2fs ctimes are 1-second
granular. It seems quite easy to get more than one email per second.
> Would it suffice to keep track of the filename of the most recent
> message added for each maildir source, and check everything with a
> time portion of the filename equal to or greater than that message for
> whether it needs to be added?  [although see above about whether that
> gains anything]
Yes, I think that''s the solution. Basically switch from > to >=
when
comparing timestamps, and realize that you''re going to get some dupes.
> Having looked into this more closely, I''m starting to seriously
> reconsider whether maildir is really what I want to be using for storing
> my mail.  There are some weird timing issues.
Well, mbox has the advantage of being nice and linear so this problem
goes away, but is horribly broken in other ways (c.f. the recent thread
about the "From problem"). IMAP is a ridiculous PITA to deal with (at
least as a client), so you''re kinda screwed in every direction here. If
anything, Maildir is less broken than the other alternatives.

Plus Maildir works really well with git. :)
-- 
William <wmorgan-sup at masanjin.net>

On Mon, May 4, 2009 at 12:52 PM, Marc Hartstein
<marc.hartstein at alum.vassar.edu> wrote:
> On Mon, May 04, 2009 at 09:10:23AM -0700, William Morgan wrote:
>> I think the collisions we are seeing are due to timestamp granularity.
>> A little research suggests that e.g. ext2fs ctimes are 1-second
>> granular. It seems quite easy to get more than one email per second.
>
> It does, but as I mentioned somewhere in that email, the reference
> implementation of maildir (qmail) says that it will only deliver one
> message per second. ?However, I definitely concede that relying on this
> behavior would be setting things up for something to go wrong down the
> line.
Just a data point: in my setup (postfix+procmail) I''m seeing multiple
messages
being delivered to the same maildir in the same second.  That was what
motivated my patch.