Redis
 sql >> Cơ Sở Dữ Liệu >  >> NoSQL >> Redis

Redis `SCAN`:làm thế nào để duy trì sự cân bằng giữa các khóa mới có thể khớp và đảm bảo kết quả cuối cùng trong một thời gian hợp lý?

Đầu tiên là một số ngữ cảnh, giải pháp ở cuối :

Từ lệnh SCAN> Đảm bảo kết thúc

Thuật toán SCAN được đảm bảo sẽ kết thúc chỉ khi kích thước của bộ sưu tập được mô tả vẫn bị giới hạn ở một kích thước tối đa nhất định, nếu không, việc giải thích một bộ sưu tập luôn phát triển có thể dẫn đến việc SCAN không bao giờ bỏ qua một lần lặp đầy đủ.

Điều này dễ dàng nhận thấy một cách trực quan:nếu bộ sưu tập phát triển thì càng có nhiều việc phải làm để truy cập tất cả các phần tử có thể có và khả năng kết thúc lặp lại phụ thuộc vào số lượng callsto SCAN và giá trị tùy chọn COUNT của nó so với tốc độ tại mà bộ sưu tập phát triển.

Nhưng trong tùy chọn COUNT, nó cho biết:

Quan trọng:không cần phải sử dụng cùng một giá trị COUNT cho mọi chuyển động. Người gọi có thể tự do thay đổi số lượng từ vòng lặp này sang số vòng lặp khác theo yêu cầu, miễn là con trỏ được truyền trong cuộc gọi tiếp theo là con trỏ thu được trong lần gọi lệnh trước đó.

Điều quan trọng cần ghi nhớ, từ đảm bảo Quét:

  • Một phần tử đã cho có thể được trả về nhiều lần. Tùy thuộc vào ứng dụng để xử lý trường hợp các phần tử bị trùng lặp, chẳng hạn như chỉ sử dụng các phần tử được trả về để thực hiện các hoạt động an toàn khi được áp dụng lại nhiều lần.
  • Các phần tử không xuất hiện liên tục trong bộ sưu tập trong một lần lặp lại đầy đủ, có thể được quay lại hoặc không:nó không được xác định.

Chìa khóa của một giải pháp nằm ở chính con trỏ. Xem Tạo ý nghĩa của con trỏ Redis ’SCAN. Có thể suy ra phần trăm tiến trình quét của bạn bởi vì con trỏ thực sự được đảo ngược bit của một chỉ mục với kích thước bảng.

Sử dụng DBSIZE hoặc INFO keyspace lệnh bạn có thể nhận được bao nhiêu khóa bạn có bất kỳ lúc nào:

> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0

Một nguồn thông tin khác là chỉ mục htstats DEBUG htstats index , chỉ để cảm nhận:

> DEBUG htstats 0
[Dictionary HT]
Hash table 0 stats (main hash table):
 table size: 262144
 number of elements: 200032
 different slots: 139805
 max chain length: 8
 avg chain length (counted): 1.43
 avg chain length (computed): 1.43
 Chain length distribution:
   0: 122339 (46.67%)
   1: 93163 (35.54%)
   2: 35502 (13.54%)
   3: 9071 (3.46%)
   4: 1754 (0.67%)
   5: 264 (0.10%)
   6: 43 (0.02%)
   7: 6 (0.00%)
   8: 2 (0.00%)
[Expires HT]
No stats available for empty dictionaries

Kích thước bảng là lũy thừa của 2 sau số phím của bạn:Phím:200032 => Kích thước bàn:262144

Giải pháp:

Chúng tôi sẽ tính toán một COUNT mong muốn đối số cho mọi lần quét.

Giả sử bạn sẽ gọi SCAN với một tần số (F tính bằng Hz) của 10 Hz (mỗi 100 mili giây) và bạn muốn nó hoàn thành trong 5 giây (T tính bằng s). Vì vậy, bạn muốn điều này hoàn thành trong N = F*T cuộc gọi, N = 50 trong ví dụ này.

