Giới thiệu về cấu trúc dữ liệu Redis:Bitmaps

Bitmap (còn được gọi là mảng bit, vectơ bit, v.v.) là cấu trúc dữ liệu ngay lập tức xuất hiện trong đầu bạn khi bạn cần ánh xạ thông tin boolean cho một miền lớn thành một tập tin nhỏ gọn sự đại diện. Đây là một cấu trúc dữ liệu rất phổ biến bất cứ khi nào dung lượng bộ nhớ ở mức cao:hạt nhân hệ điều hành (trang bộ nhớ, inodes, v.v.), hình ảnh kỹ thuật số, v.v.

Redis, là một máy chủ cấu trúc dữ liệu trong bộ nhớ, cung cấp hỗ trợ cho các hoạt động thao tác bit. Tuy nhiên, không có cấu trúc dữ liệu đặc biệt cho Bitmap trong Redis. Đúng hơn, các phép toán mức bit được hỗ trợ trên cấu trúc Redis cơ bản:Chuỗi. Bây giờ, độ dài tối đa cho chuỗi Redis là 512 MB. Do đó, miền lớn nhất mà Redis có thể ánh xạ dưới dạng Bitmap là 2 (512 MB =2 byte =2 bit).

Các thao tác liên quan đến bit trong Redis có hai loại:Thời gian không đổi (O (1)), ví dụ:các phép toán để lấy / đặt một bit cụ thể và các phép toán O (N) về cơ bản hoạt động trên một nhóm các bit. N trong những trường hợp này là độ dài của các bit mà hoạt động sẽ cần để thực hiện. Hãy xem một số ví dụ.

Lệnh

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

Ngoài các toán tử hoạt động trên chính khóa, BITOP toán tử được sử dụng cho các phép toán logic khôn ngoan giữa nhiều khóa.

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

Nội bộ

Vì hoạt động bitmap không có cấu trúc dữ liệu của riêng chúng, nên không có cấu trúc dữ liệu đặc biệt để mô tả. Bản thân các chuỗi Redis được thực hiện như một chuỗi an toàn nhị phân. Cấu trúc dữ liệu chuỗi Redis được gọi nội bộ là Chuỗi động đơn giản (SDS). Về cơ bản, nó là một char [] gốc với một số thông tin lưu giữ sách bổ sung. Chi tiết triển khai có thể được tìm thấy tại đây.

Việc triển khai các hàm bitmap nằm trong tệp bitops.c .

Tái bút:Do tầm quan trọng của các thuật toán thao tác bit đối với hệ điều hành và chức năng đồ họa quan trọng, hầu hết các kiến ​​trúc đều cung cấp các hướng dẫn đặc biệt cho các thao tác đó. Một nơi tốt để đọc các thuật toán số học thú vị khác nhau của máy tính là Hacker’s Delight cổ điển vượt thời gian.

Ứng dụng

Blog GetSpool phổ biến này là một ví dụ tuyệt vời về việc sử dụng bitmap để phân tích thời gian thực trên một tập dữ liệu lớn. Nó cũng là một ví dụ về trường hợp sử dụng cổ điển của bitmap:để lưu trữ thông tin boolean của một miền cực lớn vào không gian nhỏ (tương đối) trong khi vẫn giữ được hiệu suất tốt.

Kích thước thường là mối quan tâm đối với các ảnh bitmap thực sự lớn, vì hầu hết các phép toán hữu ích đối với nó là O (N). Để tránh làm việc với các khóa lớn, tài liệu Redis khuyên bạn nên chia các khóa lớn thành nhiều khóa nhỏ hơn. Hiệu suất BITCOUNT vẫn có thể chấp nhận được cho đến khi khóa trở nên lớn. Tại thời điểm đó, khuyến nghị là tách các khóa hoặc sử dụng các đối số phạm vi để truy vấn tăng dần. Khuyến nghị để giải quyết các hoạt động BITOP chậm là chạy nó trên nô lệ. Vì vậy, nói chung, việc xử lý các khóa có kích thước vừa phải và lập kế hoạch cho sự phát triển tiềm năng trong tương lai là hợp lý bằng cách chia các khóa thành nhiều khóa.

Bộ Redis so với Redis Bitmap

Bản chất của chức năng được cung cấp bởi Redis Sets và các hoạt động bitmap là tương tự. Vì vậy, chúng ta thường nhầm lẫn giữa hai cách tiếp cận nào là tốt hơn. Vâng, nó thực sự phụ thuộc vào bản chất chính xác của trường hợp sử dụng. Rõ ràng, cuộc thảo luận này chỉ hợp lệ đối với loại hoạt động mà cả bộ và bitmap có thể đạt được.

