Vì vậy, hãy tưởng tượng. Có 5 con mèo bị nhốt trong phòng, và để đánh thức chủ nhân, tất cả chúng phải đồng ý với nhau về điều này, vì chúng chỉ có thể mở cửa khi có XNUMX con mèo dựa vào đó. Nếu một trong những con mèo là mèo của Schrödinger và những con mèo khác không biết về quyết định của anh ta thì câu hỏi sẽ đặt ra: “Làm sao chúng có thể làm được điều đó?”
Trong bài viết này, tôi sẽ nói với bạn một cách đơn giản về thành phần lý thuyết của thế giới hệ thống phân tán và nguyên tắc hoạt động của chúng. Tôi cũng sẽ xem xét sơ bộ ý tưởng chính của Paxos.
Khi các nhà phát triển sử dụng cơ sở hạ tầng đám mây, nhiều cơ sở dữ liệu khác nhau và làm việc theo cụm có số lượng lớn nút, họ tin tưởng rằng dữ liệu sẽ đầy đủ, an toàn và luôn có sẵn. Nhưng đâu là sự đảm bảo?
Về cơ bản, những đảm bảo mà chúng tôi có là những đảm bảo của nhà cung cấp. Chúng được mô tả trong tài liệu như sau: “Dịch vụ này khá đáng tin cậy, nó có SLA nhất định, đừng lo lắng, mọi thứ sẽ hoạt động phân tán như bạn mong đợi”.
Chúng ta có xu hướng tin vào những điều tốt đẹp nhất, bởi vì những người thông minh từ các công ty lớn đã đảm bảo với chúng ta rằng mọi thứ sẽ ổn. Chúng tôi không đặt câu hỏi: trên thực tế, tại sao điều này có thể hoạt động được? Có biện minh chính thức nào cho việc vận hành chính xác của các hệ thống như vậy không?
Gần đây tôi đã đi đến và rất được truyền cảm hứng bởi chủ đề này. Các bài giảng ở trường giống như những lớp học tính toán hơn là những thứ liên quan đến hệ thống máy tính. Nhưng đây chính xác là cách các thuật toán quan trọng nhất mà chúng ta sử dụng hàng ngày mà thậm chí không hề biết đã được chứng minh tại một thời điểm.
Hầu hết các hệ thống phân tán hiện đại đều sử dụng thuật toán đồng thuận Paxos và các sửa đổi khác nhau của nó. Điều thú vị nhất là tính hợp lệ và về nguyên tắc, khả năng tồn tại của thuật toán này có thể được chứng minh chỉ bằng bút và giấy. Trong thực tế, thuật toán được sử dụng trong các hệ thống lớn chạy trên một số lượng lớn các nút trên đám mây.
Một minh họa nhẹ nhàng cho nội dung sẽ được thảo luận tiếp theo: nhiệm vụ của hai vị tướngChúng ta hãy xem để khởi động .
Chúng ta có hai đội quân - đỏ và trắng. Quân trắng đóng tại thành phố bị bao vây. Quân đỏ do tướng A1 và A2 chỉ huy đóng quân ở hai bên thành phố. Nhiệm vụ của những người tóc đỏ là tấn công thành phố da trắng và giành chiến thắng. Tuy nhiên, quân đội của từng tướng đỏ nhỏ hơn quân trắng.
Điều kiện chiến thắng của quân đỏ: cả hai tướng phải tấn công cùng lúc để có lợi thế về quân số so với quân trắng. Để làm được điều này, tướng A1 và A2 cần phải thống nhất được với nhau. Nếu mọi người tấn công riêng lẻ, những người tóc đỏ sẽ thua.
Để đạt được thỏa thuận, tướng A1 và A2 có thể cử sứ giả cho nhau qua lãnh thổ của thành phố trắng. Người đưa tin có thể tiếp cận thành công một vị tướng đồng minh hoặc có thể bị kẻ thù chặn lại. Câu hỏi: giữa các tướng tóc đỏ có trình tự liên lạc như vậy (trình tự cử sứ giả từ A1 đến A2 và ngược lại từ A2 đến A1) đảm bảo nhất trí tấn công vào giờ X. Đây, đảm bảo có nghĩa là cả hai tướng sẽ có xác nhận rõ ràng rằng một đồng minh (tướng khác) chắc chắn sẽ tấn công vào thời điểm đã định X.
Giả sử A1 gửi tin nhắn đến A2 với tin nhắn: “Hôm nay chúng ta tấn công vào lúc nửa đêm!” Tướng A1 không thể tấn công nếu không có sự xác nhận của tướng A2. Nếu người đưa tin từ A1 đã đến thì tướng A2 sẽ gửi xác nhận bằng tin nhắn: “Ừ, hôm nay chúng ta hãy giết quân trắng”. Nhưng bây giờ Tướng A2 không biết sứ giả của mình đã đến hay chưa, cũng không có gì đảm bảo liệu cuộc tấn công có đồng thời hay không. Bây giờ Tướng A2 lại cần xác nhận.
Nếu chúng ta mô tả thêm về quá trình liên lạc của họ, thì rõ ràng là cho dù có bao nhiêu chu kỳ trao đổi tin nhắn thì cũng không có cách nào đảm bảo rằng cả hai vị tướng đều nhận được tin nhắn của họ (giả sử rằng một trong hai người đưa tin có thể bị chặn).
Bài toán hai vị tướng là một minh họa tuyệt vời về một hệ thống phân tán rất đơn giản trong đó có hai nút có giao tiếp không đáng tin cậy. Điều này có nghĩa là chúng tôi không đảm bảo 100% rằng chúng được đồng bộ hóa. Các vấn đề tương tự chỉ được thảo luận ở quy mô lớn hơn ở phần sau của bài viết.
Chúng tôi giới thiệu khái niệm về hệ thống phân tán
Hệ thống phân tán là một nhóm máy tính (sau đây chúng ta sẽ gọi chúng là các nút) có thể trao đổi tin nhắn. Mỗi nút riêng lẻ là một loại thực thể tự trị. Một nút có thể tự xử lý các tác vụ, nhưng để liên lạc với các nút khác, nó cần gửi và nhận tin nhắn.
Thông báo được triển khai chính xác như thế nào, giao thức nào được sử dụng - điều này không được chúng tôi quan tâm trong bối cảnh này. Điều quan trọng là các nút của hệ thống phân tán có thể trao đổi dữ liệu với nhau bằng cách gửi tin nhắn.
Bản thân định nghĩa này trông không phức tạp lắm, nhưng chúng ta phải tính đến việc hệ thống phân tán có một số thuộc tính quan trọng đối với chúng ta.
Thuộc tính của hệ thống phân tán
- Truy cập đồng thời – khả năng xảy ra các sự kiện đồng thời hoặc đồng thời trong hệ thống. Hơn nữa, chúng tôi sẽ coi các sự kiện xảy ra trên hai nút khác nhau có khả năng xảy ra đồng thời miễn là chúng tôi không có thứ tự xuất hiện rõ ràng của các sự kiện này. Nhưng, như một quy luật, chúng tôi không có nó.
- Không có đồng hồ toàn cầu. Chúng tôi không có thứ tự sự kiện rõ ràng do thiếu đồng hồ toàn cầu. Trong thế giới đời thường của con người, chúng ta đã quen với việc chúng ta hoàn toàn có đồng hồ và thời gian. Mọi thứ thay đổi khi nói đến hệ thống phân tán. Ngay cả những đồng hồ nguyên tử cực kỳ chính xác cũng có sự trôi dạt, và có thể có những tình huống mà chúng ta không thể biết được sự kiện nào trong hai sự kiện xảy ra trước. Vì vậy, chúng ta cũng không thể dựa vào thời gian.
- Lỗi độc lập của các nút hệ thống. Có một vấn đề khác: có thể xảy ra sự cố chỉ vì các nút của chúng tôi không tồn tại mãi mãi. Ổ cứng có thể bị lỗi, máy ảo trên đám mây có thể khởi động lại, mạng có thể nhấp nháy và tin nhắn sẽ bị mất. Hơn nữa, có thể có những tình huống các nút hoạt động nhưng đồng thời lại hoạt động chống lại hệ thống. Loại vấn đề cuối cùng thậm chí còn nhận được một tên riêng: vấn đề . Ví dụ phổ biến nhất về hệ thống phân tán gặp vấn đề này là Blockchain. Nhưng hôm nay chúng ta sẽ không xem xét loại vấn đề đặc biệt này. Chúng ta sẽ quan tâm đến các tình huống trong đó chỉ một hoặc nhiều nút có thể bị lỗi.
- Mô hình truyền thông (mô hình nhắn tin) giữa các nút. Chúng tôi đã thiết lập rằng các nút giao tiếp bằng cách trao đổi tin nhắn. Có hai mô hình nhắn tin nổi tiếng: đồng bộ và không đồng bộ.
Mô hình giao tiếp giữa các nút trong hệ thống phân tán
Mô hình đồng bộ – chúng tôi biết chắc chắn rằng có một khoảng thời gian hữu hạn đã biết trong đó một thông báo được đảm bảo sẽ đến được từ nút này sang nút khác. Nếu thời gian này đã trôi qua mà tin nhắn vẫn chưa đến, chúng ta có thể nói rằng nút đó đã bị lỗi. Trong mô hình này, chúng ta có thời gian chờ đợi có thể dự đoán được.
Mô hình không đồng bộ – trong các mô hình không đồng bộ, chúng tôi coi thời gian chờ là hữu hạn, nhưng không có khoảng thời gian nào như vậy mà sau đó chúng tôi có thể đảm bảo rằng nút đã thất bại. Những thứ kia. Thời gian chờ đợi một tin nhắn từ một nút có thể dài tùy ý. Đây là một định nghĩa quan trọng và chúng ta sẽ nói thêm về nó.
Khái niệm đồng thuận trong hệ thống phân tán
Trước khi chính thức xác định khái niệm đồng thuận, hãy xem xét một ví dụ về tình huống chúng ta cần nó, cụ thể là - Sao chép máy trạng thái.
Chúng tôi có một số nhật ký phân phối. Chúng tôi muốn nó nhất quán và chứa dữ liệu giống hệt nhau trên tất cả các nút của hệ thống phân tán. Khi một trong các nút biết một giá trị mới mà nó sẽ ghi vào nhật ký, nhiệm vụ của nó sẽ là cung cấp giá trị này cho tất cả các nút khác để nhật ký được cập nhật trên tất cả các nút và hệ thống chuyển sang trạng thái nhất quán mới. Trong trường hợp này, điều quan trọng là các nút phải đồng ý với nhau: tất cả các nút đều đồng ý rằng giá trị mới được đề xuất là chính xác, tất cả các nút chấp nhận giá trị này và chỉ trong trường hợp này mọi người mới có thể ghi giá trị mới vào nhật ký.
Nói cách khác: không có nút nào phản đối rằng nó có thông tin phù hợp hơn và giá trị được đề xuất là không chính xác. Thỏa thuận giữa các nút và thỏa thuận về một giá trị được chấp nhận chính xác duy nhất là sự đồng thuận trong hệ thống phân tán. Tiếp theo, chúng ta sẽ nói về các thuật toán cho phép đảm bảo hệ thống phân tán đạt được sự đồng thuận.
Chính thức hơn, chúng ta có thể định nghĩa thuật toán đồng thuận (hoặc đơn giản là thuật toán đồng thuận) là một chức năng nhất định chuyển hệ thống phân tán từ trạng thái A sang trạng thái B. Hơn nữa, trạng thái này được tất cả các nút chấp nhận và tất cả các nút đều có thể xác nhận nó. Hóa ra, nhiệm vụ này hoàn toàn không tầm thường như thoạt nhìn.
Thuộc tính của thuật toán đồng thuận
Thuật toán đồng thuận phải có ba thuộc tính để hệ thống tiếp tục tồn tại và có một số tiến bộ trong việc chuyển từ trạng thái này sang trạng thái khác:
- Hiệp định – tất cả các nút hoạt động chính xác phải có cùng một giá trị (trong các bài viết, thuộc tính này còn được gọi là thuộc tính an toàn). Tất cả các nút hiện đang hoạt động (không bị lỗi hoặc mất liên lạc với các nút khác) phải đi đến thỏa thuận và chấp nhận một số giá trị chung cuối cùng.
Điều quan trọng là phải hiểu ở đây rằng các nút trong hệ thống phân tán mà chúng ta đang xem xét đều muốn đồng ý. Nghĩa là, chúng ta đang nói về các hệ thống trong đó một cái gì đó có thể đơn giản bị lỗi (ví dụ: một số nút bị lỗi), nhưng trong hệ thống này chắc chắn không có nút nào cố tình hoạt động chống lại các nút khác (nhiệm vụ của các tướng Byzantine). Do tính chất này, hệ thống vẫn nhất quán.
- TÍNH TOÀN VẸN — nếu tất cả các nút hoạt động chính xác đều cung cấp cùng một giá trị v, có nghĩa là mọi nút hoạt động chính xác phải chấp nhận giá trị này v.
- Chấm dứt hợp đồng – tất cả các nút hoạt động chính xác cuối cùng sẽ đảm nhận một giá trị nhất định (thuộc tính sống động), cho phép thuật toán đạt được tiến bộ trong hệ thống. Mỗi nút vận hành chính xác riêng lẻ sớm hay muộn đều phải chấp nhận giá trị cuối cùng và xác nhận nó: “Đối với tôi, giá trị này là đúng, tôi đồng ý với toàn bộ hệ thống”.
Một ví dụ về cách hoạt động của thuật toán đồng thuận
Mặc dù các thuộc tính của thuật toán có thể không hoàn toàn rõ ràng. Do đó, chúng tôi sẽ minh họa bằng một ví dụ về những giai đoạn mà thuật toán đồng thuận đơn giản nhất sẽ trải qua trong một hệ thống có mô hình nhắn tin đồng bộ, trong đó tất cả các nút hoạt động như mong đợi, tin nhắn không bị mất và không có gì bị hỏng (điều này có thực sự xảy ra không?).
- Tất cả bắt đầu bằng một lời cầu hôn (Propose). Giả sử rằng một máy khách đã kết nối với một nút có tên là "Nút 1" và bắt đầu giao dịch, chuyển một giá trị mới cho nút - O. Từ giờ trở đi, chúng ta sẽ gọi là "Nút 1" phục vụ. Với tư cách là người đề xuất, “Node 1” bây giờ phải thông báo cho toàn bộ hệ thống rằng nó có dữ liệu mới và gửi tin nhắn đến tất cả các nút khác: “Nhìn này! Ý nghĩa “O” chợt đến với tôi và tôi muốn viết nó ra! Vui lòng xác nhận rằng bạn cũng sẽ ghi “O” vào nhật ký của mình.”
- Giai đoạn tiếp theo là bỏ phiếu cho giá trị đề xuất (Voting). Nó dùng để làm gì? Có thể xảy ra trường hợp các nút khác đã nhận được thông tin gần đây hơn và chúng có dữ liệu về cùng một giao dịch.
Khi nút “Nút 1” gửi đề xuất của mình, các nút khác sẽ kiểm tra nhật ký của họ để tìm dữ liệu về sự kiện này. Nếu không có mâu thuẫn, các nút sẽ thông báo: “Có, tôi không có dữ liệu nào khác cho sự kiện này. Giá trị “O” là thông tin mới nhất mà chúng tôi xứng đáng nhận được.”Trong mọi trường hợp khác, các nút có thể phản hồi với “Nút 1”: “Nghe này! Tôi có nhiều dữ liệu gần đây hơn về giao dịch này. Không phải 'O', mà là thứ gì đó hay hơn."
Ở giai đoạn bỏ phiếu, các nút đi đến quyết định: hoặc tất cả chúng đều chấp nhận cùng một giá trị hoặc một trong số chúng bỏ phiếu phản đối, cho biết rằng anh ta có nhiều dữ liệu gần đây hơn.
- Nếu vòng biểu quyết thành công và được mọi người tán thành thì hệ thống chuyển sang giai đoạn mới - Chấp nhận giá trị. “Nút 1” thu thập tất cả phản hồi từ các nút khác và báo cáo: “Mọi người đều đồng ý về giá trị “O”! Bây giờ tôi chính thức tuyên bố rằng “O” là ý nghĩa mới của chúng tôi, mọi người đều như vậy! Hãy ghi nó vào cuốn sổ nhỏ của bạn, đừng quên. Hãy ghi nó vào nhật ký của bạn!”
- Các nút còn lại gửi xác nhận (Được chấp nhận) rằng họ đã ghi lại giá trị “O”; không có gì mới đến trong thời gian này (một loại cam kết hai giai đoạn). Sau sự kiện quan trọng này, chúng tôi coi như giao dịch phân tán đã hoàn tất.
Như vậy, thuật toán đồng thuận trong trường hợp đơn giản gồm XNUMX bước: đề xuất, bỏ phiếu (vote), chấp nhận (chấp nhận), xác nhận chấp nhận (được chấp nhận).
Nếu ở một bước nào đó chúng tôi không thể đạt được thỏa thuận thì thuật toán sẽ bắt đầu lại, có tính đến thông tin được cung cấp bởi các nút đã từ chối xác nhận giá trị đề xuất.
Thuật toán đồng thuận trong hệ thống không đồng bộ
Trước đó, mọi thứ đều suôn sẻ vì chúng ta đang nói về mô hình nhắn tin đồng bộ. Nhưng chúng ta biết rằng trong thế giới hiện đại, chúng ta đã quen với việc làm mọi thứ không đồng bộ. Thuật toán tương tự hoạt động như thế nào trong một hệ thống có mô hình nhắn tin không đồng bộ, trong đó chúng tôi tin rằng thời gian chờ phản hồi từ một nút có thể dài tùy ý (nhân tiện, lỗi của một nút cũng có thể được coi là một ví dụ khi một nút có thể phản hồi trong một thời gian dài tùy ý).
Bây giờ chúng ta đã biết thuật toán đồng thuận hoạt động như thế nào về nguyên tắc, một câu hỏi dành cho những độc giả tò mò đã đi xa đến mức này: có bao nhiêu nút trong hệ thống gồm N nút có mô hình thông báo không đồng bộ có thể thất bại để hệ thống vẫn có thể đạt được sự đồng thuận?
Câu trả lời chính xác và lời giải thích nằm đằng sau phần tiết lộ nội dung.Câu trả lời đúng là: 0. Nếu ngay cả một nút trong hệ thống không đồng bộ bị lỗi, hệ thống sẽ không thể đạt được sự đồng thuận. Tuyên bố này đã được chứng minh trong định lý FLP, nổi tiếng trong một số giới nhất định (1985, Fischer, Lynch, Paterson, liên kết đến bản gốc ở cuối bài viết): “Không thể đạt được sự đồng thuận phân tán nếu ít nhất một nút bị lỗi .”
Các bạn, vậy thì chúng ta gặp một vấn đề, chúng ta đã quen với việc mọi thứ không đồng bộ. Và nó đây. Làm sao để tiếp tục sống?
Chúng tôi chỉ đang nói về lý thuyết, về toán học. “Không thể đạt được sự đồng thuận” nghĩa là gì khi chuyển từ ngôn ngữ toán học sang ngôn ngữ kỹ thuật của chúng ta? Điều này có nghĩa là “không phải lúc nào cũng đạt được”, tức là Có trường hợp không đạt được sự đồng thuận. Đây là loại trường hợp gì?
Đây chính xác là sự vi phạm thuộc tính sống động được mô tả ở trên. Chúng tôi không có thỏa thuận chung và hệ thống không thể có tiến triển (không thể hoàn thành trong thời gian hữu hạn) trong trường hợp chúng tôi không nhận được phản hồi từ tất cả các nút. Bởi vì trong một hệ thống không đồng bộ, chúng tôi không thể dự đoán được thời gian phản hồi và chúng tôi không thể biết liệu một nút có bị hỏng hay chỉ mất nhiều thời gian để phản hồi.
Nhưng trong thực tế chúng ta có thể tìm ra giải pháp. Hãy để thuật toán của chúng tôi có thể hoạt động lâu dài trong trường hợp xảy ra lỗi (có khả năng nó có thể hoạt động vô thời hạn). Nhưng trong hầu hết các tình huống, khi hầu hết các nút đều hoạt động chính xác, chúng ta sẽ có tiến bộ trong hệ thống.
Trong thực tế, chúng ta xử lý các mô hình truyền thông đồng bộ một phần. Đồng bộ một phần được hiểu như sau: trong trường hợp tổng quát, chúng ta có một mô hình không đồng bộ, nhưng một khái niệm nhất định về “thời gian ổn định toàn cầu” của một thời điểm nhất định được chính thức đưa ra.
Thời điểm này có thể không đến trong một thời gian dài, nhưng nó phải đến vào một ngày nào đó. Đồng hồ báo thức ảo sẽ đổ chuông và từ thời điểm đó, chúng ta có thể dự đoán khoảng thời gian mà tin nhắn sẽ đến. Kể từ thời điểm này, hệ thống chuyển từ không đồng bộ sang đồng bộ. Trong thực tế, chúng tôi xử lý chính xác các hệ thống như vậy.
Thuật toán Paxos giải quyết các vấn đề đồng thuận
là một nhóm thuật toán giải quyết vấn đề đồng thuận cho các hệ thống đồng bộ một phần, có khả năng một số nút có thể bị lỗi. Tác giả của Paxos là . Ông đã đề xuất một bằng chứng chính thức về sự tồn tại và tính đúng đắn của thuật toán vào năm 1989.
Nhưng bằng chứng hóa ra lại không hề tầm thường. Ấn phẩm đầu tiên chỉ được phát hành vào năm 1998 (33 trang) mô tả thuật toán. Hóa ra, nó cực kỳ khó hiểu, và vào năm 2001, phần giải thích của bài báo đã được xuất bản, dài 14 trang. Khối lượng ấn phẩm được đưa ra nhằm chứng tỏ rằng trên thực tế, vấn đề đồng thuận không hề đơn giản chút nào, và đằng sau những thuật toán như vậy là một khối lượng công việc khổng lồ của những người thông minh nhất.
Điều thú vị là chính Leslie Lamport đã lưu ý trong bài giảng của mình rằng trong bài giải thích thứ hai có một câu, một dòng (anh ấy không nói rõ là câu nào), có thể được hiểu theo nhiều cách khác nhau. Và vì điều này, một số lượng lớn việc triển khai Paxos hiện đại không hoạt động hoàn toàn chính xác.
Một phân tích chi tiết về công việc của Paxos sẽ cần nhiều hơn một bài viết, vì vậy tôi sẽ cố gắng truyền đạt thật ngắn gọn ý tưởng chính của thuật toán. Trong các liên kết ở cuối bài viết của tôi, bạn sẽ tìm thấy tài liệu để tìm hiểu sâu hơn về chủ đề này.
Vai trò tại Paxos
Thuật toán Paxos có khái niệm về vai trò. Hãy xem xét ba cái chính (có những sửa đổi với các vai trò bổ sung):
- Người đề xuất (các thuật ngữ cũng có thể được sử dụng: lãnh đạo hoặc điều phối viên). Đây là những người tìm hiểu về một số giá trị mới từ người dùng và đảm nhận vai trò lãnh đạo. Nhiệm vụ của họ là đưa ra một loạt đề xuất về giá trị mới và điều phối các hành động tiếp theo của các nút. Hơn nữa, Paxos cho phép có sự hiện diện của một số nhà lãnh đạo trong một số tình huống nhất định.
- Người chấp nhận (Cử tri). Đây là các nút bỏ phiếu chấp nhận hoặc từ chối một giá trị cụ thể. Vai trò của họ rất quan trọng, bởi vì quyết định phụ thuộc vào họ: hệ thống sẽ (hoặc sẽ không) chuyển sang trạng thái nào sau giai đoạn tiếp theo của thuật toán đồng thuận.
- Học. Các nút chỉ chấp nhận và ghi giá trị được chấp nhận mới khi trạng thái của hệ thống thay đổi. Họ không đưa ra quyết định, họ chỉ nhận dữ liệu và có thể cung cấp dữ liệu đó cho người dùng cuối.
Một nút có thể kết hợp nhiều vai trò trong các tình huống khác nhau.
Khái niệm về số đại biểu
Chúng ta giả sử rằng chúng ta có một hệ thống N điểm giao Và trong số đó tối đa F các nút có thể thất bại. Nếu nút F bị lỗi thì chúng ta phải có ít nhất 2F+1 các nút chấp nhận.
Điều này là cần thiết để chúng ta luôn có đa số, ngay cả trong tình huống xấu nhất, các nút “tốt” hoạt động chính xác. Đó là F+1 các nút "tốt" đã đồng ý và giá trị cuối cùng sẽ được chấp nhận. Nếu không, có thể xảy ra tình huống trong đó các nhóm địa phương khác nhau của chúng ta mang những ý nghĩa khác nhau và không thể đồng ý với nhau. Vì vậy, chúng ta cần có đa số tuyệt đối để giành được phiếu bầu.
Ý tưởng chung về cách hoạt động của thuật toán đồng thuận Paxos
Thuật toán Paxos bao gồm hai giai đoạn lớn, lần lượt được chia thành hai bước:
- Giai đoạn 1a: Chuẩn bị. Trong giai đoạn chuẩn bị, người đứng đầu (người đề xuất) thông báo cho tất cả các nút: “Chúng tôi đang bắt đầu một giai đoạn bỏ phiếu mới. Chúng ta có một vòng mới. Số của vòng này là n. Bây giờ chúng ta sẽ bắt đầu bỏ phiếu." Hiện tại, nó chỉ báo cáo sự bắt đầu của một chu kỳ mới nhưng không báo cáo giá trị mới. Nhiệm vụ của giai đoạn này là bắt đầu một vòng mới và thông báo cho mọi người về con số duy nhất của nó. Số làm tròn rất quan trọng, nó phải có giá trị lớn hơn tất cả các số biểu quyết trước đó của tất cả các số dẫn đầu trước đó. Bởi vì chính nhờ số tròn mà các nút khác trong hệ thống sẽ hiểu được dữ liệu của người dẫn đầu gần đây như thế nào. Có khả năng là các nút khác đã có kết quả bỏ phiếu từ nhiều vòng sau đó và sẽ chỉ nói với người lãnh đạo rằng anh ta đi sau thời đại.
- Giai đoạn 1b: Lời hứa. Khi các nút chấp nhận nhận được số giai đoạn bỏ phiếu mới, có thể xảy ra hai kết quả:
- Số n của phiếu bầu mới lớn hơn số phiếu bầu trước đó mà người chấp nhận đã tham gia. Sau đó người chấp nhận gửi lời hứa đến người đứng đầu sẽ không tham gia thêm bất kỳ phiếu bầu nào có số phiếu nhỏ hơn n. Nếu người chấp nhận đã bỏ phiếu cho điều gì đó (nghĩa là nó đã chấp nhận một số giá trị trong giai đoạn thứ hai), thì nó sẽ gắn giá trị được chấp nhận và số phiếu bầu mà nó đã tham gia vào lời hứa của mình.
- Mặt khác, nếu người chấp nhận đã biết về phiếu bầu có số lượng cao hơn, họ có thể đơn giản bỏ qua bước chuẩn bị và không phản hồi lại người đứng đầu.
- Giai đoạn 2a: Chấp nhận. Người lãnh đạo cần đợi phản hồi từ số đại biểu (phần lớn các nút trong hệ thống) và nếu nhận được đủ số lượng phản hồi cần thiết thì anh ta có hai lựa chọn để phát triển các sự kiện:
- Một số người chấp nhận đã gửi các giá trị mà họ đã bình chọn. Trong trường hợp này, người đứng đầu chọn giá trị từ phiếu bầu có số lượng tối đa. Hãy gọi giá trị này là x và nó sẽ gửi một thông báo đến tất cả các nút như: “Chấp nhận (n, x)”, trong đó giá trị đầu tiên là số biểu quyết từ bước Đề xuất của chính nó và giá trị thứ hai là giá trị mà mọi người đã tập hợp lại, I E. giá trị mà chúng ta thực sự bỏ phiếu.
- Nếu không có người chấp nhận nào gửi bất kỳ giá trị nào mà họ chỉ hứa sẽ bỏ phiếu trong vòng này, thì người đứng đầu có thể mời họ bỏ phiếu cho giá trị của họ, giá trị mà anh ta đã trở thành người dẫn đầu ngay từ đầu. Hãy gọi nó là y. Nó gửi một thông báo đến tất cả các nút như: “Chấp nhận (n, y)”, tương tự như kết quả trước đó.
- Giai đoạn 2b: Đã chấp nhận. Hơn nữa, các nút chấp nhận, khi nhận được thông báo “Chấp nhận (...)” từ người đứng đầu, sẽ đồng ý với nó (gửi xác nhận cho tất cả các nút mà họ đồng ý với giá trị mới) chỉ khi họ chưa hứa một số (khác) ) người đứng đầu tham gia biểu quyết bằng số tròn n' > n, nếu không họ sẽ bỏ qua yêu cầu xác nhận.
Nếu phần lớn các nút phản hồi với nút dẫn đầu và tất cả chúng đều xác nhận giá trị mới thì giá trị mới được coi là được chấp nhận. Hoan hô! Nếu không đạt được đa số hoặc có các nút từ chối chấp nhận giá trị mới thì mọi thứ sẽ bắt đầu lại.
Đây là cách thuật toán Paxos hoạt động. Mỗi giai đoạn này có nhiều điểm phức tạp, thực tế chúng tôi đã không xem xét các loại lỗi khác nhau, vấn đề của nhiều nhà lãnh đạo, v.v., nhưng mục đích của bài viết này chỉ là giới thiệu với người đọc về thế giới điện toán phân tán ở mức độ cao.
Điều đáng chú ý là Paxos không phải là thuật toán duy nhất thuộc loại này, ví dụ như có các thuật toán khác , nhưng đây là chủ đề cho một bài viết khác.
Liên kết đến các tài liệu để nghiên cứu thêm
Cấp độ cho người bắt đầu:
- , Preethi Kasireddy, bài viết blog trên Medium
- , Adi Kancherla, bài viết blog trên Medium
- , Ittai Abraham, blog
- , Ittai Abraham, bài viết trên blog
Trình độ của Leslie Lamport:
- , Fischer, Lynch và Paterson, bài nghiên cứu, 1985
- , Leslie Lamport, tài liệu nghiên cứu, 1998
- , Leslie Lamport, tài liệu nghiên cứu, 2001
Nguồn: www.habr.com