CRDT trong hệ thống phân phối là gì?

Question

Tôi là một newbie trong các hệ thống phân tán và tôi đang cố gắng để có được một cái nhìn sâu sắc về khái niệm CRDT. Tôi nhận ra rằng nó có ba ký hiệu:

Conflict-free Replicated Data Type 
Convergent Replicated Data Type 
Commutative Replicated Data Type 

bất cứ ai có thể đưa ra một ví dụ mà chúng ta sử dụng CRDT trong hệ thống phân phối? Cảm ơn rất nhiều trước.

Answer 1

CRDT được lấy cảm hứng từ tác phẩm của Marc Shapiro. Trong tính toán phân tán, kiểu dữ liệu nhân bản không xung đột (CRDT viết tắt) là một kiểu cấu trúc dữ liệu được thiết kế đặc biệt được sử dụng để đạt được tính nhất quán cuối cùng (SEC) và tính đơn điệu (không có sự hồi quy). Có hai tuyến đường thay thế để đảm bảo CRDTs dựa trên hoạt động SEC và CRDT dựa trên trạng thái.

CRDT trên các bản sao khác nhau có thể phân tách nhau nhưng cuối cùng chúng có thể được hợp nhất một cách an toàn với giá trị cuối cùng nhất quán. Nói cách khác, CRDTs có một phương thức hợp nhất không có giá trị, giao hoán và kết hợp.

Hai lựa chọn thay thế là tương đương, vì người ta có thể mô phỏng khác, nhưng CRDT dựa trên hoạt động yêu cầu đảm bảo bổ sung từ phần mềm trung gian truyền thông. CRDT được sử dụng để tái tạo dữ liệu trên nhiều máy tính trong mạng, thực hiện cập nhật mà không cần đồng bộ hóa từ xa. Điều này sẽ dẫn đến xung đột hợp nhất trong các hệ thống sử dụng công nghệ thống nhất cuối cùng thông thường, nhưng CRDT được thiết kế sao cho các xung đột là không thể toán học. Theo các ràng buộc của định lý CAP, chúng cung cấp sự đảm bảo nhất quán mạnh nhất cho các cài đặt có sẵn/phân vùng dung nạp (AP).

Một số ví dụ mà chúng được sử dụng

Riak là thư viện mã nguồn mở phổ biến nhất của CRDT và được sử dụng bởi Bet365 và League of Legends. Dưới đây là một số liên kết hữu ích hỗ trợ Riak.

1- Bet365 (Sử dụng Erlang và Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

2- League of Legends sử dụng thực hiện Riak CRDT cho hệ thống chat trong game của mình (mà xử lý 7,5 triệu người dùng đồng thời và 11.000 tin nhắn mỗi giây)

3 Roshi thực hiện bởi SoundCloud hỗ trợ một LWW thời gian đóng dấu Set: bài -Blog: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

Answer 2

Ba mở rộng của từ viết tắt tất cả có nghĩa là về cơ bản giống nhau.

CRDT là hội tụ nếu các hoạt động tương tự được áp dụng trong một trình tự khác nhau tạo ra (hội tụ thành) cùng một kết quả. Đó là, các hoạt động có thể được giao hoán - đó là một RDT giao hoán. Lý do mà các hoạt động có thể được áp dụng trong một trình tự khác nhau và vẫn nhận được kết quả tương tự là các hoạt động không xung đột.

Vì vậy, CRDT có nghĩa là điều tương tự, tùy thuộc vào ba phần mở rộng bạn sử dụng - mặc dù cá nhân tôi thích "Convergent".

Answer 3

CRDTs sử dụng Math để thi hành thống nhất trên một cụm phân tán, mà không cần phải lo lắng về việc đồng thuận và một độ trễ/không có sẵn liên tục. Tập hợp các giá trị mà CRDT có thể thực hiện bất cứ lúc nào thuộc danh mục của mạng bán (cụ thể là mạng bán kết nối), là một POSET (bộ được đặt một phần) với chức năng giới hạn trên thấp nhất (LUB).

Nói một cách đơn giản, POSET là tập hợp các mục mà không phải tất cả đều có thể so sánh được. Ví dụ. trong một mảng các cặp: {(2,4), (4, 5), (2, 1), (6, 3)}, (2,4) là < (4,5), nhưng không thể so sánh với (6,3) (vì một phần tử lớn hơn và phần tử còn lại nhỏ hơn). Bây giờ, một mạng bán là một POSET trong đó cho 2 cặp, ngay cả khi bạn không thể so sánh hai cặp, bạn có thể tìm thấy một phần tử lớn hơn cả hai.

Điều kiện khác là cập nhật đối với loại dữ liệu này cần phải tăng lên, CRDT có trạng thái tăng đơn điệu, nơi khách hàng không bao giờ quan sát trạng thái cuộn ngược.

Điều này excellent article sử dụng mảng tôi đã sử dụng ở trên làm ví dụ. Đối với CRDT duy trì các giá trị đó, nếu 2 bản sao đang cố gắng đạt được sự đồng thuận giữa (4,5) và (6,3), họ có thể chọn LUB = (6,5) làm sự đồng thuận và chỉ định cả hai bản sao cho nó. Vì các giá trị đang tăng lên, đây là một giá trị tốt để giải quyết. Có 2 cách để CRDT giữ đồng bộ với nhau qua các bản sao, chúng có thể chuyển trạng thái theo định kỳ (kiểu dữ liệu được nhân bản hội tụ), hoặc chúng có thể truyền cập nhật (deltas) khi chúng nhận được chúng (kiểu dữ liệu nhân bản giao hoán).). Trước đây có thêm băng thông.

SoundCloud's Roshi là một ví dụ điển hình (mặc dù không còn phát triển), chúng lưu trữ dữ liệu được liên kết với dấu thời gian, nơi dấu thời gian rõ ràng là tăng dần. Bất kỳ cập nhật nào đến với dấu thời gian nhỏ hơn hoặc bằng giá trị được lưu trữ sẽ bị hủy bỏ, đảm bảo tính không hoạt động (lặp lại ghi là OK) và tính tương đối (không cần viết là ok). giống như update2 theo sau là update1)

Ghi được gửi tới tất cả các cụm và nếu một số nút nhất định không phản hồi do sự cố như chậm hoặc phân vùng, chúng sẽ được cập nhật sau qua read-repair. các giá trị hội tụ. Hội tụ có thể đạt được thông qua 2 giao thức như tôi đã đề cập ở trên, tuyên truyền trạng thái hoặc cập nhật cho các bản sao khác. Tôi tin Roshi là người trước đây. Là một phần của read-repair, trạng thái trao đổi bản sao và vì dữ liệu tuân theo thuộc tính bán mạng, chúng hội tụ.

PS. Các hệ thống sử dụng CRDTs cuối cùng là phù hợp, tức là chúng áp dụng AP (khả năng chịu cao và phân vùng) trong CAP theorem.

Another excellent read on the subject.