佇列(Queue)的概念似乎抽象,但在生活中無所不在。我們看演唱會進場要排隊、購買甜甜圈也要排隊、甚至連上廁所都可能需要排隊,而排隊就是佇列具體展現的行為。

在作業研究(Operation Research)的領域裡,有一個學科稱為「排隊理論(Queuing Theory)」,即在透過建構數學模型的方式,來探討排隊--即佇列應用時的行為及現象。在排隊理論裡,關心的課題包括在應用佇列或稱等候線(waiting line)時,佇列的長度、排隊請求所花費的排隊時間,以及排隊的公平性、…… 等等。

從排隊理論來看佇列的應用模型
排隊理論將排隊予以模型化,透過指定一些參數,我們可以建構出我們應用佇列時的模型。在一個排隊模型中會有三種重要的元素(1)到達系統的服務請求:代表系統必須完成的工作(2)伺服器:有能力完成服務請求(3)佇列:當伺服器處於忙碌、即正在處理一個服務請求時,已抵達系統的服務請求,就會在佇列中排隊,等待服務器空出來。

在建構排隊的模型時,會有那些參數呢?
它包括了:(1)服務請求到達的規則、(2)完成服務請求之時間的規則(3)總共有幾個伺服器(4)總共有幾個佇列(5)決定服務佇列中那一個請求的方式、……等等。

這裡所謂服務請求到達的規則,主要代表服務請求抵達系統的特性。它可能是個機率的分布,它或許很簡單,只是個均勻的機率分布,有個平均到達系統的時間。

不過,通常沒有這麼簡單。有時候,我們會說,我們的系統平均每秒會有多少個請求進來,就是在描述服務請求抵達系統的特性,但每秒有多少個請求這件事,並不是那麼持續、均勻地發生。真實的系統,可能會有尖峰時間,也會有離峰時間,服務請求到達系統的時間特性,就沒那麼單純。

相對於服務請求到達系統的規則,同樣的伺服器完成服務請求的時間,也不一定是固定的,它也可能是個機率的分布。即使伺服器的能力固定,有些工作很快可以完成,有些工作卻要花上很多的時間才能完成。

就像是單純從快取回傳資料,就是個比較快的工作,但是,從資料庫做大規模查詢,則是個較慢的工作。

一個系統可能有多個伺服器,而不是固定一個,當然佇列數量也是。而佇列的排隊方式不一定得是先到先服務,也可能是依據優先序來決定服務的先後順序,或甚至是隨機,擇一服務。

讓我們舉一個生活上的例子:一個廁所中可能有四個房間,代表它有四個伺服器,用戶想上廁所時可以是排一個隊伍,只要任一個房間空出來,就可以進去上。不過用戶也可以排成四個隊伍,要等到自己所排的那個房間空出來才可以進去上。因為模型的參數之一──佇列個數不同,就形成了不同的模型。

對應到軟體的網站系統,在系統中可以有四個伺服器、四個佇列。因此,服務請求會平均分配到四個伺服器去,當伺服器可能處於忙碌而無法處理時,對應的佇列就會記錄這個請求,直到伺服器有空閒處理為此。當然,系統也可以是單一佇列,所有的請求都會進到這個佇列,之後才分配到有空閒的伺服器上。這兩種模型,就有可能產生不同的排隊結果。

在前一回中,我們提到在佇列的應用中,「利用佇列來做資源配置的最佳化」是一個重要的應用。從排隊的模型我們可以很容易明白,大抵想要提高服務品質,增加伺服器的個數是主要的方法。但是,如果想要減少提供服務時所付出的成本,最有效的方式就是減少伺服器的個數,而這兩個目標剛好是相衝突的。

過與不及之間的拿捏

大抵資訊系統中,都有很多相衝突的因素,就像我們都熟知的,時間和空間通常是衝突的。我們會用空間換取時間,或是用時間換取空間。服務的品質和服務的成本也是一樣,我們可能選擇犧牲服務的品質,來換取提供服務的成本,或是選擇提高服務的成本,來提升服務的品質。

然而,真正的應用,多半是在品質和成本之間,拿捏一個平衡點。

我們對於品質會有一定的要求,但是不會無止盡地追求百分之百的品質,就像我們可能認為每個網頁的回應時間,都能控制在兩秒或三秒之內就好。我們不會想要無止盡地增加伺服器,以便使每個網頁的回應時間都在一秒以內。對於不同的應用、在不同的情境,我們對於服務品質及成本的要求及標準都不同。

只不過,想要更好的品質,通常就付出更多的成本,想要節省成本,通常就得犧牲一些服務的品質。因此,必須自己決定究竟要如何做取捨,找到其中的平衡點。

怎麼去控制自己想要的平衡點究竟落在何處?佇列就是一種控制的方式。

如果你有成本的限制條件,你可以倒算回自己究竟只能提供多少伺服器,接著你就可以得到一個排隊的模型,便可以估算每個服務請求在佇列中,究竟會花費多少的等待時間,才能得到服務,並且完成請求。而上述等待的時間,就是服務品質中重要的一環。

因此,你可以決定增加伺服器的個數來降低等待的時間,也可以選擇降低伺服器的個數來降低服務的成本,端視你覺得平衡點應該在何處。所以,佇列是一個允許你控制服務品質及服務成本平衡點的機制,透過佇列讓服務請求於其中排隊,便可以藉以控制。

在佇列的應用中,讓待完成的工作進入佇列中排隊,藉此取得服務品質及服務成本平衡點的這種佇列,通常被稱為工作佇列(Job Queue),而用來做非同步通訊的佇列則被稱為訊息佇列(Message Queue)。

即使應用不同,但其實它們在本質上是一樣的。首先,佇列的重要特性就是非同步,因此,對工作佇列而言,消化工作的速率,不一定要和工作抵達系統的速率匹配。

同樣地,對於訊息佇列而言,訊息被發送進來系統的速率,不一定要和訊息被從系統中接收的速率匹配。

所以對工作佇列來說,即使工作抵達系統的速度「有時候」會高過伺服器消費工作的速度,但是因為畢竟系統不是持續處於尖峰的負載,所以透過佇列中排隊的機制將工作「暫存起來」,使得伺服器還是可以接著把工作完成。

而對於訊息佇列而言,訊息的發送者不必一定要和訊息的接收者,同時在線上,而且一旦發出就立即被接收。

之所以可以有這非同步的特質,都是因為佇列本身具有「緩衝」的特性,得以將工作或訊息暫存在佇列之中。

即使因為短暫的伺服器消化速率,不及服務請求抵達系統的速率,只要長期來說,平均的服務速率大過請求速率,整個系統就不會進到佇列長度持續增加的情況。

也因為具有「非同步」和「緩衝」的特性,使得佇列成為資訊服務系統中重要的組成。

下一回中,我們會實際探討一個應用的實例,藉以介紹佇列對於想高度擴展服務規模的系統來說,究竟有多重要。

作者簡介


Advertisement

更多 iThome相關內容