Giải pháp tốt nhất cho việc tìm kiếm 1 x 1 triệu giao lộ được thiết lập? Redis, Mongo, khác

Question

Xin chào tất cả và cảm ơn trước. Tôi mới tham gia trò chơi NoSQL nhưng nơi làm việc hiện tại của tôi đã giao nhiệm vụ cho tôi với các so sánh được thiết lập của một số dữ liệu lớn.

Hệ thống của chúng tôi có bộ thẻ khách hàng và bộ thẻ được nhắm mục tiêu. Thẻ là số có 8 chữ số.
Bộ thẻ khách hàng có thể có tối đa 300 thẻ nhưng trung bình 100 thẻ
Bộ thẻ được nhắm mục tiêu có thể có tối đa 300 thẻ nhưng trung bình 40 thẻ.

Tính toán trước không phải là một tùy chọn khi chúng tôi quay cho một cơ sở khách hàng tiềm năng của một tỷ người dùng.

(Các thẻ được phân cấp do đó, có một thẻ ngụ ý rằng bạn cũng có thẻ phụ huynh và tổ tiên của mình. Đặt thông tin mà dành cho thời điểm này.)

Khi một khách hàng lượt truy cập trang web của chúng tôi, chúng ta cần phải cắt thẻ của họ đặt chống lại một triệu thẻ được nhắm mục tiêu đặt nhanh nhất có thể. Bộ khách hàng phải chứa tất cả các phần tử của tập hợp được nhắm mục tiêu để khớp.

Tôi đã khám phá các tùy chọn của mình và giao điểm được đặt trong Redis có vẻ như nó sẽ lý tưởng. Tuy nhiên, trolling của tôi thông qua internet đã không tiết lộ bao nhiêu ram sẽ được yêu cầu để giữ một triệu bộ thẻ. Tôi nhận ra giao lộ sẽ nhanh như chớp, nhưng đây có phải là giải pháp khả thi với Redis không.

Tôi nhận thấy đây là lực lượng vũ phu và không hiệu quả. Tôi cũng muốn sử dụng câu hỏi này như là phương tiện để có được các đề xuất về cách thức loại vấn đề này đã được xử lý trong quá khứ. Như đã nêu trước đây, các thẻ được lưu trữ trong một cây. Tôi cũng đã bắt đầu xem Mongodb như một giải pháp khả thi.

Cảm ơn lần nữa

Answer 1

Đây là một vấn đề thú vị và tôi nghĩ Redis có thể trợ giúp tại đây.

Redis có thể lưu trữ bộ số nguyên sử dụng định dạng "intset" được tối ưu hóa. Xem http://redis.io/topics/memory-optimization để biết thêm thông tin.

Tôi tin rằng cấu trúc dữ liệu chính xác ở đây là tập hợp các bộ thẻ được nhắm mục tiêu, cộng với chỉ mục đảo ngược để ánh xạ thẻ cho các bộ thẻ được nhắm mục tiêu của chúng.

Để lưu trữ hai bộ thẻ nhắm mục tiêu:

0 -> [ 1 2 3 4 5 6 7 8 ] 
1 -> [ 6 7 8 9 10 ] 

Tôi sẽ sử dụng:

# Targeted tag sets 
sadd tgt:0 1 2 3 4 5 6 7 8 
sadd tgt:1 2 6 7 8 9 10 
# Reverse index 
sadd tag:0 0 
sadd tag:1 0 
sadd tag:2 0 1 
sadd tag:3 0 
sadd tag:4 0 
sadd tag:5 0 
sadd tag:6 0 1 
sadd tag:7 0 1 
sadd tag:8 0 1 
sadd tag:9 1 
sadd tag:10 1 

chỉ số ngược này là khá dễ dàng để duy trì khi bộ thẻ nhắm mục tiêu được thêm/xóa khỏi hệ thống.

Mức tiêu thụ bộ nhớ toàn cầu tùy thuộc vào số lượng thẻ phổ biến cho nhiều bộ thẻ được nhắm mục tiêu. Nó là khá dễ dàng để lưu trữ dữ liệu giả trong Redis và mô phỏng mức tiêu thụ bộ nhớ. Tôi đã thực hiện nó bằng cách sử dụng simple node.js script.

Đối với 1 triệu bộ thẻ được nhắm mục tiêu (thẻ là 8 chữ số, 40 thẻ cho mỗi bộ), mức tiêu thụ bộ nhớ gần 4 GB khi có rất ít thẻ được chia sẻ bởi bộ thẻ được nhắm mục tiêu (hơn 32 triệu mục nhập) trong chỉ số ngược) và khoảng 500 MB khi các thẻ được chia sẻ rất nhiều (chỉ 100K mục trong chỉ mục ngược).

Với cấu trúc dữ liệu này, việc tìm kiếm các bộ thẻ được nhắm mục tiêu chứa tất cả các thẻ của một khách hàng nhất định là cực kỳ hiệu quả.

1- Get customer tag set (suppose it is 1 2 3 4) 
2- SINTER tag:1 tag:2 tag:3 tag:4 
    => result is a list of targeted tag sets having all the tags of the customer 

Thao tác giao cắt có hiệu quả vì Redis đủ thông minh để đặt các bộ cho mỗi thẻ và bắt đầu với tập hợp có số lượng thẻ thấp nhất.

Bây giờ tôi hiểu rằng bạn cần triển khai hoạt động trò chuyện (nghĩa là tìm các bộ thẻ được nhắm mục tiêu có tất cả các thẻ của họ trong bộ thẻ khách hàng). Chỉ số đảo ngược vẫn có thể hữu ích.

đây trong một ví dụ trong xấu xí pseudo-code:

1- Get customer tag set (suppose it is 1 2 3 4) 
2- SUNIONSTORE tmp tag:1 tag:2 tag:3 tag:4 
    => result is a list of targeted tag sets having at least one tag in common with the customer 
3- For t in tmp (iterating on the selected targeted tag sets) 
     n = SCARD tgt:t (cardinality of the targeted tag sets) 
     intersect = SINTER customer tgt:t 
     if n == len(intersect), this targeted tag set matches 

Vì vậy, bạn không bao giờ phải kiểm tra thẻ của khách hàng thiết lập chống lại 1M bộ thẻ nhắm mục tiêu. Bạn có thể dựa vào chỉ mục đảo ngược để hạn chế phạm vi tìm kiếm ở mức có thể chấp nhận được.

Answer 2

này có thể hữu ích:

Case Study: Sử dụng Redis giao nhau trên bộ rất lớn (120M + với 120M +)

http://redis4you.com/articles.php?id=016&name=Case+Study%3A+Using+Redis+intersect+on+very+large+sets

Answer 3

Những câu trả lời cung cấp đã giúp tôi bước đầu. Tuy nhiên, khi cơ sở khách hàng của chúng tôi tăng trưởng, tôi tình cờ gặp một kỹ thuật tuyệt vời liên quan đến việc sử dụng các chuỗi bit và các toán tử bit để thực hiện phân tích trên hàng trăm triệu người dùng một cách nhanh chóng.

Kiểm tra bài viết này. Antirez, tác giả của redis, cũng tham khảo rất nhiều điều này.

http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/