CAS and why I don't want to add it to Redis

[Salvatore Sanfilippo]

Hello,

from time to time somebody asks why Redis lacks "CAS", the memcached
Check And Set operator. This operator works in the following way:

when the client performs a GET the server actually returns two values:
the value of the key itself and an integer, that is called a
"cas_token" in memcached slang, but actually it's a 64 bit integer
that you can think as a "version" of the value contained inside a key.
Every time a key is set to another thing this counter increments.
Thanks to this token you can update the value stored at the key in a
way that it will only be modified if no other client changed that
value since your GET with
the following semantic:

value,cas_token = GET <key>
... perform some work on value that will produce new_value ...
CAS <key> <new_value> <cas_token_redeived_by_get>

If the token you are sending to the CAS operation matches the current
key token then the key will be set to the new value, otherwise CAS
notifies the client that no update was performed.

This allows to mount a number of atomic operations on values. For
example you can implement Redis' LPUSH:

LOOP FOREVER
value,token = GET mykey
value = .... restore the value that is probably serialized in some
way, append the element, re-serialize the value ...
CAS mykey value token
BREAK if CAS returned success (i.e. the value was updated)
END

At a first glance this may appear like a cool locking free operation
that makes possible to perform a lot of higher level atomic operations
without locking. Unfortunately if you study a bit more in depth the
semantic it turns out that CAS is a weak, ill conceived, form of
locking. Basically when CAS returns that it was not able to perform
the operation because some client updated the key in the meantime you
need to redo the operation again: this is like waiting for a lock, but
with two main drawbacks:

- You will find that the lock was not obtained after you already did
all the work to create the new value, issued and transfered the new
value, and so on...
- There is no serialization of all the clients waiting for a key, so
in theory a slow client will have a very bad time trying to modify a
key.

Imagine for example that you have two Linux boxes trying to perform a
lot of LPUSHes against a single key with a lot of value inside. But
one Linux box isi four times faster than the other one. The
de-serialize, append the new value, serialize, can be pretty slow, so
the fast Linux box will probably be able to update the key multiple
times while the slow one is trying to update the key one time. The
slow Linux box will get a lot of CAS failures before of being able to
update the key.

So IMHO CAS appears to be cool but it sucks. Moreover it's totally
conceived for a just-string-values scenario, for instance you can't
implement Redis' SMOVE with CAS, or any other operation working
against multiple elements in a Redis List or Set. For complex
operations what we want is a very fast and flexible locking primitive,
and this is what Redis will get in the long run. That said thanks to
the higher level operations offered by Redis we can live well and
without locking for now, and this will be anyway the preferred way to
do things, but sometimes locking is really needed.

Ok looks like we have a new entry for the FAQ :)

Regards,
Salvatore

--
Salvatore 'antirez' Sanfilippo
http://invece.org

[Toby DiPasquale]

On May 3, 8:42 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:

I'm forced to disagree with you on this one, Salvatore. Scusi ;-)

Optimistic concurrency as implemented via CAS (which is "Compare and
Swap", btw, named after the assembly language instruction that's the
reason why your Linux box is so fast these days ;-)) is a very valid
concurrency technique in the case where reads dominate writes. Most
writes will be uncontested and reads do not have to incur locking
overhead. If that's not the case, you should definitely use a more
pessimistic or hybrid concurrency scheme, but I'd imagine that a lot
of the potential uses for Redis would be read-heavy (e.g. what Engine
Yard is planning to use it for in Nanite).

> LOOP FOREVER

Nobody ever does this. You try some number of times and then give up
and return an error after that.

>     value,token = GET mykey
>     value = .... restore the value that is probably serialized in some
> way, append the element, re-serialize the value ...
>     CAS mykey value token
>     BREAK if CAS returned success (i.e. the value was updated)
> END

[...]

> - There is no serialization of all the clients waiting for a key, so
> in theory a slow client will have a very bad time trying to modify a
> key.

In theory, this is true. In practice this is hardly ever an issue as
most clients will be on the same infrastructure (except when Redis is
exposed to the public WAN, which ought to be rare given its lack of
hardening or security features).

> So IMHO CAS appears to be cool but it sucks. Moreover it's totally
> conceived for a just-string-values scenario, for instance you can't
> implement Redis' SMOVE with CAS, or any other operation working
> against multiple elements in a Redis List or Set. For complex
> operations what we want is a very fast and flexible locking primitive,
> and this is what Redis will get in the long run. That said thanks to
> the higher level operations offered by Redis we can live well and
> without locking for now, and this will be anyway the preferred way to
> do things, but sometimes locking is really needed.

Again, this is just simply not true. Every list or set could have its
own counter value for operations that affect the whole and that could
easily be used for CAS. You could even have the list/set with its own
counter and each element of the list/set with its own counter for use
with CAS and that would work just fine, as well (although you may have
more contention for the elements this way).

I'm not saying you have to put CAS in Redis, but don't be confused
about its potential utility. Also, for a real world example of how CAS
works really well on these types of data structures, consult your
local Linux kernel engineer for a tutorial on RCU in the later 2.6.x
kernels.

--
Toby DiPasquale

[Salvatore Sanfilippo]

On Sun, May 3, 2009 at 10:08 PM, Toby DiPasquale <codes...@gmail.com> wrote:
>
> On May 3, 8:42 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:
>
> I'm forced to disagree with you on this one, Salvatore. Scusi ;-)

