Bỏ qua nội dung chính

Giải thích chi tiết 3 kiểu dữ liệu đặc biệt của Redis

GuideDatabaseRedisKhoảng 2198 từKhoảng 7 phút

Ngoài 5 kiểu dữ liệu cơ bản, Redis còn hỗ trợ 3 kiểu dữ liệu đặc biệt: Bitmap, HyperLogLog và GEO.

Bitmap (bit map)

Giới thiệu

Theo giới thiệu trên trang web chính thức:

Bitmaps are not an actual data type, but a set of bit-oriented operations defined on the String type which is treated like a bit vector. Since strings are binary safe blobs and their maximum length is 512 MB, they are suitable to set up to 2^32 different bits.

Bitmap không phải là một kiểu dữ liệu thực tế trong Redis, mà là một tập hợp các thao tác hướng bit được định nghĩa trên kiểu String và được xem như một vector bit. Vì String là các blob binary-safe, có độ dài tối đa 512 MB, chúng phù hợp để thiết lập tối đa 2^32 bit khác nhau.

Bitmap lưu trữ các số nhị phân liên tiếp (0 và 1). Với Bitmap, chỉ cần một bit để biểu diễn giá trị hoặc trạng thái tương ứng của một phần tử, còn key là phần tử tương ứng. 8 bit có thể tạo thành một byte, vì vậy bản thân Bitmap tiết kiệm đáng kể không gian lưu trữ.

Bạn có thể xem Bitmap như một array lưu trữ các số nhị phân (0 và 1), chỉ số của mỗi phần tử trong array được gọi là offset.

Lệnh thường dùng

LệnhGiới thiệu
SETBIT key offset valueThiết lập giá trị tại vị trí offset được chỉ định
GETBIT key offsetLấy giá trị tại vị trí offset được chỉ định
BITCOUNT key start endLấy số phần tử có giá trị bằng 1 giữa start và end
BITOP operation destkey key1 key2 ...Thực hiện phép toán trên một hoặc nhiều Bitmap, gồm AND, OR, XOR và NOT

Minh họa thao tác cơ bản với Bitmap:

# SETBIT trả về giá trị của bit trước đó (mặc định là 0), ở đây sẽ tạo 7 bit
> SETBIT mykey 7 1
(integer) 0
> SETBIT mykey 7 0
(integer) 1
> GETBIT mykey 7
(integer) 0
> SETBIT mykey 6 1
(integer) 0
> SETBIT mykey 8 1
(integer) 0
# Dùng bitcount để thống kê số bit đã được đặt thành 1.
> BITCOUNT mykey
(integer) 2

Trường hợp áp dụng

Các trường hợp cần lưu thông tin trạng thái (0/1 là đủ để biểu diễn)

  • Ví dụ: tình trạng check-in của người dùng, trạng thái hoạt động của người dùng, thống kê hành vi người dùng (chẳng hạn đã thích một video nào đó hay chưa).
  • Lệnh liên quan: SETBIT, GETBIT, BITCOUNT, BITOP.

HyperLogLog (đếm cardinality)

Giới thiệu

HyperLogLog là một thuật toán xác suất đếm cardinality nổi tiếng, được tối ưu hóa và cải tiến từ LogLog Counting (LLC), không phải tính năng riêng của Redis. Redis chỉ triển khai thuật toán này và cung cấp một số API có thể dùng ngay.

HyperLogLog do Redis cung cấp chiếm không gian cực kỳ nhỏ, chỉ cần 12k không gian là có thể lưu gần 2^64 phần tử khác nhau. Điều này thực sự ấn tượng, đây chính là sức hấp dẫn của toán học! Ngoài ra, Redis đã tối ưu cấu trúc lưu trữ của HyperLogLog và sử dụng hai cách đếm:

  • Ma trận thưa: chiếm rất ít không gian khi số lượng phần tử được đếm còn nhỏ.
  • Ma trận dày: chiếm 12k không gian khi số lượng phần tử được đếm đạt đến một ngưỡng nhất định.

