Mon premier point serait de noter que 4 Go sont justes pour stocker 20M d'ensembles triés. Un essai rapide montre que 20 millions d'utilisateurs, chacun d'eux avec 20 balises, prendraient environ 8 Go sur une boîte de 64 bits (et cela tient compte des optimisations de mémoire de liste de zip triées fournies avec Redis 2.4 - n'essayez même pas cela avec les versions antérieures) .
Les ensembles triés constituent la structure de données idéale pour prendre en charge votre cas d'utilisation. Je les utiliserais exactement comme vous l'avez décrit.
Comme vous l'avez souligné, KEYS ne peut pas être utilisé pour itérer sur les clés. Il s'agit plutôt d'une commande de débogage. Pour prendre en charge l'itération de clé, vous devez ajouter une structure de données pour fournir ce chemin d'accès. Les seules structures dans Redis qui peuvent prendre en charge l'itération sont la liste et l'ensemble trié (via les méthodes de plage). Cependant, ils ont tendance à transformer les algorithmes d'itération O(n) en O(n^2) (pour liste), ou O(nlogn) (pour zset). Une liste est également un mauvais choix pour stocker des clés car il sera difficile de la maintenir à mesure que des clés sont ajoutées/supprimées.
Une solution plus efficace consiste à ajouter un index composé d'ensembles réguliers. Vous devez utiliser une fonction de hachage pour associer un utilisateur spécifique à un compartiment et ajouter l'ID utilisateur à l'ensemble correspondant à ce compartiment. Si les identifiants d'utilisateur sont des valeurs numériques, une simple fonction modulo suffira. Si ce n'est pas le cas, une simple fonction de hachage de chaîne fera l'affaire.
Donc, pour prendre en charge l'itération sur user:1000, user:2000 et user:1001, choisissons une fonction modulo 1000. user:1000 et user:2000 seront placés dans bucket index:0 tandis que user:1001 sera placé dans bucket index:1.
Ainsi, en plus des zsets, nous avons maintenant les clés suivantes :
index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]
Dans les ensembles, le préfixe des clés n'est pas nécessaire, et cela permet à Redis d'optimiser la consommation de mémoire en sérialisant les ensembles à condition qu'ils soient suffisamment petits (optimisation des ensembles d'entiers proposée par Sripathi Krishnan).
L'itération globale consiste en une simple boucle sur les buckets de 0 à 1000 (exclus). Pour chaque compartiment, la commande SMEMBERS est appliquée pour récupérer l'ensemble correspondant, et le client peut ensuite itérer sur les éléments individuels.
Voici un exemple en Python :
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ----------------------------------------------------
import redis, random
POOL = redis.ConnectionPool(host='localhost', port=6379, db=0)
NUSERS = 10000
NTAGS = 500
NBUCKETS = 1000
# ----------------------------------------------------
# Fill redis with some random data
def fill(r):
p = r.pipeline()
# Create only 10000 users for this example
for id in range(0,NUSERS):
user = "user:%d" % id
# Add the user in the index: a simple modulo is used to hash the user id
# and put it in the correct bucket
p.sadd( "index:%d" % (id%NBUCKETS), id )
# Add random tags to the user
for x in range(0,20):
tag = "tag:%d" % (random.randint(0,NTAGS))
p.zincrby( user, tag, 1 )
# Flush the pipeline every 1000 users
if id % 1000 == 0:
p.execute()
print id
# Flush one last time
p.execute()
# ----------------------------------------------------
# Iterate on all the users and display their 5 highest ranked tags
def iterate(r):
# Iterate on the buckets of the key index
# The range depends on the function used to hash the user id
for x in range(0,NBUCKETS):
# Iterate on the users in this bucket
for id in r.smembers( "index:%d"%(x) ):
user = "user:%d" % int(id)
print user,r.zrevrangebyscore(user,"+inf","-inf", 0, 5, True )
# ----------------------------------------------------
# Main function
def main():
r = redis.Redis(connection_pool=POOL)
r.flushall()
m = r.info()["used_memory"]
fill(r)
info = r.info()
print "Keys: ",info["db0"]["keys"]
print "Memory: ",info["used_memory"]-m
iterate(r)
# ----------------------------------------------------
main()
En ajustant les constantes, vous pouvez également utiliser ce programme pour évaluer la consommation globale de mémoire de cette structure de données.
IMO cette stratégie est simple et efficace, car elle offre une complexité O(1) pour ajouter/supprimer des utilisateurs, et une véritable complexité O(n) pour itérer sur tous les éléments. Le seul inconvénient est que l'ordre d'itération des clés est aléatoire.