Bộ Redis nói chung hoạt động hiệu quả và có quy mô tốt và phải là cấu trúc dữ liệu được lựa chọn cho đến khi kích thước của nó trở nên không thể kiểm soát được. Redis Sets cũng dễ quản lý hơn, chương trình và gỡ lỗi sẽ hoạt động tốt cho hầu hết các ứng dụng. Không nên đánh giá thấp tính dễ sử dụng của Sets:Mã thao tác bitmap thường khó đọc, hiểu, gỡ lỗi và bảo trì. Ngay cả khi miền rất lớn, các bộ vẫn có thể phù hợp. Ví dụ nếu một ứng dụng nhằm theo dõi lượt truy cập hàng ngày vào một trang web thương mại điện tử phổ biến, thì kết quả có thể vẫn phù hợp với một tập hợp vì thường chỉ có 5-10% toàn bộ cơ sở người dùng sẽ truy cập trang web hàng ngày. Điều này rõ ràng là thay đổi đối với một trang web mà 60% toàn bộ cơ sở người dùng dự kiến ​​sẽ đăng nhập hàng ngày. Sau đó, bitmap trở nên phù hợp hơn với kích thước và hiệu suất của các phép toán khôn ngoan bit logic trên một số lượng lớn các khóa. Redis Sets cũng có lợi thế khác biệt là không phải ánh xạ các ID thành các hiệu số bit. Tương tự, nếu các giá trị của bạn đến từ một miền lớn hơn 2 thì Bộ Redis phải dễ sử dụng hơn là tìm ra các cơ chế để phân chia miền cho bitmap.

Phân tích cho MOOC

Đây là một ví dụ tổng hợp (nhưng đủ thực tế!) cho một nơi mà người ta có thể áp dụng các phép toán bitmap của Redis. Giả sử bạn đang chạy một MOOC trực tuyến rất phổ biến mà hàng trăm nghìn sinh viên đã đăng ký. Nhóm học thuật tạo điều kiện cho khóa học muốn có một bảng điều khiển vì họ có thể thấy trạng thái thời gian thực về sự tiến bộ của sinh viên cũng như nền tảng chung của sinh viên đã đăng ký. Bạn quyết định thực hiện điều này thông qua các hoạt động bitmap của Redis. Đây là cách tiếp cận từng bước đối với nó.

1. Tạo một kế hoạch ánh xạ giữa mã số sinh viên với độ lệch bitmap. Nó có thể đơn giản như ID là phần bù trong bitmap.
2. Tạo và điền các ảnh bitmap liên quan đến nhân khẩu học khác nhau khi khóa học bắt đầu. Ví dụ sinh viên đã đăng ký vào các MOOC khác từ cùng một trường đại học, trình độ học vấn, giới tính, v.v.
3. Bây giờ khi khóa học tiến triển, bạn có thể tạo các ảnh bitmap mới để ghi lại tiến trình của khóa học. Ví dụ những sinh viên đã hoàn thành việc xem tất cả các bài giảng của tuần 1, những sinh viên đã hoàn thành tất cả các bài tập của tuần 1. v.v.
4. Giờ đây, việc tạo phân tích thời gian thực dựa trên các phím này sẽ là một bài tập rất đơn giản và có thể được thực hiện trên giao diện người dùng kéo và thả. Đối với ví dụ:

• Một giáo sư muốn xem có bao nhiêu sinh viên đã xem bài giảng trong tuần 1 (A) nhưng không hoàn thành bài tập trong tuần 1 (B):Toán tử:BITOP. Hoạt động:A VÀ (KHÔNG PHẢI B).
• Học sinh đã hoàn thành tất cả các bài tập trong tuần 1 (A), tuần 2 (B), tuần 3 (C) và tuần 4 (D):Toán tử:BITOP. Thao tác A VÀ B VÀ C VÀ D. Giả sử, đây là những người đã vượt qua khóa học.
• Tất cả nam sinh viên (M) đã vượt qua khóa học (như đã tính ở trên, giả sử P):Toán tử:BITOP. Hoạt động:M VÀ P.
• Số sinh viên đã vượt qua khóa học:BITCOUNT P.

Tương tự, bất kỳ số lượng nhóm thuần tập thú vị nào cũng có thể được thiết lập dưới dạng bitmap và các hoán vị như vậy chạy trên chúng.

Chú thích cuối trang

Các bài đăng khác trong chuỗi cấu trúc dữ liệu Redis của chúng tôi:

• Bộ
• Hàm băm
• Bộ được sắp xếp