Khi tôi bắt đầu lập kế hoạch để học về các kiến thức nền tảng cho công việc của mình, tôi mất 6 tháng đầu tiên để học code. Đầu tiên, tôi đã không đặt câu hỏi là "làm thế nào(how) nó hoạt động". Tôi chỉ cố gắng tìm hiểu cách nó hoạt động và cố gắng làm theo để code có thể chạy được.

 

Nhưng mà sau một vài tháng, tôi đã bắt đầu tự hỏi rằng "làm thế nào tất cả bọn nó đều có thể hoạt động". Đồng thời, ngay lúc này tôi đã bắt đầu cảm thấy choáng ngợp bởi những điều mới mẻ mà tôi được nhận những điều mà tôi chưa từng nghĩ tới trong tâm trí khi cố gắng thử trả lời câu hỏi "how" đó, thay vào đó tôi chỉ tập trung cố gắng làm cho code chạy được ngay.

 

Sau này, một năm sau, trong một cuộc phỏng vấn ở đâu đó, một người nào đó đã hỏi tôi về các công việc, các tác vụ và cách mà tôi nghĩ làm thế nào mà mọi thứ hoạt động. Tôi phỏng đoán, điều đầu tiên tôi nghĩ trong đầu và tôi đã nói rằng các công việc là sự trộn lẫn các đối tượng trong mảng bạn phải duyệt qua và hoàn thành rồi loại bỏ chúng sau khi thực hiện xong. Hóa ra, điều tôi phỏng đoán không xa với sự thật là mấy.

 

Điều mà tôi thích về abstraction(sự từu trượng) là thứ bạn bắt đầu tìm kiếm một mô hình từu trượng hóa trong hệ thống, ngôn ngữ, hay codebase, nó trở nên dễ dàng hơn nhiều để bắt đầu nhận ra rằng những khuôn mẫu(pattern) đó đã từng xuất hiện ở nơi khác. Và có những pattern đã được sử dụng rất nhiều trong phần mềm mà chúng tôi không cần phải nghĩ, quan tâm về chúng mặc dù chúng tôi sử dụng chúng rất nhiều. Một trong những abstraction là chúng đã được sử dụng để triển khai trong công việc, và đơn giản nhất là trong network request - chúng được gọi là queue. Và chúng có mặt ở tất cả mọi nơi.

 

Làm thế nào để thêm một đối tượng vào queue

Làm thế nào để bạn thêm một đối tượng vào queue

 

Các queue(hàng đợi) và stack (ngăn xếp) thường được dạy cùng nhau trong các khóa học về khoa học máy tính bởi vì chúng thực sự giống nhau, mặc dù cách sử dụng và triển khai là hoàn toàn khác nhau. Chúng tôi đã từng biết một chút về cách hoạt động của stack và làm thế nào chúng tôi có thể thêm và xóa các phần tử cho chúng từ một phía.

Đây là nơi mà các queue và stack khác nhau: chúng được cấu trúc và xây dựng theo cách khác nhau.

 

Phương thức enqueue(thêm) và dequeue(xóa) trong queue

 

Queue là một kiểu dữ liệu tuyến tính (theo hàng ngang) có thể chứa một danh sách rất dài các phần tử. Nhưng điều quan trọng khi nhớ về chúng là làm thế nào chúng có thể mở rộng và thu nhỏ kích thước.

 

Có một số thuật ngữ (term) mà chúng tôi có lẽ đã từng nghe trước đây nguồn gốc từ các thuật ngữ của việc thêm hay xóa các phần tử từ một cấu trúc queue. Quá trình xử lý việc thêm một phần tử vào một queue gọi là enqueuing, khi mà xóa một phần tử từ một queue thì đó là dequeuing. Điều thú vị về queue là nơi mà enqueuing và dequeuing xảy ra(ở vị trí nào trong queue).

 

Các queue đều tuân theo nguyên tắc FIFO(first-in, first-out)

Nêu chúng ta nghĩ các queue trong một cửa hàng bán thức ăn ngon mọi thứ thường bắt đầu quy trình thế này: bạn lấy một số và xếp hàng để đợi đến lượt mình được gọi. Người đến trước sẽ là người được phục vụ trước. Đấy là điều thực tế, có đúng không?

 

Tương tự cho cấu trúc dữ liệu queue: phần tử đầu tiên phía trước của queue là phần tử đầu tiên được phục vụ hay ở các trường hợp cụ thể nó được xử lý, sử dụng, thực thi là phụ thuộc vào "phần tử đó là gì".

Trong phần lớn các trường hợp queue hoạt động theo nguyên tắc first-in, first-out. Phần tử đầu tiên trong queue hay phần tử phía trước queue luôn luôn được xử lý và xóa khỏi queue đầu tiên.

 

