Hi all,
After reviewing the source code, I am still not 100% sure how write_expire is implemented.
Basically, I want to know if I have a table with n elements, and each element should expire 1 minute after its insertion - will bro loop over all elements in the list checking if they are expired ?
if this is the case then write_expire should be O(n), is this correct ?
Thank you,
B
Hi,
the main function implementing expiry is TableVal::DoExpire in Val.cc
(approximately line 2175).
Basically, I want to know if I have a table with n elements, and each
element should expire 1 minute after its insertion - will bro loop over all
elements in the list checking if they are expired ?
Yes, Bro will loop over all elements from time to time, setting internal
timeouts that cause a loop over the whole table removing expired elements.
Note that elements are not guaranteed to expire after the expiration time;
they will be removed sometime after expiration time, but it can take a
bit.
if this is the case then write_expire should be O(n), is this correct ?
The time overhead of expiration is O(n), correct.
Johanna
To clarify because there could be different interpretations here: it's
indeed O(n) for the whole expire operation, however that is amortized
over a longer time frame: when Bro iterates over the table, it works
on short slices at a time (which is the reason that it can take longer
to expire an element, as Johanna wrote). So it's not O(n) for each
table operation or such.
Robin
I have a couple of bro policies in production where I store/expire/extend hundreds of thousands (if not million+) elements/records from table(s). SO far has been operationally workable. Offcourse, the expirations don't happen at the dot on the clock but often little later but that doesn't concern much.
Aashish
Oh! good point. That also reminds me that if your expire times are < 10seconds then you'd have to redef table_expire_interval to a value < 10 seconds.
bro ./test-expire-func.bro
1483204866.281666 starting: table_iteration, 1
1483204866.281932 inside table_expire_func: table_iteration, 2
1483204876.381928 inside table_expire_func: table_iteration, 3
1483204886.481921 inside table_expire_func: table_iteration, 4
1483204896.582114 inside table_expire_func: table_iteration, 5
Note: expire kicks in every 10 seconds.
## Check for expired table entries after this amount of time.
Oh! good point. That also reminds me that if your expire times are < 10seconds then you'd have to redef table_expire_interval to a value < 10 seconds.
I was just typing the same! You can also influence the delay and step
size using table_expire_interval and table_incremental_step
(https://www.bro.org/sphinx/scripts/base/init-bare.bro.html?#id-table_expire_delay).
Jan