Hello Toby! Disagreeing is the first step for constructive arguments
so it's welcomed :)

> Optimistic concurrency as implemented via CAS (which is "Compare and
> Swap", btw, named after the assembly language instruction that's the
> reason why your Linux box is so fast these days ;-)) is a very valid
> concurrency technique in the case where reads dominate writes. Most

The CAS in a CISC architecture makes a lot of sense since being
implemented in hardware this allows for a synchronization primitive
that is very fast indeed. My original arguments are about the behavior
of a CAS instruction in KV stores that are usually connected to
clients by a relatively slow link (i.e. a socket).

> writes will be uncontested and reads do not have to incur locking
> overhead. If that's not the case, you should definitely use a more

key-granularity locking (or token based locking) in a KV store does
not need to be slower than a CAS instruction. This is my primary
point. Also it is less memory intensive since every key will use 8
byte less memory (otherwise used for the 64 bit counter).

> pessimistic or hybrid concurrency scheme, but I'd imagine that a lot
> of the potential uses for Redis would be read-heavy (e.g. what Engine
> Yard is planning to use it for in Nanite).

Most of the time in Redis to lock is not needed at all. When it's
needed you usually need to perform a complex, multi-keys or
multi-elements operation that is not possible to define via CAS.

>> LOOP FOREVER
>
> Nobody ever does this. You try some number of times and then give up
> and return an error after that.

That is an implementation detail. If we want to argue about creating
algorithms on primitives you must assume the operation eventually will
succeed.

>> - There is no serialization of all the clients waiting for a key, so
>> in theory a slow client will have a very bad time trying to modify a
>> key.
>
> In theory, this is true. In practice this is hardly ever an issue as
> most clients will be on the same infrastructure (except when Redis is
> exposed to the public WAN, which ought to be rare given its lack of
> hardening or security features).

The link speed is not in question here. I mean a CPU four times
slower, and a lot of serialization/de-serialization work
(milliseconds), is all you need for this scenario to be real-world.

>> So IMHO CAS appears to be cool but it sucks. Moreover it's totally
>> conceived for a just-string-values scenario, for instance you can't
>> implement Redis' SMOVE with CAS, or any other operation working
>> against multiple elements in a Redis List or Set. For complex
>> operations what we want is a very fast and flexible locking primitive,
>> and this is what Redis will get in the long run. That said thanks to
>> the higher level operations offered by Redis we can live well and
>> without locking for now, and this will be anyway the preferred way to
>> do things, but sometimes locking is really needed.
>
> Again, this is just simply not true. Every list or set could have its
> own counter value for operations that affect the whole and that could

The problem is that most of the time you need locking in Redis it is
going to be multi-key or multi-element, so CAS can't work, without to
mention that LOCK/UNLOCK will basically be as fast and without the
scaling issues and so on.

Example: atomically takes an element from key1 and put it on key2:

LOCK key1 key2
val = LPOP key1
LPUSH key2 <val>
UNLOCK key1 key2

How to do this with CAS? Note that Redis LOCK will be token based, so
while we are using "key1" and "key2" as tokens because it's natural to
lock the keys with the same name it is possible to use any kind of
token, it just needs to be a string.

> I'm not saying you have to put CAS in Redis, but don't be confused
> about its potential utility. Also, for a real world example of how CAS
> works really well on these types of data structures, consult your
> local Linux kernel engineer for a tutorial on RCU in the later 2.6.x
> kernels.

I'm not saying optimistic locking does not make sense in general, it
can be a valuable technique to have the advantages of locking without
to require all the cost of locking. I simply think that in this
specific domain of KV stores with a networking-speed link it is
absolutely questionable if it's worth to have this instead of a simple
for of locking, so I exposed my concerns in order to publicly motivate
why in Redis I think this is not going to be a good idea.

Optimistic locking, check and swap instructions in CISC processors,
are all very valid techniques used in a very different domain.

Thanks for your arguments,
Salvatore

>
> --
> Toby DiPasquale

[Michal Frackowiak]

Nevertheless, I think some kind of (optimistic) locking would be
really welcomed for Redis. Conflicts when updating values are one of
the first things you run into when creating a high-concurrency
application.

Let us forget about complex operations for a while. Key-value is what
should IMHO have at least basic conflict resolution, and perhaps there
is a dead simple way to do this.

First of all - 90% of time you do not need conflict resolution, and
this is fine. But in a simple case when two clients fetch the value
and try to commit the new update, conflicts are not nice. At our
application we are running about 5k updates per second (Redis rocks),
and during the test-run we got a few conflicts and data
inconsistencies so far. Redis is the only db storage for us, so it
looks important.

Here is just an idea: a new, simple command:

SETIF key, value, checksum

it would work like SET, but client should also pass a checksum of the
OLD value the client thinks should be replaced (or the old value, but
sometimes you store large values, so it might be not efficient). If
within Redis the checksums do not match, error is returned. Now it is
the client application that should decide what to do next - this would
vary depending on the particular scenario.

The checksum could be calculated using MD5, SHA1 or any other hashing
algorithm that is quick enough and provides low probability of
collisions. Or the old value itself could be passed - it would work
better for short values.

Values are always strings, so there is no serialization problem here.

