最近在把之前弄的新聞萬事通做優化, 話說, 好久沒來宣傳一下新聞萬事通了(毆飛~~)

加入新聞萬事通請按 :

加入好友 加入好友

好, 回歸正題, 之前新聞萬事通檢查假新聞的邏輯是:

  1. 載入新聞小幫手資料庫到記憶體(server啟動時), 四千多筆資料存放在一個map的資料結構
  2. 使用者輸入的訊息如果含有url去map裡面找到對應的url
  3. 但常常有類似內容的新聞有不同來源, 因此會用Gojieba取出標題的關鍵字去四千多筆資料的標題對應關鍵字出現的次數

聽起來很沒效率(四千筆在記憶體內, 其實也不算慢啦, 但就吃記憶體), 那就要優化囉? 那需要一個搜尋引擎囉?

第一個先想到的是Elastic search, 但我還不想搞那麼大, 為了四千多筆資料多拉一台search server,我只想 一台respberry pi就能搞定

Gojieba知道, 有Bleve Search這東西, Bleve Search也是一個full text index engine, 但跟Elastic search不同的是, 它是內嵌在你的程式內, 而不是獨立的server, 而且它是用Go寫的(開心), 而不是Java

Bleve

Bleve Search的來頭也不小,它是來自於著名的NoSQL DB : Couchbase, 這篇有介紹一下他的功能 : Bleve:来自Couchbase、基于Go语言的全文索引与检索库

使用Bleve Search也很簡單, 就建立index, 然後search:

import "github.com/blevesearch/bleve"

func main() {
    // open a new index
    mapping := bleve.NewIndexMapping()
    index, err := bleve.New("example.bleve", mapping)

    // index some data
    err = index.Index(identifier, your_data)

    // search for some text
    query := bleve.NewMatchQuery("text")
    search := bleve.NewSearchRequest(query)
    searchResults, err := index.Search(search)
}

Bleve Search會把indexes放到資料庫內, 預設是使用Bolt DB, Bolt跟leveldbRocksDb 類似, 都是一種Key-Value database, 只是Bolt是純粹以Go開發的

如果你不想要用Bolt, Bleve也是支援使用leveldb和Rocksdb的, 純粹是作者想做成全Go的方案才預設Bolt db, 我自己有實測幾次, 使用這三種DB, 搜尋的速度差不多, 但建立index時bolt較快, 需求的磁碟空間則是Rocksdb優(比Bolt好很多)

Bleve Search的架構做成很有彈性, 除了可以使用不同的DB(我自己也有實作以Redis當KV database的plugin, 不過實在也沒好多少就作罷了), 文字分析(Text Analysis)比如說斷詞, 也是可以用plugin擴增的

官方支援的語言為: Danish, Dutch, English, Finnish, French, German, Hungarian, Italian, Norwegian, Persian, Portuguese, Romanian, Russian, Sorani, Spanish, Swedish, Thai, Turkish

就是沒中文!

還好Gojieba後來也加入了bleve的analyzer和tokenizer, 這一部分可以獲得解決

使用Gojieba斷詞:

	indexMapping := bleve.NewIndexMapping()
    os.RemoveAll(INDEX_DIR)
    // clean index when example finished
    defer os.RemoveAll(INDEX_DIR)

    err := indexMapping.AddCustomTokenizer("gojieba",
        map[string]interface{}{
            "dictpath":     gojieba.DICT_PATH,
            "hmmpath":      gojieba.HMM_PATH,
            "userdictpath": gojieba.USER_DICT_PATH,
            "type":         "gojieba",
        },
    )
    if err != nil {
        panic(err)
    }
    err = indexMapping.AddCustomAnalyzer("gojieba",
        map[string]interface{}{
            "type":      "gojieba",
            "tokenizer": "gojieba",
        },
    )
    if err != nil {
        panic(err)
    }
    indexMapping.DefaultAnalyzer = "gojieba"

Wukong

除了Bleve外, 還有一個悟空 Wukong, 這孫猴子也好像蠻識字的嘛

