Мое первое замечание: 4 ГБ недостаточно для хранения 20М отсортированных наборов.Быстрая попытка показывает, что 20M пользователей, каждый из которых с 20 тегами, заняли бы около 8 ГБ в 64-битном боксе (и это учитывает оптимизацию памяти ziplist с отсортированным набором, предоставляемую Redis 2.4 - даже не пытайтесь делать это с более ранними версиями).
Сортированные наборы - это идеальная структура данных для поддержки вашего варианта использования.Я бы использовал их в точности так, как вы описали.
Как вы указали, KEYS нельзя использовать для итерации ключей.Это скорее подразумевается как команда отладки.Для поддержки итерации ключей необходимо добавить структуру данных, чтобы обеспечить этот путь доступа.Единственные структуры в Redis, которые могут поддерживать итерацию, - это список и отсортированный набор (с помощью методов диапазона).Однако они имеют тенденцию преобразовывать O (n) итерационных алгоритмов в O (n ^ 2) (для списка) или O (nlogn) (для zset).Список также является плохим выбором для хранения ключей, поскольку его будет сложно поддерживать при добавлении / удалении ключей.
Более эффективное решение состоит в добавлении индекса, состоящего из регулярных наборов.Вам необходимо использовать хеш-функцию, чтобы связать определенного пользователя с сегментом и добавить идентификатор пользователя в набор, соответствующий этому сегменту.Если идентификатор пользователя является числовым значением, простой функции по модулю будет достаточно.Если это не так, простая хеш-функция для строк выполнит свою задачу.
Таким образом, чтобы поддержать итерацию для пользователя: 1000, пользователя: 2000 и пользователя: 1001, давайте выберем функцию по модулю 1000.пользователь: 1000 и пользователь: 2000 будут помещены в индекс сегмента: 0, а пользователь: 1001 будет помещен в индекс сегмента: 1.
Итак, в дополнение к zsets у нас теперь есть следующие ключи:
index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]
В наборах префикс ключей не нужен, и он позволяет Redis оптимизировать потребление памяти путем сериализации наборов при условии, что они достаточно малы (оптимизация целых наборов, предложенная Sripathi Krishnan).
Глобальная итерация состоит из простого цикла в сегментах от 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) сложность для добавления / удаления пользователей, и trueO (n) сложность для перебора всех элементов.Единственным недостатком является случайный порядок ключей.