Giới thiệu về cấu trúc dữ liệu Redis:Hàm băm

Hàm băm của Redis là (đủ trực quan!) hàm băm ánh xạ tên chuỗi thành giá trị chuỗi. Về cơ bản, chúng là vùng chứa được đặt tên của các trường duy nhất và giá trị của chúng. Chúng là cách hoàn hảo để biểu diễn một đối tượng dưới dạng cấu trúc dữ liệu Redis. Như mong đợi, chúng cung cấp các hoạt động cơ bản với thời gian không đổi như get, set, being, v.v. Một loạt các hoạt động nâng cao cũng được cung cấp. Danh sách đầy đủ các lệnh băm có ở đây.

Hãy cùng tìm hiểu kỹ từ redis-cli .

# hmset key field value [field value ...] :  Insert elements in a hash. O(N), N is # of field being set
127.0.0.1:6379> hmset std:101 name "John Smith" dob "01-01-2000" gender M active 0 cgpa 2.9
OK

# hgetall key : key all keys and values in the hash. O(N), N is size of hash
127.0.0.1:6379> hgetall std:101
 1) "name"
 2) "John Smith"
 3) "dob"
 4) "01-01-2000"
 5) "gender"
 6) "M"
 7) "active"
 8) "0"
 9) "cgpa"
10) "2.9"
127.0.0.1:6379> hmset std:102 name "Jane" name "Ann"
OK
# If duplicates are found, only the last set is valid
127.0.0.1:6379> hgetall std:102
1) "name"
2) "Ann"

# hexists key field: does field exist in the hash with key. O(1)
127.0.0.1:6379> hexists std:102 cgpa
(integer) 0

# hincrby key field increment: Increment the integer field by increment. O(1)
127.0.0.1:6379> hincrby std:101 active 1
(integer) 1

# hget key field : the value for field in the hash stored at key. O(1)
127.0.0.1:6379> hget std:101 active
1) "1"
# If field doesn't exist, hincrby sets it to 0 and then applies increment
127.0.0.1:6379> hincrby std:102 active 2
(integer) 2

# hmget key field [field ...]: the values of the fields requested for the hash with key. O(N), N is # of keys requested
127.0.0.1:6379> hmget std:102 active
1) "2"

# hincrbyfloat key field increment: Increment the float value in field by increment. O(1) 
127.0.0.1:6379> HINCRBYFLOAT std:101 cgpa 1.0
"3.9"

# HSETNX key field value: set field to value if not alread set. O(1)
127.0.0.1:6379> hsetnx std:102 cgpa 4.0
(integer) 1
127.0.0.1:6379> hget std:102 cgpa
"4.0"

# hlen key: number of fields in the hash. O(1)
127.0.0.1:6379> hlen std:101
(integer) 5

# hkeys key : all fields in the hash. O(N), N is size of hash
127.0.0.1:6379> hkeys std:101
1) "name"
2) "dob"
3) "gender"
4) "active"
5) "cgpa"

Như chúng tôi đã mong đợi từ máy chủ lưu trữ Redis ™ * của chúng tôi như một máy chủ cấu trúc dữ liệu, chúng tôi thấy rằng Redis cung cấp các hoạt động khá hữu ích và nâng cao trên mã băm.

Nội bộ

Giống như Redis Sets, hàm băm Redis cũng được triển khai dưới dạng từ điển. Các từ điển trong Redis được triển khai dưới dạng bảng băm sử dụng hàm băm MurmurHash2 và phát triển thông qua thay đổi kích thước gia tăng. Các va chạm băm được xử lý bằng cách xâu chuỗi. Bạn có thể tìm thêm thông tin chi tiết trong phần triển khai Redis của từ điển tại dict.c.
Cũng như với Sets, có tối ưu hóa lưu trữ được thực hiện cho các hàm băm nhỏ hơn. Cấu trúc dữ liệu này được gọi là ziplist (Hashes được tối ưu hóa bằng cách sử dụng một cấu trúc dữ liệu khác được gọi là zipmap trước Redis 2.6) trong quá trình triển khai Redis. Về cơ bản, nó là một danh sách liên kết kép được mã hóa đặc biệt được tối ưu hóa để tiết kiệm bộ nhớ. Dữ liệu, cũng như các con trỏ được lưu trữ nội tuyến. Ziplist cũng được sử dụng để tối ưu hóa việc lưu trữ các tập hợp và danh sách được sắp xếp nhỏ hơn. Một băm khi được làm phẳng thành một danh sách như vậy trông giống như, [key1, value1, key2, value2, ...]. Làm thế nào điều này hiệu quả hơn các phím đơn giản? Hàm băm có ít khóa có thể được đóng gói khéo léo vào cấu trúc giống như mảng tuyến tính này (tức là danh sách zip) trong khi vẫn đảm bảo hiệu suất O (1) được phân bổ cho get và set. Rõ ràng là điều này không thể theo kịp khi các trường băm tăng lên. Khi hàm băm phát triển, nó được chuyển đổi thành cấu trúc từ điển tiêu chuẩn để duy trì hiệu suất O (1) và việc tiết kiệm dung lượng sẽ bị mất. Các thông số cấu hình Redis kiểm soát quá trình chuyển đổi này là:

