Re: spamprobe-1.1x7 released

Graham Toal wrote:
>>The hash format itself couldn't be any more trivial.  It's just an array 
>>of 12 byte records with no fancy data structures.  Worst case I could 
>>think of is if the system crashed in such a way that only part of a 
>>record was written to disk. 
> 
> Do you have room for a tombstone on each end?  Even one byte would do it,
> just increment the previous byte cyclically.  If the head stone isn't
> the same as the foot stone, it's an empty slot.

Currently each record is a 4 byte key value (the hash) followed by two 3
byte counts (good and spam) and a 2 byte flag (date stamp).

When terms are removed I zero out their counts but leave their keys in
the record so that keys which depended on their existence can still be
found (see below).  Effectively that zero record serves as a tombstone.

On the next run of cleanup or purge I build a new hash file containing
only the records with non-zero counts.  So I am able to effectively
rehash the file on every cleanup/purge to reclaim free space.


>> At worst that would make one term invalid 
>>so I don't think it'd be a disaster.
> 
> What about collisions, do you chain hashes?  Would one corrupt
> entry being wiped out take an overflow bucket with it?

On collisions I move on to the next record and continue until a match or
an empty record (linear probing).  In the worst case if a key gets
corrupted I might wind up wasting that record and moving on to the next
available record when I would otherwise have matched.  Or a key could
get cleared when it shouldn't have and a few terms after that record
will be unreachable if they depended on a collision with the incorrectly
cleared record.

I don't think there is such a thing as a completely crash proof file
structure unless you resort to journaling and full fledged transactions
and I don't think that's called for here.


One note about this format is that it is slightly lossy.  Since I am
only using a 32 bit hash function and throwing out the original string
to conserve disk space there will be terms that have the same 32 bit
hash value as other terms.  In my own database of around 2.24 million
terms I lost 628 terms.  That's around 1 in 3,580 terms or 0.027%.

I'm not too worried about the losses since the database is constantly
evolving and I expect it to adjust dynamically to any problems that
arise as new email comes in.

BTW there is also a database format call split

   spamprobe -d split:40:$HOME/.spamprobe auto-train ...

split is a combination of a hash database for most of the terms and an
ISAM (PBL or BDB) database to hold the message digests.  That ensures
that you never "lose" a digest at cost of a loss of completely fixed
storage space.

All the best,
++Brian



-------------------------------------------------------
SF email is sponsored by - The IT Product Guide
Read honest & candid reviews on hundreds of IT Products from real users.
Discover which products truly live up to the hype. Start reading now.
http://ads.osdn.com/?ad_id=6595&alloc_id=14396&op=click