Re: Stale entries in dnscache's cache structure

My thought is that you begin with a simple

- queue { *prev, unixtime; **data }; // and whatever required fields.
- one function that swaps current struct with parent when a struct is
accessed.

stale data with sink to the bottom.

oh and one var **latest, which points to end of list. furthest from the head
of the list.

On Wed, Mar 10, 2010 at 4:39 PM, Laurent Bercot <[email protected]>wrote:

>  Let's be a bit technical for a change, shall we?
>
>  Let's assume, for academic purposes, that I am designing a cache
> structure meant to store generic data with an expiration date - for
> instance, DNS entries.
>
>  I studied dnscache's cache structure, and am appalled by its simplicity.
> It's just beautiful that such a simple structure can be used; no wonder
> dnscache is fast.
>  However, this simplicity comes at the cost of a little functionality.
> Entries cannot be directly removed, they remain in the cache until the
> cache is full and oldest entries are overwritten in a round-robin way.
> Expiration time is not a factor in deciding what entry should be removed
> to make room.
>  As a result, a cache might be full of stale entries, and entries that
> might still be valid will be deleted before entries that have been
> written afterwards, but with a smaller TTL, and that have become stale.
>
>  Since dnscache seems to work well, it seems like a minor inconvenience;
> I don't think it's causing enough superfluous DNS traffic to be an issue.
> But still, the architect in me frowns. It would be better design to
> remove stale entries *first* when the cache is full; and then, if it's
> still full, remove the oldest valid entries.
>  I can do this; it's not even very complex (store indices in a binary
> search tree ordered by expiration time as well as by key hash).
> Still, compared to dnscache's absolute simplicity, this is adding quite
> a lot of code, and probably a bit of CPU usage and a loss of RAM
> efficiency for a likely minor benefit.
>
>  What do you think ? Should I go for the theoretically better solution,
> or does usage show that this flaw in dnscache is never a problem in
> practice and simplicity wins ?
>
> --
>  Laurent
>



-- 

- If you don't ask a question, you get nothing.

- to not see and believe is better than to see and not believe.

*** Note Well: This email address is private and may NOT be used nor
redistributed to third parties for the purpose of sending me information
that I have NOT requested.  Any use of this email address without *MY*
explicit permission will be considered a Trespass and may result in a
Monetary consequences.