Trước lần quét đầu tiên, bạn biết tiến trình hiện tại của mình là 0, vì vậy phần trăm còn lại của bạn là RP = 1 (100%).

Trước mỗi SCAN cuộc gọi (hoặc mỗi số cuộc gọi nhất định mà bạn muốn điều chỉnh COUNT của mình nếu bạn muốn lưu Thời gian khứ hồi (RTT) của DBSIZE gọi), bạn gọi DBSIZE để lấy số lượng khóa K .

Bạn sẽ sử dụng COUNT = K*RP/N

Đối với cuộc gọi đầu tiên, đây là COUNT = 200032*1/50 = 4000 .

Đối với bất kỳ lệnh gọi nào khác, bạn cần tính toán RP = 1 - ReversedCursor/NextPowerOfTwo(K) .

Ví dụ:giả sử bạn đã thực hiện 20 cuộc gọi, vì vậy bây giờ N = 30 (số cuộc gọi còn lại). Bạn đã gọi DBSIZE và nhận K = 281569 . Điều này có nghĩa là NextPowerOfTwo(K) = 524288 , đây là 2 ^ 19.

Con trỏ tiếp theo của bạn là 14509 trong hệ thập phân =000011100010101101 trong hệ nhị phân. Vì kích thước bảng là 2 ^ 19, chúng tôi biểu diễn nó bằng 18 bit.

Bạn đảo ngược các bit và nhận được 101101010001110000 trong hệ nhị phân =185456 trong hệ thập phân. Điều này có nghĩa là chúng tôi đã bao phủ 185456 trong số 524288. Và:

RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%

Vì vậy, bạn phải điều chỉnh:

COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100

Vì vậy, trong SCAN tiếp theo của bạn cuộc gọi bạn sử dụng 6100 . Có nghĩa là nó đã tăng lên vì:

  • Số lượng khóa đã tăng từ 200032 lên 281569.
  • Mặc dù chúng tôi chỉ còn 60% ước tính ban đầu về số cuộc gọi, nhưng tiến độ vẫn còn chậm vì 65% không gian phím đang chờ được quét.

Tất cả điều này được giả định rằng bạn đang nhận được tất cả các chìa khóa. Nếu bạn đang khớp mẫu , bạn cần sử dụng quá khứ để ước tính số lượng chìa khóa còn lại được tìm thấy. Chúng tôi thêm dưới dạng một yếu tố PM (phần trăm so khớp) với COUNT tính toán.

COUNT = PM * K*RP/N

PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))

Nếu sau 20 cuộc gọi, bạn chỉ tìm thấy keysFound = 2000 các phím, sau đó:

PM = 2000 / ( 281569 * 185456 / 524288) = 0.02

Điều này có nghĩa là chỉ có 2% số khóa phù hợp với mẫu của chúng tôi cho đến nay, vì vậy

COUNT = PM * K*RP/N = 0.02 * 6100 = 122

Thuật toán này có thể được cải thiện, nhưng bạn hiểu rồi đấy.

Đảm bảo chạy một số điểm chuẩn trên COUNT số bạn sẽ sử dụng để bắt đầu, để đo lường SCAN của bạn là bao nhiêu mili giây nhận, vì bạn có thể cần phải điều chỉnh kỳ vọng của mình về số lượng cuộc gọi bạn cần (N ) để thực hiện việc này trong thời gian hợp lý mà không chặn máy chủ và điều chỉnh F của bạn và T theo đó.




  1. Redis
  2.   
  3. MongoDB
  4.   
  5. Memcached
  6.   
  7. HBase
  8.   
  9. CouchDB
  1. Lỗi:Không thể kết nối với Redis tại redis:6379:Không xác định được tên hoặc dịch vụ

  2. Redis lọc theo phạm vi, sắp xếp và trả về 10 đầu tiên

  3. PooledRedisClientManager không giải phóng kết nối

  4. Làm thế nào để MỞ RỘNG khóa con HSET trong redis?

  5. Redis pub / sub cho máy chủ trò chuyện trong node.js