寫寫Code / 技術

原始slide在這裡。原文的範例缺了一些東西以致於compile起來會錯誤，我把缺的東西順手補上去，以及補上一些我這邊的心得跟額外的測試方法。

範例 : Google Search

  • Google Search是幹嘛的
    • 給一個query string，回傳搜尋結果（也許還加些廣告）
  • 我們要怎麼得到搜尋結果
    • 分別送query string到Web/Image/Youtube/Map/News…等搜尋引擎，然後把結果合併起來

我們要怎麼implement這個系統?

先來Mockup這個系統的樣子吧

我們用fakeSearch來模擬一個Server，這個server可能會很快即時的反應，也可能最多會在100ms以後才反應。

var (
    Web = fakeSearch("web")
    Image = fakeSearch("image")
    Video = fakeSearch("video")
)

type Search func(query string) Result
type Result string

//第一個版本的google search, 最直觀
func Google(query string) (results []Result) {
	results = append(results, Web(query))
	results = append(results, Image(query))
	results = append(results, Video(query))
	return
}

func fakeSearch(kind string) Search {
        return func(query string) Result {
        //模擬Server延遲
              time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
              return Result(fmt.Sprintf("%s result for %q\n", kind, query))
        }
}

測試一下這個mock能不能work

func main() {
    rand.Seed(time.Now().UnixNano())
    start := time.Now()
    results := Google("golang")
    elapsed := time.Since(start)
    fmt.Println(results)
    fmt.Println(elapsed)
}

Google Search 1.0

1.0就是我們放在mockup裡面的那個版本，google會去各種來源搜尋結果，然後把它給合併起來傳回去。

func Google(query string) (results []Result) {
	results = append(results, Web(query))
	results = append(results, Image(query))
	results = append(results, Video(query))
	return
}

Google Search 2.0

1.0顯然有些問題，他的query都是要等上一個query完成以後才能啟動，所以整個程序會被阻塞好一陣子。這個實作不需要鎖，沒有conditional variable，也不需要callbacks

func Google(query string) (results []Result) {
    c := make(chan Result)
    go func() { c <- Web(query) } ()
    go func() { c <- Image(query) } ()
    go func() { c <- Video(query) } ()

    for i := 0; i < 3; i++ {
        result := <-c
        results = append(results, result)
    }
    return
}

Google Search 2.1

那要是我們設定一個timeout呢?

    c := make(chan Result)
    go func() { c <- Web(query) } ()
    go func() { c <- Image(query) } ()
    go func() { c <- Video(query) } ()

    timeout := time.After(80 * time.Millisecond)
    for i := 0; i < 3; i++ {
        select {
        case result := <-c:
            results = append(results, result)
        case <-timeout:
            fmt.Println("timed out")
            return
        }
    }
    return

但是顯然的，drop掉太慢的search其實不太好。假設Server回應時間就是0-100之間，而太慢的response就是會被drop掉，那有沒有什麼方法能拿到完整的result呢？

Google Search 3.0

解決drop過慢result的問題

要解決2.1的問題其實也不難，我們對同一個服務（比方說Video）做出多個request，取其中最快的一個就可以了 — 這也是google目前的做法，所以大家知道為什麼搜尋那麼耗電了吧….

func First(query string, replicas ...Search) Result {
    c := make(chan Result)
    searchReplica := func(i int) { c <- replicas[i](query) }
    for i := range replicas {
        go searchReplica(i)
    }
    return <-c
}

func main() {
    rand.Seed(time.Now().UnixNano())
    start := time.Now()
    result := First("golang",
        fakeSearch("replica 1"),
        fakeSearch("replica 2"))
    elapsed := time.Since(start)
    fmt.Println(result)
    fmt.Println(elapsed)
}

所以3.0實作大概會長這樣

記得要先在上方額外宣告Web2/Image2/Video2

var (
	Web = fakeSearch("web")
	Image = fakeSearch("image")
	Video = fakeSearch("video")
	Web2 = fakeSearch("web")
	Image2 = fakeSearch("image")
	Video2 = fakeSearch("video")
)

然後3.0會是長這樣

    c := make(chan Result)
    go func() { c <- First(query, Web, Web2) } ()
    go func() { c <- First(query, Image, Image2) } ()
    go func() { c <- First(query, Video, Video2) } ()
    timeout := time.After(80 * time.Millisecond)
    for i := 0; i < 3; i++ {
        select {
        case result := <-c:
            results = append(results, result)
        case <-timeout:
            fmt.Println("timed out")
            return
        }
    }
    return

3.0還有什麼問題呢?

