Feature: Multi-server support

[botondus]

This would be also a very nice thing that I've been seriously looking at.
I think some options would be to integrate a smarter client wrapper instead of redis-py like:
https://github.com/gmr/mredis
https://github.com/salimane/rediscluster-py

Or just implement it directly, with the minimum required feature set for cacheops. I quite like how rediscluster works.
There are some obstacles however.

1. The straightforward solution is to distribute all cache keys evenly based on the modulo of CRC32 hash. This is handled by the libs above. However the way cacheops works, I suppose the schemas would need to be always stored/updated on every (master) server.
2. Cacheops uses pipelining in some places which is more tricky to update for multi-server. But should be doable, especially with rediscluster.

Any thoughts on this matter would be appreciated.

[Suor]

There are two different ways to use multiple redises. First is when there are separate caches on different servers (this is handy when you have geographically distributed application servers), second when cache is distributed between redises. In both cases you need to invalidate on all servers. (You probably can ignore this and invalidate only local cache in first case when you know that queries on different app servers are different).

I assume you are talking about second case - sharding. Regarding schemes, storing all schemes on all instances is a bad idea, as far as I can see, cause then you'll need to update them on all instances on every cache miss. I was thinking about storing making each instance kind of self contained cache which holds its schemes and invalidators. This way you can write to cache to a single instance, you'll still need to invalidate on all of them, but I didn't found a general way to avoid this.

Also I should ask. Why do you need this? Are you out of CPU on single redis instance? out of memory on single server? need more durability? (In the latter case replication should work). I ask all these questions because the answers will determine what kind of multi-server support you need.

I myself actually looked into first variant of multi-server support, but found it's ok to rely on timeout invalidation for not so high coherent data.

[botondus]

My reasons would be, in order of importance:

1. Durability
2. Out of memory on single server

And 1. should also be the easiest to solve indeed. Set up 1 master with N slaves and use for example rediscluster to do all the communication with the cache. It already knows to do all writes to the master and distribute reads to the slaves by default. We still write to a single server so that remains simple.
One potential problem that could appear here is replication lag... but not sure if that would really be noticeable enough to cause visible issues. Probably not.

And actual sharding would be the ideal solution (if implemented fairly efficiently of course) for the 2nd problem, similarly how you can easily add N memcache servers if using more standard Django caching solutions.

[Suor]

Sharding won't work with redis cluster cause we need to store our keys with their invalidators on single instance and cluster stores keys as it wants. And you most probably don't need cluster for 1. So it's out of question as I know.

For 1 the single thing is needed from cacheops is failover, redis already handles replication.

2 is not so easy. One need to map keys to instances and then use single instance for data, invalidators and schemes in cache_thing(). This means there would be separate collection of schemes for each redis node. And when you invalidate you will use all these schemes and all nodes. This is doable, still messy.

I was thinking to rewrite cacheops with lua scripting, this will allow me to trash in memory cache of schemes, and that will make sharding trivial. My very initial hacks are in scripting branch.

[ttyS15]

I think I stand closely to solving this problem. Please check my approach.

#68

[Suor]

Given production-ready redis cluster and not using transactions but scripting now, this is relatively easy to implement. I don't need this functionality, but if anyone is willing to make a pull request I'll work with him/her on it.

Here are my preliminary designs. I see 2 approaches.

Shard data logically. By model or some condition, e.g. user id, geographic region or whatever. This is especially convinient when you already shard your database. In this scenario each of redis clusters 16384 shards acts as independent cacheops database - each key goes to same shard with its invalidation set and schemes. This way we invalidate in single place with one request.

This could be facilitated by use of hash tags - parts of keys in {}. User will need to supply a hash tag function:

def hash_tag_func(model, attname, value):
    # Shard these by model
    if model in (City, Country, Category):
        return model.__name__
    # Shard users by id
    elif model is User and attname == 'id':
        return 'u%d' % value
    # Shard the rest by user
    else:
        user_fk = first(f.attname for f in model._meta.fields 
                                  if f.rel and f.rel.to is User)
        assert user_fk, "Need foreign key to User to shard %s" % model.__name__
        if field == user_fk:
            return 'u%d' % value

Whatever hash_tag_func() returns we prepend to all keys supplied to redis commands. This way they will be assigned to same shard and thus to same node:

cache_key = '{u42}q:G7A...'
conj_key = '{u42}conj:...'
...

Hash tag function is called each time we make a cache fetch, save or invalidation. When we have dnf tree (or queryset from which that is derivable) we pass all elementary conditions from that to this function, in invalidate_obj() we pass all the (key, value) pairs from object dict. Several results of hash tag function for single op should be consistent and defining (at least one non-None). This way all cache operations will be performed against single redis cluster node. So it's infinitely scalable approach.

Shard by full cache key, invalidate everywhere. It's actually as simple as it sounds. When we cache_thing() all the invalidation data is stored on the same node as cache, so if we later run invalidate.lua against all master nodes everything will work. Invalidation against several nodes could be run in parallel with either threads or async IO, but simple for loop will also work for small number of nodes. Additionally invalidate_obj|dict() calls could be grouped and pipelined.

Both approaches could also be used with client side sharding or twemproxy, so redis cluster is not strictly needed. Also, they are not mutually exclusive, eventually both could be implemented.

[Suor]

@botondus, @ttyS15 are you still interested?

[alexandersimeonov]

We are using redis cluster together with redis-py-cluster in the rest of our application, so I think I could integrate that into django-cacheops.

At very first attempt, changing redis.StrictRedis to rediscluster.StrictRedisCluster produces the following errors:

Upon read, it complaints about accessing accessing keys from a different node, in the cache_thing function:

ResponseError: Error running script (call to f_c54d7c8aeb17b974055d5eb1f1a08f0dafcaaf81): @user_script:37: @user_script: 37: Lua script attempted to access a non local key in a cluster node

Repeating the read 3 (number of master nodes in the cluster) times in eventually succeeds.

Upon invalidation, (e.g. when saving an model), in the invalidate_dict function:

RedisClusterException: EVALSHA - all keys must map to the same key slot

Any suggestions on how to approach this are appreciated.

[Suor]

@anac0nda you need to decide how you shard. Cacheops has keys depending on each other so you can't just distribute them by generic hash key as redis cluster does. See my comment with hash_tag_func() above.

Note that to use second approach from there you need to disable redis cluster check if key belongs to node. Not sure whether this is possible, you may need to use just and a bunch of nodes instead of cluster.