[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kmail-devel
Subject:    Re: How to keep the index in sync?
From:       Don Sanders <sanders () kde ! org>
Date:       2003-09-29 4:45:18
[Download RAW message or body]

On Saturday 27 September 2003 09:01, Ingo Klöcker wrote:
> On Friday 26 September 2003 05:22, Don Sanders wrote:
> > On Friday 26 September 2003 03:39, Stephan Kulow wrote:
> > > Hi!
> > >
> > > As I went through the kmail bugs, one problem arises in the one
> > > or the other incarnation, but the most visible are the ghost
> > > messages (http://bugs.kde.org/show_bug.cgi?id=43931): out of
> > > sync running indices.
> > >
> > > Whatever they cause them (problems in kmail or external
> > > problems like NFS servers), we need to address them urgently. I
> > > believe we don't need a bug fix, we need some drastic change
> > > the way they are done. Some extra check sum,
>
> Till and Marc wrote a proposal for an improved index file format
> which would include check sums and magic numbers to make recovering
> as much information as possible from partially broken indeces
> possible. A long time ago I proposed to add the file length (of the
> mbox file) as additional criteria for checking whether the index is
> still in sync with the folder contents. Obviously this makes only
> sense for mbox folders. But those really shouldn't be used anymore
> unless maildir can't be used (e.g. because the mail is stored on a
> FAT partition where the colon which is part of the filename of
> maildir files is illegal). The problem with storing the length in
> the index was (as Don pointed out) that we would have to open the
> index in order to read the stored length. This is obviously a lot
> slower than a simple comparison of the mtime of mbox and index
> file.
>
> For maildir all of this is a lot easier because there is no risk of
> corrupting messages because all messages are in a file of their own
> (in mbox we store the offset of the start of each message in the
> index and if this offsets changes hell could break lose). Apart
> from serious file corruption (due to a crash) the only problems
> that can occur with maildir are:
> a) Messages which have already been deleted are still listed in the
> index (-> the infamous ghost messages).
> b) There are messages in the folder which are not listed in the
> index (because they were put into the folder by another MUA or by
> procmail).
>
> So index file recovery is much easier for maildir then for mbox.

I would like to find an efficient checksum function for detecting 
cases a & b. Maybe something equivalent to calculating the MD5 
checksum of doing an ls -l on the Maildir directories.