Tài liệu chính thức của Redis có phần giải thích chi tiết tương ứng:

Để tiết kiệm bộ nhớ, thuật toán xác suất đếm cardinality không lưu trực tiếp metadata, mà ước tính giá trị cardinality (số phần tử trong tập hợp) thông qua một phương pháp thống kê xác suất. Vì vậy, kết quả đếm của HyperLogLog không phải là giá trị chính xác và có sai số nhất định (sai số chuẩn là 0.81%).

Cách sử dụng HyperLogLog rất đơn giản, nhưng nguyên lý lại rất phức tạp. Bạn có thể xem nguyên lý của HyperLogLog và cách triển khai trong Redis tại bài viết này: Giải thích nguyên lý của thuật toán HyperLogLog và cách Redis áp dụng nó.

Ngoài ra, đây là một công cụ giúp hiểu nguyên lý của HyperLogLog: Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure.

Ngoài HyperLogLog, Redis còn cung cấp các cấu trúc dữ liệu xác suất khác. Địa chỉ tài liệu chính thức tương ứng: https://redis.io/docs/data-types/probabilistic/.

Lệnh thường dùng

Các lệnh liên quan đến HyperLogLog rất ít, thường dùng nhất chỉ có 3 lệnh.

LệnhGiới thiệu
PFADD key element1 element2 ...Thêm một hoặc nhiều phần tử vào HyperLogLog
PFCOUNT key1 key2Lấy số lượng phần tử duy nhất của một hoặc nhiều HyperLogLog
PFMERGE destkey sourcekey1 sourcekey2 ...Gộp nhiều HyperLogLog vào destkey; destkey kết hợp các nguồn để tính số lượng phần tử duy nhất tương ứng

Minh họa thao tác cơ bản với HyperLogLog:

> PFADD hll foo bar zap
(integer) 1
> PFADD hll zap zap zap
(integer) 0
> PFADD hll foo bar
(integer) 0
> PFCOUNT hll
(integer) 3
> PFADD some-other-hll 1 2 3
(integer) 1
> PFCOUNT hll some-other-hll
(integer) 6
> PFMERGE desthll hll some-other-hll
"OK"
> PFCOUNT desthll
(integer) 6

Trường hợp áp dụng

Các trường hợp đếm số lượng cực lớn (từ cấp triệu, chục triệu trở lên)

  • Ví dụ: thống kê số lượng IP truy cập website phổ biến theo ngày/tuần/tháng, thống kê UV của bài đăng phổ biến.
  • Lệnh liên quan: PFADD, PFCOUNT.

Geospatial (vị trí địa lý)

Giới thiệu

Geospatial index (chỉ mục không gian địa lý, gọi tắt là GEO) chủ yếu được dùng để lưu trữ thông tin vị trí địa lý và được triển khai dựa trên Sorted Set.

Với GEO, bạn có thể dễ dàng tính khoảng cách giữa hai vị trí, lấy các phần tử ở gần một vị trí được chỉ định và thực hiện các chức năng khác.

Lệnh thường dùng

LệnhGiới thiệu
GEOADD key longitude1 latitude1 member1 ...Thêm thông tin kinh độ, vĩ độ tương ứng của một hoặc nhiều phần tử vào GEO
GEOPOS key member1 member2 ...Trả về thông tin kinh độ, vĩ độ của các phần tử đã cho
GEODIST key member1 member2 M/KM/FT/MITrả về khoảng cách giữa hai phần tử đã cho
GEORADIUS key longitude latitude radius distanceLấy các phần tử khác trong phạm vi distance quanh vị trí được chỉ định, hỗ trợ các tham số ASC (gần đến xa), DESC (xa đến gần), Count (số lượng)
GEORADIUSBYMEMBER key member radius distanceTương tự lệnh GEORADIUS, chỉ khác là điểm trung tâm tham chiếu là một phần tử trong GEO