Nếu chúng ta đã không nhớ mọi thứ về sự khác biệt về queue và stack, thì chỉ cần nhớ một điều quan trọng về sự khác biệt giữa chúng đó là: stack là cấu trúc last-in, first-out (LIFO) trong khi queue là cấu trúc first-in, first-out (FIFO).

 

Queue và danh sách liên kết(linked list): chúng là bạn tốt của nhau

 

Một lý do để các queue và stack có xu hướng đi song song cùng với nhau là chúng tôi sử dụng các function, phương thức tương tự để xây dựng cả hai loại dữ liệu. Ví dụ, cả hai đều có tên function khác nhau nhưng lại thực hiện chức năng như nhau:

  1. function push của stack lại tương tự với function enqueue của queue
  2. function pop của stack lại tương tự với function dequeue của queue
  3. sizeisEmpty là những function chung để kiểm tra kích thước

 

Tuy nhiên có một lý do khác để giải thích tại sao queue và stack đi cùng và đan xen lẫn nhau: cả hai đều có thể thực hiện như một array hay như một linked list.

 

Như chúng ta đã biết, triển khai một stack dưới dạng array có thể dẫn đến tình trạng tràn stack nếu như các element được push vào stack lớn hơn kích thước giới hạn của stack đó có thể xử được. Vì vậy khi nói đến queue, sẽ được điều gì?

 

Array rất mạnh mẽ khi chúng ta biết trước được kích thước của cấu trúc dữ liệu (tức là biết trước được độ dài của mảng). Nhưng có rất nhiều lúc (trong trường hợp này là queue) khi mà chúng ta không biết kích thước và kích thước của một queue sẽ lớn đến một mức nào. Vậy chuyện gì sẽ xảy ra khi chúng ta enqueue một element vào queue? Được thôi, nếu chúng ta không biết trước kích thước của queue và chúng ta lại sử dụng array, có lẽ sớm hay muộn thì chúng ta sẽ bị thiếu bộ nhớ và không có không gian bộ nhớ để cấp phát. Vì vậy chúng tôi cần sao chép tất cả các content của mảng của chúng tôi sau đó cấp phát thêm không gian và memory rồi sau đó mới enqueue một element mới vào cuối queue.

 

Nhưng khi triển khai queue dựa trên array sẽ xuất hiện các vấn đề phức tạp khác: chúng ta cần enqueue ở cuối của array, và dequeue ở đầu array - không phải lúc nào cũng quá khủng khiếp vì việc truy cập vào phần tử đầu hoặc cuối của một mảng không tốn quá nhiều thời gian, nhưng nó lại không đơn giản với stack, nơi việc thêm hay xóa một phần tử luôn xảy ra ở đầu cấu trúc. Khi mà kích thước của array lớn dần, chúng ta cần phải truy cập giữa 2 đầu của mảng như vậy độ phức tạp về thời gian sẽ tăng vì thời gian duyệt các phần tử tăng theo độ dài của mảng(phải duyệt từ đầu đến cuối).

 

Triển khai array và triển khai một danh sách liên kết của các queue

 

Tuy nhiên, với việc thực hiện linked list (danh sách liên kết) của một queue, mọi thứ trở nên đơn giản hơn rất nhiều. Đầu tiên, chúng ta không phải lo lắng về kích thước của queue, khi bộ nhớ có thể phân phối và việc triển khai linked list của một queue có thể phát triển động (miễn là chúng tôi không sử dụng tất cả các bộ nhớ của máy tính). Enqueuing và dequeuing trở nên dễ dàng bởi vì chúng ta có thể dễ dàng tìm một vùng trống trong bộ nhớ và thêm một node có tham chiếu đến phần tử kế tiếp bên cạnh nó. Không cần phải sao chép và tạo lại queue như cách khi triển khai array. Và nếu chúng ta thêm một tham chiếu trỏ vào đầu và cuối danh sách của chúng ta, chúng ta không cần phải duyệt qua toàn bộ cấu trúc để enqueue hoặc dequeue.

 

Trong thực tế khi bạn loại bỏ đi sự cần thiết khi duyệt qua toàn bộ phần tử trong queue, độ phức tạp vể thời gian của các hàm enqueue và dequeue trên một queue sẽ không đổi hay đó là O(1); điều đó nói rằng, không có vấn đề gì khi xử lý một queue lớn hay nhỏ, số lượng thời gian cần để thêm hoặc xóa một phần tử vẫn giữ nguyên không đổi.

 

Tất nhiên, nó hoàn toàn hợp lệ để triển khai cả stack và queue trong cả array và linked list. Nhưng điều quan trọng là phải nhận ra sự khác biệt giữa hai cách triển khai này khi nào cần sử dụng cho hợp lý.

 

Hidden line, bí mật về queue

 

Bây giờ chúng ta đã biết cách hoạt động của queue, điều khác biệt giữa chúng với stack và khi nào và cách nào để chúng ta có thể triển khai chúng, hãy trả lời cầu hỏi lớn hơn ở đây:  tại sao lại có vấn đề quan trọng này?

