Prohoster > Blog > quản lý > Khóa phân tán bằng Redis

Khóa phân tán bằng Redis

Này Habr!

Hôm nay chúng tôi mang đến cho bạn bản dịch của một bài viết phức tạp về việc triển khai khóa phân tán bằng Redis và mời bạn nói về triển vọng của Redis như một chủ đề. Phân tích thuật toán Redlock được đề cập từ Martin Kleppmann, tác giả cuốn sách "Ứng dụng tải cao", được cho đây.

Khóa phân tán là một nguyên thủy rất hữu ích được sử dụng trong nhiều môi trường trong đó các quy trình khác nhau phải hoạt động trên các tài nguyên được chia sẻ theo cách loại trừ lẫn nhau.

Có một số thư viện và bài đăng mô tả cách triển khai DLM (Trình quản lý khóa phân tán) bằng Redis, nhưng mỗi thư viện có một cách tiếp cận khác nhau và những đảm bảo mà chúng cung cấp khá yếu so với những gì có thể đạt được với thiết kế phức tạp hơn một chút.

Trong bài viết này, chúng tôi sẽ cố gắng mô tả một thuật toán chuẩn có điều kiện trình bày cách triển khai khóa phân tán bằng Redis. Chúng ta sẽ nói về một thuật toán được gọi là Khóa đỏ, nó triển khai một trình quản lý khóa phân tán và theo quan điểm của chúng tôi, thuật toán này an toàn hơn so với cách tiếp cận một phiên bản thông thường. Chúng tôi hy vọng cộng đồng sẽ phân tích nó, cung cấp phản hồi và sử dụng nó làm điểm khởi đầu cho các dự án phức tạp hơn hoặc thay thế.

Thực hiện

Trước khi chuyển sang mô tả thuật toán, chúng tôi cung cấp một số liên kết đến các triển khai được tạo sẵn. Chúng có thể được sử dụng để tham khảo.

Đảm bảo an ninh và sẵn có

Chúng tôi sẽ lập mô hình thiết kế của mình chỉ với ba thuộc tính mà chúng tôi cho rằng cung cấp những đảm bảo tối thiểu cần thiết để sử dụng khóa phân tán một cách hiệu quả.

  1. Thuộc tính bảo mật: Loại trừ lẫn nhau. Tại bất kỳ thời điểm nào, chỉ có một khách hàng có thể giữ khóa.
  2. Thuộc tính sẵn có A: Không có bế tắc. Cuối cùng luôn có thể lấy được khóa, ngay cả khi máy khách đã khóa tài nguyên không thành công hoặc nằm trên một phân đoạn đĩa khác.
  3. Thuộc tính sẵn có B: Khả năng chịu lỗi. Miễn là phần lớn các nút Redis đang chạy, khách hàng có thể lấy và giải phóng các khóa.

Tại sao việc triển khai dựa trên việc khôi phục lỗi là không đủ trong trường hợp này
Để hiểu những gì chúng tôi sẽ cải thiện, hãy phân tích tình trạng hiện tại với hầu hết các thư viện khóa phân tán dựa trên Redis.

Cách đơn giản nhất để khóa tài nguyên bằng Redis là tạo khóa trong phiên bản. Thông thường, một khóa được tạo với thời gian tồn tại giới hạn, điều này đạt được bằng cách sử dụng tính năng hết hạn được cung cấp trong Redis, do đó sớm hay muộn khóa này sẽ được phát hành (thuộc tính 2 trong danh sách của chúng tôi). Khi khách hàng cần giải phóng tài nguyên, nó sẽ xóa khóa.

Thoạt nhìn, giải pháp này hoạt động khá tốt nhưng có một vấn đề: kiến ​​trúc của chúng tôi tạo ra một điểm lỗi duy nhất. Điều gì xảy ra nếu phiên bản Redis của máy chủ bị lỗi? Hãy thêm một nô lệ sau đó! Và chúng tôi sẽ sử dụng nó nếu người trình bày không có mặt. Thật không may, tùy chọn này không khả thi. Bằng cách này, chúng tôi sẽ không thể triển khai đúng thuộc tính loại trừ lẫn nhau mà chúng tôi cần để đảm bảo an ninh, vì tính năng sao chép trong Redis là không đồng bộ.

