CAS is broken

Tomash Brechko tomash.brechko at
Sun Nov 11 17:39:33 UTC 2007

Hi there,

>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
  set ...

  # 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?

   Tomash Brechko

More information about the memcached mailing list