History hash collisions

Russ Allbery rra at stanford.edu
Mon Nov 15 09:23:49 UTC 1999

Forrest J Cavalier <mibsoft at mibsoftware.com> writes:

> Any history API work should be so major that it is not rework, but a
> ground-up rewrite.  In this case, "increasing" the size of the stored
> hash doesn't ensure correctness, it just makes failure less likely.  I
> don't like solutions like that.

You can have complete correctness or you can have fixed-width history
records; pick one.  You can have fast history lookups, less memory
consumption, or less chance at a collision; pick any two.  Unless I'm
missing something really fundamental, you can't ever have both of the
first set or all three of the second set.

Part of the goal of a history API for me is to expose the above choices so
that sites can make their own choice about the tradeoffs and we don't have
to make those choices for all sites.

> There are three fundamental problems with the INN history architecture.
> They have been self-evident for quite some time now.

> In no particular order...
>    1. Deletions are expensive.  You have to rewrite the data file,
>       and rebuild the .pag hash table.

Right.  Fixed-width history records can fix this, and most of the
architectures I'm looking at would solve this problem.  I don't know of
any way of solving this problem and still retaining the entire message ID
in the history file without going to a completely different type of

>    2. The locations stored in the hash table are 4 byte offsets to
>       a single file.

This is easily addressable in a number of different ways; one of the
obvious ones would be to allocate a sparse binary history file that
parallels the arrangement of the hash.

>    3. Linear probing for empty slots degrades performance quickly,
>       even though the probing is run-length limited, with the 
>       spillover/expansion hash tables.

In practice, in the current history implementation, spillover doesn't
exist.  I'm not sure it even works.  In fact, if it doesn't work, that
could explain some of the problems we've seen.

Anyway, do you have some concrete benchmarking on the degredation of
performance when using linear probing?  I've pretty much convinced myself
that if you have the tables allocated at the correct size, it really isn't
a performance problem, which limits the problem to the initial history
build.  While we should do something to address it, redesigning the
storage format to deal with a fairly unusual case doesn't seem like the
right thing to do.

> You can't solve all of these problems by making adjustments to dbz.

I think you can solve quite a bit of them using the same architecture as
dbz.  I'm open to suggestions of new architectures, but I'd really like to
see them come with working code and benchmark figures; dbz looks pretty
fast to me.

> Obviously, there other problems which you would want to tackle at the
> same time, like integration of cache, pre-commit cache, memory mapping,
> the problem of hash collision I mentioned, and probably more I can't
> remember off the top of my head.  Is there a list you are working on,
> Russ, Katsuhiro?  I guess I should slog through that thread on n.s.n....

It's mostly still in my head; I haven't really written anything down.

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

More information about the inn-workers mailing list