You are viewing a plain text version of this content. The canonical link for it is here.
Posted to users@spamassassin.apache.org by Kai Schaetzl <ma...@conactive.com> on 2004/04/12 23:31:34 UTC
Why doesn't expire simply expire the oldest x tokens?
This would cure all the problems one currently has when token atimes have
wrong values (in the future or too old or zero or negative) or magic
tokens don't have reasonable or expected values. Or even when you have
correct (!) values but never had an expiry before then the expire may
fail.
I troubleshooted today a problem with our Bayes databases I had already
discussed here in mid-February (and didn't find a solution back then). The
main problem here is that if your database is somewhat big and you either
run the first expiry or sa-learn decides that the database is weird (which
it deems it already after 30 days of non-expiry) it switches in the
"calculation" mode and stops after ten cycles. However, with a big and old
database (let's say 500.000 tokens, maybe half a year or older) the
calculated atime delta is still going to expire so many items after ten
cycles that the expire won't run. I was able to fix the problem by faking
several magic token values, so the "estimate" mode would be used instead
of the "calculation" mode.
Also, if I understands this correctly this expiry method can result in a
much different value of expirations than the target value. F.i. in this
case the goal was 5747 but it expired only 36 tokens. That means that the
next SA run will trigger expiry again and so on until it finally is under
the expiry threshold. That uses much more ressources than just expiring
the oldest 5747 tokens.
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Kai Schaetzl <ma...@conactive.com>.
Alan Baxter wrote on Mon, 12 Apr 2004 23:56:29 -0600:
> I assumed that Kai meant the oldest atime values.
>
Yes, my fault, sorry.
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Kai Schaetzl <ma...@conactive.com>.
Theo Van Dinter wrote on Tue, 13 Apr 2004 21:49:41 -0400:
> Are you saying they're negative based on --dump output? If so, the
> display is signed (fixed in 3.0 btw), but the actual value is unsigned.
Not sure what you mean with signed and unsigned, the minus symbol? There
were several thousand (didn't count) atime values of "-17982" (or so, all
the same), 0 and dates in the future (up until 2011). I didn't count but
the negative values must have been at least several hundred. Yes, this was
per the result of a --dump all.
>
> > Yes, but fairly old, so old that it can't be true. Or not?
>
> Unlikely, but possible.
>
0 would represent 1, 1, 1970 wouldn't it, so this should only happen when
the system had this date, which it didn't ever have. Or are there other
occasions which could result in an 0 atime?
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Theo Van Dinter <fe...@kluge.net>.
On Wed, Apr 14, 2004 at 01:07:12AM +0200, Kai Schaetzl wrote:
> But I had, several thousand of them, apparently. Ok, they may have been created
> by SA 2.50 but the conversion kept them. I hope I won't get any new ones now
> the db is fixed.
Are you saying they're negative based on --dump output? If so, the
display is signed (fixed in 3.0 btw), but the actual value is unsigned.
> Yes, but fairly old, so old that it can't be true. Or not?
Unlikely, but possible.
--
Randomly Generated Tagline:
"Having a firewall that allows NFS to the Internet is like having a seat belt
that lets your head touch the dashboard." - Marcus Ranum
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Kai Schaetzl <ma...@conactive.com>.
Theo Van Dinter wrote on Tue, 13 Apr 2004 17:56:51 -0400:
> Well, ok, but sorting then looping takes more resources than just doing
> the loop twice.
Yes, that was my first guess when I tried to answer myself why you don't simply
expire the oldest atimes. I didn't compare to looping, though :-)
> As for atimes in 2.6x, you can't have negative values (it's an unsigned
> value).
But I had, several thousand of them, apparently. Ok, they may have been created
by SA 2.50 but the conversion kept them. I hope I won't get any new ones now
the db is fixed.
> 0 is valid.
Yes, but fairly old, so old that it can't be true. Or not?
The problem with the expire algorithm as I see it is not the wrong atime
values. It would possibly happily expire them (except for the negative values
where it thinks they are newer than current and won't ever touch them I
suppose). Those wrong values were just what you and other people pointed at
when I first mentioned my problem and posted the magic token output back then.
But these are not the cause of the problem. The problem occurs when you allow
the db to grow in size without expiring for some time. Then the "guesstimate"
won't be used and the "estimation pass" is likely to fail. So, no expiry will
occur. I think this would not occur with the proposal I made. (It may have
other, worse side effects, though, I don't know.)
As it occurs I think the posting by Nels Lindquist from today is just about the
same problem and he only started in mid-February.
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Theo Van Dinter <fe...@kluge.net>.
On Tue, Apr 13, 2004 at 11:31:32PM +0200, Kai Schaetzl wrote:
> then you remove all "oldest" tokens until you reach the goal count, then you
> remove all remaining tokens with the same atime as the last removed token
> and then you stop.
Well, ok, but sorting then looping takes more resources than just doing
the loop twice. And there are other issues with sorting/expiring anyway,
such as having to backtrack and such. 2.5x did that kind of thing,
and it sucked horribly.
> I think the expire should always remove any tokens where the atime is very
> old (a year?) or newer than the current time. I had about 5.000 (of nearly
> 700.000) values in that db which were negative or 0 or in the future. So,
> that apparently happens.
2.50 was the first SA to have Bayes. I rewrote a majority of the Bayes
backend code for 2.6x, so it's essentially night and day.
As for atimes in 2.6x, you can't have negative values (it's an unsigned
value). 0 is valid. In the future ... does, but shouldn't, happen.
That's fixed in 3.0.
--
Randomly Generated Tagline:
"Ever heard of .cshrc?
That's a city in Bosnia. Right?" - Unknown
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Kai Schaetzl <ma...@conactive.com>.
Theo Van Dinter wrote on Tue, 13 Apr 2004 11:56:32 -0400:
> The slightly longer answer is: no matter what, you need to go through
> all the tokens in a loop once. to calculate the atime "x" from above,
> you have to go through all the tokens in a loop first (aka: first pass)
> to figure out the right "x", then go through that previous loop (second
> pass) to do the expire.
That's a bit different from what I figured about the reason (see my other
mail from today), but it's also about time/ressource usage I guess. You
don't need to do two complete passes, though. You sort in the first run and
then you remove all "oldest" tokens until you reach the goal count, then you
remove all remaining tokens with the same atime as the last removed token
and then you stop.
>
> In our alg, we exploit the "as tokens get older they become less
> important" characteristic,
and I think that makes sense.
and put tokens in bins as described in the
> expiry section of the sa-learn docs. The first pass generates the bins
> and figures out the count, the second pass does the expiry.
The problem here is that there are situations where the expiry will fail
even for completely valid and uncorrupted databases and there's no way to
*really* force the expiry. F.i. if bayes_expiry_max_db_size is set to
500.000 or there's so few mail flowing thru the system that it takes months
to reach the 150.000 default threshold the db won't expire for months.
There's a good chance that the db was trained with much more force in the
first days and then got built with much less effort and by auto-learning.
So, there is a higher percentage of older tokens (or long ago learned and
long not used tokens). I guess even if your tokens are equally distributed
over time the currently used method will fail when the db is much older than
a few months (= has a delta of that age). Also, if you change your
max_db_size value drastically over time it will possibly fail.
Take the example I gave in my other email. When I first posted on Feb 15
about the problem everyone pointed at the negative value and that it's
possibly corrupted. Well, I removed all wrong values and rebuilt the db but
the expiry still failed. It wasn't the weird atime values which prohibited
its success but the fact that it apparently never had expired before and the
"estimation pass" was bound to fail because of the algorithm used. The atime
delta in that db was about 1 year (30000000) after I had corrected it. The
expire calculation stopped with the tenth try at about a delta of 22000000.
So, the next delta would have been 44000000 and removed nothing because
there aren't tokens that old. Which means even when continuing there would
have been no expire, never. In that stage (ten) it would have expired about
200.000 tokens. That sounds like a lot but is less than a third of the whole
token count of nearly 700.000. Also, that's not too bad in terms of equal
distribution in time I think. The time range of the "old" tokens (8000000)
is a bit less than one third of the whole time range (30000000) and the
number of tokens in that range is a bit less than a third. So, that fits
together, roughly.
In retrospect, going with the "as tokens get older they become less
important" premise I would have possibly told it to remove those 200.000
tokens. But there's no way to do that. Of course, there's one way: reduce
the bayes_expiry_max_db_size by at least 200.000 = a value which will be a
little bit higher than the tenth try would remove. I think in that case the
tenth try should be able to expire, shouldn't it? I didn't think of that
when I was trying to get the expire run, though. I recreated the db with
wrong values for the last two magic tokens, so that it wouldn't go in the
"estimation pass". And maybe even some of those "spared" 200.000 tokens
prove valuable in the near future :-)
I guess when you have Bayes dbs for individual users it's quite likely that
databases need months before the first expire would run and many won't have
even reached that yet. Which means that many people haven't hit the problem
yet, but will.
>
> Tokens in the future shouldn't occur since we use received time as the
> atime, but sometimes it happens, so in 3.0 if received time > current
> time, atime == current time.
I think the expire should always remove any tokens where the atime is very
old (a year?) or newer than the current time. I had about 5.000 (of nearly
700.000) values in that db which were negative or 0 or in the future. So,
that apparently happens. Maybe only in older versions, I don't know. This db
was started with the first Bayes implementation in a released SA version
(2.43, I think).
>
> If things work as they should (you generally get the same amount of
> email over time), the algorithm works fine.
Possibly not if your first expiry happens only after several months.
> Overall, it works very well though.
I believe that, but there are also cases where it will fail completely for
the above mentioned reasons although your database is fine. And it's
possible that a lot of people are still to hit that problem because they
haven't reached the first expire yet. I think the proposal I make in the
other mail would solve the problem that the "estimation pass" fails in the
described situation.
>
> FYI, the Bayes DB is expected to be "expendible", so in a worst case
> scenario, delete the bayes db and start anew.
Who wants to delete a Bayes db which tags almost every incoming spam with
bayes_99 and almost every incoming ham with bayes_00? I also didn't see any
negative effects on performance with that 20+ MB db, so I wanted to keep it.
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Kai Schaetzl <ma...@conactive.com>.
Pilar Sancho wrote on 14 Apr 2004 09:20:33 +0200:
> I have spamassassin 2.63 installed for system-wide and also I had many
> problems with the expiration of the data base, after much to look I
> thought that it happened when it had tokens with atime as date to
> future,
Makes sense. Once an expire has been run and later you get atimes in the
future the guesstimate expire won't work because it will expire nothing.
And after a while when the estimation pass gets used it may expire too
much, so would fail again.
for what I put a control in Bayes.pm and BayesStore.pm when he
> learns a new message in order that if atime was a date to future it was
> changing it to the date of the system.
>
I thought SA would be using the current time of the system, anyway. If it
uses the time of the mail instead then I understand how the past and
future dates got in our db.
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Pilar Sancho <pi...@unizar.es>.
I have spamassassin 2.63 installed for system-wide and also I had many
problems with the expiration of the data base, after much to look I
thought that it happened when it had tokens with atime as date to
future, for what I put a control in Bayes.pm and BayesStore.pm when he
learns a new message in order that if atime was a date to future it was
changing it to the date of the system. This is
my $time_system;
$time_system = time();
if ($atime > $time_system) {
$atime = $time_system;
}
$self->{db_toks}->{$tok} = $self->tok_pack ($ts, $th, $atime);
In BayesStore.pm also change
if (!defined ($oldmagic) || $oldmagic eq "" || $atime < $oldmagic) {
$self->{db_toks}->{$OLDEST_TOKEN_AGE_MAGIC_TOKEN} = $atime;
}
by
$oldmagic = 0 if (defined($oldmagic) && $oldmagic eq < "");
if (!defined ($oldmagic) || $atime < $oldmagic) {
$self->{db_toks}->{$OLDEST_TOKEN_AGE_MAGIC_TOKEN} = $atime;
}
Pilar
El mar, 13 de 04 de 2004 a las 17:56, Theo Van Dinter escribió:
> On Mon, Apr 12, 2004 at 11:56:29PM -0600, Alan Baxter wrote:
> > I assumed that Kai meant the oldest atime values. Why doesn't expire
> > simply expire the LRU x tokens?
>
> The short answer is: that's essentially what 2.5x did, and it didn't work
> very well, so we spent some time and developed a more complex algorithm
> for 2.6x. overall, the new algorithm works well and has less issues
> than the 2.5x version.
>
> The slightly longer answer is: no matter what, you need to go through
> all the tokens in a loop once. to calculate the atime "x" from above,
> you have to go through all the tokens in a loop first (aka: first pass)
> to figure out the right "x", then go through that previous loop (second
> pass) to do the expire. all of the tokens at the given atime "x" should
> be expired at the same time, since they all have the same importance.
>
> In our alg, we exploit the "as tokens get older they become less
> important" characteristic, and put tokens in bins as described in the
> expiry section of the sa-learn docs. The first pass generates the bins
> and figures out the count, the second pass does the expiry.
>
> Tokens in the future shouldn't occur since we use received time as the
> atime, but sometimes it happens, so in 3.0 if received time > current
> time, atime == current time.
>
> If things work as they should (you generally get the same amount of
> email over time), the algorithm works fine. There's even an estimation
> system in place to bypass the first pass above, unless estimation is
> likely to come up with bad results (aka: "something looks fishy ...")
> In certain corner case situations, there are some issues though, which
> is standard for most algorithms. Overall, it works very well though.
>
> FYI, the Bayes DB is expected to be "expendible", so in a worst case
> scenario, delete the bayes db and start anew.
--
________________________________________
Pilar Sancho Moreno
Área de Sistemas
Servicio de Informática y Comunicaciones
Universidad de Zaragoza
Tf: 976 761000 ext 3210
e-mail: psancho@unizar.es
________________________________________
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Theo Van Dinter <fe...@kluge.net>.
On Mon, Apr 12, 2004 at 11:56:29PM -0600, Alan Baxter wrote:
> I assumed that Kai meant the oldest atime values. Why doesn't expire
> simply expire the LRU x tokens?
The short answer is: that's essentially what 2.5x did, and it didn't work
very well, so we spent some time and developed a more complex algorithm
for 2.6x. overall, the new algorithm works well and has less issues
than the 2.5x version.
The slightly longer answer is: no matter what, you need to go through
all the tokens in a loop once. to calculate the atime "x" from above,
you have to go through all the tokens in a loop first (aka: first pass)
to figure out the right "x", then go through that previous loop (second
pass) to do the expire. all of the tokens at the given atime "x" should
be expired at the same time, since they all have the same importance.
In our alg, we exploit the "as tokens get older they become less
important" characteristic, and put tokens in bins as described in the
expiry section of the sa-learn docs. The first pass generates the bins
and figures out the count, the second pass does the expiry.
Tokens in the future shouldn't occur since we use received time as the
atime, but sometimes it happens, so in 3.0 if received time > current
time, atime == current time.
If things work as they should (you generally get the same amount of
email over time), the algorithm works fine. There's even an estimation
system in place to bypass the first pass above, unless estimation is
likely to come up with bad results (aka: "something looks fishy ...")
In certain corner case situations, there are some issues though, which
is standard for most algorithms. Overall, it works very well though.
FYI, the Bayes DB is expected to be "expendible", so in a worst case
scenario, delete the bayes db and start anew.
--
Randomly Generated Tagline:
"Bill thinks having a bird crap on him is a complement to him from the
gods." - News Radio
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Alan Baxter <at...@baxtersys.com>.
On Mon, 12 Apr 2004 18:14:14 -0400, Matt Kettler <mk...@evi-inc.com>
wrote:
>I hate to say it, but why exactly would token age be a good expiry value?
>
>You'd still have similar problems if your ctime got corrupted, and ctime is
>a lousy criteria for dumping tokens compared to atime.
I assumed that Kai meant the oldest atime values. Why doesn't expire
simply expire the LRU x tokens?
Alan
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Kai Schaetzl <ma...@conactive.com>.
Matt Kettler wrote on Mon, 12 Apr 2004 18:14:14 -0400:
> I hate to say it,
you don't ;-)
> but why exactly would token age be a good expiry value?
Sorry, wrong wording. I recalled incorrectly from the discussion in Feb that
atime = addtime. Of course, atime = accesstime make much more sense, since as
you say, we don't want to expire tokens which might have been accessed quite
recently. Sorry for leading you in the wrong path.
But the basic problem remains: why doesn't SA simply expire the oldest x atime
values? I think I can give now the answer to this: that would involve
sorting/indexing the db for atime and the authors possibly want to avoid it
for time/ressource reasons. That's only fair. The problem with the current
expiry method, at least as far as I understand it, though, is that it fails
for good databases (!) just because of the way it determines when it needs to
switch to calculation mode. Also, I'm not convinced that the calculation
method (which can take several minutes before it finally fails) is faster than
resorting the db.
I just need to have a db which wasn't expired for a month or didn't ever have
tokens removed and it goes to calculation mode (per
http://useast.spamassassin.org/doc/sa-learn.html which contains a quite good
explanation of the mechanism but doesn't explain atime ;-). Now, I can imagine
a lot of valid reasons why this may happen (no expiry for one month). The
problem with calculation mode I guess is that it is not very fine-grained. It
stops after ten tries and maybe even if it didn't stop it may never succeed
because a run might either expire too many or too few tokens. So, it's
possible that it fails for completely valid databases.
F.i. I think this shows quite valid values:
0.000 0 2 0 non-token data: bayes db version
0.000 0 18734 0 non-token data: nspam
0.000 0 5126 0 non-token data: nham
0.000 0 695747 0 non-token data: ntokens
0.000 0 1051791290 0 non-token data: oldest atime
0.000 0 1081791290 0 non-token data: newest atime
0.000 0 1081782255 0 non-token data: last journal sync atime
0.000 0 1080581038 0 non-token data: last expiry atime
0.000 0 0 0 non-token data: last expire atime delta
0.000 0 0 0 non-token data: last expire reduction
count
but it won't expire because it goes into calculation mode and fails since the
tenth run would still expire some 200.000 tokens (with the db I used).
(The table above is the result from the table/db below after
removing/correcting all wrong values/tokens but leaving the last two lines
uncorrected. The table below is the original table but with corrected last two
values, these are the values I finally changed above to trigger correct
expiry.)
On the other hand:
0.000 0 2 0 non-token data: bayes db version
0.000 0 18734 0 non-token data: nspam
0.000 0 5126 0 non-token data: nham
0.000 0 695747 0 non-token data: ntokens
0.000 0 0 0 non-token data: oldest atime
0.000 0 -17982 0 non-token data: newest atime
0.000 0 1081782255 0 non-token data: last journal sync atime
0.000 0 1080581038 0 non-token data: last expiry atime
0.000 0 30000000 0 non-token data: last expire atime delta
0.000 0 5700 0 non-token data: last expire reduction
count
has values which indicate wrong atimes for tokens. However, it might
nevertheless correctly expire because I give it faked values for the last two
values (I didn't try, I corrected all wrong values including all tokens before
running expire). With these values it will start an estimate run instead of a
calculation run. I also think there's something wrong in the calculation here
because it thinks that -17982 is the newest value, but it's the oldest I would
think.
A better approach might be to assume that tokens are equally distributed over
time and then expire the x% "oldest". That is take the oldest/newest atime
delta, reduce this to 100-x% (say 95%) and expire all tokens below this atime
and above the current time. This would automatically eliminate all tokens with
wrong atime values, too. I mean it would never fail to expire, no matter how
corrupted the atime values are. We would use two configuration options:
expire_range: 5 (in percent)
expire_threshold: 50 (in percent)
This setting would remove all tokens which don't belong in the 95% range of
"newest" tokens, but would stop if it removes more than goal+50% tokens. This
would prevent too many removals in case the tokens in your db are so unequally
distributed that a big amount of them belongs in the 5% "oldest" range.
Does this explanation and proposal make sense?
Kai
--
Kai Sch�tzl, Berlin, Germany
Get your web at Conactive Internet Services: http://www.conactive.com
IE-Center: http://ie5.de & http://msie.winware.org
Re: Why doesn't expire simply expire the oldest x tokens?
Posted by Matt Kettler <mk...@evi-inc.com>.
I hate to say it, but why exactly would token age be a good expiry value?
You'd still have similar problems if your ctime got corrupted, and ctime is
a lousy criteria for dumping tokens compared to atime.
By using age (aka creation time) you're suggesting that SA use FIFO (first
in, first out) for flushing old tokens, instead of LRU (least recently
used) which it currently does.
FIFO is a pretty lousy algorithm for caches in terms of hit rate, LRU is
substantially better, there's LOTS of research to back that up. The same
concept applies to memory paging, and pretty much every limited datasize
system where performance is based on hit-rate.
citation:
http://www.cs.ucr.edu/~marek/pubs/lru_vs_fifo.ps
I can't see why switching to ctime would be good.. However, I can see why
it would suck, as you throw away the oldest tokens, despite their recent
occurrence in email.
Now, I'll admit SA could use some improvements in handling corrupted DBs,
but I don't think switching to token age is a very good idea.