Il mio primo punto sarebbe notare che 4 GB sono stretti per memorizzare 20 milioni di set ordinati. Un rapido tentativo mostra che 20 milioni di utenti, ciascuno con 20 tag, impiegherebbero circa 8 GB su una scatola a 64 bit (e tiene conto delle ottimizzazioni della memoria ziplist impostate fornite con Redis 2.4 - non provare nemmeno con le versioni precedenti) .
I set ordinati sono la struttura dati ideale per supportare il tuo caso d'uso. Li userei esattamente come hai descritto.
Come hai sottolineato, KEYS non può essere utilizzato per eseguire iterazioni sulle chiavi. È piuttosto inteso come un comando di debug. Per supportare l'iterazione delle chiavi, è necessario aggiungere una struttura dati per fornire questo percorso di accesso. Le uniche strutture in Redis che possono supportare l'iterazione sono l'elenco e l'insieme ordinato (attraverso i metodi dell'intervallo). Tuttavia, tendono a trasformare O(n) algoritmi di iterazione in O(n^2) (per list) o O(nlogn) (per zset). Un elenco è anche una scelta sbagliata per memorizzare le chiavi poiché sarà difficile mantenerlo man mano che le chiavi vengono aggiunte/rimosse.
Una soluzione più efficiente consiste nell'aggiungere un indice composto da insiemi regolari. È necessario utilizzare una funzione hash per associare un utente specifico a un bucket e aggiungere l'ID utente al set corrispondente a questo bucket. Se gli user id sono valori numerici, sarà sufficiente una semplice funzione modulo. In caso contrario, una semplice funzione di hashing di stringhe farà il trucco.
Quindi, per supportare l'iterazione su user:1000, user:2000 e user:1001, scegliamo una funzione modulo 1000. user:1000 e user:2000 verranno inseriti nel bucket index:0 mentre user:1001 verrà inserito nel bucket index:1.
Quindi, oltre agli zset, ora abbiamo le seguenti chiavi:
index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]
Negli insiemi, il prefisso delle chiavi non è necessario e consente a Redis di ottimizzare il consumo di memoria serializzando gli insiemi purché mantenuti sufficientemente piccoli (ottimizzazione degli insiemi interi proposta da Sripathi Krishnan).
L'iterazione globale consiste in un semplice loop sui bucket da 0 a 1000 (esclusi). Per ogni bucket, viene applicato il comando SMEMBERS per recuperare il set corrispondente e il client può quindi eseguire l'iterazione sui singoli elementi.
Ecco un esempio in 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()
Modificando le costanti, puoi anche utilizzare questo programma per valutare il consumo di memoria globale di questa struttura dati.
IMO questa strategia è semplice ed efficiente, perché offre una complessità O(1) per aggiungere/rimuovere utenti e una vera complessità O(n) per iterare su tutti gli elementi. L'unico aspetto negativo è che l'ordine di iterazione delle chiavi è casuale.
