Điểm đầu tiên của tôi là lưu ý rằng 4 GB rất khó để lưu trữ 20 triệu bộ được sắp xếp. Một thử nghiệm nhanh cho thấy rằng 20 triệu người dùng, mỗi người trong số họ có 20 thẻ sẽ chiếm khoảng 8 GB trên một hộp 64 bit (và nó chiếm khoảng tối ưu hóa bộ nhớ ziplist đã được sắp xếp được cung cấp với Redis 2.4 - thậm chí không thử điều này với các phiên bản trước đó) .
Tập hợp được sắp xếp là cấu trúc dữ liệu lý tưởng để hỗ trợ trường hợp sử dụng của bạn. Tôi sẽ sử dụng chúng chính xác như bạn đã mô tả.
Như bạn đã chỉ ra, KEYS không thể được sử dụng để lặp lại trên các phím. Nó đúng hơn có nghĩa là một lệnh gỡ lỗi. Để hỗ trợ lặp lại khóa, bạn cần thêm cấu trúc dữ liệu để cung cấp đường dẫn truy cập này. Các cấu trúc duy nhất trong Redis có thể hỗ trợ lặp là danh sách và tập hợp được sắp xếp (thông qua các phương thức phạm vi). Tuy nhiên, họ có xu hướng biến đổi các thuật toán lặp O (n) thành O (n ^ 2) (cho danh sách), hoặc O (nlogn) (cho zset). Danh sách cũng là một lựa chọn tồi để lưu trữ các khóa vì sẽ khó duy trì nó khi các khóa được thêm / bớt.
Một giải pháp hiệu quả hơn là thêm một chỉ mục bao gồm các tập hợp thông thường. Bạn cần sử dụng hàm băm để liên kết một người dùng cụ thể với một nhóm và thêm id người dùng vào nhóm tương ứng với nhóm này. Nếu id người dùng là các giá trị số, một hàm modulo đơn giản là đủ. Nếu không, một hàm băm chuỗi đơn giản sẽ thực hiện thủ thuật.
Vì vậy, để hỗ trợ lặp lại trên user:1000, user:2000 và user:1001, chúng ta hãy chọn một hàm modulo 1000. user:1000 và user:2000 sẽ được đưa vào chỉ mục nhóm:0 trong khi người dùng:1001 sẽ được đưa vào chỉ mục nhóm:1.
Vì vậy, trên zsets, bây giờ chúng ta có các khóa sau:
index:0 => set[ 1000, 2000 ]
index:1 => set[ 1001 ]
Trong các tập hợp, tiền tố của các khóa không cần thiết và nó cho phép Redis tối ưu hóa mức tiêu thụ bộ nhớ bằng cách tuần tự hóa các tập hợp miễn là chúng được giữ đủ nhỏ (tối ưu hóa tập hợp số nguyên do Sripathi Krishnan đề xuất).
Việc lặp lại toàn cục bao gồm một vòng lặp đơn giản trên các nhóm từ 0 đến 1000 (bị loại trừ). Đối với mỗi nhóm, lệnh SMEMBERS được áp dụng để truy xuất nhóm tương ứng và sau đó khách hàng có thể lặp lại trên các mục riêng lẻ.
Đây là một ví dụ bằng 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()
Bằng cách tinh chỉnh các hằng số, bạn cũng có thể sử dụng chương trình này để đánh giá mức tiêu thụ bộ nhớ chung của cấu trúc dữ liệu này.
IMO chiến lược này đơn giản và hiệu quả vì nó cung cấp độ phức tạp O (1) để thêm / xóa người dùng và độ phức tạp O (n) thực sự để lặp lại trên tất cả các mục. Nhược điểm duy nhất là thứ tự lặp lại khóa là ngẫu nhiên.
