rakelimit icon indicating copy to clipboard operation
rakelimit copied to clipboard

compress countmin state to 64bits

Open lmb opened this issue 4 years ago • 0 comments

The value we store in a count-min sketch is currently 128bit:

struct cm_value {
        fpoint value;
        __u64 ts;
};

I think we can compress this to 64 bits total: a __u32 for the estimated rate in pps and a __u32 for the timestamp. This means the timestamp would wrap every 4.2s but given our current WINDOW that isn't a problem. It just needs code to deal with it.

Doing this will halve the memory we need, plus on 64bit arches we can (probably) use a single load and store for struct cm_value which reduces the likelihood of observing a race condition.

lmb avatar Sep 21 '20 08:09 lmb