這個Wukong是由阿里巴巴的陳輝所開發的, 一樣是內嵌的全文檢索引擎

package main

import (
    "github.com/huichen/wukong/engine"
    "github.com/huichen/wukong/types"
    "log"
)

var (
    // searcher是协程安全的
    searcher = engine.Engine{}
)

func main() {
    // 初始化
    searcher.Init(types.EngineInitOptions{
        SegmenterDictionaries: "github.com/huichen/wukong/data/dictionary.txt"})
    defer searcher.Close()

    // 将文档加入索引,docId 从1开始
    searcher.IndexDocument(1, types.DocumentIndexData{Content: "此次百度收购将成中国互联网最大并购"}, false)
    searcher.IndexDocument(2, types.DocumentIndexData{Content: "百度宣布拟全资收购91无线业务"}, false)
    searcher.IndexDocument(3, types.DocumentIndexData{Content: "百度是中国最大的搜索引擎"}, false)

    // 等待索引刷新完毕
    searcher.FlushIndex()

    // 搜索输出格式见types.SearchResponse结构体
    log.Print(searcher.Search(types.SearchRequest{Text:"百度中国"}))
}

架構上跟Bleve有點接近, 寫法也差不多, 但效率上來說, Bleve根本不能比, index的效率快上許多, 它的docId不像是Bleve用string而是uint64

比較快的原因目前我也還沒深究, 不過它存儲並沒用到BoltDB或LevelDB之類的, 而是自己的格式, 它也像Bleve一樣支援換資料庫引擎, 我嘗試想用BoltDB來取代它原生的, 想試看看是不是這原因, 但一直沒換成功過(後來也懶得追了)

另一點的差別在於是, 剛剛Bleve我用的斷詞器是Gojieba, 而Wukong用的是陳輝自己寫的sego, 這時我就好奇這會不會有影響?

BleveSego

好, 既然要確認斷詞器對index效率有沒影響, 我就得自己實作一個基於Sego的Bleve text analyzer和Tokenizer, 因此仿Gojieba的做了:

blevesego

使用blevesego跟使用Gojieba的有點類似:

	indexMapping := bleve.NewIndexMapping()
	err := indexMapping.AddCustomTokenizer("sego",
		map[string]interface{}{
			"dictpath": "dictionary.txt",
			"type":     "sego",
		},
	)

	if err != nil {
		getLogger().Fatal(err)
		return nil
	}

	err = indexMapping.AddCustomAnalyzer("sego",
		map[string]interface{}{
			"type":      "sego",
			"tokenizer": "sego",
		},
	)

	if err != nil {
		getLogger().Fatal(err)
		return nil
	}

	newsHelperIndexMapping.DefaultAnalyzer = "sego"

實驗的結果, 同樣Bleve, 用不同的斷詞, 似乎用sego有稍微快一點(在raspberry pi下, 約五千多筆資料大約快個一秒鐘), 但似乎不是Wukong效率高過於Bleve的主因

到最後, 我是選擇了Bleve, 原因是, 它目前看起來比較活躍, 而Wukong就比較沒啥更新

昨天趁等著去面試前稍微把這之前想要寫一下的這題目打包成一個Gin的middleware :

Rate limiting 通常在很多開放API的服務內會常看到, 像是Twitter, 像是Facebook或是新浪微博, 其目的就是希望API不要被特定節點頻繁存取以致於造成伺服器端的過載

rate limiter

一般的Rate limiting的設計大致上來說就是限制某一個特定的節點(或使用者或API Key等等)在一段特定的時間內的存取次數, 比如說, 限制一分鐘最多60次存取這樣的規則, 最直覺的方式我們是可以起一個timer和一個counter, counter大於60就限制存取, timer則每60秒重置counter一次, 看似這樣就好了, 但其實這有漏洞, 假設我在第59秒時瞬間存取了60次, 第61秒又瞬間存取了60次, 在這設計上是合法的, 因為counter在第60秒時就被重置了, 但實質上卻違反了一分鐘最多60次這限制, 因為他在兩秒內就存取了120次, 遠大於我們設計的限制, 當然我們也可以用Sliding time window來解決, 但那個實作上就稍稍複雜點

目前兩個主流比較常見的做法是Token BucketLeaky Bucket, 這兩個原理上大同小異

先來說說Token Bucket, 他的做法是, 假設你有個桶子, 裡面是拿來裝令牌(Token)的, 桶子不是Doraemon的四次元口袋, 所以他空間是有限的, 令牌(Token)的作用在於, 要執行命令的人, 如果沒從桶子內摸到令牌, 就不准執行, 然後我們一段時間內丟一些令牌進去, 如果桶子裡面已經裝滿就不丟, 以上個例子來說, 我們可以準備一個最多可以裝60個令牌的桶子, 每秒鐘丟一個進去, 如果消耗速度大於每秒一個, 自然桶子很快就乾了, 就沒牌子拿了

Leaky BucketToken Bucket很像, 不過就是反過來, 我們把每次的存取都當作一滴水滴入桶子中, 桶子滿了就會溢出(拒絕存取), 桶子底下打個洞, 讓水以固定速率流出去, 這樣一樣能達到類似的效果

Leaky Bucket

Go的rate limiter實作

Go官方的package內其實是有rate limiter的實作的:

照他的說法他是實作了Token Bucket, 創建一個Limiter, 要給的參數是Limit和b, 這個Limit指的是每秒鐘丟多少Token進桶字(? 我不知道有沒理解錯), 而b是桶子的大小

實際上去用了之後發現好像也不是那麼好用, 可能我理解有問題, 出現的並不是我想像的結果, 因此我換用了Juju’s ratelimit, 這個是在gokit這邊看到它有用, 所以應該不會差到哪去, 一樣也是Token Bucket,給的參數就是多久餵一次牌子, 跟桶子的大小, 這就簡單用了一點

包裝成Gin middleware

要套在web server上使用的話, 包裝成middleware是比較方便的, 因此我就花了點時間把Juju’s ratelimit包裝成這個:

使用範例如下:

    //Allow only 10 requests per minute per API-Key
	lm := limiter.NewRateLimiter(time.Minute, 10, func(ctx *gin.Context) (string, error) {
		key := ctx.Request.Header.Get("X-API-KEY")
		if key != "" {
			return key, nil
		}
		return "", errors.New("API key is missing")
	})
	//Apply only to /ping
	r.GET("/ping", lm.Middleware(), func(c *gin.Context) {
		c.JSON(200, gin.H{
			"message": "pong",
		})
	})

	//Allow only 5 requests per second per user
	lm2 := limiter.NewRateLimiter(time.Second, 5, func(ctx *gin.Context) (string, error) {
		key := ctx.Request.Header.Get("X-USER-TOKEN")
		if key != "" {
			return key, nil
		}
		return "", errors.New("User is not authorized")
	})

	//Apply to a group
	x := r.Group("/v2")
	x.Use(lm2.Middleware())
	{
		x.GET("/ping", func(c *gin.Context) {
			c.JSON(200, gin.H{
				"message": "pong",
			})
		})
		x.GET("/another_ping", func(c *gin.Context) {
			c.JSON(200, gin.H{
				"message": "pong pong",
			})
		})
	}

這邊本來想說為了簡單理解一點把參數設計成"每分鐘不能超過10次"這樣的描述, 然後後面再轉換成實際的fillInterval, 不過好像覺得怪怪的, 有點不太符合Token Bucket的特質, 寫成middleware後的彈性就較大一點, 可以全部都用一個limiter或是分不同的資源不同限制都可

這邊建構時要傳入一個用來產生key的函數, 這是考慮到每個人想限制的依據不同, 例如根據API key, 或是session, 或是不同來源之類的, 由這函數去 產生一個對應的key來找到limiter, 如果傳回error, 就是這個request不符合規則, 直接把他拒絕掉

跨server的rate limit

這方法只能針對單一server, 但現在通常都是多台server水平擴展, 因此也是會需要橫跨server的解決方案, 這部分的話, 用Redis來實作Token Bucket是可行的, 這等下次再來弄好了