使用go的并發(fā)性來解決Hilbert酒店問題
Hilbert酒店
Hilbert酒店是一個與無限有關(guān)的問題。
假設(shè)Hilbert是一個酒店的所有者，且該酒店有無限個房間。
一天一個大巴達到了Hilbert的酒店，假設(shè)大巴上有無限個旅客想要住在Hilbert的酒店，假設(shè)Hilbert的酒店有無限個房間，因此能夠容納無限個旅客。
但有一天有無限輛大巴達到了Hilbert的酒店，每輛大巴上載有無限個旅客，且所有大巴的旅客都要在酒店過夜。
Hilbert想了一會說"沒問題"，然后他畫了一個數(shù)字三角形，然后把房間的鑰匙遞給沿著三角形對角線的所有乘客。通過這種方式，Hilbert能夠給每輛大巴的每個乘客一把唯一的鑰匙。
Hilbert酒店的非并發(fā)算法
我們可以通過重復Hilbert的做法來解決Hilbert酒店問題。
例如，可以創(chuàng)建數(shù)組的數(shù)組來代表三角形的數(shù)字，然后遍歷該數(shù)組的數(shù)組來構(gòu)建對角線并沿著對角線將房間鑰匙交給每輛大巴的乘客。文章末給出了這種方式的實現(xiàn)，當然也存在其他的非并發(fā)實現(xiàn)。下面換個角度看下這個問題。
Hilbert酒店的遞歸并發(fā)算法
遞歸并發(fā)算法中，每輛大巴所需的鑰匙位于三角形的最右側(cè)對角線。對角線中的鑰匙所在的位置等于三角形高度，這一點就是判定某把鑰匙是不是本大巴的關(guān)鍵。
假設(shè)Hilbert的酒店中有無限個雇員，每個雇員負責給一輛大巴的所有旅客發(fā)放鑰匙。負責第一輛大巴的雇員(Bus 1 Clerk)靠近負責第二輛大巴的雇員(Bus 2 Clerk)，負責第二輛大巴的雇員(Bus 2 Clerk)靠近負責第三輛大巴的雇員(Bus 3 Clerk)，以此類推。
此外還有一個雇員(Room Key Clerk)，他負責將所有房間的鑰匙依次交給第一個雇員(Bus 1 Clerk)，即房間一是第一把鑰匙，房間二是第二把鑰匙，房間三是第三把鑰匙，以此類推。
(從Room Key Clerk接收到鑰匙的)Bus 1 Clerk知道接收到的第一把鑰匙是給他負責的大巴的第一個乘客，因此Bus 1 Clerk會為第一輛巴士的第一位乘客準備一號房間的含鑰匙在內(nèi)的歡迎禮包(welcome kit)，此外他還知道接收到的第二把鑰匙不是給他負責的大巴的，而是給下一個雇員的，第三把鑰匙是給Bus 1的，因此由Bus 1 Clerk負責，但第四把和第五把鑰匙不是給Bus 1的，因此Bus 1 Clerk會將它們傳給下一個雇員。當歡迎禮包發(fā)放給Bus 1的所有乘客之后(此時需要假設(shè)顧客是有限的，防止程序無法結(jié)束)，Bus 1 Clerk會將它們返還給Hilbert。后面將會看到，將鑰匙還給Hilbert是一個有用的步驟，可以并發(fā)實現(xiàn)最終的類似reduce的操作。
下一個雇員Bus 2 Clerk的行為和第一個雇員相同，他知道接收到的第一個鑰匙需要交給他負責的大巴的第一個乘客，而第二把鑰匙則需要交給下一個雇員，以此類推。
在某種程度上，由于我們的程序不能像原來的Hilbert問題那樣永遠繼續(xù)下去，因此需要能夠停止移交鑰匙，并通知所有雇員停止工作。此時需要將雇員準備的歡迎禮包還給Hilbert。最終，所有的雇員都會停止工作，并在Hilbert接收到準備好的歡迎禮包之后就可以通知Hilbert也停止工作。
Go實現(xiàn)
這里提供了一個Go實現(xiàn)的并發(fā)算法。使用goroutine來代表每一個角色，包括Hilbert和雇員。
Hilbert是主goroutine，用于啟動整個流程并收集大巴雇員創(chuàng)建的歡迎禮包
Key Handler Clerk是一個由Hilbert啟動的goroutine，負責依次一系列房間鑰匙，并交給Bus 1 Clerk，直到達到鑰匙上限
Bus 1 Clerk是另一個由Hilbert啟動的goroutine，它從Key Handler Clerk接收鑰匙，并實現(xiàn)對應的邏輯：為自己負責的大巴準備歡迎禮包，并將其他鑰匙交給下一個雇員
Bus 2 Clerk是由Bus 1 Clerk啟動的goroutine，處理邏輯和Bus 1 Clerk相同
其他Bus Clerks都執(zhí)行相同的邏輯，每一個都是一個獨立的goroutine，且共享相同的代碼
下面是Hilbert的實現(xiàn)：
func Hilbert(upTo int) {
? keysCh := make(chan int) ? go RoomKeysClerk(upTo, keysCh) ?//1
? make(chan []hilberthotel.WelcomeKit) ? go BusClerk(1, keysCh, welcomeKitCh) //2
? for envelope := range welcomeKitCh { //3
? ? ? fmt.Println(envelope)
? }
}
其代碼比較簡單，入?yún)?code>upTo表示房間鑰匙的上限：
首先它會為鑰匙創(chuàng)建channel?
keysch，并使用keysch作為參數(shù)來啟動Room Key Clerk的goroutine。然后它會創(chuàng)建另一個channel?
welcomeKitCh(雇員會從該channel中接收鑰匙，并在雇員結(jié)束工作后發(fā)送歡迎禮包)，用于接收Welcome Kits(歡迎禮包)，并使用keysch和welcomeKitCh作為參數(shù)來啟動第一個BusClerk(大巴雇員)最后，它會通過
welcomeKitCh循環(huán)接收雇員準備的禮包
Room Key Clerk 的實現(xiàn)也很簡單，它通過keysCh將鑰匙分發(fā)出去，在鑰匙到達上限upTo之后，關(guān)閉keysCh：
func RoomKeysClerk(upTo int, keysCh chan<- int) { ? for i := 0; i < upTo; i++ {
? ? ? keysCh <- i + 1
? } ? close(keysCh)
}
Bus Clert的實現(xiàn)要復雜一些：
func BusClerk(busNumber int, roomKeysCh <-chan int, welcomeKitsCh chan<- []hilberthotel.WelcomeKit, buffer int, delay time.Duration) { //1
? var count = 0 ? ? ? ? ? ? ? ? ?//2
? var keyPosition = 0
? var nextClerkCh chan int
? welcomeKits := []hilberthotel.WelcomeKit{} ? for roomKey := range roomKeysCh { ? ? ? if nextClerkCh == nil { ? ?//3
? ? ? ? ? nextClerkCh = make(chan int, buffer) ? ? ? ? ? go BusClerk(busNumber+1, nextClerkCh, welcomeKitsCh, buffer, delay)
? ? ? } ? ? ? if count == keyPosition { ?//4
? ? ? ? ? kit := hilberthotel.NewWelcomeKit(busNumber, keyPosition, roomKey, delay)
? ? ? ? ? welcomeKits = append(welcomeKits, kit)
? ? ? ? ? keyPosition++
? ? ? ? ? count = 0
? ? ? ? ? continue
? ? ? }
? ? ? nextClerkCh <- roomKey
? ? ? count++
? } ? if nextClerkCh != nil { //5
? ? ? welcomeKitsCh <- welcomeKits ? ? ? close(nextClerkCh)
? } else { ? ? ? close(welcomeKitsCh) //6
? }
}
每個Bus Clert對應一個goroutine。BusClerk的第一個參數(shù)是其所屬的大巴號，
welcomeKitCh?用于在處理結(jié)束之后發(fā)送歡迎禮包(welcomeKits)，roomKeysCh用于讀取鑰匙號在初始化內(nèi)部計數(shù)器
count之后，使用一個變量keyPosition來保存下一個乘客的鑰匙位置，使用channel?nextClerkCh通知下一個BusClerk。通過循環(huán)讀取roomKeysCh來啟動整個處理邏輯。在接收到第一個鑰匙之后，此時
nextClerkCh為nil，之后會初始化nextClerkCh并啟動下一個BusClerk對比
count和keyPosition，用于確定此時的鑰匙是給本大巴的還是給其他大巴的。當鑰匙是給本大巴的，它會創(chuàng)建一個WelcomeKit并將其保存在它的集合中，反之，將鑰匙傳給下一個BusClerk當鑰匙接收完之后(即
roomKeysCh被關(guān)閉)，它會關(guān)閉用于通知下一個BusClerk的nextClerkCh?channel最后一個BusClerk將不會再接收到任何房間鑰匙，因此它會關(guān)閉
welcomeKitCh并通知Hilbert其將結(jié)束任務
相對獨立的處理流程
上述解決方案基于"相對獨立"的處理流程：
Room Key Clerk的任務
相對獨立于Bus Clerk 1，這里說的"相對獨立"并不是完全獨立，因為Room Key Clerk還需要等待Bus Clerk 1從keyCh?channel接收鑰匙(即使用了帶緩存的 keysCh channel，緩沖區(qū)仍然會被填滿，從而迫使 Room Key Clerk 等待Bus Clerk 1從通道讀取數(shù)據(jù))類似地，Bus Clerk 1也會依賴Bus Clerk 2來從它們共享的keysCh中讀取數(shù)據(jù)，以此類推
最終，所有的Bus Clerk 都會依賴Hilbert從
welcomeKitCh?channel中接收welcomeKits
因此，我們可以說所有的Bus Clerk和Hilber執(zhí)行的都是"相對獨立"的邏輯，需要通過調(diào)整channel的發(fā)送/接收來達到期望的結(jié)果。
并發(fā)是有代價的，但啟用并行可以帶來好處
雖然我們的并發(fā)設(shè)計實現(xiàn)的方案很優(yōu)雅，但它也帶來了如下開銷：
生成的goroutine數(shù)目等于大巴的數(shù)目 + Hilbert + Room Key Clerk
需要不斷在可用的核上調(diào)度goroutines
需要初始化和goroutines一樣多的channels
需要通過這些channels執(zhí)行發(fā)送和接收操作
另一方面，這種設(shè)計的好處在于，如果在多核硬件上運行該并發(fā)算法，算法中固有的并行邏輯會帶來性能上的提升。
并發(fā)goroutine的任務越重，并行的提升幅度越大
每個大巴雇員都有一些核心的工作需要完成，此外還有一些并發(fā)編排的工作(即配置goroutine和通過channel發(fā)送/接收鑰匙)。
并行可以提升核心工作的性能。在Hilbert的例子中，核心工作就是為每個客戶準備歡迎禮包(即函數(shù)NewWelcomeKit執(zhí)行的內(nèi)容)。能夠并行執(zhí)行的核心工作越多，就越能在相同的時間內(nèi)服務更多的顧客。
為了實現(xiàn)并行處理，我們需要執(zhí)行一些并發(fā)編排工作。與并發(fā)編排工作相比，核心工作占主導地位越高，從并行性中獲得的好處就越多。在Hilbert的例子中，每個大巴雇員的核心工作是準備歡迎禮包。因此，準備歡迎禮包的工作占比越高，多核硬件上運行并發(fā)設(shè)計的效率就越高。另一方面，處理的顧客越多，并發(fā)編排工作也就越重(由于需要在更多的goroutines之間進行切換和發(fā)送/接收鑰匙)，因此并發(fā)的成本也會越高。
可以使用樣例代碼提供的benchmarks，通過變更顧客數(shù)目來對性能進行驗證。
附錄
也可以使用上面所使用的并發(fā)方案的基本設(shè)計導出非并發(fā)遞歸方案：
將RoomKeysClerk 轉(zhuǎn)變?yōu)橐粋€生成鑰匙并將其傳遞給第一個BusClerk的循環(huán)
使用閉包(即一個封裝了上下文狀態(tài)的函數(shù)(當前計數(shù)器，keyPosition和 nextClerk))來實現(xiàn)BusClerk，
使用Hilbert函數(shù)用來觸發(fā)整個執(zhí)行邏輯，并收集各個BusClerk構(gòu)造的welcomeKits
