5 ms·

Redis (consistent hashing based) sharding made easy

31 points by emre-yilmaz 13y ago

stephen_mcd 13y ago
It seems like you've tried to support the set/store (sinterstore, sdiffstore, etc) methods across multiple instances in a non-atomic way - won't that lead to potential data loss?
- emre-yilmaz 13y ago
  Yes, these methods are dangerous to use. I need a locking mechanism to do it safely but this will wait until I need it most likely.
janerik 13y ago
The TCP server example shows a different protocol than the default redis protocol. (As I could not install it correctly I couldn't try it.) If this is the case current redis client libraries cannot be used.
- antirez 13y ago
  Hello, Redis accepts both a structured protocol, and a simple space-separated tokens protocol (called the inline protocol) that helps sysadmins to avoid a disaster just because they lack a proper redis-cli but are in need to run a Redis command ASAP. Perhaps this proxy is also supporting both forms. You can do that with any modern enough Redis server: Escape character is '^]'. ping +PONG set foo bar +OK get foo $3 bar
  - janerik 13y ago
    I know of that simple protocol. But the responses in the example telnet session on that side return "True" and "13" where it should be "+OK" and ":13" with the redis protocol.
    - antirez 13y ago
      good point...
  - emre-yilmaz 13y ago
    It doesn't support like this. It seems easy to implement it like that though. I will do it when I have free time.
- emre-yilmaz 13y ago
  What was the problem for installation? I use redis-router in production as a library. some of my non-pythoneer friends asked to use it in PHP, so I made a little wrapper with gevent. It's probably not compatible with current clients. Needs testing :)
  - janerik 13y ago
    Had problems installing "ketama". I re-read the README now and it explicitely states that libketama should be installed from the git repository. I'll try it again later.
- mmcnickle 13y ago
  The servers are returning the output of the redis-py library, which maps returned values from redis into python objects (hashes -> dicts etc). I had a quick look but I don't see an easy way to have redis-py pass forward the raw return values, though I think it could be done with some effort. So this isn't a drop in proxy for a redis server just yet. Edit: referring to the TCP/HTTP Servers above, the library itself can be used as a drop in replacement for redis-py in python.
antirez 13y ago
See also: Twitter's Twemproxy (http://github.com/twitter/twemproxy http://github.com/twitter/twemproxy)
- emre-yilmaz 13y ago
  another good alternative: https://github.com/disqus/nydus https://github.com/disqus/nydus
unwind 13y ago
The "abstract" text (copied from the Wikipedia page) lacks the variable names, making the text incomprehensible: When a hash table is resized and consistent hashing is used, only keys need to be remapped on average, where is the number of keys [...] it should end "only K/n keys need to be remapped on average, where K is the number of keys [...]". Just thought I'd point this out so it could get fixed, should only take a few seconds to edit.
- emre-yilmaz 13y ago
  thanks! https://github.com/emre/redis-router/commit/0d9307436e4c3b69c257943bd6df1883e742fbc7 https://github.com/emre/redis-router/commit/0d9307436e4c3b69...
peterhunt 13y ago
Somewhat off-topic, but just wondering: is anyone using consistent hashing for their DB masters? Every setup I've seen uses a manual sharding table.
- nasalgoat 13y ago
  Yes, and it works fine as long as you accept that data will need to be migrated at some point when you run out of memory and/or instances. To put this off as long as possible, you can max out the memory in your boxes and use a large number of servers - 100s in some cases - running on those servers, hopefully with less than 1 per CPU core to maximize performance. Then if you begin maxing out memory, you can easily split those servers onto their own hardware. My calculations showed that would allow scaling to trillions of keys without problems.
kijin 13y ago
> Q: What about data invalidation if I move servers, change the config etc. > A: It's minimum. At least better than: Node = Hash(key) MOD N Seriously? Redis is not just a cache. Let me repeat that. Redis is not just a cache. Lots of people use Redis as a primary data store. If Redis is your primary data store, you can't afford to have any of your keys invalidated, ever. "Minimum" might be good enough when you're talking to Memcached, but it's not enough when you're taking to Redis. Consistent hashing has been a solved problem for a long time if you can afford to misplace a few keys from time to time, which will happen every time a node is added to or removed from the pool. There are Redis client libraries implementing consistent hashing in nearly every language, and most of them work just fine if you use Redis as a cache or if your pool size never changes. Solving this problem again isn't particularly interesting. What really would be interesting is a server that sits between Redis nodes and clients and intelligently moves keys from one node to another in the background so that no key is ever invalidated even when the pool size changes. I believe that project is called Redis Cluster or something. That might be worth an extra TCP connection. But right now, I'm not seeing why I should prefer Redis-Router to any tried-and-true client library with built-in lossy consistent hashing.
- nasalgoat 13y ago
  What you're describing sounds a lot like mongodb - it has the server (mongos) that sits between the client and the upstream databases (mongod) and stores metadata about where data is located, and it moves that data around based on shard keys. Unfortunately it's the weakest part of mongodb.
- emre-yilmaz 13y ago
  okay, tell me a python library comes with consistent hashing? (for the record = HASH(key) MOD N is not 'consistent hashing'.) redis-router is just a library that wraps redis-py with consistent-hashing. nothing more. I use it in production heavily since it solves the client-side sharding problem for me. When I wrote this, there was no trustable client library comes with consistent-hashing. I don't know what do you want to see actually. "saving the world" is a todo though. wait for the new releases. you might like it. :)

31 points by emre-yilmaz 13y ago

It seems like you've tried to support the set/store (sinterstore, sdiffstore, etc) methods across multiple instances in a non-atomic way - won't that lead to potential data loss?

emre-yilmaz 13y ago
Yes, these methods are dangerous to use. I need a locking mechanism to do it safely but this will wait until I need it most likely.

janerik 13y ago

The TCP server example shows a different protocol than the default redis protocol. (As I could not install it correctly I couldn't try it.) If this is the case current redis client libraries cannot be used.

antirez 13y ago
Hello, Redis accepts both a structured protocol, and a simple space-separated tokens protocol (called the inline protocol) that helps sysadmins to avoid a disaster just because they lack a proper redis-cli but are in need to run a Redis command ASAP. Perhaps this proxy is also supporting both forms. You can do that with any modern enough Redis server: Escape character is '^]'. ping +PONG set foo bar +OK get foo $3 bar
- janerik 13y ago
  I know of that simple protocol. But the responses in the example telnet session on that side return "True" and "13" where it should be "+OK" and ":13" with the redis protocol.
  - antirez 13y ago
    good point...
- emre-yilmaz 13y ago
  It doesn't support like this. It seems easy to implement it like that though. I will do it when I have free time.
emre-yilmaz 13y ago
What was the problem for installation? I use redis-router in production as a library. some of my non-pythoneer friends asked to use it in PHP, so I made a little wrapper with gevent. It's probably not compatible with current clients. Needs testing :)
- janerik 13y ago
  Had problems installing "ketama". I re-read the README now and it explicitely states that libketama should be installed from the git repository. I'll try it again later.
mmcnickle 13y ago
The servers are returning the output of the redis-py library, which maps returned values from redis into python objects (hashes -> dicts etc). I had a quick look but I don't see an easy way to have redis-py pass forward the raw return values, though I think it could be done with some effort. So this isn't a drop in proxy for a redis server just yet. Edit: referring to the TCP/HTTP Servers above, the library itself can be used as a drop in replacement for redis-py in python.

antirez 13y ago

See also: Twitter's Twemproxy (http://github.com/twitter/twemproxy http://github.com/twitter/twemproxy)

emre-yilmaz 13y ago
another good alternative: https://github.com/disqus/nydus https://github.com/disqus/nydus

unwind 13y ago

The "abstract" text (copied from the Wikipedia page) lacks the variable names, making the text incomprehensible: When a hash table is resized and consistent hashing is used, only keys need to be remapped on average, where is the number of keys [...] it should end "only K/n keys need to be remapped on average, where K is the number of keys [...]". Just thought I'd point this out so it could get fixed, should only take a few seconds to edit.

emre-yilmaz 13y ago
thanks! https://github.com/emre/redis-router/commit/0d9307436e4c3b69c257943bd6df1883e742fbc7 https://github.com/emre/redis-router/commit/0d9307436e4c3b69...

peterhunt 13y ago

Somewhat off-topic, but just wondering: is anyone using consistent hashing for their DB masters? Every setup I've seen uses a manual sharding table.

nasalgoat 13y ago
Yes, and it works fine as long as you accept that data will need to be migrated at some point when you run out of memory and/or instances. To put this off as long as possible, you can max out the memory in your boxes and use a large number of servers - 100s in some cases - running on those servers, hopefully with less than 1 per CPU core to maximize performance. Then if you begin maxing out memory, you can easily split those servers onto their own hardware. My calculations showed that would allow scaling to trillions of keys without problems.

kijin 13y ago

> Q: What about data invalidation if I move servers, change the config etc. > A: It's minimum. At least better than: Node = Hash(key) MOD N Seriously? Redis is not just a cache. Let me repeat that. Redis is not just a cache. Lots of people use Redis as a primary data store. If Redis is your primary data store, you can't afford to have any of your keys invalidated, ever. "Minimum" might be good enough when you're talking to Memcached, but it's not enough when you're taking to Redis. Consistent hashing has been a solved problem for a long time if you can afford to misplace a few keys from time to time, which will happen every time a node is added to or removed from the pool. There are Redis client libraries implementing consistent hashing in nearly every language, and most of them work just fine if you use Redis as a cache or if your pool size never changes. Solving this problem again isn't particularly interesting. What really would be interesting is a server that sits between Redis nodes and clients and intelligently moves keys from one node to another in the background so that no key is ever invalidated even when the pool size changes. I believe that project is called Redis Cluster or something. That might be worth an extra TCP connection. But right now, I'm not seeing why I should prefer Redis-Router to any tried-and-true client library with built-in lossy consistent hashing.

nasalgoat 13y ago
What you're describing sounds a lot like mongodb - it has the server (mongos) that sits between the client and the upstream databases (mongod) and stores metadata about where data is located, and it moves that data around based on shard keys. Unfortunately it's the weakest part of mongodb.
emre-yilmaz 13y ago
okay, tell me a python library comes with consistent hashing? (for the record = HASH(key) MOD N is not 'consistent hashing'.) redis-router is just a library that wraps redis-py with consistent-hashing. nothing more. I use it in production heavily since it solves the client-side sharding problem for me. When I wrote this, there was no trustable client library comes with consistent-hashing. I don't know what do you want to see actually. "saving the world" is a todo though. wait for the new releases. you might like it. :)