• list-max-ziplist-entry default (512):Thay đổi thành biểu diễn tiêu chuẩn nếu hàm băm lớn hơn giới hạn này.

• list-max-ziplist-value default (64):Thay đổi thành biểu diễn chuẩn nếu phần tử lớn nhất trong hàm băm trở nên lớn hơn giới hạn này.

Bạn có thể hiểu thêm chi tiết từ mã và nhận xét trong quá trình triển khai tại đây. Tiết kiệm bộ nhớ từ việc sử dụng tối ưu hóa đặc biệt này là đáng kể. Chúng ta sẽ nói chi tiết hơn trong phần tiếp theo.

Tối ưu hóa bộ nhớ

Một trong những khuyến nghị nổi tiếng để tiết kiệm bộ nhớ khi sử dụng Redis là sử dụng hàm băm thay vì chuỗi đơn giản. Đây là một trường hợp sử dụng quan trọng để sử dụng sức mạnh của hàm băm Redis trong các ứng dụng thế giới thực. Từ tài liệu chính thức của Redis về tối ưu hóa bộ nhớ:

Sử dụng hàm băm khi có thể

Các hàm băm nhỏ được mã hóa trong một không gian rất nhỏ, vì vậy bạn nên thử biểu diễn dữ liệu của mình bằng cách sử dụng hàm băm bất cứ khi nào có thể. Ví dụ:nếu bạn có các đối tượng đại diện cho người dùng trong một ứng dụng web, thay vì sử dụng các khóa khác nhau cho tên, họ, email, mật khẩu, hãy sử dụng một hàm băm duy nhất với tất cả các trường bắt buộc.

Bài đăng đó sau đó tiếp tục đề xuất một cách để ánh xạ một loạt các đối tượng thành một tập hợp các hàm băm để tận dụng việc tiết kiệm bộ nhớ. Instagram, trong một bài đăng trên blog rất phổ biến, mô tả việc sử dụng một kỹ thuật tương tự đã giúp họ đạt được các đơn hàng tiết kiệm tiềm năng lớn. Một blog khác cố gắng đo lường lợi ích của việc tối ưu hóa là blog này.

Ứng dụng

• Redis Hashes đương nhiên phù hợp để lưu trữ các đối tượng:phiên, người dùng, khách truy cập, v.v. Điều này khiến nó trở thành một trong những cấu trúc dữ liệu quan trọng do Redis cung cấp.
• Ở dạng tối ưu hóa bộ nhớ, đây là một lựa chọn tuyệt vời để lưu vào bộ nhớ đệm một lượng lớn dữ liệu.

Lưu trữ địa chỉ đối tượng

Vì tối ưu hóa bộ nhớ là một trường hợp sử dụng quan trọng đối với hàm băm, hãy thảo luận về một ví dụ tương tự như việc triển khai Instagram để chỉ ra cách sử dụng các tính năng tiết kiệm bộ nhớ của hàm băm Redis. Giả sử, chúng tôi triển khai bộ nhớ theo địa chỉ theo nội dung (CAS) khổng lồ với hàng trăm triệu đối tượng được lưu trữ. Vị trí của mỗi đối tượng là một chuỗi băm. Chúng tôi dự định phát triển một hệ thống tra cứu để tìm ra vị trí của đối tượng với ID của nó. Cách điển hình để thực hiện việc này trong Redis là sử dụng chuỗi.

set object:14590860 "007f80f0a62408..."
set object:11678 "009f80abcd0a60..."
...


Cách tiếp cận này hoạt động tốt. Tuy nhiên, vì số lượng đối tượng mà chúng ta có là rất lớn, chúng ta sẽ cần rất nhiều bộ nhớ cho Redis. Chúng tôi muốn làm tốt hơn. Hãy thực hiện phương pháp băm tối ưu hóa bộ nhớ cho vấn đề này. Chúng tôi sẽ phải chọn các giá trị phù hợp cho list-max-ziplist-entry và list-max-ziplist-value . Giá trị chính xác cho list-max-ziplist-value là bất kỳ độ dài tối đa nào của chuỗi băm địa chỉ lưu trữ có thể là. Giá trị của list-max-ziplist-entry phải được giữ ở mức đủ thấp và sẽ phụ thuộc vào số lượng tổng số nhóm băm mà chúng tôi muốn tạo. Nó sẽ được hình dung tốt nhất theo kinh nghiệm. Ví dụ đối với 100 triệu đối tượng, chúng tôi có thể chọn sử dụng 100k băm. Các mục nhập tối đa trong trường hợp đó sẽ là 100m / 100k =1000. Logic của ứng dụng để quyết định băm địa chỉ lưu trữ của đối tượng có thể là:chia ID đối tượng cho 100k và loại bỏ phần còn lại. Do đó, ID đối tượng 14590860 sẽ chuyển thành băm (14590860 / 100k) =145, tức là


hset object:145 14590860 "007f80f0a62408..."
hget object:145 14590860
> "007f80f0a62408..."


Việc triển khai này sẽ không chỉ nhẹ hơn nhiều về bộ nhớ mà còn phải cung cấp vị trí bộ nhớ cache tốt.

Đây là các bài đăng khác của chúng tôi trong chuỗi cấu trúc dữ liệu Redis.

• Redis tập hợp
• Redis bitmaps
• Đã sắp xếp lại các tập hợp đã được sắp xếp