[Dovecot] Indexes again

[Timo Sirainen]

A bit quiet here, so here's some more thoughts about indexes. Even
though I was thinking only how to make them usable with NFS (I wrote it
to doc/nfs.txt), it then occured to me that exactly the same tricks
would help with local filesystem indexes as well. Especially the
lockless reading would help with lock contention issues I was worrying
about earlier with shared mailboxes.

Also it occured to me that keeping maildir filenames fully synchronized
in index file probably isn't very good idea from performance point of
view..

BTW. I almost committed the .tree removal code to CVS today. Then I
noticed that expunging ignores about half of the deleted messages. This
could have been actually happening with the old code in some situations
as well, although it probably would have skipped only a couple of
messages. Anyway, fixing this properly takes some more time..

--------

Ideas how to make indexes work pretty well with NFS:

Reading shouldn't require locks, so modifying should be done using only
atomic operations. These include:

 - Replacing the file completely using rename()
 - We probably can't assume that writing more than one byte at a time is
   atomic. If we have to modify a larger dataset, we could do:
    - struct { bit_t use_first; dataset_t first; dataset_t second; }
    - when reading, we use first if use_first is set, second if it's unset
    - when writing, we first write to the non-used variable, only then we
      update the flag.
    - This of course requires twice the amount of space for dataset plus
      one extra bit, so it shouldn't be used too much
    - If data can be only set, but never changed, we need only one extra bit
      to specify if the data is set.
 - Appending new data to end of file. We'd have to have used_file_size
   variable in header, done like described above.
 - Each cached message record would have a pointer to next part, so more
   cached data could be appended to file.

Message flags are the most commonly modified data. If we just modify them
directly, a simultaneous read might catch the change only partially. But
luckily for us, this is accepted behaviour so we can do it.

Another commonly modified data is maildir filenames. We probably want to
store only the base name in index and keep the full name synchronized only
locally.

Compressing unused data from index files would have to be done by rewriting
the index into index.lock file and renaming it over the index file.

All file operations should probably be done with lseek(), read() and
write() to avoid extra network traffic. There should be some clever
read-ahead caching however.