Redis Presharding
antirez.com
antirez.com
I wonder if it would make sense for Redis to support cross key operations where you can tell it another Redis server to retrieve the keys from?
# Connect to redis server 1
r = Redis('server1.dev', 6379)
# Tell it to perform an intersection with a key on server 2
r.sinterremote('my-key', 'server2.dev:6379/remote-key')
# Same, but store the result on server 1
r.sinterremotestore('local-storage-key', 'my-key', 'server2.dev:6379/remote-key')But Redis Cluster supports the MIGRATE command, so what we plan is to provide the client with a very cool way to do this kin do things.
Basically MIGRATE is able to transfer a key from an instance to another (or to copy it). The performance is pretty impressive. So the idea is that you can migrate two keys from two different instances into a "temporary" instance that you use just for computation, and then perform what you want in this instance.
This way we'll provide all the tools needed to people that understand what they are doing to do that. But will not provide direct support for something that in the general case can't be super fast and horizontally scalable.
the process can be thought of as a map-reduce. first pass would be figure out where all your SETs are located and how big they are. then intersect all co-located SETs. then (in parallel) take smaller SETs and MIGRATE them towards larger SETS, intersect those and repeat (respecting new sizes). A pyramid of SET intersection can be done until the result is the final two SETs being intersected, a process will need to coordinate all of this, but luckily intersections are idempotent, so if one parallel job finishes quicker, it doesn't need to wait.
W/ redis speed, the overhead (for the coordinator) to get the size of the different SETs in all these steps should be minimal as compared to the time taken to MIGRATE the data (meaning for-free). Also w/ redis' speed the MIGRATE will be very fast and the cross-node-join (or cross-node-intersecton) bottlenecks on network I/O, so if a good framework for this redis map-reduce is created, it will be a pretty optimal setup, and it wont bloat the server w/ tasks that can not be done directly in the server (cross-node-intersections are done at something more like a proxy level, they require intermediate results).
this problem is a hard one, data analytic stores optimise to this problem by storing data redundantly w/ a "pre-joined" colocation strategy, which works for star schemas and a limited number of tables, but doesnt make sense w/ 1000s of SETs, so this is a real good solution and classic redis anti-bloat.
But in an ideal world (Redis cluster) you would run a single node per machine, and Redis would automatically handle sharding, replication etc?
The point of the article is that with what you have now as stable releases you can mount a schema that may work for you.
I think the concept is much more interesting then consistent hashing, as it is a discrete way to see the problem. Dividing the key space into N pieces, and assigning this pieces to different nodes. Resharding this way is easy, just move one hash slot from one instance to another. For moving data around Redis uses the MIGRATE command.
What you don't want is a client not aware of the new configuration -- or reading and writing before the new one is ready. That's where vbucket states allow us to atomically move things.
It's not obvious from your doc how one can actually accomplish this with zero downtime while maintaining consistency.
I'd like to be able to use Redis Cluster as soon as it is available, here is my question: how can I help? Recently, I want to start write some script for rehashing, but there are some problems, namely, I cannot just "get/set" everything (e.g., I cannot "get/set" a list with some serialized format). Do you have recommended way of doing that?
when all the clients are pointed to write in the new instance, that is a slave, but as all Redis slaves can accept writes, you are already ok. Then you elect the instance as master just to disconnect the real master without issues.
Redis Cluster is something where we (Redis core team, that is, I and Pieter) can't get help for now, but will need help soon with testing.
Have you considered relying on Zookeeper for the gossip heavy-lifting?
Yes it's java (ugh) and would add an external dependency (ugh), but it's battle-tested and could perhaps save you from re-inventing such a complex wheel?
Zookeeper is also not just config management, it's state management. It helps to solve some of the really nasty problems of distributed state, e.g. achieving quorum and dealing with split brain situations.
However, it's been a while since I read up on the planned redis-cluster design, so I'm not sure how they are tackling these issues.
It doesn't look like redis is doing exactly what we're doing, but since it's been doing it well for a long time now with plenty of documentation, I'm hoping the knowledge we've shared about it can help others learn how to do similar things.
But then I realized that it's pretty common to invent the same things. You should try doing the same, especially since the idea was made public by Redis before. Check yourself in the git history.
That said, I really don't care at all. I want to build stuff that work, I want to have fun, understand new things. This is why I build Redis.
@dippsy what exactly are you insinuating here? It sounds like your suggesting #Redis somehow has borrowed/learned from concepts in your unreleased code?? It's actually quite rude.
I don't think anybody is insinuating anything here. The same solution to a common problem has been found independently. This happens all the time (See the Erlang process model and the Actor model e.g.).
Down the line, this isn't even important. Can we move along now and build some awesome databases?
In this scheme, you can add and remove servers without mving all your data.
There is apparently a memcached plugin to do this: http://www.mikeperham.com/2009/01/14/consistent-hashing-in-m...
You still have to move some data when you shuffle nodes and the devil is in the detail there; when/how to move chunks without interrupting access or violating integrity, how to ensure n-copies (if redundancy is required), how to prevent hot-spots. And of course all the aggregation/routing to allow complex queries that span nodes.
That's the reason why there are very few out-of-the-box sharding solutions. It's just very tough to get right, and one size won't fit all.
1. Hash each field in the key in some fashion
2. Concatenate the hashes, for example implode(".", $hashes)
3. Now you've got a point in the space of all possible concatenated hashes. On each client, have a partition like this for each key:
["", "abf34.9f8c7.92833", ...]
4. go through the partition and find the last point that is smaller than your point. That point maps to your shard.
5. Monitor your machines. If one of your shards becomes too full, or too much action is going, SPLIT IT. You do this simply by replicating the data to one or more new shards (like it says in the article) introducing one or more points in the partition right after the point mapping to the shard. Point them to the new shards. And update all the clients!
That's all Greg