IMHO it provides a simple and efficient way of making the client
application sure that there is no conflict in updating values. Also,
it looks (at least at the first sight) dead simple to implement, and
does not change any of the existing commands nor data structures.

What do you guys think about it?

regards - Michal

[Jason Watkins]

> The CAS in a CISC architecture makes a lot of sense since being
> implemented in hardware this allows for a synchronization primitive
> that is very fast indeed. My original arguments are about the behavior

CAS is on RISC architectures as well. AFAIK it or it's cousin Load
Linked / Store Conditional is the basis of mutual exclusion on almost
every processor architecture.

> key-granularity locking (or token based locking) in a KV store does
> not need to be slower than a CAS instruction. This is my primary
> point. Also it is less memory intensive since every key will use 8
> byte less memory (otherwise used for the 64 bit counter).

CAS can be based on checksums/hashes or any similar implicit function
of the value, though this does expose a potential false positive that
makes an update silent when the history of a key is A B A. This isn't
important for most algorithms however since applications that care
about history tend to be append only (accountants don't use erasers).
I believe memcached's CAS is designed to use the local memory address
by default in order to avoid any per key overhead.

> Most of the time in Redis to lock is not needed at all. When it's
> needed you usually need to perform a complex, multi-keys or
> multi-elements operation that is not possible to define via CAS.

These are entirely possible, and several different schemes exist in
the literature. The common approach is to do something similar to:

1.) Store a transaction descriptor at some arbitrary unused key. The
descriptor among other things contains the read/write set for the
transaction, possible as a bloom filter.
2.) Store a reference to the transaction descriptor in each key of the
read/write set, using CAS on each key
3.) Store the new value in each key of the write set, restore values
in each key of the read set, using CAS on each key

If a CAS fails at any point in this, contention is detected. There are
many possible contention management strategies that make different
tradeoffs. Common schemes are for all parties to help restore old
values, all parties to assist in setting new values where earliest
transaction wins, exponential back off and retry, before doing one of
the above, etc. There are also choices about when you set keys to
reference the descriptor, either at the beginning of the transaction
or at commit time. Generally the choices are based on whether you're
more worried about livelock or read latency. Additionally, most of the
schemes above have correctness proofs in the presence of arbitrary
failures, which is quite useful in distributed systems.

I'll admit that these choices get complex, but the beauty of CAS is
that allows such flexibility. Many applications don't need full STM,
and can use semantics specific to their situation to shortcut work.

> > Nobody ever does this. You try some number of times and then give up
> > and return an error after that.
>
> That is an implementation detail. If we want to argue about creating
> algorithms on primitives you must assume the operation eventually will
> succeed.

All transactional systems must deal with contention, and in general
require all but one of the conflicting parties to retry their
operation.

> The problem is that most of the time you need locking in Redis it is
> going to be multi-key or multi-element, so CAS can't work, without to
> mention that LOCK/UNLOCK will basically be as fast and without the
> scaling issues and so on.
>
> Example: atomically takes an element from key1 and put it on key2:
>
> LOCK key1 key2
> val = LPOP key1
> LPUSH key2 <val>
> UNLOCK key1 key2

It's not nearly this simple. What happens if someone else does a LPUSH
in the middle of this? This matters for real applications (example:
doing anything that looks like merge sort). If redis tracks what keys
are locked, how does it do this when distributed and keys reside on
different machines? This will require atomic broadcast at best, or a
paxos implementation at worst. If redis doesn't track this and clients
attempt to check if keys are locked, locks will be exposed to the
double checked lock pitfall.

Perhaps I'm missing something but I don't think there exists any
simple form of locking in the distributed setting.

Jason

[jstrellner]

Hi Salvator,

If you do ever implement CAS, please also include a toggle variable in
the configuration to disable it. We do very heavy writes, and few
reads (but important reads nonetheless).

I actually kind of like Michal's solution. It allows you to use a CAS-
like feature any time that you need to, and if you use the normal SET
command, it wouldn't slow things down with a CAS implementation.

[Jason Watkins]

Now that I've posted a bunch of specific replies about how scary
complex distributed transactions are, no matter how you attempt to
implement them, let me shed some hope and say what I think 99% of web
applications can do: Treat keys as sets.

1.) When writing, append to the set. No locking required as this is a
commutative update.
2.) When reading, the application must be written so as to tolerate
several potential conflicting values.
3.) When resolving conflicts, do so by replacing the entire set of
values at a key as a transaction.

Here we avoid any multi-key transactions, hence transactions are
single site, making life dramatically simpler. Point 3 can often be
done as a cleaner/scraper process outside of any request/response loop
for minimal impact on performance.

Writing applications in the style of 2 can be a bit weird for people
who are used to the global consistency of a SQL db, but I don't think
it's a huge burden in the majority of cases, doubly so when we're just
using the K/V store as an object store for an OO language.