Thao tác cơ bản:

> GEOADD personLocation 116.33 39.89 user1 116.34 39.90 user2 116.35 39.88 user3
3
> GEOPOS personLocation user1
116.3299986720085144
39.89000061669732844
> GEODIST personLocation user1 user2 km
1.4018

Khi dùng công cụ trực quan hóa Redis để xem personLocation, đúng như dự đoán, cấu trúc bên dưới chính là Sorted Set.

Dữ liệu kinh độ và vĩ độ được lưu trong GEO được chuyển đổi thành một số nguyên thông qua thuật toán GeoHash. Số nguyên này được dùng làm score (tham số trọng số) của Sorted Set.

Lấy các phần tử khác trong phạm vi quanh vị trí được chỉ định:

> GEORADIUS personLocation 116.33 39.87 3 km
user3
user1
> GEORADIUS personLocation 116.33 39.87 2 km
> GEORADIUS personLocation 116.33 39.87 5 km
user3
user1
user2
> GEORADIUSBYMEMBER personLocation user1 5 km
user3
user1
user2
> GEORADIUSBYMEMBER personLocation user1 2 km
user1
user2

Bạn có thể xem bài viết của Alibaba này để tìm hiểu nguyên lý bên dưới của lệnh GEORADIUS: Redis thực sự triển khai chức năng “người ở gần” như thế nào?.

Xóa phần tử:

GEO sử dụng Sorted Set ở tầng dưới, nên bạn có thể dùng các lệnh liên quan đến Sorted Set cho GEO.

> ZREM personLocation user1
1
> ZRANGE personLocation 0 -1
user3
user2
> ZSCORE personLocation user2
4069879562983946

Trường hợp áp dụng

Các trường hợp cần quản lý và sử dụng dữ liệu không gian địa lý

  • Ví dụ: người ở gần.
  • Lệnh liên quan: GEOADD, GEORADIUS, GEORADIUSBYMEMBER.

Tổng kết

Kiểu dữ liệuMô tả
BitmapBạn có thể xem Bitmap như một array lưu trữ các số nhị phân (0 và 1), chỉ số của mỗi phần tử trong array được gọi là offset. Với Bitmap, chỉ cần một bit để biểu diễn giá trị hoặc trạng thái tương ứng của một phần tử, còn key là phần tử tương ứng. 8 bit có thể tạo thành một byte, vì vậy bản thân Bitmap tiết kiệm đáng kể không gian lưu trữ.
HyperLogLogHyperLogLog do Redis cung cấp chiếm không gian cực kỳ nhỏ, chỉ cần 12k không gian là có thể lưu gần 2^64 phần tử khác nhau. Tuy nhiên, kết quả đếm của HyperLogLog không phải là giá trị chính xác và có sai số nhất định (sai số chuẩn là 0.81%).
Geospatial indexGeospatial index (chỉ mục không gian địa lý, gọi tắt là GEO) chủ yếu được dùng để lưu trữ thông tin vị trí địa lý và được triển khai dựa trên Sorted Set.

Tham khảo

Lời cuối

Nếu nội dung hữu ích với bạn, hãy tiện tay tặng JavaGuide một Star miễn phí để ủng hộ: GitHub | Gitee.

JavaGuide đã được duy trì gần bảy năm, tích lũy 6100+ commit, với sự chung tay hoàn thiện của 620+ contributor. Star, phản hồi và PR của bạn đều là động lực để dự án tiếp tục cập nhật.

Nếu bạn đang chuẩn bị phỏng vấn backend / phát triển ứng dụng AI, có thể tham khảo Knowledge Planet của tôi, bao gồm các project thực tế về backend và AI, tối ưu CV, hỏi đáp 1-1 và tài liệu về các trọng điểm thường gặp, đã được duy trì liên tục sáu năm.