Rõ ràng, trong mô hình như vậy, điều kiện chủng tộc sẽ xảy ra:

  1. Khách hàng A có được một khóa trên máy chủ.
  2. Máy chủ bị lỗi trước khi mục nhập khóa được chuyển sang máy phụ.
  3. Người theo sau được thăng chức lên lãnh đạo.
  4. Khách hàng B có được khóa trên cùng một tài nguyên mà A đã khóa. VI PHẠM AN NINH!

Đôi khi điều hoàn toàn bình thường là trong những trường hợp đặc biệt, chẳng hạn như lỗi, nhiều khách hàng có thể giữ khóa cùng một lúc. Trong những trường hợp như vậy, giải pháp dựa trên bản sao có thể được áp dụng. Nếu không, chúng tôi đề xuất giải pháp được mô tả trong bài viết này.

Thực hiện đúng với một trường hợp duy nhất

Trước khi cố gắng khắc phục những thiếu sót của cấu hình một phiên bản được mô tả ở trên, hãy tìm hiểu cách xử lý đúng trường hợp đơn giản này, vì giải pháp này thực sự hợp lệ trong các ứng dụng mà điều kiện dồn đuổi đôi khi được chấp nhận và cũng vì việc chặn trên trường hợp duy nhất đóng vai trò là cơ sở được sử dụng trong thuật toán phân tán được mô tả ở đây.

Để có được một khóa, hãy làm điều này:

SET resource_name my_random_value NX PX 30000

Lệnh này chỉ cài đặt khóa nếu nó chưa tồn tại (tùy chọn NX), với thời gian hiệu lực là 30000 mili giây (tùy chọn PX). Khóa được đặt thành “myrandomvalue" Giá trị này phải là duy nhất trên tất cả các máy khách và tất cả các yêu cầu khóa.
Về cơ bản, một giá trị ngẫu nhiên được sử dụng để mở khóa một cách an toàn, với đoạn mã thông báo cho Redis: chỉ xóa khóa nếu nó tồn tại và giá trị được lưu trong đó chính xác như mong đợi. Điều này đạt được bằng cách sử dụng tập lệnh Lua sau:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Điều này rất quan trọng để ngăn chặn việc khóa do khách hàng khác nắm giữ bị xóa. Ví dụ: một máy khách có thể có được một khóa, sau đó bị khóa trong một số thao tác kéo dài hơn khóa đầu tiên (để khóa có thời gian hết hạn) và sau đó xóa khóa mà một số máy khách khác đã đặt.
Việc sử dụng DEL đơn giản là không an toàn vì máy khách có thể xóa khóa do máy khách khác nắm giữ. Ngược lại, khi sử dụng đoạn script trên, mỗi khóa được “ký” bằng một chuỗi ngẫu nhiên, do đó chỉ khách hàng đã đặt nó trước đó mới có thể xóa nó.

Chuỗi ngẫu nhiên này nên là gì? Tôi đoán nó phải là 20 byte từ/dev/urandom, nhưng bạn có thể tìm ra những cách ít tốn kém hơn để làm cho chuỗi đủ độc đáo cho mục đích của mình. Ví dụ: sẽ ổn nếu gieo RC4 bằng /dev/urandom và sau đó tạo luồng giả ngẫu nhiên từ nó. Một giải pháp đơn giản hơn bao gồm sự kết hợp thời gian unix ở độ phân giải micro giây cộng với ID khách hàng; nó không an toàn bằng, nhưng nó có thể đáp ứng được nhiệm vụ trong hầu hết các bối cảnh.

