- vừa được xem lúc

Giải quyết deadlock cho hệ thống phân tán bằng những thuật toán phổ biến

0 0 32

Người đăng: Popping Khiem

Theo Viblo Asia

Giải quyết deadlock cho hệ thống bằng những thuật toán phổ biến:

Dưới đây là một số phương pháp và công nghệ phổ biến được sử dụng:

Thuật toán bầu chọn (voting algorithm) và Thuật toán gắn nhãn thời gian (time stamping algorithm) là hai phương pháp thường được sử dụng để giải quyết vấn đề deadlock trong hệ thống phân tán. Tuy nhiên, mỗi thuật toán có cách tiếp cận và cơ chế hoạt động khác nhau. Dưới đây là mô tả về cả hai thuật toán:

1. Bầu chọn (Voting algorithm):

Ý tưởng: Thuật toán bầu chọn được sử dụng để chọn ra một tiến trình để giải quyết deadlock trong hệ thống phân tán.

Cơ chế hoạt động:

  1. Mỗi tiến trình gửi thông điệp yêu cầu giải quyết deadlock đến các tiến trình khác.
  2. Tiến trình nhận thông điệp đếm số lượng thông điệp yêu cầu deadlock đã nhận.
  3. Nếu một tiến trình nhận được tất cả các thông điệp yêu cầu deadlock, nó trở thành tiến trình chủ động giải quyết deadlock.
  4. Tiến trình chủ động sẽ giải quyết deadlock bằng cách xóa một hoặc nhiều tiến trình khác để giải phóng tài nguyên.
  • Khi tiến trình điều phối gặp lỗi thì sẽ phải có quá trình bầu chọn để chọn ra một tiến trình khác làm điều phối thay cho nó. 
  • Có hai giải thuật bầu chọn hay được sử dụng là:
    o Giải thuật áp đảo (Bully Algorithm)
    o Giải thuật vòng (Ring Algorithm)

1.1 Bầu chọn áp đảo:

Giả sử:

  1. Mỗi một tiến trình đều có một ID duy nhất.

  2. Tất cả các tiến trình khác đều có thể biết được số ID và địa chỉ của mỗi tiến trình trong hệ thống.

  3. Chọn một tiến trình có ID cao nhất làm khóa.

  4. Tiến trình sẽ khởi động việc bầu chọn nếu như nó khôi phục lại sau quá trình xảy ra lỗi hoặc tiến trình điều phối bị trục trặc.

1.2 Giải thuật vòng

Các bước của giải thuật:

  1. Một tiến trình bắt đầu gửi thông điệp Election tới các nút còn tồn tại gần nhất, quá trình gửi theo 1 hướng nhất định.

  2. Nó sẽ thăm dò liên tiếp trên vòng cho đến khi tìm được 1 nút còn tồn tại.

  3. Mỗi một tiến trình sẽ gắn ID của mình vào thông điệp gửi.

  4. Cuối cùng sẽ chọn ra 1 tiến trình có ID cao nhất trong số các tiến trình còn hoạt động và gửi thông điệp điều phối cho tiến trình đó.

2. Thuật toán gắn nhãn thời gian Lamport:


Gắn nhãn thời gian (Time stamping) là một thuật toán được sử dụng để gắn nhãn một thời điểm cụ thể vào một sự kiện, một giao dịch hoặc một thông tin nào đó. Mục đích của việc gắn nhãn thời gian là cung cấp thông tin về thời gian xảy ra sự kiện hoặc tạo ra một chứng cứ thời gian.

Dưới đây là mô tả cơ bản về thuật toán gắn nhãn thời gian:

  1. Lấy thời gian hiện tại: Sử dụng các công cụ và hàm thích hợp trong ngôn ngữ lập trình hoặc hệ điều hành để lấy thời gian hiện tại. Thời gian này có thể được biểu diễn dưới dạng dấu thời gian Unix (epoch time) hoặc định dạng ngày giờ khác.

  2. Định dạng thời gian: Chuyển đổi thời gian lấy được thành định dạng thời gian phù hợp, ví dụ: định dạng ngày giờ ISO 8601.

  3. Gắn nhãn thời gian: Gắn nhãn thời gian vào sự kiện, giao dịch hoặc thông tin cần được gắn nhãn. Điều này có thể được thực hiện bằng cách thêm một trường thời gian vào dữ liệu hoặc sử dụng một phương pháp khác tương thích với ngữ cảnh sử dụng.

  4. Lưu trữ và xử lý: Dữ liệu đã được gắn nhãn thời gian có thể được lưu trữ trong cơ sở dữ liệu, tệp tin, gửi đi qua mạng hoặc xử lý bởi các thuật toán và ứng dụng khác để phục vụ mục đích nào đó.