這個留作Bonus給大家參考一下。3.0有一個相當明顯的bug就是，當First後面的所有Search都大於80的時候，會導致掉結果。比方說，c <- First(query, Image, Image2)當後面兩個回應速度都比80慢（設定上他們速度是0-100），該結果就不見了，你會看到印出timed out。

所以我們還可以研究看看 :

  • 如何避免掉資料？
  • 如何在掉資料的時候動態把容忍值拉高？好處跟壞處分別是？
  • 或者換個方法，如何動態增加replica？好處跟壞處分別是？在現實生活中，動態增加replica的話，應該要注意什麼條件？
  • 事實上網路連線速度並非fakeSearch這樣的穩定在兩個數值中間徘徊，有沒有更好的模型可以模擬一段好一段壞的不穩定網路？甚至package drop?

如果要測試這個極端狀態的話，我們可以把timeout := time.After(80 *time.Millisecond)的80改成一個更小的數字，比方說40。或者說，我們可以把fakeSearch的response time動態拉到一個更大的範圍，就可以很容易重現出這個掉資料的狀態。

來比較一下1.0 2.0 3.0的效能

demo code如下，結果大約會像是這樣

Function : main.Google1 Total time : 1639 Avg time : 163 Function : main.Google2 Total time : 712 Avg time : 71 Function : main.Google3 Total time : 550 Avg time : 55

package main

import (
	"fmt"
	"math/rand"
	"reflect"
	"runtime"
	"time"
)

var (
	Web = fakeSearch("web")
	Image = fakeSearch("image")
	Video = fakeSearch("video")
	Web2 = fakeSearch("web")
	Image2 = fakeSearch("image")
	Video2 = fakeSearch("video")
)

type Search func(query string) Result
type Google func(query string) []Result
type Result string

func fakeSearch(kind string) Search {
	return func(query string) Result {
		time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
		return Result(fmt.Sprintf("%s result for %q\n", kind, query))
	}
}

func Google1(query string) (results []Result) {
	results = append(results, Web(query))
	results = append(results, Image(query))
	results = append(results, Video(query))
	return
}

func Google2(query string) (results []Result) {
	c := make(chan Result)
	go func() { c <- Web(query) } ()
	go func() { c <- Image(query) } ()
	go func() { c <- Video(query) } ()

	for i := 0; i < 3; i++ {
		result := <-c
		results = append(results, result)
	}
	return
}

func Google21(query string) (results []Result) {
	c := make(chan Result)
	go func() { c <- Web(query) } ()
	go func() { c <- Image(query) } ()
	go func() { c <- Video(query) } ()

	timeout := time.After(80 * time.Millisecond)
	for i := 0; i < 3; i++ {
		select {
		case result := <-c:
			results = append(results, result)
		case <-timeout:
			fmt.Println("timed out")
			return
		}
	}
	return
}

func First(query string, replicas ...Search) Result {
	c := make(chan Result)
	searchReplica := func(i int) { c <- replicas[i](query) }
	for i := range replicas {
		go searchReplica(i)
	}
	return <-c
}

func Google3(query string) (results []Result) {
	c := make(chan Result)
	go func() { c <- First(query, Web, Web2) } ()
	go func() { c <- First(query, Image, Image2) } ()
	go func() { c <- First(query, Video, Video2) } ()
	timeout := time.After(80 * time.Millisecond)
	for i := 0; i < 3; i++ {
		select {
		case result := <-c:
			results = append(results, result)
		case <-timeout:
			fmt.Println("timed out")
			return
		}
	}
	return
}

func Benchmark(google Google) (output []Result, start time.Time, elapsed time.Duration) {
	start = time.Now()
	output = google("golang")
	elapsed = time.Since(start)
	return
}

func GetFunctionName(i interface{}) string {
	return runtime.FuncForPC(reflect.ValueOf(i).Pointer()).Name()
}

func main() {
	test := []Google{Google1, Google2, Google3}
	const loops = 10
	for _, google := range test {
		var totalTime int64
		for round := 0; round < loops; round++ {
			rand.Seed(time.Now().UnixNano())
			//fmt.Printf("start\t : %d -> %s\n", round, GetFunctionName(google))
			_, _, elapsed := Benchmark(google)
			totalTime += elapsed.Milliseconds()
			//fmt.Printf("end\t : %d -> %s(%s)\n", round, GetFunctionName(google), elapsed)
		}
		fmt.Printf("Function : %s\tTotal time : %d\tAvg time : %d\n", GetFunctionName(google), totalTime, totalTime / 10)
	}
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *