Redis sorterade set och bästa sättet att lagra uids

Min första punkt är att notera att 4 GB är snävt för att lagra 20 miljoner sorterade set. Ett snabbt försök visar att 20 miljoner användare, var och en av dem med 20 taggar skulle ta ungefär 8 GB på en 64-bitars box (och det står för de sorterade ziplist-minnesoptimeringarna som tillhandahålls med Redis 2.4 - försök inte ens detta med tidigare versioner) .

Sorterade uppsättningar är den idealiska datastrukturen för att stödja ditt användningsfall. Jag skulle använda dem precis som du beskrev.

Som du påpekade kan KEYS inte användas för att iterera på nycklar. Det är snarare menat som ett felsökningskommando. För att stödja nyckeliteration måste du lägga till en datastruktur för att tillhandahålla denna åtkomstväg. De enda strukturerna i Redis som kan stödja iteration är listan och den sorterade uppsättningen (genom intervallmetoderna). De tenderar dock att omvandla O(n) iterationsalgoritmer till O(n^2) (för lista) eller O(nlogn) (för zset). En lista är också ett dåligt val för att lagra nycklar eftersom det blir svårt att underhålla den eftersom nycklar läggs till/tas bort.

En mer effektiv lösning är att lägga till ett index som består av vanliga uppsättningar. Du måste använda en hash-funktion för att associera en specifik användare till en hink, och lägga till användar-id:t till den uppsättning som motsvarar denna hink. Om användar-id är numeriska värden räcker det med en enkel modulo-funktion. Om de inte är det, kommer en enkel stränghashningsfunktion att göra susen.

Så för att stödja iteration på användare:1000, användare:2000 och användare:1001, låt oss välja en modulo 1000-funktion. user:1000 och user:2000 kommer att läggas i bucket index:0 medan user:1001 kommer att läggas i bucket index:1.

Så ovanpå zsets har vi nu följande nycklar:

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

I uppsättningarna behövs inte prefixet för nycklarna, och det tillåter Redis att optimera minnesförbrukningen genom att serialisera uppsättningarna förutsatt att de hålls tillräckligt små (optimering av heltalsuppsättningar föreslagen av Sripathi Krishnan).

Den globala iterationen består av en enkel slinga på hinkarna från 0 till 1000 (exklusive). För varje hink används kommandot SMEMBERS för att hämta motsvarande uppsättning, och klienten kan sedan iterera på de enskilda objekten.

Här är ett exempel 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()

Genom att justera konstanterna kan du också använda det här programmet för att utvärdera den globala minnesförbrukningen för denna datastruktur.

IMO är denna strategi enkel och effektiv, eftersom den erbjuder O(1)-komplexitet för att lägga till/ta bort användare, och sann O(n)-komplexitet att iterera på alla objekt. Den enda nackdelen är att nyckelns iterationsordning är slumpmässig.