Hệ thống phân tán: Bầu cử lãnh đạo

Question

Hiện tại, tôi đang làm việc trên một hệ thống phân phối nơi chúng tôi phải triển khai một số loại Leader Election. Vấn đề là chúng tôi muốn tránh tất cả các máy tính phải biết lẫn nhau - nhưng chỉ là người lãnh đạo. Có cách nào nhanh chóng để chúng ta có thể sử dụng Broadcast để đạt được những gì chúng ta muốn không?

Hoặc chúng ta chỉ cần biết ít nhất một, để thực hiện một cuộc bầu cử lãnh đạo tốt?

Có thể giả định rằng tất cả các máy tính đều ở cùng một mạng con.

Cảm ơn sự giúp đỡ của bạn.

Answer 1

Là một trong những giải pháp 'cơ học phân tán' thú vị mà tôi đã thấy lần trước, tôi muốn giới thiệu dự án Apache zookeeper. Đây là giải pháp nguồn mở nên ít nhất bạn sẽ có thể nhận được vài ý tưởng từ đó. Ngoài ra nó được phát triển mạnh mẽ vì vậy có lẽ bạn có thể tái sử dụng nó chỉ là một phần của giải pháp của bạn.

Zookeeper là một dịch vụ tập trung cho việc duy trì cấu hình thông tin, đặt tên, cho phép đồng bộ phân phối và cung cấp dịch vụ nhóm. Tất cả các loại dịch vụ này được sử dụng trong một số hình thức này hoặc cách khác bởi các ứng dụng được phân phối. Mỗi khi chúng được triển khai, có rất nhiều công việc đi vào sửa lỗi và các điều kiện chủng tộc là không thể tránh khỏi. Do khó khăn khi thực hiện các loại dịch vụ này, các ứng dụng ban đầu thường là tiết kiệm năng lượng, khiến chúng trở nên dễ vỡ khi có sự thay đổi và khó quản lý. Ngay cả khi được thực hiện chính xác, việc triển khai khác nhau của các dịch vụ này dẫn đến sự phức tạp về quản lý khi các ứng dụng được triển khai.

Answer 2

Tôi khuyên bạn nên JGroups giải quyết vấn đề này - giả sử bạn đang xây dựng một hệ thống trên JVM.

Sử dụng LockService để đảm bảo rằng chỉ có 1 nút trong cluster là người lãnh đạo. JGroups có thể được thiết lập để sử dụng Khóa ngang hàng hoặc Khóa trung tâm - hoặc sẽ hoạt động trong trường hợp của bạn.

Xem http://withmeta.blogspot.com/2014/01/leader-election-problem-in-elastic.html để thực hiện Clojure hoặc http://javabender.blogspot.com.au/2012/01/jgroups-lockservice-example.html cho cài đặt Java.

Answer 3

Vấn đề là chúng tôi muốn tránh tất cả các máy tính phải biết lẫn nhau - nhưng chỉ là người lãnh đạo.

Cuộc bầu cử lãnh đạo là vấn đề chọn một nhà lãnh đạo duy nhất trong số các ứng cử viên lãnh đạo tiềm năng. Xem xét nó khi có hai thuộc tính bắt buộc: liveness và an toàn. Ở đây, liveness có nghĩa là "hầu hết thời gian, có một nhà lãnh đạo", trong khi an toàn có nghĩa là "có hoặc là không hoặc một nhà lãnh đạo". Hãy xem xét cách chúng tôi sẽ giải quyết tài sản an toàn này trong ví dụ của bạn, bằng cách sử dụng chương trình phát sóng.

Hãy chọn một thuật toán đơn giản (bị hỏng), giả sử mỗi nút có một ID duy nhất. Mỗi nút phát sóng ID của nó và lắng nghe. Khi nhận được một ID cao hơn của riêng nó, nó ngừng tham gia.Nếu nó nhận được một ID thấp hơn của riêng nó, nó sẽ gửi chương trình phát sóng riêng của mình một lần nữa. Giả sử một mạng đồng bộ, ID cuối cùng mà mọi người nhận được là ID của người dẫn đầu. Bây giờ, giới thiệu một phân vùng mạng. Giao thức sẽ vui vẻ tiếp tục ở hai bên của phân vùng, và hai nhà lãnh đạo sẽ được bầu.