Thời gian chúng tôi sử dụng làm thước đo tuổi thọ của khóa được gọi là "thời gian tồn tại của khóa". Giá trị này vừa là khoảng thời gian trước khi khóa được tự động giải phóng vừa là khoảng thời gian một máy khách phải hoàn thành một thao tác trước khi một máy khách khác có thể lần lượt khóa tài nguyên đó mà không thực sự vi phạm các đảm bảo loại trừ lẫn nhau. Bảo đảm này chỉ được giới hạn trong một khoảng thời gian nhất định, bắt đầu từ thời điểm khóa được mua.

Vì vậy, chúng tôi đã thảo luận về một cách tốt để lấy và mở khóa. Hệ thống (nếu chúng ta đang nói về một hệ thống không phân tán bao gồm một phiên bản duy nhất và luôn có sẵn) là an toàn. Hãy mở rộng khái niệm này sang hệ thống phân tán, nơi chúng ta không có sự đảm bảo nào như vậy.

Thuật toán khóa đỏ

Phiên bản phân tán của thuật toán giả định rằng chúng ta có N Redis master. Các nút này hoàn toàn độc lập với nhau nên chúng tôi không sử dụng tính năng sao chép hoặc bất kỳ hệ thống phối hợp ngầm nào khác. Chúng tôi đã đề cập đến cách lấy và giải phóng khóa một cách an toàn trên một phiên bản. Chúng tôi chấp nhận rằng thuật toán khi làm việc với một phiên bản duy nhất sẽ sử dụng chính xác phương pháp này. Trong ví dụ của chúng tôi, chúng tôi đặt N thành 5, đây là một giá trị hợp lý. Vì vậy, chúng ta sẽ cần sử dụng 5 Redis master trên các máy tính hoặc máy ảo khác nhau để đảm bảo rằng chúng hoạt động độc lập với nhau.

Để có được khóa, khách hàng thực hiện các thao tác sau:

  1. Nhận thời gian hiện tại tính bằng mili giây.
  2. Tuần tự cố gắng lấy khóa trên tất cả N phiên bản, sử dụng cùng tên khóa và giá trị ngẫu nhiên trong mọi trường hợp. Trong Giai đoạn 2, khi máy khách thiết lập khóa trên cơ sở từng phiên bản, máy khách sẽ sử dụng độ trễ để thu được khóa đủ ngắn so với thời gian sau đó khóa được tự động mở. Ví dụ: nếu thời lượng chặn là 10 giây thì độ trễ có thể nằm trong khoảng ~5-50 mili giây. Điều này giúp loại bỏ tình huống máy khách có thể bị chặn trong thời gian dài khi cố gắng truy cập nút Redis bị lỗi: nếu phiên bản không khả dụng thì chúng tôi sẽ cố gắng kết nối với một phiên bản khác càng sớm càng tốt.
  3. Để lấy khóa, khách hàng tính toán lượng thời gian đã trôi qua; Để thực hiện việc này, nó sẽ trừ đi giá trị thời gian thực tế dấu thời gian thu được ở bước 1. Khi và chỉ khi khách hàng có thể lấy được khóa trên phần lớn các phiên bản (ít nhất là 3) và tổng thời gian cần thiết để thực hiện việc này. lấy được khóa, ít hơn thời hạn khóa thì coi như đã lấy được khóa.
  4. Nếu khóa đã được lấy, thời lượng khóa được lấy bằng thời lượng khóa ban đầu trừ đi thời gian đã trôi qua được tính ở bước 3.
  5. Nếu máy khách không lấy được khóa vì lý do nào đó (hoặc nó không thể khóa N/2+1 phiên bản hoặc thời lượng khóa là âm), thì nó sẽ cố gắng mở khóa tất cả các phiên bản (ngay cả những phiên bản mà nó nghĩ rằng nó không thể chặn ).

Thuật toán có đồng bộ không?

Thuật toán này dựa trên giả định rằng, mặc dù không có đồng hồ đồng bộ để tất cả các quy trình hoạt động, thời gian cục bộ trong mỗi quy trình vẫn chảy với tốc độ xấp xỉ như nhau và sai số là nhỏ so với tổng thời gian sau đó khóa được thực hiện. tự động được giải phóng. Giả định này rất giống với tình huống điển hình của các máy tính thông thường: mỗi máy tính có một đồng hồ cục bộ và chúng ta thường có thể tin tưởng vào thực tế là chênh lệch thời gian giữa các máy tính khác nhau là nhỏ.

