Redis posortowane zestawy i najlepszy sposób na przechowywanie uidów

Moim pierwszym punktem byłoby odnotowanie, że 4 GB są ciasne, aby pomieścić posortowane zestawy 20M. Szybka próba pokazuje, że 20 milionów użytkowników, każdy z 20 tagami, zajęłoby około 8 GB na 64-bitowym pudełku (i uwzględnia to posortowane optymalizacje pamięci listy zip dostarczane z Redisem 2.4 – nawet nie próbuj tego z wcześniejszymi wersjami) .

Posortowane zestawy to idealna struktura danych wspierająca Twój przypadek użycia. Używałbym ich dokładnie tak, jak opisałeś.

Jak wspomniałeś, KEYS nie można używać do iteracji na klawiszach. Jest to raczej polecenie debugowania. Aby obsługiwać iterację kluczy, musisz dodać strukturę danych, aby zapewnić tę ścieżkę dostępu. Jedyne struktury w Redis, które mogą obsługiwać iterację, to lista i posortowany zestaw (za pomocą metod zakresu). Jednak mają tendencję do przekształcania algorytmów iteracji O(n) na O(n^2) (dla listy) lub O(nlogn) (dla zset). Lista jest również kiepskim wyborem do przechowywania kluczy, ponieważ trudno będzie ją utrzymać, gdy klucze są dodawane/usuwane.

Wydajniejszym rozwiązaniem jest dodanie indeksu składającego się z regularnych zestawów. Musisz użyć funkcji skrótu, aby powiązać określonego użytkownika z zasobnikiem i dodać identyfikator użytkownika do zestawu odpowiadającego temu zasobnikowi. Jeśli identyfikator użytkownika to wartości liczbowe, wystarczy prosta funkcja modulo. Jeśli tak nie jest, wystarczy prosta funkcja mieszająca ciągi znaków.

Tak więc, aby wesprzeć iterację na użytkownikach:1000, użytkownik:2000 i użytkownik:1001, wybierzmy funkcję modulo 1000. user:1000 i user:2000 zostaną umieszczone w zasobniku o indeksie:0, podczas gdy użytkownik:1001 zostanie umieszczony w zasobniku o indeksie:1.

Oprócz zsetów mamy teraz następujące klawisze:

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

W zestawach prefiks kluczy nie jest potrzebny i pozwala Redisowi zoptymalizować zużycie pamięci poprzez serializację zestawów, pod warunkiem, że są one wystarczająco małe (optymalizacja zestawów liczb całkowitych zaproponowana przez Sripathi Krishnana).

Globalna iteracja polega na prostej pętli na wiadrach od 0 do 1000 (wykluczone). Dla każdego zasobnika stosowane jest polecenie SMEMBERS w celu pobrania odpowiedniego zestawu, a klient może następnie wykonać iterację poszczególnych elementów.

Oto przykład w Pythonie:

#!/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()

Modyfikując stałe, możesz również użyć tego programu do oceny globalnego zużycia pamięci przez tę strukturę danych.

IMO ta strategia jest prosta i wydajna, ponieważ oferuje złożoność O(1) do dodawania/usuwania użytkowników i prawdziwą złożoność O(n) do iteracji na wszystkich elementach. Jedynym minusem jest to, że kluczowa kolejność iteracji jest losowa.