Vâng, nó thực sự rất quan trọng. Lý do là: queue có khắp mọi nơi. Chúng ở xung quanh chúng ta. Chúng ta chỉ cẩn xem xét kỹ hơn cách thức thực sự mà chúng ta làm việc với chúng mỗi ngày.

 

Nếu là bạn là một backend developer, bạn thường phải lên lịch cho các công việc, các task vụ hay phải chia nhỏ các quy trình các công việc khác nhau. Việc bạn lên lịch trình để hoàn thành công việc hay các task vụ công việc tại các thời điểm chính là bạn thực hiện theo cấu trúc FIFO - công việc đầu tiên sẽ thêm vào lịch trình và sẽ xóa khỏi lịch trình nếu nó được hoàn thành cho đến khi lịch trình trống tức là công việc đã được xử lý hết.

 

Nếu bạn là một frontend developer, có lẽ bạn đã từng làm việc với jQuery, thậm chí bạn đã từng tạo các animation với các API mà jQuery cung cấp. Các API của jQuery sử dụng các queue cho phép một loạt các function được thực thi đồng bộ (asynchronous) trên các phần tử của DOM và xây dựng các step như trong queue để chuyển tiếp từ giá trị CSS này sang giá trị CSS khác để tạo các animation mượt mà. Trong thực tế các API jQuery như một dequeue() function cho phép bạn di chuyển các element này trong queue sang queue tiếp theo.

 

Nhưng nó không chỉ tồn tại trong cuộc sống của chúng ta (là các nhà phát triển ) hay trong các codebase nơi xuất hiện các vấn đề về queue. Nó cũng tồn tại trong chính máy tính cá nhân của bạn.

 

Khi phần mềm chạy, hệ điều hành của bạn có queue riêng để chứa các quy trình xử lý. Nhưng nhìn chung nó không phải chạy qua các list xử lý tại các thời điểm, thay vào đó máy tính của bạn sẽ chạy các xử lý khác nhau theo các độ ưu tiên tại các thời điểm. Đôi khi, điều này được thực hiện như một multilevel priority queue(queue ưu tiên), trong đó các lịch trình được sắp xếp theo thứ tự ưu tiên và các queue được thực hiện dựa trên mức độ quan trọng của chúng.

 

Multilevel, hệ thống chỉ định, queue ưu tiên

 

Ví dụ, một queue về xử lý hệ thống (system process) thường sẽ ưu tiên hơn một queue về background process, do đó, queue cuả background process sẽ phải đợi đến khi queue của xử lý hệ thống đã chạy và được thực hiện đầy đủ cho đến khi hàng đợi tiếp theo có thể bắt đầu thực hiện.

 

Nhưng hãy nhìn rộng hơn nữa, ở mức độ vĩ mô, các queue sẽ trông như thế nào. Vâng, nó không chỉ là các máy tính cá nhân của chúng ta chạy các queue đồng thời tại mọi thời điểm mà là các máy chủ trên khắp thế giới (chạy nhiều ứng dụng khác nhau và được xây dựng khắp nơi) tất cả đều xử lý mọi thứ bằng cách sử dụng ... như bạn có thể đoán đó là các queue.

 

Khi mà nhiều (hàng trăm hoặc hàng trăm nghìn) ứng dụng yêu cầu hay gửi dữ liệu đến một máy chủ của ứng dụng, máy chủ có thể bị quá tải với nhiều yêu cầu được gửi đến một lúc. Bạn có tự hỏi là làm thế nào mà nó có thể xử lý những yêu cầu đó? Và làm thế nào mà nó có thể xử lý được chúng...?

 

Vâng, một phương pháp điên rồ đó là queue. Các request (yêu cầu) được đưa vào hàng đợi trước khi được ứng dụng xử lý

Hàng đợi request là tốt nhất!

 

Ví dụ, nếu hàng trăm người cố gắng truy cập vào trang web của Amazon vào dịp Black Friday như vậy một loạt các yêu cầu sẽ gửi đến một máy chủ duy nhất. Máy chủ đó sẽ xử lý tất cả các yêu cầu đó bằng cách enqueuing chúng, từng yêu cầu một vào một queue của các request đang đến (incoming request queue). Từng yêu cầu một, các yêu cầu đó sẽ được đưa vào ứng dụng và được xử lý trước. Và khi đến lúc phản hồi lại các yêu cầu đó, hệ thống sẽ đưa ra các phản hồi theo thứ tự mà chúng xử lý (request nào vào trước, xử lý trước rồi trả về phản hồi trước) trong một queue của request gửi đi.

 

Khá tuyệt vời khi mà bạn nghĩ về nó phải không. Một cấu trúc queue đơn giản là thứ được chiếm ưu thế trên web, làm cho tất cả phần mềm hoạt động và điều mà queue làm được là làm cho internet hoạt động trơn tru.

 

Bài viết được dịch từ medium.com-basecs