Đó là sự thật của giao thức bị hỏng này, nhưng nó cũng đúng với tất cả các giao thức có thể. Làm thế nào để bạn biết sự khác biệt giữa các nút bạn không thể giao tiếp với và các nút không tồn tại nếu bạn không biết (ít nhất) có bao nhiêu nút tồn tại? Vì vậy, có kết quả an toàn đầu tiên an toàn: bạn cần phải biết có bao nhiêu nút tồn tại hoặc bạn không thể đảm bảo chỉ có một nhà lãnh đạo.

Bây giờ, hãy thư giãn an toàn an toàn của chúng tôi ràng buộc là một xác suất: "có thể có không hoặc nhiều nhà lãnh đạo, nhưng hầu hết thời gian có một". Điều đó làm cho vấn đề có thể xử lý được, và một giải pháp được sử dụng rộng rãi là tin đồn (giao thức dịch bệnh). Ví dụ: xem A Gossip-Style Failure Detection Service thảo luận về một biến thể của vấn đề chính xác này. Bài báo chủ yếu liên quan đến việc phát hiện và liệt kê thất bại chính xác theo xác suất, nhưng nếu bạn có thể làm điều đó bạn cũng có thể thực hiện cuộc bầu cử lãnh đạo đúng theo xác suất.

Theo như tôi có thể nói, bạn không thể có cuộc bầu cử lãnh đạo không có xác suất an toàn trong các mạng chung mà không cần ít nhất liệt kê những người tham gia.

Answer 4

Giải pháp thực tế là sử dụng DB làm điểm "cuộc họp".

Giải pháp này là rất tiện dụng đặc biệt nếu bạn đã sử dụng SQL DB, tất cả phải mất là một bảng mới. Nếu bạn đang sử dụng cụm DB, bạn có thể tận dụng tính sẵn sàng cao của nó.

Dưới đây là bảng thực hiện của tôi sử dụng:

CREATE TABLE Lease (
    ResourceId varchar(64), 
    Expiration datetime, 
    OwnerId varchar(64), 
    PRIMARY KEY(ResourceId) 
); 

Ý tưởng là để có một hàng cho mỗi tài nguyên chia sẻ. Các nhà lãnh đạo sẽ cạnh tranh cho cùng một hàng.

tôi qua đơn giản C# thực hiện trông thích này:

class SqlLease { 
    private ISqlLeaseDal _dal; 
    private string _resourceId; 
    private string _myId; 

    public SqlLease(ISqlLeaseDal dal, string resourceId) { 
    _dal = dal; 
    _resourceId = resourceId; 
    _myId = Guid.NewGuid().ToString(); 
    } 

    class LeaseRow { 
     public string ResourceId {get; set;} 
     public string OwnerId {get; set;} 
     public Datetime Expiration {get; set;} 
     public byte[] RowVersion {get; set;} 
    } 

    public bool TryAcquire(Datetime expiration) { 
    expiration = expiration.ToUniversalTime(); 
    if (expiration < DateTime.UtcNow) return false; 
    try { 
     var row = _dal.FindRow(_resourceId); 
     if (row != null) { 
     if (row.Expiration >= DateTime.UtcNow && row.OwnerId != _myId) { 
      return false; 
     } 
     row.OwnerId = _myId; 
     row.Expiration = expiration; 
     _dal.Update(row); 
     return true; 
     } 
     _dal.Insert(new LeaseRow { 
     ResourceId = _resourceId, 
     OwnerId = _myId, 
     Expiration = expiration, 
     }); 
     return true; 
    } catch (SqlException e) { 
     if (e.Number == 2601 || e.Number == 2627) return false; 
     throw e; 
    } catch (DBConcurrencyException) { 
     return false; 
    } 
    } 
} 

Các ISqlLeaseDal lớp đóng gói kết nối SQL và truy cập ở mức thấp để bàn.

Sử dụng thời hạn hợp lý. Hãy nhớ rằng trong trường hợp nhà lãnh đạo hiện tại không thành công, tài nguyên sẽ bị khóa cho đến khi hết hạn.