Permalink
5b6790a Dec 28, 2012
182 lines (139 sloc) 7.18 KB
THREDIS TODO: Add a descrption of SQLite integration.
Thredis
-------
Thredis is threaded Redis. (Apparently "thredis" is also "ribbons" in
Scots). At this point it is work-in-progress ALPHA quality, probably
contains many bugs and in need of much improvement, but should be
sufficient as proof-of-concept to toy around with. Use at your own
risk.
Thredis is for the most part identical to Redis. We did rename the
executable to thredis-server so that it looks different from
redis-server when running ps, etc.
Problem
If you're using Redis for complex operations (such as big ZUNION
operations), the server can block for a long time and only uses one
core. It would be nice if other operations could take place
concurrently, using many cores.
Solution
Certain commands (the ones that are obviously O(N) or more) are
submited to their own threads.
How / implications
Clearly this requires locking. The total number of locks required is
equal to the number of clients + one per every db + a global server
lock. Every operation requires checking the hash of locked keys, which
makes everything slower. Also, determinism is impossible with
concurrency, therefore you should NEVER use Thredis as a master - your
slaves will have a different database from the master.
Getting started
You probably want start out by trying the thredis-2.6 branch. It is
based on a stable Redis release.
Performance
-----------
The most striking performance gain can be observed on SMP systems when
running time-consuming operations. In a simple experiement, 20 clients
running a ZUNIONSTORE operation on 25 Sorted Sets of 100,000 random
entries took 61.79s on single-threaded Redis versus 6.30s on
Thredis. This test was conducted on a 24-core server. This is a more
than 980% (or almost 10x) performance improvement!
For simple O(1) or similar operations Thredis is only slightly slower
than Redis. Simple operations are not submitted to separate threads
and run in the main event loop, just like Redis. When no threads are
running, Thredis bypasses locking altogether (for the mostpart) which
makes it nearly identical to Redis.
Here is the output of a redis-benchmark -n 1000000 run comparing Redis
2.6 with Thredis 2.6 on the same machine (4-core Linux in a VirtualBox
on a MacBook Pro):
Thredis Redis
PING_INLINE 47016.79 46611.36 100.87%
PING_BULK 47118.69 46702.79 100.89%
SET 45651.68 46193.64 98.83%
GET 47030.05 46761.75 100.57%
INCR 45345.3 46596.15 97.32%
LPUSH 45246.82 45639.18 99.14%
LPOP 44692.74 46212.86 96.71%
SADD 46189.38 46687.52 98.93%
SPOP 46831.83 46792.38 100.08%
LPUSH (needed to benchmark LRANGE) 44165.71 46255.61 95.48%
LRANGE_100 (first 100 elements) 19529.34 28648.37 68.17%
LRANGE_300 (first 300 elements) 11363.25 13526.13 84.01%
LRANGE_500 (first 450 elements) 8519.05 9408.84 90.54%
LRANGE_600 (first 600 elements) 6818.77 7376.43 92.44%
MSET (10 keys) 26227.45 27472.53 95.47%
AVERAGE: 94.63%
Locking Strategy (for Developers)
================
Basic Idea
----------
The objective of locking is to make sure that no command is attempting
to use (i.e. read or write) any key at the same time.
At first glance it may seem that there needs to be a lock per key that
is in use, but actually, if we consider that the number of operations
potentially running in parallel is limited to the number of connected
clients, it becomes apparent that there only needs to be a lock per
client.
Thredis maintains a per-database dictionary of locked keys. To "lock a
key" means to assign a lock (pthread_mutex_t object) to the key name.
So, upon connection a client gets its own lock. This lock exists for
as long as the client remains connected and will be destroyed after
the client disconnects, when the redisClient is freed. Clients lock
their lock before any operation they submit and unlock it immediately
after it's over.
Let's say we have two clients, A and B, connected at the same
time. They each have their locks, lock_A and lock_B. Client A submits
an operation that uses key_1. Client B submits an operation
that also uses key_1. Here is one way this could play out:
Client A locks lock_A
Client A checks locked_keys dictionary for key_1 and it's not there.
Client A assigns its lock key_1:
locked_keys[key_1] = lock_A
Client B locks lock_B
Client B checks locked_keys for key_1 and gets lock_A.
Client B attempts to lock lock_A and blocks
Client A operation executes and is complete.
Client A deletes locked_keys[key_1]
Client A unlocks lock_A
Client B now has lock_A
Client B assigns its lock to key_1:
locked_keys[key_1] = lock_B
Client B unlocks lock_A
Client B operation executes and is complete
Client B deletes locked_keys[key_1]
Client B unlocks lock_B
NOTE: We have skipped an important step above for simplicity - any
access to the locked_keys dictionary needs to be protected by a lock
of its own, which is why there exists a per-database lock.
Certain operations also require locking a per-server lock,
e.g. anything that touches server-level data structures.
Avoiding Deadlocks
------------------
First rule of obtaining multiple locks is that they always have to
obtained and released in the same order or deadlocks will happen. To
ensure this Thredis provides lockKeys and unlockKeys functions which
use qsort() to sort keys before locking/unlocking. (Actually
unlockKeys doesn't need to sort them because they remain sorted from
prior lockKeys).
There is still a possibility of a circular deadlock. This is because
our locks are per-client rather than per key, and pthread mutex do not
guarantee that the order in which you attempt to obtain a lock is the
order in which they will acquired. So it is possible that client B is
waiting on lock_A for key X, while client A is done with key X, has
re-obtained its own lock for the next operation and is now witing on
lock_A for some key that Client A has locked. (In this case Client B
is waiting on lock_A "mistakingly" for key X which client A no longer
needs).
The way to solve this is to use a lock timeout. If a client is
attempting to lock multiple locks, A, B and C, attempt to lock C times
out, it should unlock B and A and attempt to start over. Using this
unroll and start from stratch strategy, sooner or later one client
will win all the locks.
Locking Mode
------------
Because O(1) commands in Thredis still run on the main thread, when
there are no threads running there is no point in locking. Thredis
maintains a counter of threads (server.locking_mode) which is
incremented every time a thread is submitted and decremented when it's
finished. Whenever locking_mode is 0, the lockKey* functions just
return without doing anything.
Note that commands that always run in a thread do not check
server.locking_mode because locking mode would always be on when they
are executed.