Làm cách nào để dấu thời gian có thể gây ra "bế tắc toàn cầu"?

Question

Tôi đang thực hiện một số đọc về những ưu điểm/nhược điểm của việc sử dụng dấu thời gian để kiểm soát đồng thời trong cơ sở dữ liệu phân tán. Các tài liệu tôi đang đọc đề cập rằng mặc dù dấu thời gian vượt qua các vấn đề bế tắc truyền thống có thể ảnh hưởng đến khóa vẫn còn là vấn đề của "bế tắc toàn cầu" mà nó dễ bị tổn thương.

Tài liệu mô tả bế tắc toàn cầu là tình huống không có chu kỳ tồn tại trong đồ thị chờ của đồ thị địa phương nhưng có một chu kỳ trong biểu đồ toàn cầu.

Tôi tự hỏi làm thế nào điều này có thể xảy ra? Ai đó có thể mô tả một tình huống mà một hệ thống dấu thời gian có thể gây ra vấn đề này?

Answer 1

Dưới đây là một ví dụ, có thể đơn giản nhất có thể. Chúng tôi có máy A và B. Máy A có khóa T1 và T2 với mối quan hệ T1 < T2. Máy B có T3 và T4 với T3 > T4.

Bây giờ, biểu đồ cục bộ chỉ là T2 phải đợi T1 và T3 phải đợi T4. Vì vậy, không có chu kỳ cục bộ. Nhưng bây giờ, giả sử chúng ta có T4 < T1 vì vậy T1 phải chờ T4. Và đồng thời T2 < T3 nên T3 phải đợi T2. Trong trường hợp này, có một chu kỳ trên toàn cầu.

Vậy chu kỳ đó xảy ra như thế nào? Chìa khóa ở đây là bạn không bao giờ có đầy đủ thông tin trong một hệ thống phân tán. Vì vậy, chúng ta có thể tìm hiểu sau đó rằng các phụ thuộc giữa các máy có ở đó. Và sau đó chúng tôi có một vấn đề.

Answer 2

Dấu thời gian được sử dụng để xác định xung đột giữa các quá trình cục bộ trên máy. Nó đưa ra một phương tiện để giải quyết các deadlocks ở cấp độ đó. Đối với các quá trình phân tán, có thể có hai quá trình trên các máy khác nhau để chờ đợi lẫn nhau. Đó là trong thực tế, một bế tắc thường xuyên, nhưng trên máy. Đây được gọi là bế tắc 'toàn cầu'. Imho timestamping có thể được sử dụng ở đó nhưng cũng không thực tế.

Một số thông tin về điều này có thể được tìm thấy trên http://www.cse.scu.edu/~jholliday/dd_9_16.htm