Tại thời điểm này, chúng ta phải xây dựng quy tắc loại trừ lẫn nhau một cách cẩn thận hơn: loại trừ lẫn nhau chỉ được đảm bảo nếu khách hàng giữ khóa thoát ra trong thời gian khóa hợp lệ (giá trị này có được ở bước 3), trừ đi một ít thời gian (tổng cộng một vài mili giây để bù đắp cho sự chênh lệch thời gian giữa các tiến trình).

Bài viết thú vị sau đây cho biết thêm về các hệ thống đòi hỏi sự phối hợp giữa các khoảng thời gian: Hợp đồng thuê: một cơ chế chịu lỗi hiệu quả để đảm bảo tính nhất quán của bộ đệm tệp được phân phối.

Thử lại khi thất bại

Khi máy khách không lấy được khóa, nó phải thử lại sau một khoảng thời gian trễ ngẫu nhiên; điều này được thực hiện để hủy đồng bộ hóa nhiều máy khách đang cố gắng lấy khóa trên cùng một tài nguyên cùng một lúc (điều này có thể dẫn đến tình huống "phân chia não" trong đó không có người chiến thắng). Ngoài ra, khách hàng cố gắng lấy khóa trên phần lớn các phiên bản Redis càng nhanh thì khoảng thời gian có thể xảy ra tình huống phân chia não càng thu hẹp (và nhu cầu thử lại càng ít). Do đó, lý tưởng nhất là máy khách nên cố gắng gửi đồng thời các lệnh SET đến N phiên bản bằng cách ghép kênh.

Cần nhấn mạnh ở đây tầm quan trọng của việc các khách hàng không có được phần lớn các khóa có thể giải phóng các khóa có được (một phần), để họ không phải đợi khóa hết hạn trước khi có thể lấy lại khóa trên tài nguyên. (mặc dù nếu xảy ra phân mảnh mạng và khách hàng mất liên lạc với các phiên bản Redis thì bạn phải trả tiền phạt về tính khả dụng trong khi chờ khóa hết hạn).

Mở khóa

Giải phóng khóa là một thao tác đơn giản chỉ yêu cầu mở khóa tất cả các phiên bản, bất kể máy khách có vẻ như đã khóa thành công một phiên bản cụ thể hay không.

Cân nhắc về Bảo mật

Thuật toán có an toàn không? Chúng ta hãy thử tưởng tượng điều gì sẽ xảy ra trong các tình huống khác nhau.

Để bắt đầu, hãy giả sử rằng máy khách có thể lấy được khóa trong phần lớn các trường hợp. Mỗi phiên bản sẽ chứa một khóa có cùng thời gian tồn tại cho tất cả. Tuy nhiên, mỗi khóa này được cài đặt vào một thời điểm khác nhau nên chúng sẽ hết hạn vào những thời điểm khác nhau. Tuy nhiên, nếu khóa đầu tiên được cài đặt vào thời điểm không tệ hơn T1 (thời điểm chúng tôi chọn trước khi liên hệ với máy chủ đầu tiên) và khóa cuối cùng được cài đặt vào thời điểm không tệ hơn T2 (thời điểm nhận được phản hồi từ máy chủ cuối cùng), thì chúng tôi tin tưởng rằng khóa đầu tiên trong bộ hết hạn sẽ tồn tại ít nhất MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Tất cả các khóa khác sẽ hết hạn sau đó, vì vậy chúng tôi có thể chắc chắn rằng tất cả các khóa sẽ có hiệu lực đồng thời trong ít nhất thời gian này.

Trong thời gian mà hầu hết các khóa vẫn hợp lệ, một máy khách khác sẽ không thể lấy được khóa, vì các thao tác N/2+1 SET NX không thể thành công nếu khóa N/2+1 đã tồn tại. Do đó, một khi khóa đã được lấy thì không thể lấy lại khóa đó cùng lúc (điều này sẽ vi phạm thuộc tính loại trừ lẫn nhau).
Tuy nhiên, chúng tôi muốn đảm bảo rằng nhiều khách hàng đang cố gắng lấy khóa cùng một lúc không thể thành công cùng một lúc.

Nếu máy khách đã khóa phần lớn các phiên bản trong khoảng thời gian khóa tối đa hoặc nhiều hơn, nó sẽ coi khóa đó là không hợp lệ và mở khóa các phiên bản đó. Do đó, chúng tôi chỉ phải tính đến trường hợp khách hàng có thể chặn phần lớn các trường hợp trong thời gian ngắn hơn ngày hết hạn. Trong trường hợp này, liên quan đến lập luận trên, trong thời gian MIN_VALIDITY không có khách hàng nào có thể lấy lại được khóa. Do đó, nhiều khách hàng sẽ chỉ có thể khóa N/2+1 phiên bản trong cùng một thời điểm (kết thúc ở cuối giai đoạn 2) khi thời gian khóa phần lớn lớn hơn thời gian TTL, khiến khóa không hợp lệ.

Bạn có thể cung cấp bằng chứng chính thức về bảo mật, chỉ ra các thuật toán tương tự hiện có hoặc tìm ra lỗi ở trên không?

Cân nhắc về khả năng tiếp cận

Tính khả dụng của hệ thống phụ thuộc vào ba đặc điểm chính:

  1. Tự động mở khóa (khi khóa hết hạn): Chìa khóa cuối cùng sẽ có sẵn trở lại để sử dụng cho khóa.
  2. Thực tế là các khách hàng thường giúp đỡ lẫn nhau bằng cách tháo khóa khi chưa có được khóa mong muốn hoặc đã có được và công việc đã hoàn thành; nên rất có thể chúng ta sẽ không phải đợi chìa khóa hết hạn mới lấy lại được khóa.
  3. Thực tế là khi khách hàng cần thử lại để lấy khóa, nó sẽ đợi một khoảng thời gian tương đối dài hơn khoảng thời gian cần thiết để lấy hầu hết các khóa. Điều này làm giảm khả năng xảy ra tình trạng chia não phát sinh khi tranh giành tài nguyên.

Tuy nhiên, có một mức phạt về tính khả dụng tương đương với TTL của các phân đoạn mạng, vì vậy nếu có các phân đoạn liền kề thì mức phạt có thể là vô thời hạn. Điều này xảy ra bất cứ khi nào máy khách có được một khóa và sau đó chuyển sang phân đoạn khác trước khi có thể mở khóa.

Về nguyên tắc, với các phân đoạn mạng liền kề vô hạn, hệ thống có thể không khả dụng trong một khoảng thời gian vô hạn.

Hiệu suất, chuyển đổi dự phòng và fsync

Nhiều người sử dụng Redis vì họ cần hiệu suất máy chủ khóa cao xét về độ trễ cần thiết để lấy và giải phóng các khóa cũng như số lượng chuyển đổi/phát hành có thể được hoàn thành mỗi giây. Để đáp ứng yêu cầu này, có một chiến lược giao tiếp với máy chủ N Redis để giảm độ trễ. Đây là một chiến lược ghép kênh (hoặc "ghép kênh của người nghèo", trong đó ổ cắm được đặt ở chế độ không chặn, gửi tất cả các lệnh và đọc các lệnh sau, giả sử rằng thời gian khứ hồi giữa máy khách và mỗi phiên bản là tương tự nhau) .

Tuy nhiên, chúng tôi cũng phải tính đến việc cân nhắc liên quan đến việc lưu trữ dữ liệu lâu dài nếu chúng tôi cố gắng tạo ra một mô hình có khả năng phục hồi đáng tin cậy sau các lỗi.