Personally I still like using a CAS instruction for the implementation
of point 3, since it is also a useful primitive for applications to
implement application specific distributed transaction semantics. We
can use locks instead, but will have to implement some sort of timeout
to avoid deadlock on client failure mid transaction. We could still do
distributed transactions with a transaction manager that monitors the
lock timeouts and issues compensating transactions. For most
applications throughput will be poor compared to optimistic schemes
however (set Pat Helland's criticisms).

Also note that CAS'd get is useful as a performance optimization:
clients may have a process local cache and periodically wish to poll
if values are current. CAS'd get lets them do this using minimal
bandwidth when current and no extra operations when not current. HTTP
uses this to great benefit.

Jason

[Salvatore Sanfilippo]

On Mon, May 4, 2009 at 6:36 PM, Jason Watkins
<jasonpau...@gmail.com> wrote:

>> key-granularity locking (or token based locking) in a KV store does
>> not need to be slower than a CAS instruction. This is my primary
>> point. Also it is less memory intensive since every key will use 8
>> byte less memory (otherwise used for the 64 bit counter).
>
> CAS can be based on checksums/hashes or any similar implicit function
> of the value, though this does expose a potential false positive that
> makes an update silent when the history of a key is A B A. This isn't
> important for most algorithms however since applications that care
> about history tend to be append only (accountants don't use erasers).
> I believe memcached's CAS is designed to use the local memory address
> by default in order to avoid any per key overhead.

checksum/hashes based CAS can't have the described semantic btw:

SET foo "bar"
value,cas_token = GET foo
SET foo "a"
SET foo "b"
SET foo "bar"
CAS foo "newvalue" cas_token

what's supposed to do? If it's based on checksum or even the full
value CAS is going to set the value anyway even if changes occurred in
the middle.

If it's based on pointers I guess that either memcached never release
memory about keys, or it may happen that the same pointer is
reassinged to another key.

>> Most of the time in Redis to lock is not needed at all. When it's
>> needed you usually need to perform a complex, multi-keys or
>> multi-elements operation that is not possible to define via CAS.
>
> These are entirely possible, and several different schemes exist in
> the literature. The common approach is to do something similar to:
>
> 1.) Store a transaction descriptor at some arbitrary unused key. The
> descriptor among other things contains the read/write set for the
> transaction, possible as a bloom filter.
> 2.) Store a reference to the transaction descriptor in each key of the
> read/write set, using CAS on each key
> 3.) Store the new value in each key of the write set, restore values
> in each key of the read set, using CAS on each key

You need to perform "undo" in this schema and restore values. Locking
allows for the same things without this undo stage. Why bother? I
mean, it looks like locking has all the advantages of CAS, and a lot
more in our scenario.

> I'll admit that these choices get complex, but the beauty of CAS is
> that allows such flexibility. Many applications don't need full STM,
> and can use semantics specific to their situation to shortcut work.

So I can admire that a so simple primitive can be used in many
different ways, I read a paper where there is even a mathematical
proof that CAS is almost as capable as other form of lockings, but
again, in our domain the recover of multi-keys/values lock is complex,
and while in CPUs there is a very important reason to implement
optimistic locking even at a cost of complex recovery (you get a lot
of speed) in Redis a simple blocking LOCK is going to solve all this
problems without any kind of slow down.

>> That is an implementation detail. If we want to argue about creating
>> algorithms on primitives you must assume the operation eventually will
>> succeed.
>
> All transactional systems must deal with contention, and in general
> require all but one of the conflicting parties to retry their
> operation.

Sure but usually with locking you need to retry the operation only
when a client did something really bad. For example it crashed in the
middle of the operation or something like this. The lock may timeout
and there is to acquire it again and so on. CAS requires recovery even
in the trivial case of different clients trying to update the same
values at around the same time. LOCK will trivially serialize the
different clients and nothing will fail.

This is extremely important in Redis. memcached is used as a cache
often but in Redis there are a lot of different use cases where the
same key requires serialization and at the same time is contented by a
lot of different clients. We don't want to fail or have scaling
problems in this case, but to serialize the clients.

>> The problem is that most of the time you need locking in Redis it is
>> going to be multi-key or multi-element, so CAS can't work, without to
>> mention that LOCK/UNLOCK will basically be as fast and without the
>> scaling issues and so on.
>>
>> Example: atomically takes an element from key1 and put it on key2:
>>
>> LOCK key1 key2
>> val = LPOP key1
>> LPUSH key2 <val>
>> UNLOCK key1 key2
>
> It's not nearly this simple. What happens if someone else does a LPUSH
> in the middle of this? This matters for real applications (example:

Who wants to LPUSH in the middle of this has to LOCK the key before to
push, and the operation is blocking, so until the other client didn't
finished the LOCK command will not return, nor the other commands will
be processed. Hey that's just plain locking, what's wrong or strange
about this?

> doing anything that looks like merge sort). If redis tracks what keys
> are locked, how does it do this when distributed and keys reside on
> different machines? This will require atomic broadcast at best, or a
> paxos implementation at worst. If redis doesn't track this and clients
> attempt to check if keys are locked, locks will be exposed to the
> double checked lock pitfall.

The LOCK primitive I want to implement can deal with:

a) distributed environments where there is per-key lock or multi-values lock.
b) against a single Redis instance when multi-key lock is required

What is missing is c) that is:

c) distributed environments where there is a multi-key (with keys in
different servers) locking.

But in order to do this, given that Redis lock is "token based" you
can do it actually!
Just use a single server to issue the LOCK calls, and all the other
Redis servers for the rest of the work.

> Perhaps I'm missing something but I don't think there exists any
> simple form of locking in the distributed setting.

Maybe I should clarify better how Redis LOCK will work.

The semantic is the following:

LOCK <token> <timeout_in_seconds>

this is the blocking lock. Basically "token" is any string and does
not require to be the name of a key. Is a truly general form of
locking at the point people may want to use a Redis server just for
locking of clients performing work against something different than
Redis data.

