Redis сортирани набори и най-добрият начин за съхранение на uid

Първата ми точка би била да отбележа, че 4 GB са тесни за съхраняване на 20 милиона сортирани комплекта. Бърз опит показва, че 20 милиона потребители, всеки от тях с 20 маркера, ще заеме около 8 GB на 64-битова кутия (и това отчита оптимизациите на паметта за сортирани набори ziplist, предоставени с Redis 2.4 - дори не опитвайте това с по-ранните версии) .

Сортираните набори са идеалната структура от данни в подкрепа на вашия случай на употреба. Бих ги използвал точно както описахте.

Както посочихте, KEYS не може да се използва за повторение на ключове. По-скоро е предвидена като команда за отстраняване на грешки. За да поддържате ключови итерации, трябва да добавите структура от данни, за да осигурите този път за достъп. Единствените структури в Redis, които могат да поддържат итерация, са списъкът и сортираният набор (чрез методите за диапазон). Те обаче са склонни да трансформират O(n) итерационните алгоритми в O(n^2) (за списък) или O(nlogn) (за zset). Списъкът също е лош избор за съхраняване на ключове, тъй като ще бъде трудно да се поддържа, тъй като ключовете се добавят/премахват.

По-ефективно решение е да добавите индекс, съставен от редовни набори. Трябва да използвате хеш-функция, за да свържете конкретен потребител към кофа и да добавите потребителския идентификатор към набора, съответстващ на тази кофа. Ако потребителският идентификатор са числови стойности, проста модулна функция ще бъде достатъчна. Ако не са, обикновена функция за хеширане на низ ще свърши работа.

Така че, за да поддържаме итерация на user:1000, user:2000 и user:1001, нека изберем функция по модул 1000. user:1000 и user:2000 ще бъдат поставени в bucket index:0, докато user:1001 ще бъдат поставени в bucket index:1.

Така че отгоре на zsets вече имаме следните ключове:

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

В наборите префиксът на ключовете не е необходим и позволява на Redis да оптимизира консумацията на памет чрез сериализиране на наборите, при условие че се поддържат достатъчно малки (оптимизация на целочислени набори, предложена от Срипати Кришнан).

Глобалната итерация се състои в обикновен цикъл на кофите от 0 до 1000 (изключени). За всяка кофа се прилага командата SMEMBERS за извличане на съответния набор и след това клиентът може да повтори отделните елементи.

Ето един пример в 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()

Чрез настройване на константите можете също да използвате тази програма, за да оцените глобалната консумация на памет на тази структура от данни.

IMO тази стратегия е проста и ефективна, защото предлага O(1) сложност за добавяне/премахване на потребители и истинска O(n) сложност за повторение на всички елементи. Единственият недостатък е, че редът на ключовите итерации е произволен.