Về cơ bản, để làm rõ vấn đề, hãy giả sử rằng chúng ta định cấu hình Redis không có bộ lưu trữ dữ liệu dài hạn nào cả. Khách hàng quản lý để chặn 3 trong số 5 trường hợp. Một trong những phiên bản mà máy khách quản lý chặn đã được khởi động lại và tại thời điểm này, lại có 3 phiên bản cho cùng một tài nguyên mà chúng tôi có thể chặn và đến lượt một máy khách khác có thể chặn phiên bản được khởi động lại, vi phạm thuộc tính bảo mật mà giả định tính độc quyền của ổ khóa.

Nếu bạn bật dữ liệu trước (AOF), tình hình sẽ được cải thiện đôi chút. Ví dụ: bạn có thể quảng bá máy chủ bằng cách gửi lệnh SHUTDOWN và khởi động lại nó. Vì các hoạt động hết hạn trong Redis được triển khai theo ngữ nghĩa theo cách mà thời gian vẫn tiếp tục trôi ngay cả khi máy chủ bị tắt nên tất cả các yêu cầu của chúng tôi đều ổn. Điều này là bình thường miễn là đảm bảo tắt máy bình thường. Phải làm gì khi mất điện? Nếu Redis được cấu hình theo mặc định, với fsync đồng bộ hóa trên đĩa mỗi giây, thì có thể sau khi khởi động lại, chúng ta sẽ không có khóa của mình. Về mặt lý thuyết, nếu chúng ta muốn đảm bảo tính bảo mật của khóa trong bất kỳ lần khởi động lại phiên bản nào, chúng ta nên kích hoạt fsync=always trong cài đặt để lưu trữ dữ liệu lâu dài. Điều này sẽ làm mất hiệu suất hoàn toàn, thậm chí đến mức hệ thống CP thường được sử dụng để triển khai các khóa phân tán một cách an toàn.

Nhưng tình hình tốt hơn so với cái nhìn đầu tiên. Về nguyên tắc, tính bảo mật của thuật toán được duy trì vì khi phiên bản được khởi động lại sau một lỗi, nó sẽ không còn tham gia vào bất kỳ khóa nào hiện đang hoạt động.

Để đảm bảo điều này, chúng tôi chỉ cần đảm bảo rằng sau khi xảy ra lỗi, phiên bản vẫn không khả dụng trong một khoảng thời gian vượt quá mức TTL tối đa một chút mà chúng tôi sử dụng. Bằng cách này, chúng tôi sẽ đợi cho đến ngày hết hạn và tự động giải phóng tất cả các khóa đang hoạt động tại thời điểm xảy ra lỗi.

Sử dụng khởi động lại bị trì hoãn, về nguyên tắc có thể đạt được bảo mật ngay cả khi không có bất kỳ sự tồn tại lâu dài nào trong Redis. Tuy nhiên, hãy lưu ý rằng điều này có thể dẫn đến bị phạt vì vi phạm khả năng tiếp cận. Ví dụ: nếu phần lớn các phiên bản không thành công, hệ thống sẽ không còn khả dụng đối với TTL trên toàn cầu (và không có tài nguyên nào có thể bị chặn trong thời gian này).

Chúng tôi tăng tính khả dụng của thuật toán: chúng tôi mở rộng tính năng chặn

Nếu công việc do khách hàng thực hiện bao gồm các bước nhỏ, có thể giảm thời lượng khóa mặc định và triển khai cơ chế mở rộng khóa. Về nguyên tắc, nếu máy khách đang bận tính toán và giá trị hết hạn khóa thấp đến mức nguy hiểm, bạn có thể gửi tập lệnh Lua tới tất cả các phiên bản mở rộng TTL của khóa nếu khóa vẫn tồn tại và giá trị của nó vẫn là giá trị ngẫu nhiên thu được khi khóa khóa đã được mua lại.

Khách hàng chỉ nên cân nhắc việc lấy lại khóa nếu nó đã khóa được phần lớn các phiên bản trong thời hạn hiệu lực.

Đúng, về mặt kỹ thuật, thuật toán không thay đổi, do đó, số lần thử lặp lại tối đa để lấy khóa phải được giới hạn, nếu không các thuộc tính khả năng truy cập sẽ bị vi phạm.

Nguồn: www.habr.com

Thêm một lời nhận xét