CAS is broken
tomash.brechko at gmail.com
Sun Nov 11 17:39:33 UTC 2007
>From the description of the protocol:
- <cas unique> is a unique 64-bit value of an existing entry.
Clients should use the value returned from the "gets" command
when issuing "cas" updates.
If I understood the corresponding thread right, the idea is to provide
some sort of atomicity: if multiple clients 'gets' CAS value, only one
would be able to update the entry with 'cas', and everyone else will
However internally (and this was mentioned in the thread) CAS value is
actually a pointer (cast to uint32_t for some reason). So I thought,
how we know the pointer won't be reused?
I spend some time trying to compose the test case, but indeed, no CAS
value for which you did 'gets' was ever reused. This made me to
conclude that gets simply leaks some data (what's called item
Next two patches show that CAS is broken: first is a test case that
runs indefinite loop and does 'set', 'gets'. See how memory usage
Second patch fixes the leak, and adds a test that shows that without
this leak item addresses are really reused, and so can't be used for
I think this might be fixed with proper generation counters wide
enough to never wraparound (64-bit). Besides, such generation
counters will enable a fast path in the client:
# set the value
# get CAS
CAS = gets ...
# update the value
cas ... CAS
# update the value. If we are lucky, no need to call gets again.
cas ... CAS+1
What do you think?
More information about the memcached