Mein erster Punkt wäre anzumerken, dass 4 GB knapp sind, um 20 Millionen sortierte Sätze zu speichern. Ein kurzer Versuch zeigt, dass 20 Millionen Benutzer, jeder von ihnen mit 20 Tags, etwa 8 GB auf einer 64-Bit-Box benötigen würden (und dies berücksichtigt die mit Redis 2.4 bereitgestellten Sortiersatz-Ziplist-Speicheroptimierungen - versuchen Sie dies nicht einmal mit früheren Versionen). .
Sortierte Sätze sind die ideale Datenstruktur zur Unterstützung Ihres Anwendungsfalls. Ich würde sie genau so verwenden, wie Sie es beschrieben haben.
Wie Sie bereits betont haben, kann KEYS nicht zum Iterieren von Schlüsseln verwendet werden. Es ist eher als Debug-Befehl gedacht. Um die Schlüsseliteration zu unterstützen, müssen Sie eine Datenstruktur hinzufügen, um diesen Zugriffspfad bereitzustellen. Die einzigen Strukturen in Redis, die eine Iteration unterstützen können, sind die Liste und die sortierte Menge (durch die Bereichsmethoden). Sie neigen jedoch dazu, O(n)-Iterationsalgorithmen in O(n^2) (für list) oder O(nlogn) (für zset) umzuwandeln. Eine Liste ist auch eine schlechte Wahl zum Speichern von Schlüsseln, da es schwierig sein wird, sie zu pflegen, wenn Schlüssel hinzugefügt/entfernt werden.
Eine effizientere Lösung besteht darin, einen Index hinzuzufügen, der aus regulären Sätzen besteht. Sie müssen eine Hash-Funktion verwenden, um einen bestimmten Benutzer einem Bucket zuzuordnen, und die Benutzer-ID zu dem Satz hinzufügen, der diesem Bucket entspricht. Wenn es sich bei der Benutzer-ID um numerische Werte handelt, reicht eine einfache Modulo-Funktion aus. Wenn dies nicht der Fall ist, reicht eine einfache String-Hashing-Funktion aus.
Um also die Iteration auf user:1000, user:2000 und user:1001 zu unterstützen, wählen wir eine Modulo-1000-Funktion. user:1000 und user:2000 werden in Bucket-Index:0 eingefügt, während user:1001 in Bucket-Index:1 eingefügt wird.
Zusätzlich zu den zsets haben wir nun die folgenden Schlüssel:
index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]
In den Sätzen wird das Präfix der Schlüssel nicht benötigt, und es ermöglicht Redis, den Speicherverbrauch zu optimieren, indem die Sätze serialisiert werden, vorausgesetzt, sie werden klein genug gehalten (Integer-Sets-Optimierung vorgeschlagen von Sripathi Krishnan).
Die globale Iteration besteht aus einer einfachen Schleife für die Buckets von 0 bis 1000 (ausgeschlossen). Für jeden Bucket wird der SMEMBERS-Befehl angewendet, um den entsprechenden Satz abzurufen, und der Client kann dann die einzelnen Elemente durchlaufen.
Hier ist ein Beispiel 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()
Durch Anpassen der Konstanten können Sie mit diesem Programm auch den globalen Speicherverbrauch dieser Datenstruktur auswerten.
IMO ist diese Strategie einfach und effizient, da sie O(1)-Komplexität zum Hinzufügen/Entfernen von Benutzern und echte O(n)-Komplexität zum Iterieren aller Elemente bietet. Der einzige Nachteil ist, dass die Schlüssel-Iterationsreihenfolge zufällig ist.