so

LOCK "foobar" 10

will just succeed ASAP if "foobar" token is not already locked.
Otherwise it will block waiting for the UNLOCK of the client currently
holding the lock.

What is the timeout about? If a client gets a lock against "foobar"
and does not unlock it in 10 seconds the lock will be removed and the
connection to this client closed ASAP. This should never happen under
normal conditions, but will happen if a client will be very slow for
some reason, or if it crashed and so on.

When a client want to release the lock it just calls

UNLOCK "foobar"

Usually when there are a lot of reads and few writes both LOCK and
UNLOCK will return OK ASAP and will basically be for free. When
instead there is contention the second client trying to perform LOCK
will wait until UNLOCK is called by the first client.

Add to this TRYLOCK. This is like LOCK but returns ASAP if the lock
can't be acquired with "0". Otherwise "1" is returned and the clients
knows the lock was acquired.

Given that token can be any kind of string (the same limitations of
the name of the key applies, no spaces, no newlines in token name) it
is natural sometimes to use as name the same name of the key itself,
but this is not required at all.

How this clarify a bit what will be the semantic of LOCK/UNLOCK

Cheers,
Salvatore

> Jason

[Salvatore Sanfilippo]

On Mon, May 4, 2009 at 10:16 AM, Michal Frackowiak <redb...@openlabs.pl> wrote:

> it would work like SET, but client should also pass a checksum of the
> OLD value the client thinks should be replaced (or the old value, but
> sometimes you store large values, so it might be not efficient). If
> within Redis the checksums do not match, error is returned. Now it is
> the client application that should decide what to do next - this would
> vary depending on the particular scenario.
>
> The checksum could be calculated using MD5, SHA1 or any other hashing
> algorithm that is quick enough and provides low probability of
> collisions. Or the old value itself could be passed - it would work
> better for short values.

Hello Michal,

Is the LOCK semantic I described enough to fix your issue? Please if
you can it is possible to have more details about the kind of data
manipulation requires this SETIF instruction? I'm not sure I'm able to
argument on this without a bit more details since I wonder if you need
SETIF in order to just give up at all with the update if the data
changed in the meanwhile or if you instead retry the operation.

Using lock your code could change in the following:

LOCK key
GET key
... manipulate key by code ...
SET key <newval>
UNLOCK key

Note that reading clients will not use LOCK at all, so they will be
able to read the data without any kind of locking.

Thank you very much!
Salvatore

[Jason Watkins]

> what's supposed to do? If it's based on checksum or even the full
> value CAS is going to set the value anyway even if changes occurred in
> the middle.

Right, this is the false positive I mentioned in the section you
quoted.
1.) It doesn't matter in most applications
2.) When it does, applications can include a monotonic counter in the
payload, which also decollates the CAS tag values.

> If it's based on pointers I guess that either memcached never release
> memory about keys, or it may happen that the same pointer is
> reassinged to another key.

Memcached doesn't care so much since it's permitted to lose data at
any time it likes. Actually, I may be incorrect about that statement:
I remember reading the discussion on the memcached list, but not what
the conclusion was.

> Maybe I should clarify better how Redis LOCK will work.

Ah, so advisory locks like in c/c++/java. I was thinking you meant
something more like mandatory locking specific keys.

This comes down to the classic arguments between pessimistic and
optimistic concurrency, as well as all the various criticisms of
manual locking. Personally I would still lean toward CAS since
algorithms built on top of CAS are typically obstruction free at least
and wait-free at best, but arguments could be made for including both.
I also think CAS is less likely to hoist one by their own petard, but
TBH I don't have enough experience with either scheme in this
situation to be sure of that. Certainly implementing transactions and
higher level data structures on top of CAS is as complex as getting
manual locking correct, if not more.

Both could work fine in the architecture I suggest most applications
use.

Jason

[Salvatore Sanfilippo]

On Mon, May 4, 2009 at 7:58 PM, Jason Watkins
<jasonpau...@gmail.com> wrote:

> Ah, so advisory locks like in c/c++/java. I was thinking you meant
> something more like mandatory locking specific keys.
>
> This comes down to the classic arguments between pessimistic and
> optimistic concurrency, as well as all the various criticisms of
> manual locking. Personally I would still lean toward CAS since
> algorithms built on top of CAS are typically obstruction free at least
> and wait-free at best, but arguments could be made for including both.

I want clarify on this about the implementation. If the key is not
already locked Redis's LOCK will just create an entry into an hash
table, and UNLOCK will remove this key. The only overhead is to send
the commands actually. On the other side there is no need to GET at
all when the locking is about doing things against multiple keys,
since no cas_token is needed. For example:

LOCK mykey_remove_from_both
LREM mkey_list ....
LDEL mykey_set ....
UNLOCK mykey_remove_from_both

So it's a really cheap operation. Of course when the key is instead
already looked, the pessimistic scenario, it's where LOCK starts to
have a serious advantage against CAS. It will just serialize the
different clients.

So basically in the optimistic scenario the overhead is just the fact
we have to send the commands to the server.

> I also think CAS is less likely to hoist one by their own petard, but
> TBH I don't have enough experience with either scheme in this
> situation to be sure of that. Certainly implementing transactions and
> higher level data structures on top of CAS is as complex as getting
> manual locking correct, if not more.

