Redis sorterede sæt og bedste måde at opbevare uids på

Mit første punkt ville være at bemærke, at 4 GB er trangt til at opbevare 20M sorterede sæt. Et hurtigt forsøg viser, at 20 millioner brugere, hver af dem med 20 tags, ville tage omkring 8 GB på en 64-bit boks (og det tegner sig for de sorterede sæt ziplist-hukommelsesoptimeringer leveret med Redis 2.4 - prøv ikke engang dette med tidligere versioner) .

Sorterede sæt er den ideelle datastruktur til at understøtte din use case. Jeg ville bruge dem præcis som du beskrev.

Som du påpegede, kan NØGLER ikke bruges til at iterere på nøgler. Det er snarere ment som en fejlretningskommando. For at understøtte nøgle iteration skal du tilføje en datastruktur for at give denne adgangssti. De eneste strukturer i Redis, der kan understøtte iteration, er listen og det sorterede sæt (gennem rækkeviddemetoderne). De har dog en tendens til at transformere O(n) iterationsalgoritmer til O(n^2) (for liste) eller O(nlogn) (for zset). En liste er også et dårligt valg til at gemme nøgler, da det vil være vanskeligt at vedligeholde den, da nøgler tilføjes/fjernes.

En mere effektiv løsning er at tilføje et indeks sammensat af almindelige sæt. Du skal bruge en hash-funktion til at knytte en bestemt bruger til en bucket og tilføje bruger-id'et til det sæt, der svarer til denne bucket. Hvis bruger-id'et er numeriske værdier, vil en simpel modulo-funktion være nok. Hvis de ikke er det, vil en simpel streng-hash-funktion gøre tricket.

Så for at understøtte iteration på bruger:1000, bruger:2000 og bruger:1001, lad os vælge en modulo 1000-funktion. bruger:1000 og bruger:2000 vil blive sat i bucket index:0, mens bruger:1001 vil blive sat i bucket index:1.

Så oven i zsets har vi nu følgende nøgler:

index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]

I sættene er nøglernes præfiks ikke nødvendig, og det giver Redis mulighed for at optimere hukommelsesforbruget ved at serialisere sættene, forudsat at de holdes små nok (optimering af heltalsæt foreslået af Sripathi Krishnan).

Den globale iteration består af en simpel løkke på buckets fra 0 til 1000 (ekskluderet). For hver spand anvendes SMEMBERS-kommandoen for at hente det tilsvarende sæt, og klienten kan derefter iterere på de enkelte elementer.

Her er et eksempel i 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()

Ved at justere konstanterne kan du også bruge dette program til at evaluere det globale hukommelsesforbrug for denne datastruktur.

IMO er denne strategi enkel og effektiv, fordi den tilbyder O(1) kompleksitet til at tilføje/fjerne brugere, og ægte O(n) kompleksitet til at iterere på alle elementer. Den eneste ulempe er, at nøgle iterationsrækkefølgen er tilfældig.