Natterings about history files

[Russ Allbery]

Fabien Tassin <fta at sofaraway.org> writes:
> According to Russ Allbery:

>> Unfortunately, if I understand how this works correctly, we can't use a
>> perfect hash function even for old history files, since the point of a
>> perfect hash function is that you'll only ever look up keys that you
>> fed to your function generator when you made it.  Since one of the main
>> purposes (and the most common queries) for old history entries is
>> whether one has an article that one *doesn't* have, this doesn't work
>> very well.  We'd be looking up a whole bunch of keys that we didn't
>> give to the perfect hash generator, and which therefore would likely
>> collide left and right in unuseful ways.

> Do you have an idea of the rate collision in the current model ?
> I assume it is quite high unfortunatly. In the past, Matt Dillon did
> the exercise for its Diablo history system but I can't put my hand on
> its report.

I don't have a firm idea, no; bear in mind that as our history format is
currently designed, a lot of collisions is to be expected since we're
using a table that's 2/3rds full.  (That's with the collisions when
hashing into a table; we have a separate problem of multiple message IDs
hashing to the same value, and I'm worried about that since we're not
using all of the MD5 hash like we really should.)

>> Anyway, one thing that I think might be a win if we stay with the
>> nightly expire idea for history entries would be separate, daily
>> history files.  The lookup time would be somewhat slower, but it would
>> save a lot of time with expire since there's no need to even look at
>> the history files that are younger than /remember/.

> I've tried to evaluate the gain in having multiple history files but I'm
> not convinced it will be that interesting.

Neither am I.  It's nice for expire, but it's worse for lookups, since the
cost of a lookup is going to be linear in the number of history files one
is using unless there's a fancier algorithm that I'm not yet seeing.

> The problem is more in the expire design than in history. We want it to
> undo very quickly what has been done in a day. A discrete approach
> should give better results.  I see two ways to achieve that : a cyclic
> history (constant size) or an expired.

Okay, I don't understand why the concept of a cyclic history file would
work at all; could someone who likes that solution explain to me how that
would work?  The painful part of history is building the queriable index,
and it seems to me that with a cyclical design we'd have to keep clearing
old entries as they're overwritten so that we know which slots in the
table are free, and that would be a huge performance hit, much more than
using multiple files.

> The later is easier because it require no change to the model to bring
> the pure CNFS performances to other spool methods. The bad point is that
> it still need to be periodically cleaned.

What do you mean by an expired?  (I'm not at all sure that just spreading
the work that expire does throughout the day is a good idea.  You then
have to deal with locking problems on top of everything else, and you
can't batch your writes for better performance so it would be even
slower.)

>> The API that I'm currently considering is:
>> 
>>     struct history *HISopen(const char *path, int flags);
>>     bool HISclose(struct history *);
>>     bool HISsync(struct history *);
>> 
>>     void HISsetcache(struct history *, size_t size);

> I prefer to hide the cache completly. In INNT, I've merged HISopen and
> HISsetcache into HISsetup.

You want to be able to specify the cache size.  I suppose you could make
that a third argument to HISopen.  I don't really like generic *setup
functions; I'd rather have a separate function call for each value that
can be set unless one routinely wants to set a whole struct worth of
values all the time.

>>     bool HISlookup(struct history *, const char *key, time_t *arrived,
>>                    time_t *posted, time_t *expires, TOKEN *token);
>>     bool HIScheck(struct history *, const char *key);

> are your keys HASH or message-id ?

Message ID.  The details of the hash should be internal to the history
implementation.

>>     bool HISwrite(struct history *, const char *key, time_t arrived,
>>                   time_t posted, time_t expires, const TOKEN *token);

> used for HISremember too ?
> (I've called mine HISadd and HISaddbogus)

Yup, although having two separate interfaces is also reasonable and may be
cleaner.  One would probably just call the other.

>>     bool HISreplace(struct history *, const char *key, time_t arrived,
>>                     time_t posted, time_t expires, const TOKEN *token);

> replace ? you mean have to remember transition such a expired but
> remembered and cancelled ?

That possibly, but more to the point change the value of token for an
existing article on spool.  I *really* want that functionality to make
expire a lot easier and to allow one to move articles between storage
backends.

>>     bool HISexpire(struct history *, time_t threshold,
>>                    bool (*exists)(TOKEN *));

> can you explain this one ?

I think there was some later clarification of what would make a good
interface here, but the basic idea was that for every entry in the history
file that was older than threshold, exists would be called with the token,
and if exists returned false, the article would be considered to have
expired off disk and the appropriate things would happen in the history
file (clearing the token, removing the history entry if it's older than
/remember/, etc.).

> in that case, you need some more low level functions such as those
> called by makedbz.

I'm not sure.  I'd like to take a close look at that.  I think a lot of
makedbz's functionality isn't actually desireable once we have a good
generic API and there may be better ways to deal with it.  But I haven't
taken a close look at it yet.

>> I think the best organizational structure to use in terms of code is to
>> make a new directory called history and build a library out of the
>> history code in there.  libinnhist?  libhistory is too general and
>> would conflict with part of readline.

> I'll welcome it if it hides dbz completly from the rest of INN.

That's the goal.  One should be able to drop a Berkeley DB history
implementation in place if one wants to try it without having the rest of
INN care.

-- 
Russ Allbery (rra at stanford.edu)             <http://www.eyrie.org/~eagle/>