Well manual locking is a can of worms in programming, for example when
writing multi threaded applications, but here in Redis is going to be
very trivial. It's just a LOCK/UNLOCK block with some operation to
protect in the middle so my feeling is it will be pretty trivial to
use.

> Both could work fine in the architecture I suggest most applications
> use.

Probably yes, but my feeling is that for the nature of Redis
lock/unlock will be much more general and given that there are uses of
Redis when a lot of clients will work against few keys serialization
and pessimistic locking can be very helpful.

Also I love the idea of Redis being used just as locking server in
distributed environments. This is a feature we get for free this way.

[Jason Watkins]

Pragmatically LOCK with TRYLOCK addresses most of my concerns, though
you still can't implement wait free structures on top of it. I'd agree
this won't matter for most applications.

> Also I love the idea of Redis being used just as locking server in
> distributed environments. This is a feature we get for free this way.

Due to SPOF concerns I think zookeeper or similar would be much more
suitable for this usage.

[Adam Michaels]

Hello everyone.

Just wanted to say thanks to Salvatore and everyone who has
contributed thus far. This project really shows the greatness of open
source. A simple idea, well executed by a leader who is passionate yet
reasonable and open to debate. Ok, enough ass kissing for now.

This discussion inspired me to post what I've noticed in dealing with
locking in general.

LOCK mykey_remove_from_both
LREM mkey_list ....
LDEL mykey_set ....
UNLOCK mykey_remove_from_both

Does this lock the keys contained within the lock and unlock commands?
If so, you could do distributed locking by sending the lock and unlock
commands to all servers via the client or you could implement this in
the redis server by using the replication protocol. For those that
want optimistic locking they could use generational key names or
values. For example:

$var = GET mykey_counter
SET mykey_$var
$var = INCR mykey_counter 1
RENAME mykey mykey_$var


If there isn't one already, maybe redis can support a primitive to
make the above code simpler.

Generally, I do prefer the pessimistic locking approach since dealing
with write conflicts is a PITA. Optimistic locking ends up putting
your writes out of order as you retry them over and over and reload
stale data.

On May 4, 2:19 pm, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> On Mon, May 4, 2009 at 7:58 PM, Jason Watkins
>

[Josiah Carlson]

On Sat, Aug 4, 2012 at 11:39 PM, Kei Son <hey.ca...@gmail.com> wrote:
> OK, what's going on this issue at now?
>
> We have at this point MULTI, WATCH, SETNX for locking or similar purpose.
> But anything couldn't be a silver bullet as we see.
>
> MULTI provides multiple commands to be atomic. Any other command can't inject inside to between the commands tied with MULTI, but it can't stop following command when a former command failed in the MULTI command.
>
> SETNX can provides non-blocking lock. It's cool, but there are endless discussion at bottom of the page about timeout situation.

A 3 year old conversation of just a few messages is hardly "endless".

If you want a lock that times out reliably, I posted an implementation
and discussion about what was going on and why that specific
implementation was correct on my blog:
http://dr-josiah.blogspot.com/2012/01/creating-lock-with-redis.html

Note that with scripting, acquiring and releasing a lock with timeouts
is super easy. I'll be covering it as one of probably a dozen
simplifications in my book when I get to the chapter, or you can
figure it out for yourself, or someone else can post it.

> WATCH provides us an exclusive lock to modify a shared value in blocking way, but it blocks a connection not a command so if we have a connection or a limited connection pool the WATCH blocks all of pipes we have to reach to Redis. It makes the dead lock situation.

These are all well-known drawbacks of optimistic locking. You use more
'pessimistic' explicit locking (the way I discuss in the blog post),
which solves the issue from the other side, significantly reduces
contention, and can significantly improve performance. I saw (for one
example) a reduction of 14ms average latency to under 1ms on a
moderately loaded system, and 498ms average latency dropping to below
3ms for heavily loaded system.

Regards,
- Josiah

[Joseph Jang]

Let's think about the following scenario:

1. GET uid:n:base-key

2. long (say, 1 min) calculation based on the value of uid:n:base-key

3. SET the result to uid:n:result-key

This access is triggered by some rare condition, so the contended situation does not occur very frequently.

Assume we don't want to bother us with the pessimistic locking scheme because we don't want to pay for it when we can be optimistic.

