Mým prvním bodem by bylo poznamenat, že 4 GB jsou omezené na uložení 20 milionů tříděných sad. Rychlý pokus ukazuje, že 20 milionů uživatelů, každý z nich s 20 tagy, by zabralo asi 8 GB na 64bitovém boxu (a zohledňuje to seřazené optimalizace paměti ziplistu poskytované s Redis 2.4 – to ani nezkoušejte se staršími verzemi) .
Seřazené sady jsou ideální datovou strukturou pro podporu vašeho případu použití. Použil bych je přesně tak, jak jste popsal.
Jak jste zdůraznili, KEYS nelze použít k iteraci klíčů. Je to spíše myšleno jako ladicí příkaz. Chcete-li podporovat iteraci klíče, musíte přidat datovou strukturu, která poskytne tuto přístupovou cestu. Jediné struktury v Redis, které mohou podporovat iteraci, jsou seznam a seřazená sada (prostřednictvím metod rozsahu). Mají však tendenci transformovat O(n) iterační algoritmy na O(n^2) (pro seznam) nebo O(nlogn) (pro zset). Seznam je také špatnou volbou pro ukládání klíčů, protože bude obtížné jej udržovat, protože klíče jsou přidávány/odebírány.
Efektivnějším řešením je přidání indexu složeného z pravidelných sad. Chcete-li přiřadit konkrétního uživatele k segmentu, musíte použít hašovací funkci a přidat ID uživatele do sady odpovídající tomuto segmentu. Pokud jsou ID uživatele číselné hodnoty, bude stačit jednoduchá funkce modulo. Pokud tomu tak není, postačí jednoduchá funkce hashování řetězce.
Abychom tedy podpořili iteraci na user:1000, user:2000 a user:1001, zvolíme funkci modulo 1000. user:1000 a user:2000 budou vloženy do segmentu index:0, zatímco user:1001 bude vložen do segmentu index:1.
Takže nad zsets máme nyní následující klíče:
index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]
V sadách není předpona klíčů potřeba a umožňuje společnosti Redis optimalizovat spotřebu paměti serializací sad za předpokladu, že jsou dostatečně malé (optimalizace celočíselných sad navržená Sripathi Krishnanem).
Globální iterace spočívá v jednoduché smyčce na segmentech od 0 do 1000 (vyloučeno). Pro každý segment je použit příkaz SMEMBERS k načtení odpovídající sady a klient pak může iterovat jednotlivé položky.
Zde je příklad v Pythonu:
#!/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()
Vyladěním konstant můžete tento program použít také k vyhodnocení globální spotřeby paměti této datové struktury.
IMO je tato strategie jednoduchá a efektivní, protože nabízí složitost O(1) pro přidávání/odebírání uživatelů a skutečnou složitost O(n) pro iteraci všech položek. Jedinou nevýhodou je, že pořadí iterací klíče je náhodné.