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.
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.
On Sun, May 3, 2009 at 10:08 PM, Toby DiPasquale <codeslin...@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:
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.
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.
> 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:
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.
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.
On May 3, 5:42 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> 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 :)
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.
<jasonpaulwatk...@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:
> 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
On Mon, May 4, 2009 at 10:16 AM, Michal Frackowiak <redbe...@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.
> 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.
<jasonpaulwatk...@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:
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.
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.
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.
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:
> <jasonpaulwatk...@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:
> 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.
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.
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.
For example I have this kind of situation:
There are a resource which is shared by several clients. And a server that dealing with the resource in the middle of the clients and a Redis server.
* Client-A send a request for manipulating the shared resource
* Client-B send a request for same thing
* The server send a request to fetch the shared resource as asynchronous by C-A's request
* The server send a request again to same thing by C-B's request
* Now the server have the resource, modify it and send it to store as asynchronous
* As just next command in same tick the server do same thing for C-B
* Redis stores by the first command
* Redis replaces same resource with new value from C-B
* C-A's changes are gone
It can't be a solution for this situation that using WATCH to acquire a lock to get a permission for the shared resource. Because there are only a server with a connection to Redis. So C-A's request can acquire a lock, C-B's request block the connection and C-A couldn't get a chance to release the lock.
CAS(as a simple STM) can handle this situation.
Why shouldn't we get a more another locking solution even if there are uncompleted tool set for that?
2009년 5월 5일 화요일 오후 4시 0분 23초 UTC+9, Adam Michaels 님의 말:
On Sat, Aug 4, 2012 at 11:39 PM, Kei Son <hey.calmd...@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".
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.
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 님의 말:
> > 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.
On Wed, Aug 8, 2012 at 8:08 AM, Joseph Jang <josephj...@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
> On Wed, Aug 8, 2012 at 8:08 AM, Joseph Jang <josep...@gmail.com<javascript:>> > 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
On Wed, Aug 8, 2012 at 8:35 AM, Kei Son <hey.calmd...@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.
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 님의 말:
> On Wed, Aug 8, 2012 at 8:35 AM, Kei Son <hey.ca...@gmail.com <javascript:>> > 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.
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?
On Wed, Aug 8, 2012 at 10:35 AM, Kei Son <hey.calmd...@gmail.com> wrote:
> 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 님의 말:
>> 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.
> To post to this group, send email to redis-db@googlegroups.com.
> To unsubscribe from this group, send email to
> redis-db+unsubscribe@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/redis-db?hl=en.
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 님의 말:
> 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
> On Wed, Aug 8, 2012 at 10:35 AM, Kei Son <hey.ca...@gmail.com<javascript:>> > wrote: > > 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 님의 말:
> >> 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.
> > To post to this group, send email to redi...@googlegroups.com<javascript:>.
> > To unsubscribe from this group, send email to > > redis-db+u...@googlegroups.com <javascript:>. > > For more options, visit this group at > > http://groups.google.com/group/redis-db?hl=en.
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<javascript:>> > 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
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)..
On Wednesday, August 15, 2012 12:09:44 AM UTC-7, Joseph Jang wrote:
> 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: >> > 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
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 ?
