Redis 排序集和存储 uid 的最佳方式

Question

我的数据由用户 ID 和这些用户 ID 的标签组成。user_ids 出现多次并具有预先指定的标签数 (500)，但是这可能会在功能中发生变化。必须存储的是user_id、他们的标签和他们的数量。我想稍后轻松找到得分最高的标签..等等。每次出现标签时它都会递增

我在redis中的实现是使用排序集完成的

• 每个 user_id 都是一个有序集

• key 是 user_id，是一个十六进制数

像这样工作:

zincrby user_id:x 1 "tag0"

zincrby user_id:x 1 "tag499"

zincrby user_id:y 1 "tag3"

等等

考虑到我想获得得分最高的标签，有没有更好的方法？

第二个问题是，现在我正在使用“keys *”来检索这些 key 以进行客户端操作，我知道它不是针对生产系统的。

此外，迭代指定数量的键(在 10000 范围内)对于内存问题会很好。我知道 key 必须存储在内存中，但是它们不遵循允许部分检索的特定模式，这样我就可以避免“zmalloc”错误(4GB 64 位 debian 服务器)。 key 数量达到 2000 万个。有什么想法吗？

Answer 1

我要指出的第一点是，4 GB 空间不足以存储 20M 个排序集。快速尝试显示 2000 万用户，每个用户有 20 个标签，在 64 位盒子上将占用大约 8 GB(并且它考虑了 Redis 2.4 提供的排序集 ziplist 内存优化 - 甚至不要在早期版本中尝试这个) .

排序集是支持您的用例的理想数据结构。我会完全按照您的描述使用它们。

正如您所指出的，KEYS 不能用于迭代键。它更像是一个调试命令。要支持 key 迭代，需要添加一个数据结构来提供这个访问路径。 Redis 中唯一可以支持迭代的结构是列表和排序集(通过范围方法)。但是，他们倾向于将 O(n) 迭代算法转换为 O(n^2)(对于列表)或 O(nlogn)(对于 zset)。列表也是存储 key 的糟糕选择，因为在添加/删除 key 时很难维护它。

一个更有效的解决方案是添加一个由正则集组成的索引。需要使用哈希函数将特定用户关联到一个桶中，并将用户id添加到这个桶对应的集合中。如果用户 id 是数值，一个简单的模函数就足够了。如果不是，一个简单的字符串哈希函数就可以解决问题。

因此，为了支持 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 通过序列化集合来优化内存消耗，前提是它们保持足够小(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) 复杂度来添加/删除用户，以及真正的 O(n) 复杂度来迭代所有项目。唯一的缺点是 key 迭代顺序是随机的。