Quá trình gắn nhãn thời gian cho phép theo dõi, phân tích và xử lý các sự kiện theo thời gian, từ việc xác định thứ tự xảy ra của chúng cho đến việc tính toán khoảng thời gian giữa các sự kiện. Điều này có thể hữu ích trong nhiều lĩnh vực, bao gồm hệ thống giao dịch tài chính, ghi log hệ thống, theo dõi sự kiện trong mạng, và nhiều ứng dụng khác.

Xét định nghĩa mối quan hệ “xảy ra trước” (→)

  • Khi có a→ b :  a xảy ra trước b thì tất cả các tiến trình trong hệ phân tán thỏa thuận sự kiện a
  • xảy ra trước rồi đến sự kiện b. Trong đó a và b là hai sự kiện của cùng một tiến trình.
  • Nếu a xảy ra trước b thì a→b là đúng.
  • Nếu a là sự kiện bản tin được gửi bởi một tiến trình nào đó và b là sự kiện bản tin
  • đó được nhận bởi một tiến trình khác thì quan hệ a→ b là đúng.
  • Quan hệ xảy ra trước có tính bắc cầu: a→ b, b→c thì a→c.

Trên đây là 2 thuật toán tôi đã nêu, ngoài ra còn giải thuật Vector, giải thuật Christian ...được áp dụng rộng rãi trong việc xử lý các hệ thống phân tán. Khi có thời gian tôi sẽ tiếp tục ngâm cứu series này. Chúc các bạn vui vẻ.

Author: PoppinKhiem

Bình luận

Bài viết tương tự

- vừa được xem lúc

Tìm hiểu SQL Transaction và cách sử dụng trong Laravel

Bài toán thực tế. Trước khi tìm hiểu về SQL Transaction là gì và cách sử dụng như thế nào thì bạn cùng xem qua một bài toán dưới đây để hình dung ra cách áp dụng transaction khi nào nhé.

0 0 22

- vừa được xem lúc

014: PostgreSQL transaction isolation

Bài viết nằm trong series Performance optimization với PostgreSQL. Bài viết này sẽ tập trung vào tính isolation - transaction isolation.

0 0 57

- vừa được xem lúc

[Redis] - Spring Boot Redis Transaction

Trong bài viết này chúng ta sẽ tìm hiểu về Redis Transaction. Đầu tiên chúng ta nói với redis rằng chúng ta sẽ thực thi một tập hợp các thao tác bằng cách gọi command multi.

0 0 37

- vừa được xem lúc

DeadLock trong cơ sở dữ liệu và cách phòng tránh

Các hệ quản trị cơ sở dữ liệu đảm bảo tài nguyên trong database có tính nhất quán (consistency), có nghĩa là cùng một dữ liệu sẽ không thể đọc ghi tại cùng 1 thời điểm. Điều này sẽ dẫn tới hiện tượng

0 0 65

- vừa được xem lúc

Distributed transaction - Two-phase commit

Microservices Architecture (MSA) - không còn quá mới mẻ nhưng vẫn nóng hổi và hấp dẫn. Nó hấp dẫn bởi rất nhiều yếu tố khác nhau và một trong số đó là sự phức tạp.

0 0 47

- vừa được xem lúc

Đào sâu về SQL Transactions

Trong bất kỳ database nào, sự yếu kém trong việc quản lý các thao tác với dữ liệu thường dẫn tới các vấn đề về xung đột và hiệu năng trong hệ thống có nhiều users. Khi số lượng users thao tác với dữ l

0 0 33