(We don't want to concern what we should do on timeout or how we can handle memory footprint for the keys for locks.)

As Josiah explained, WATCH scheme - a form of optimistic locking can be a solution.

BTW, IMHO, Kei Son has a concern about number of connections when using WATCH scheme.

What if we have 1 billion users and each user has his/her own base-key and result-key.

In that case, there are possibility of 1 billion concurrent connection for 1 minutes when using WATCH scheme.

I think CAS scheme don't have those problems.

I guess this is not a problem of optimistic locking and it's about WATCH.

-- Joseph

2012년 8월 7일 화요일 오후 4시 41분 9초 UTC+9, Josiah Carlson 님의 말:

[Andrea Campi]

On Wed, Aug 8, 2012 at 8:08 AM, Joseph Jang <josep...@gmail.com> wrote:
> Let's think about the following scenario:
>
> 1. GET uid:n:base-key
> 2. long (say, 1 min) calculation based on the value of uid:n:base-key
> 3. SET the result to uid:n:result-key
>

…

> BTW, IMHO, Kei Son has a concern about number of connections when using
> WATCH scheme.
>
> What if we have 1 billion users and each user has his/her own base-key and
> result-key.
> In that case, there are possibility of 1 billion concurrent connection for 1
> minutes when using WATCH scheme.

It looks like your use case is very specific; IMHO Redis can't
possibly cater to all "edge cases".

That said, there's something I don't understand:

Are you saying all of your 1 billion users are going to run this
calculation at the same time?
If not, does the calculation for 1 user depend on the base-key for other users?
If not, why would you need to WATCH the other base-keys?
It looks to me you only need to concern yourself with the number of
*concurrent* calls to this sequence.

Moreover, this is not how optimistic locking works, in my experience
at least. You want something like:

1. GET uid:n:base-key
2. long (say, 1 min) calculation based on the value of uid:n:base-key

3. WATCH uid:n:base-key
4. GET uid:n:base-key
5. if it's changed, call UNWATCH and go back to 2
6. MULTI
7. SET the result to uid:n:result-key
8. EXEC
9. if EXEC returns an error, go back to 1

That looks totally reasonable to me.

Andrea

[Kei Son]

Think about this scenario:

You have a web server that have one connection for Redis. Several clients request modify a shared resource. Every operations with Redis work as async.

C1

WATCH a

GET a

---- async

MULTI

SET a

EXEC

---- async

C2

WATCH a

GET a

---- async

MULTI

SET a

EXEC

What happend?

2012년 8월 8일 수요일 오후 4시 7분 42초 UTC+9, Andrea Campi 님의 말:

[Josiah Carlson]

On Wed, Aug 8, 2012 at 8:35 AM, Kei Son <hey.ca...@gmail.com> wrote:
> Think about this scenario:
>
> You have a web server that have one connection for Redis. Several clients
> request modify a shared resource. Every operations with Redis work as async.

I'm going to stop you right there. If your web server has only 1
connection to Redis, then there are a lot of things that you won't be
able to do (like WATCH/MULTI/EXEC transactions), unless you are also
only processing one request at a time with that web server. If your
client is only letting you create 1 connection at a time to Redis,
then your client is deficient, not Redis.

I don't know why, but for some reason I thought that one of you were
using Node.js, and looking at both of the libraries for Node, neither
supports any sort of connection pooling framework (which is something
that almost every other Redis client supports). To work around this
with your single client, you are going to either need to perform a
pessimistic lock (like I said earlier), add connection pooling
yourself, or not do those operations.

My advice: build a pessimistic lock in whatever language you are
using. Or implement the pessimistic lock using Lua (minus the repeated
retries), and use EXEC from your client.

Regards,
- Josiah

[Kei Son]

If you have a single worker thread and every io goes async, and the endpoint service(Redis at here) also run as single thread, there are no need to have a connection pool. It just an overhead.

And thanks for you advice, but sometimes optimistic locking works well over others.

2012년 8월 9일 목요일 오전 12시 57분 20초 UTC+9, Josiah Carlson 님의 말:

[Josiah Carlson]

The purpose of a connection pool is to say, "sometimes, I need more
than one connection". WATCH/MULTI/EXEC is one of those situations, and
by *not* having a connection pool, you don't have access to that
functionality in practice.

You offered a solution to have a built-in command for check-and-set.
Lua scripting with EVAL offers that *exact* functionality, in whatever
semantics you want. You can use it to build a lock (like I've
mentioned twice before), add timeouts to the lock, release the lock
conditionally, detect when the lock timed out, ...

Does your client not support the EVAL command? Can you not upgrade
your Redis servers to 2.6 (or even a 2.4 with Lua scripting)? What is
stopping you from using Lua (inside Redis) to solve your problem?

Regards,
- Josiah

> --
> You received this message because you are subscribed to the Google Groups
> "Redis DB" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/redis-db/-/RBGdo3Y26pEJ.
>
> To post to this group, send email to redi...@googlegroups.com.
> To unsubscribe from this group, send email to
> redis-db+u...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/redis-db?hl=en.

[Kei Son]

OK, lets make a short conclusion:

  Redis can have an exact CAS by EVAL after 2.6 release.

I still want to have a native feature for that, but Redis is moving on to the script base transaction, so it's reasonable solution. Thanks.

And additional:

First

@Josiah as you mentioned if i need to have a connection pool for BLPOP or WATCH/MULTI/EXEC - meaning connection-scope-features, I don't have a reason unless I do not use them. right?

Second

There are use-cases that optimistic lock is more acceptable over pessimistic in the world.

Thanks everyone

Kei

2012년 8월 9일 목요일 오전 3시 31분 53초 UTC+9, Josiah Carlson 님의 말:

[Joseph Jang]

I admit my scenario is a bit, no, very extreme.

Certainly, your pseudo code works perfectly for my scenario.

But, In a normal situation (e.g. calculation takes 100 us in 99%, 10 s in 1%), you do not code that way from the first time.

And, WATCH can do everything CAS can do because WATCH is a generalized version of CAS families.

I wanted to emphasize CAS families over WATCH because CAS

- can introduce simple programing model/API

- does not need resource (i.e. connection) involvement

- is powerful enough to support the most scenarios

- does not need more than one round trip (for CAS itself)

I guess I understand WATCH's generality/simplicity have advantages and based on the philosophy of Redis.

But I'm saying myself "If I would have a CAS op in Redis..." whenever programming Redis accesses that requires the concurrency concerns.

(Certainly, you can say, "better have your own")

Thanks.

2012년 8월 8일 수요일 오후 4시 7분 42초 UTC+9, Andrea Campi 님의 말:

On Wed, Aug 8, 2012 at 8:08 AM, Joseph Jang <josep...@gmail.com> wrote:

[Aaron Blohowiak]

http://evalsha.com/commands/cas

Very simple to implement in an atomic way with lua scripting.

Note that the sha in the examples doesn't match the sha on the page because I am having an issue with newlines on the server currently.. (user input is being changed from \n to \r\n)..

- Aaron

[martin mauchauffée]

 I'm not sure my answer is relevant, but with Kyoto/Tokyo Cabinet, the CAS command takes 3 arguments: the key, the old value and the new value. No need cas_token/checksum, right ?

[Salvatore Sanfilippo]

Ok that makes sense, with Lua scripting you are well served in this context:

   if (redis.call("type",KEYS[1]) ~= "string" or
        redis.call("get",KEYS[1]) ~= ARGV[1])
    then
        redis.call("set",KEYS[1],ARGV[2])
    end

You can easily modify this in order to set a value just if the key does not exist.

On Thu, Nov 22, 2012 at 3:48 AM, Ritesh Tijoriwala <riteshti...@gmail.com> wrote:

LOCK key
GET key
... manipulate key by code ...
SET key <newval>
UNLOCK key

The problem with this is that client has to "GET" the value of the key first, check it and then "SET" it. This is one extra roundtrip to the server. For e.g. here's how I plan to use Redis as pure cache:

Customer getCustomerData(customerId) {

   Customer c = redis.get(customerId);

   if (c == null) {

      c = db.get(customerId);

      redis.put(customerId, c); 

   }

   return c;

} 

Note that the "put" above needs to be a conditional put. I only want to put the Customer record in cache if this is a newest version. If some other client already put a newer version, I don't want to overwrite it. So with your current solution, I will have to do the following:

Customer getCustomerData(customerId) {

   Customer c = redis.get(customerId);

   if (c == null) {

      c = db.get(customerId);

      redis.LOCK(customerId);

      oldValue = redis.get(customerId);

      if (oldValue.version < c.version) {

          redis.put(customerId, c); 

      }

      redis.UNLOCK(customerId);

   }

   return c;

} 

The above pattern forces me to fetch the value on client side (one extra roundtrip to redis cache server). I would really like to avoid it. Is there a way to do that?

Ideally, I would like to do the following:

Customer getCustomerData(customerId) {

   Customer c = redis.get(customerId);

   if (c == null) {

      c = db.get(customerId);

      redis.putIfAbsent(customerId, c, c.version); // OR if I updated the customer record, I would invoke "redis.put(customerId, c.version /* current version */, expectedVersion)"  

   }

   return c;

} 

This pattern of CAS avoids one complete round-trip to fetch the value from cache and also any multi-instruction LOCK. 

--

You received this message because you are subscribed to the Google Groups "Redis DB" group.

To view this discussion on the web visit https://groups.google.com/d/msg/redis-db/-/EZ2e9GVsaSEJ.

To post to this group, send email to redi...@googlegroups.com.
To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.

--
Salvatore 'antirez' Sanfilippo
open source developer - VMware
http://invece.org

Beauty is more important in computing than anywhere else in technology because software is so complicated. Beauty is the ultimate defence against complexity.
       — David Gelernter

[Ritesh Tijoriwala]

Hi Salvatore,

   if (redis.call("type",KEYS[1]) ~= "string" or
        redis.call("get",KEYS[1]) ~= ARGV[1])
    then
        redis.call("set",KEYS[1],ARGV[2])
    end

You can easily modify this in order to set a value just if the key does not exist.

I read that executing Lua scripts is synchronous i.e. no other clients can run commands on the server while the script is executing (See "atomicity of scripts" section: http://redis.io/commands/eval). Will this not seriously affect concurrency/throughput?  

[Salvatore Sanfilippo]

On Thu, Nov 22, 2012 at 5:46 PM, Ritesh Tijoriwala <riteshti...@gmail.com> wrote:

I read that executing Lua scripts is synchronous i.e. no other clients can run commands on the server while the script is executing (See "atomicity of scripts" section: http://redis.io/commands/eval). Will this not seriously affect concurrency/throughput?  

All the Redis commands are like that, in Lua scripting is extremely fast at executing code (it caches scripts, uses a single Lua interpreter that is never destroyed, and so forth). A typical small Lua script will be speed-wise comparable to a native command (it will be slower but not order of magnitudes, you can still expect like 20k requests per sec with EVALSHA).

Cheers,

Salvatore

[Ritesh Tijoriwala]

 

All the Redis commands are like that

So is a "GET k1" and "GET k2" from different clients serialized?

[Marc Gravell]

Redis is single-threaded. All commands from all clients are serialized.

Marc

On 22 Nov 2012, at 16:58, Ritesh Tijoriwala <riteshti...@gmail.com> wrote:

 

All the Redis commands are like that

So is a "GET k1" and "GET k2" from different clients serialized?

--

You received this message because you are subscribed to the Google Groups "Redis DB" group.

To view this discussion on the web visit https://groups.google.com/d/msg/redis-db/-/AvSHHO0PTQEJ.