> For maildir we just have to compare the filenames of all messages
> in the folder's subdirectories with the filenames in the index. But
> IIRC we don't store the filenames in the index. This should be
> changed.
>
> For mbox (which doesn't suffer from the ghost message syndrome
> AFAIK) we should, as a first step, just improve the detection of
> out-of-sync situations by adding the file size of the mbox file to
> the index. Instead of writing the file size into the index I had
> the idea to simply put the file size into the name of the index
> file, e. g. .inbox.12345.index if the inbox file is 12345 bytes.
> This should be much faster than opening the index file and reading
> the file size. Furthermore "writing" the file size is much less
> expensive since it's just a rename. In fact, renaming is even an
> atomic operation (at least for local storage; I don't know about
> NFS).
>
> IMO we need completely different strategies for mbox and maildir.
> IMO we should first concentrate on maildir because this case is
> much easier to handle and, as maildir is default in KMail, it's the
> much more common folder format.
>
> > > some information weaving back
> > > in the mails (so the indices are completly volatile)
>
> That's very expensive. We would have to reserve a certain amount of
> space for each message so that we can write the necessary
> information into the special header without changing any offsets.
> But with maildir this would involve opening every message (very
> slow) and with mbox this would involve a seek for every message
> (also quite slow). So weaving information back in the messages is
> IMO no option. At least not information which has to be changed a
> lot (like the status of a message). Just imagine how slow a "mark
> all messages as read" in a maildir folder with 10,000+ messages
> would be.
> OTOH I think that writing the serial number into the header of the
> messages makes some sense. But we would have to take extra care in
> order to avoid serial number clashes (e.g. if someone merges two
> mail storages like the one from work and his private one at home).
> If index file recovery is improved then writing any information
> back into the messages shouldn't be necessary.
>
> > > - I don't
> > > know. But as I consider the topic important enough, we should
> > > discuss possible ways _NOW_. Let's find out what's possible in
> > > that area, I'm willing to spend some time implementing, but I'm
> > > not even sure where to head to ;(
>
> [snip]
>
> > But this ghost messages in the outbox problem is a special case,
> > it seems to be due to logic in the KMail code causing the index
> > file to be out of sync with the folder data.
> >
> > Normally I think index files get out of sync for one of five main
> > reasons. Firstly because NFS is used, many NFS systems don't
> > return accurate file times and this messes with the KMail logic
> > that requires the index file to be newer than the folder file (I
> > know Ingo did work in this area, can't remember exactly what the
> > status of this is).
>
> Well, the status is: The user has to make sure that clock of his
> workstation is in sync with the clock of the NFS server because
> else he'll end up with false "index out-of-sync" alerts. Unless we
> add an expensive checksum verification there is no reliable way to
> tell whether the time difference between folder and index is caused
> by NFS or by a real out-of-sync problem.
>
> > Secondly ReiserFS has historically done an outstanding job of
> > maintaining file system integrity while completely screwing files
> > after an unclean shutdown, but recent versions may be better.
> > This might not be so bad for pampered server based software,
> > running on UPS protected hardware, but it's certain doom for a
> > mail client that has to operate in a hostile environment where
> > many users routinely shut down their systems by hitting the power
> > off button, and often do so while KDE itself is being logged out
> > of.
>
> A sad comment about ReiserFS: For some reason it's impossible to
> run gdb in SuSE 8.2 if one has an XFS partition (don't ask me why).
> After I found this out I converted my XFS partions back to
> ReiserFS. Now gdb works again. But while recompiling kdebase I got
> a strange error message about some problems with a Makefile. First
> I thought of the usual occasional compilation problem. But a look
> at the Makefile showed that the problem was more serious. The
> Makefile contained parts of an ELF file. Obviously a ReiserFS bug.
> Luckily (?) I wasn't able to reproduce the problem, so I'm still
> using ReiserFS hoping that this won't happen again. Note that this
> file corruption happened during normal operation and not during an
> unclean system shutdown.
>
> > Thirdly Mutt deserves an honorable mention for messing with
> > folder files while forcing file dates to remain the same. Also a
> > great way to confuse KMail time based logic.
>
> This shouldn't be a problem with maildir. And with mbox remembering
> the file size would at least give another hint. Of course, it's can
> still happen that time and size are the same although the contents
> of the mbox file changed. In order to notice this we just have to
> add some sanity checks (like that the message at the saved offset
> really starts with "From ...").
>
> > Fourthly bad hardware leads to corrupted files, but normally
> > KMail immediately exits in this case, thus minimizing the damage.
> > (Which I think is better behavior than 'elegantly' recovering
> > from the error, and going on to blindly mangle what is left of
> > the users data).
>
> This is debatable. But since bad hardware won't only cause trouble
> with KMail I don't think we have to put much effort in handling
> such exceptional cases. I agree that it's okay that KMail simply
> aborts itself in this case.
>
> > Finally KMail stores its mail in ~/Mail unlike Netscape, Mozilla,
> > and Evo (index/summary based mail clients). This is asking for
> > trouble. Especially procmail users find it hard to understand
> > that the historical practice of having mail sorting programs
> > directly access mail folder files is efficiency wise a thoroughly
> > despicable practice. KMail by storing mail in ~/Mail is simply
> > being belligerent in this matter, but it's pretty late to revert
> > back to ~/KMail.
>
> That's also debatable. I would even consider using ~/.kmail (note
> the leading dot) for storing the mail.
>
> > Two approaches come to mind for most robust operation in this
> > environment.
> >
> > In KMFolder there is a mCompactable member variable. This is set
> > to false when an out of sync index file is detected in
> > (KMFolder::getMsg). It might be a good idea to call
> > createIndexFromContents when !mCompactable in KMFolderMbox::open
> > and KMFolderMaildDir::open, after the (mOpenCount > 1) test.
>
> I agree. If we detect a possible out-of-sync situation then we
> should act appropriately, i.e. regenerate the index. The problem is
> that the current code simply dumps anything we know and regenerates
> the index from scratch. This results in lost status information.
> Therefore we should definitely improve the index regeneration code
> so that it reuses the already known information.
>
> > Secondly I don't think it makes much sense to checksum entries in
> > the index file.
>
> I agree to a certain degree. The partial corruption of the index
> file is not the problem we try to solve. OTOH checksum calculation
> isn't that expensive.
>
> > But I do think it makes sense for the index file to
> > checksum the corresponding folder data. For instance ignoring
> > efficiency, for mbox, the index file header could contain and
> > update a single MD5 checksum for the entire contents of the mbox
> > file whenever the mbox file is modified (by KMail).
>
> For mbox I partially agree. But for maildir it should not be
> necessary.

Perhaps it isn't useful to checksum the contents of messages for 
maildir. I do think the general idea of a checksum is sensible for 
both maildir and mbox. So I advocate the creation of a pure virtual 
KMFolderIndex::checksum() method and concrete implementations for 
maildir and mbox. For mbox (as Ingo suggested) the checksum could 
just return the file length, for maildir the checksum should catch 
cases (a) & (b) that Ingo described above.

I think the checksum should be recorded in the header field of the 
index. When the checksum should be checked and updated is debatable,
and something worthy of careful consideration by the implementor.

> > Then whenever the mbox file is compacted or appended to (that is
> > modfied in any way), the checksum contained in the index file
> > could be compared to the mbox contents before modification and
> > updated after modification.
>
> I don't think it's necessary to check the checksum in case of
> appending. Only before the destructive compaction this is really
> necessary.
>
> > Now consider efficiency. Really efficiency is what this is all
> > about, there is a fundamental efficiency/correctness tradeoff at
> > play. Instead of calculating the MD5 sum of all the folder data,
> > it might be better to calculate the CRC32 sum of every millionth
> > int in the folder data, basically statistically sample the folder
> > data in some way.
>
> I guess every millionth int is no serious suggestion. So it would
> be more like every 10000th int or so. But this will require a whole
> lot seek operations which isn't really that much faster than linear
> reading with modern hard disks. So all we save is a bit time during
> checksum calculation because we use less input data for the
> calculation. But since we will spend most of the time anyway
> waiting for the hard disk to give us the next int we can as well
> calculate the checksum over the complete data.
>
> I have no comments to the rest of Don's message.

I think Ingo and my comments give a pretty comprehensive overview of 
the situation.

Don.
_______________________________________________
KMail Developers mailing list
kmail@mail.kde.org
http://mail.kde.org/mailman/listinfo/kmail
[prev in list] [next in list] [prev in thread] [next in thread]