Tiếp tục từ bài viết trước

Tiếp theo [Điểm nổi bật | [Chủ đề Cấu trúc dữ liệu thuật toán] "Thuật toán hàng đợi trễ" trước đó phân tích và giới thiệu rất chi tiết về cách triển khai hướng dẫn nguyên tắc của hàng đợi trễ thông qua bánh xe thời gian (TimingWheel), chúng ta đã biết cơ bản về nguyên tắc và cơ chế thuật toán cốt lõi của "thuật toán bánh xe thời gian". Tiếp theo, chúng ta cần phân tích cách triển khai hệ thống cơ chế thuật toán của bánh xe thời gian theo góc độ phát triển và triển khai thực tế.

---

Lời nói đầu Đánh giá

Bánh xe thời gian là gì?

• Mô hình lập lịch :Bánh xe thời gian là một ý tưởng về mô hình/thuật toán lập lịch được tạo ra để giải quyết vấn đề lập lịch hiệu quả.
• Cấu trúc dữ liệu :Một cấu trúc dữ liệu thường được triển khai bằng bảng băm và danh sách liên kết kép.

Tại sao lại sử dụng bánh xe thời gian?

Ưu điểm so với hàng đợi truyền thống

So với trình lập lịch theo hàng đợi truyền thống, bánh xe thời gian có thể quản lý hiệu quả nhiều tác vụ bị trì hoãn, tác vụ định kỳ, tác vụ thông báo, v.v. theo từng đợt. Ví dụ, hệ thống hàng đợi bị trì hoãn/nhiệm vụ bị trì hoãn.

Hệ thống nhiệm vụ/hàng đợi bị trì hoãn

**Các nhiệm vụ bị trì hoãn và nhiệm vụ định kỳ chủ yếu được sử dụng để trì hoãn các nhiệm vụ bị trì hoãn trên quy mô lớn và các nhiệm vụ theo lịch trình định kỳ.

Trường hợp - Chuỗi hoạt động trì hoãn Kafka

Ví dụ, các yêu cầu mạng tốn thời gian (chẳng hạn như chờ bản sao ISR được sao chép thành công trong Produce) sẽ được đóng gói dưới dạng DelayOperation cho các hoạt động xử lý bị trì hoãn để tránh chặn luồng xử lý yêu cầu Kafka, do đó ảnh hưởng đến hiệu quả và hiệu suất.

Các vấn đề về hiệu suất do hàng đợi truyền thống gây ra

Kafka không sử dụng cơ chế hàng đợi truyền thống (triển khai Timer+DelayQueue đi kèm với JDK). Do độ phức tạp về thời gian của cả thao tác chèn và xóa là O(logn) nên nó không thể đáp ứng được các yêu cầu hiệu suất cao của Kafka.

Dựa trên triển khai Timer+DelayQueue của JDK

JDK Timer và DelayQueue đều là hàng đợi ưu tiên ở dưới cùng, tức là chúng sử dụng cấu trúc dữ liệu minHeap và tác vụ cần được thực thi nhanh nhất sẽ được đặt đầu tiên trong hàng đợi. Sự khác biệt là Timer có một luồng để kéo tác vụ để thực thi và DelayQueue thực sự là một container cần làm việc với các luồng khác.

ScheduledThreadPoolExecutor là một cách để triển khai các tác vụ theo lịch trình của JDK, thực chất là một triển khai của DelayQueue+luồng gộp.

Triển khai dựa trên TimeWheel

Các hoạt động chèn và xóa của thuật toán bánh xe thời gian có độ phức tạp thời gian là O(1), đáp ứng các yêu cầu về hiệu suất của Kafka. Ngoài Kafka, các dự án nguồn mở như Netty, ZooKeepr, Dubbo và thậm chí cả hạt nhân Linux đều sử dụng triển khai bánh xe thời gian.

Khi lưu lượng truy cập nhỏ, sử dụng DelayQueue sẽ hiệu quả hơn. Khi lưu lượng giao thông lớn, việc sử dụng bộ hẹn giờ sẽ cải thiện hiệu quả đáng kể.

Thuật toán bánh xe thời gian là gì và ý tưởng của thuật toán là gì?

Cấu trúc dữ liệu của bánh xe thời gian

Mô hình cấu trúc dữ liệu chủ yếu bao gồm: hàng đợi vòng tròn bánh xe thời gian và danh sách tác vụ bánh xe thời gian.

• TimingWheel là một mảng chu kỳ lưu trữ các tác vụ được tính thời gian. Lớp cơ bản được triển khai bằng cách sử dụng một mảng chu kỳ. Mỗi phần tử trong mảng có thể tương ứng với một TimeWheelTaskList.

• TimeWheelTaskList là danh sách liên kết hai chiều dạng vòng, mỗi phần tử là một mục tác vụ bị trì hoãn/được lên lịch (TaskEntry), bao gồm thông tin cơ bản và siêu dữ liệu của tác vụ.

Bạn có thể thấy một số thông số trong hình:

• startMs: thời gian bắt đầu.

• tickMs: Đơn vị nhỏ nhất của quá trình thực hiện bánh xe thời gian. Bánh xe thời gian bao gồm nhiều lưới thời gian, mỗi lưới thời gian biểu thị khoảng thời gian cơ bản của bánh xe thời gian hiện tại, tức là tickMs.

• wheelSize: Số lượng hàng đợi tròn trong bánh xe thời gian. Số lượng lưới thời gian của bánh xe thời gian là cố định và có thể được biểu diễn bằng wheelSize.

• khoảng thời gian: Khoảng thời gian tổng thể của bánh xe thời gian = tickMs * wheelSize.

Dựa trên hai tính chất trên, ta có thể nói rằng khoảng thời gian tổng thể (khoảng cách) của toàn bộ bánh xe thời gian có thể được tính bằng công thức tickMs × wheelSize. Ví dụ, nếu tickMs của bánh xe thời gian là 1ms và wheelSize là 20, thì khoảng thời gian có thể được tính là 20ms.

con trỏ currentTime con trỏ

Ngoài ra, bánh xe thời gian có một con trỏ trỏ, mà chúng ta gọi là (currentTime), được sử dụng để chỉ thời gian hiện tại của bánh xe thời gian. CurrentTime là bội số nguyên của tickMs.

Khoảng thời gian tổng thể của toàn bộ bánh xe thời gian không thay đổi. Khi con trỏ currentTime tiếp tục di chuyển, khoảng thời gian mà bánh xe thời gian hiện tại có thể xử lý cũng liên tục di chuyển ngược lại. Phạm vi thời gian của toàn bộ bánh xe thời gian nằm giữa currentTime và currentTime+interval.

currentTime có thể chia toàn bộ bánh xe thời gian thành một phần đã hết hạn và một phần chưa hết hạn. Lưới thời gian hiện đang được currentTime trỏ đến cũng thuộc về phần đã hết hạn, nghĩa là nó vừa hết hạn và tất cả các tác vụ trong TimeWheelTaskList tương ứng với lưới thời gian này cần được xử lý.

Luồng hoạt động của con trỏ currentTime

1. Ban đầu, con trỏ quay số currentTime trỏ đến lưới thời gian 0. Vào thời điểm này, một tác vụ có bộ đếm thời gian 2ms được chèn và lưu trữ trong danh sách tác vụ có lưới thời gian 2.

2. Khi thời gian trôi qua, con trỏ currentTime tiếp tục di chuyển về phía trước. Sau 2ms, khi đạt đến lưới thời gian 2, tác vụ trong danh sách tác vụ tương ứng với lưới thời gian 2 cần phải hết hạn tương ứng.

3. Nếu một tác vụ khác có bộ đếm thời gian 8ms được chèn vào thời điểm này, tác vụ đó sẽ được lưu trữ trong khe thời gian 10 và currentTime sẽ trỏ đến khe thời gian 10 sau 8ms nữa.

Tóm lại, khoảng thời gian chung của toàn bộ bánh xe thời gian không thay đổi. Khi con trỏ currentTime tiếp tục tiến lên, khoảng thời gian mà bánh xe thời gian hiện tại có thể xử lý cũng liên tục di chuyển ngược lại và phạm vi thời gian chung nằm giữa currentTime và currentTime+interval.

Cơ chế bánh xe thời gian phân cấp

Chúng ta nên làm gì nếu một tác vụ bị trì hoãn vượt quá khoảng thời gian tổng thể được nộp? Do đó, khái niệm bánh xe thời gian phân cấp được giới thiệu. Khi thời gian hết hạn của một tác vụ vượt quá phạm vi thời gian được biểu thị bởi bánh xe thời gian hiện tại, nó sẽ cố gắng được thêm vào bánh xe thời gian phân cấp.

Giới thiệu về nguyên lý thực hiện của bánh xe thời gian phân cấp

Chuyển đổi nhiệm vụ nâng cấp bánh xe thời gian phân cấp

Khi chèn một nhiệm vụ, nếu bánh xe thời gian cấp một không đáp ứng các điều kiện, hãy thử chèn nó vào bánh xe thời gian cấp cao hơn, v.v.

• Bánh xe thời gian của lớp đầu tiên tickMs=1ms, wheelSize=20, interval=20ms.

• Khoảng thời gian tích tắc của bánh xe thời gian lớp thứ hai là khoảng thời gian của bánh xe thời gian lớp thứ nhất, là 20ms.

Kích thước bánh xe của bánh xe thời gian thứ nhất và thứ hai là cố định, cả hai đều là 20, do đó khoảng thời gian chung của bánh xe thời gian thứ hai là 400ms. Nó gấp chính xác 20 lần vòng quay thời gian ở cấp độ đầu tiên. Tương tự như vậy, 400ms này cũng là kích thước của tickMs của lớp thứ ba và khoảng thời gian tổng thể của bánh xe thời gian của lớp thứ ba là 8000ms.

• Một vòng tròn của bánh xe thời gian thứ N tương đương với một lưới của bánh xe thời gian thứ N+1. Nghĩa là, khoảng thời gian của bánh xe thời gian cấp cao hơn bằng với khoảng thời gian chung của bánh xe thời gian hiện tại.

Chuyển đổi hạ cấp nhiệm vụ bánh xe thời gian phân cấp

Theo thời gian trôi qua, cũng sẽ có một hoạt động hạ cấp vòng thời gian. Các nhiệm vụ ban đầu bị trì hoãn lâu sẽ được gửi lại từ vòng thời gian cấp cao hơn đến vòng thời gian, sau đó sẽ được đưa vào vòng thời gian cấp thấp hơn phù hợp để chờ xử lý;

Giới thiệu trường hợp

Chuyển đổi nhiệm vụ nâng cấp bánh xe thời gian phân cấp

Ví dụ, đối với tác vụ được lên lịch 350ms, bánh xe thời gian lớp đầu tiên rõ ràng không thể đáp ứng các điều kiện, do đó, nó được nâng cấp lên bánh xe thời gian lớp thứ hai và cuối cùng được chèn vào TimeWheelTaskList tương ứng với lưới thời gian 17 trong bánh xe thời gian lớp thứ hai. Nếu có một tác vụ khác có bộ đếm thời gian là 450ms, thì bánh xe thời gian cấp độ hai rõ ràng không thể đáp ứng các điều kiện, do đó nó được nâng cấp lên bánh xe thời gian cấp độ ba và cuối cùng được chèn vào TimeWheelTaskList của lưới thời gian 1 trong bánh xe thời gian cấp độ ba.

Chuyển đổi hạ cấp nhiệm vụ bánh xe thời gian phân cấp

Nhiều tác vụ trong khoảng thời gian [400ms, 800ms) (chẳng hạn như các tác vụ được lên lịch 446ms, 455ms và 473ms) sẽ được đặt vào khe thời gian 1 của bánh xe thời gian cấp độ thứ ba. Khoảng thời gian chờ của TimerTaskList tương ứng với khe thời gian 1 là 400ms.

Theo thời gian, khi TimeWheelTaskList hết hạn, tác vụ ban đầu được lên lịch trong 450ms còn lại 50ms và hoạt động hết hạn của tác vụ này không thể được thực hiện.

Ở đây, có một hoạt động hạ cấp bánh xe thời gian, hoạt động này sẽ gửi lại tác vụ đã lên lịch với thời gian còn lại là 50ms cho bánh xe thời gian phân cấp. Vào thời điểm này, khoảng thời gian tổng thể của bánh xe thời gian cấp một là không đủ, nhưng cấp hai là đủ, do đó tác vụ được đặt trong lưới thời gian của bánh xe thời gian cấp hai với thời gian hết hạn là [40ms, 60ms).

Sau 40ms nữa, tác vụ lại được "phát hiện" lần nữa, nhưng vẫn còn 10ms nữa nên không thể thực hiện thao tác hết hạn ngay lập tức. Do đó, có một lần hạ cấp khác của bánh xe thời gian. Nhiệm vụ này được thêm vào lưới thời gian của lớp đầu tiên của bánh xe thời gian với thời gian hết hạn là [10ms, 11ms). Sau 10ms nữa, nhiệm vụ này thực sự đến hạn và hoạt động hết hạn tương ứng cuối cùng được thực hiện.

Xem trước chương tiếp theo

Tiếp theo, biên tập viên sẽ phát hành [Chủ đề đặc biệt về cấu trúc dữ liệu thuật toán] "Thuật toán hàng đợi trễ" để hướng dẫn bạn cách triển khai phát triển hàng đợi trễ cho bánh xe thời gian phân cấp (TimingWheel) (Phần 2) và tiến hành mã hóa thực tế để phát triển thuật toán bánh xe thời gian phân cấp tương ứng.

Cuối cùng, bài viết này về [Algorithm Data Structure Topic] "Delay Queue Algorithm" Teach you step by step to implement the development and implementation of delay queues for hierarchical timing wheels (TimingWheel) (Part 1) đã kết thúc. Nếu bạn muốn biết thêm về [Algorithm Data Structure Topic] "Delay Queue Algorithm" Teach you step by step to implement the development and implementation of delay queues for hierarchical timing wheels (TimingWheel) (Part 1), vui lòng tìm kiếm các bài viết trên CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .