Reading time ~4 minutes

昨天趁等著去面試前稍微把這之前想要寫一下的這題目打包成一個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 Bucket和Leaky Bucket, 這兩個原理上大同小異

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

Leaky Bucket跟Token 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是可行的, 這等下次再來弄好了

Reading time ~4 minutes

在之前工作的時候, 做了一個專門用來產生thumbnail(縮圖)的服務, 當時這東西主要的目的是為了因應Zencircle會有不同尺寸的縮圖的需求, 而且每次client app改版又可能多新的尺寸, 因此當時寫了這個叫Minami的服務, 當時幾個簡單的需求是:

  1. 要能夠被CDN所cache (因此URL設定上不採用query string,而是簡單的URL)
  2. 能夠容易被deploy
  3. 能夠的簡單的被擴展 (加一台新的instance就可以)
  4. 不需要太多額外的dependencies

不過那時候寫的版本, 沒寫得很好, 這兩天花了點時間重寫了一個叫做Minami_t(本來Minami這名字就是來自於Minami Takahashi, 所以加個"t" XD), 新的這個重寫的版本採一樣的架構(使用了groupcache), 但多加了Peer discovery的功能(使用etcd), 但少了 臉部辨識跟色情照片偵測功能(原本在前公司的版本有, 新寫的這個我懶得加了)

我把這次重寫的版本放到github上: Minami_t

不過這算是一個sample project, 影像來源來自於Imgur, 如何使用或如何改成支援自己的Image host, 那就自行看source code吧, 這版本縮圖的部分用了我改過的VIPS, 當然原來版本的VIPS也是可用, 這版本只是我當初為了支援Face crop所改出來的

Groupcache

先來說說為什麼採用groupcache? 我不是很確定當時為何會看到groupcache這來, 但後來想想, 採用它的原因可能是看到這份投影片, 它是memchached的作者寫來用在dl.google.com上面的, 架構上剛好也適合thumbnail service, 可能剛好投影片又提到thumbnail(我腦波也太弱了吧), 所以當初採用它來實作這個service

架構上會像是這樣:

Groupcache有幾個特色

  1. Embedded, 不像memcached, redis需要額外的server, 它是嵌入在你原本的程式內的
  2. Shared, Cache是可以所有Peer共享的, 資料未必放在某特定的Peer上, 有可能在本機, 也可能在另一台, 當然如果剛好在本機時就會快一點
  3. LRU, Cache總量有上限限制的, 過久沒使用的資料有可能會被移出記憶體
  4. Immutable, key所對應的值不像memcached, redis可以修改, 而是當cache miss時, 他會再透過你實作的getter去抓真正的資料

要讓Groupcache可以在不同node間共享cache, 就必須開啟HTTPPool, 像下面

	ln, err := net.Listen("tcp", fmt.Sprintf(":%d", port))
	if err != nil {
		return nil, err
	}

	if port == 0 {
		port = ln.Addr().(*net.TCPAddr).Port
	}

	_url := fmt.Sprintf("http://%s:%d", ip, port)
	pool := groupcache.NewHTTPPool(_url)

	go func() {
		log.Printf("Group cache served at port %s:%d\n", ip, port)
		if err := http.Serve(ln, http.HandlerFunc(pool.ServeHTTP)); err != nil {
			log.Printf("GROUPCACHE PORT %d, ERROR: %s\n", port, err.Error())
			os.Exit(-1)
		}
	}()

Groupcache 的getter範例:

func getter(ctx groupcache.Context, key string, dest groupcache.Sink) error {
	log.Println("Cache missed for " + key)

	params := strings.Split(key, ":")

	if len(params) != 3 {
		return ErrWrongKey
	}

	d := ctx.(*Downloader)
	fileName, err := d.Download("http://i.imgur.com/" + params[2])

	if err != nil {
		return err
	}

	//Should assume correct since it is checked at where it is from
	width, _ := strconv.Atoi(params[0])
	height, _ := strconv.Atoi(params[1])

	data, err := resize(fileName, width, height)

	if err != nil {
		return err
	}

	dest.SetBytes(data)
	return nil
}

etcd

我之前寫的版本有個問題是, 沒有自動的peer discovery的功能, 所以必須手動加peer, 這版本把etcd導入, etcd已經是coreos的核心之一了, 簡單, 又蠻好用的, 不過選它也是它直接有Go的client了

Peer discovery的部分, 參考了Go kit的etcd實作, Go kit是一個蠻好的Go的微服務框架, 它裡面也有實作用etcd做service discovery, 這一部分正好是這邊需要的, 因此 參考並寫出了這邊這個版本

重點是要能夠在有新server加入後就新增到peer list去, 有server離開後要拿掉, 因此必須利用到etcd的watch功能

func (s *ServiceRegistry) Watch(watcher Watcher) {
	key := fmt.Sprintf("/%s/nodes", s.name)
	log.Println("watch " + key)
	w := s.etcd_client.Watcher(key, &etcd.WatcherOptions{AfterIndex: 0, Recursive: true})

	var retryInterval time.Duration = 1

	for {
		_, err := w.Next(s.ctx)

		if err != nil {
			log.Printf("Failed to connect to etcd. Will retry after %d sec \n", retryInterval)
			time.Sleep(retryInterval * time.Second)

			retryInterval = (retryInterval * 2) % 4096
		} else {
			if retryInterval > 1 {
				retryInterval = 1
			}

			list, err := s.GetNodes()
			if err == nil {
				watcher(list)
			} else {
				//skip first
			}
		}
	}
}

Watch可以用來監測某一個key有無改變, 因此我們只要一直監測server node的list就好(指定一個key來放), 因此流程是這樣的:

  1. Server開啟後, 自己到etcd註冊自己, 並把etcd上找到的nodes全加到peer list中
  2. 另一台由etcd發現有另一台出現後, 把它加到peer list中
  3. Server下線後, 要移除自己的註冊, 其他機器要從peer list把它移除

問題點在最後一點, Server下線有可能是被kill的, 也有可能按ctrl-c中斷的, 這時候就要監聽os的signal, 在程式被結束前, 可以先去移除註冊, 像這樣:

//Listening to exit signals for graceful leave
go func() {
	c := make(chan os.Signal, 1)
	signal.Notify(c, os.Interrupt, syscall.SIGINT, syscall.SIGTERM)
	<-c
	log.Println("I'm leaving")
	cm.Leave()
	os.Exit(0)
}()

這只是一個sample而已, 還有一些待改進的

Reading time ~2 minutes

這個語法蠻有趣的, 早上一直都在看這個想能拿來幹嘛? 結果早上有個phone interview就有點腦袋小小的轉不過來, 不過這不是重點, 先簡單的來講一下Generators

產生器? 顧名思義或許是這樣, 可以先看一下MDN上的文件, 這是一個從ES6開始才有的功能, 因此要在比較新的瀏覽器, 或是nodejs 6之後才有支援, 先來看看MDN上那個簡單的例子:

function* idMaker(){
  var index = 0;
  while(index < 3)
    yield index++;
}

var gen = idMaker();

console.log(gen.next().value); // 0
console.log(gen.next().value); // 1
console.log(gen.next().value); // 2
console.log(gen.next().value); // undefined

一個generator是以"function*“宣告的, 可以說它是一種特別的function, 跟一般的function一次跑到結束不同, 它是可以中途暫停的, 以上面這例子來說, 如果習慣傳統的寫法, 可能會有點小暈, while loop在idMaker裡面不是一次做到完嗎? 剛剛說generator是可被中途暫停的, 因此, 在第一輪的時候會先停在"yield"處, 當你呼叫next()才會到下一個yield位置停下來並回傳, 我的感覺是比較像一種有帶state的function之類的

有什麼用途? 從上面的例子, 當然最直覺想到的是ID產生器或是計數器之類的東西, 網路上應該可以找到一些不同的用法, 比如說搭配Promise, 有興趣可以自己找找, 是不只可以用在產生器, 拿我早上interview被問到的實作strstr, 不是很難的東西, 我原本拿go寫,出了點小槌, 而且也只能找第一個發生的字串, 後來用generator改了這版本:

以這個來說, 第一次呼叫會找出第一個發生的點, 可以持續呼叫到所有的都找出來為止, generator是可以被iterate的, 因此這邊可以用

for(var i of gen) {
    console.log(i);
}

不需要一直call next(), next()回傳回來的會是{value:…, done:…}, 因此可以看done知道是否已經結束

下面這範例則是一個質數產生器, 一直call next就可以產生下一個質數:

Reading time ~10 minutes

這應該是這系列最後一篇了吧, 雖然回頭看, 可能有些漏寫, 不過, 以後想到再補吧, 如果還沒看過前兩篇, 可以再複習一下: 概念篇,多服務彙整

這篇主要要著眼在如何做Timeline這東西(怎又突然把它叫Timeline了? 好吧, 複習了一下很多文章, 發現這還是比較通用的名詞)

先借用一下以前跟老闆報告時, 老闆問的

"做這很難嗎?"

這不是啥記恨啦(雖然我還蠻有印象這問題跟我的回答的), 而是開始做這個的時候, 我也覺得應該沒什麼難的, 不過, 實作這個功能本身的確不難, 倒是要讓它可以擴展(scale)這件事, 的確會比較麻煩, 也不止一個方法做, 先從基本來看一下

什麼構成一個Timeline (Social feed)

Twitter和Facebook主要把這東西分為兩類 - User timeline和Home timeline

User timeline主要就是單一使用者的近況更新, 也就是所有的內容都是由那個使用者產生, 並以時間排序(不然怎叫Timeline), 這部分倒沒什麼困難的, 因為它就是單一個人的流水帳(從軟體的角度也可以說成他活動的"log")

Home timeline包含的則不是單一個人的, 而是包含你關注的人所有的動態, 在Twitter就是你follow的人, 而Facebook則是你的朋友加上你關注的人(follow)和粉絲頁, 講"follow"其實蠻貼切的啦, 有點偷窺(光明正大吧?), 又有點跟蹤狂的感覺, 但現今的Home timeline大多(尤其是Facebook)不是用時間排序, 好像也不能真的叫Timeline (ㄠ回來了, 這樣我叫Social feed好像比較貼切 XD)

假設我follow了user1, user2, user3等三個人, 那我的Home timeline就會變成這樣:

Ok, 其實這有點像前一篇講的多服務彙整那種, 不同的是, 這些feeds是來自於同一個來源, 並不是多個不同的服務, 比較沒資料異質性問題

1 9 90 理論

在切入實作面之前, 先提一下這個理論, 這邊有Mr. Jamine對這個的解釋: “網路內容的 1/9/90 定律” (他用"定律", 但定律是比較恆常的, 但這比例並不是那麼的絕對, 所以我比較覺得用理論或假設比較適合)

這理論說的是, 大約有90%(甚或以上)的人是屬於讀者, 9%的人會參與進一步互動(比如說按讚或回文), 只有1%的創作者(你可以看一下你自己是屬於哪類的人), 根據我的經驗, 讀者可能會多於90%, 創作者甚至可能少於1%

那對於開發者來說, 知道這些有什麼用? 我個人是覺得一個開發者或是架構設計者, 必須要清楚暸解所做的東西所會產生的行為才能產出一個好的架構, 以這個來說, 如果要設計一個高度可擴展的架構的話, 我們可知道, 絕大部分的request其實都是讀取(read), 高併發(highly concurrent)的寫入機會並不大(反而比較容易發生在like, comment)

比較直覺的實作方式

好, 難免的, 我一開始也是選用這種方式 - 都交給資料庫(database), 這邊的資料庫, 不管SQL或No-SQL, 差不多原理啦, 雖然說針對Feed這種time squences看起來像比較適合No SQL, 但Facebook不也是用My SQL(雖然用的方式比較是key-value的方式)

依照前面的說法, 我們可以簡單的假設有兩種資料 - 使用者(User)和內容(Feed)

  1. 使用者可以跟隨(Follow)其他使用者(這邊引用Twitter的設定), 因此每個使用者會有n個"follower"
  2. 使用者可以發文(Feed/Post), 每則發文都有(只有)一個作者(author)
  3. 每個使用者的Homeline是由他跟隨的所有人的發文所組成
  4. 每次client來要求homeline最多給m則(比如說25則)

按照這樣的說法, 我們可以想像Query或許長得像這樣(No SQL版本自行想像):

SELECT * FROM FEED WHERE AUTHOR IN (SELECT FOLLOWERS FROM USER WHERE ID='myid') ORDER BY TIME LIMITS m

這邊暫時先省略掉query出來你還要再query出user大頭照跟人名的部分, 但加上這部分每次至少要有兩次queries

這樣不就搞定了? 有什麼問題? 有, 後面就會撐不住了! (切身之痛), 先來看看什麼問題

查詢效率

從上面的query來說, 它還包含了個sub query去取出所有的followers, 所以這整串在資料庫裡可能的做法是, 把所有相關使用者的feed取出, 在記憶體中排序, 取前m個, 前面有提到, Feed就像流水帳, 全部的人加起來可能不少, 這聽起來就像是耗時耗CPU的查詢

因此在兩個狀況下就慘了:

  1. 讀取高併發時
  2. 使用者follow了"一大堆"人!!!

關於第一點, 這很容易發生呀! 90%的人一天到晚窺探…ㄟ …關心…人家在幹嘛, 當一堆這些queries湧入, 資料庫會非常忙碌的, 因為沒有不同的兩個人會follow同樣的人, 根本無法cache

第二點其實更慘了, follow個幾個人還好, 幾十個人還搞得定, 偏偏這個社群網路時代的, 幾百人是標配, 上千人的也不少, 如果有上萬, 可能更跑不動了(Facebook限制你只能交5000個朋友, Twitter超過5000也是選擇性的讓你少量follow, 所以上萬目前應該還比較少見)

Materialized View

有些資料庫, 像是MySQL, Postgresql, Cassandra (3.0+)都有支援Materialized view, materialized view就像是一個query的snapshot, join的部分是發生在create或是refresh時, 因此用來解決讀取高併發可能是可行的, 因為讀取時只有單純的query, 直到有更新時再呼叫refresh

但對於更新比較頻繁, 比較熱門的social network service, 資料庫的負擔還是不算小

Sharding

如果以時間為基準來做sharding, 或許可以解決這兩個問題, 因為不是所有的人不時都在更新狀態, 所以在含有最新的shard裡面包含的可能只有少數人的feed, 這減少了遍訪所有人的feed的工, 而且不用排序所有的feed

但還是有幾個問題:

  1. 無法join, 如果根據feed的時間去做sharding, feed跟user就不見得在同一資料庫, 這樣就無法join了
  2. 邊界問題, 有可能你需要的資料剛好就在時間間界的附近, 導致一開始query不到足夠的資料

其實上面問題寫程式解決都不是問題啦, 這邊想說的只是, 沒辦法以一兩個簡單的queries就搞定了

大家都怎麼做

這邊講的"大家"就那些大咖囉, Facebook, Twitter, Pinterest, Tumblr …等等, 關於這個問題, 其實Yahoo曾經出過一篇論文:

“Feeding Frenzy: Selectively Materializing Users’ Event Feeds”

如果沒耐心看完論文(我也沒耐心), 這邊先簡單提一下兩種模式:

  1. Push model
  2. Pull model

Push model又被稱為Megafeed(根據某場Facebook的分享), 而Pull model則是Facebook使用的Multifeed, 其實不管哪種模式, 大多不是直接存取資料庫增加資料庫的負擔, 而是大量的應用快取(cache), 像是Memcached, Redis等等

簡單的來說, Push model在整合feed的時間發生在寫入, 而Pull model則是發生在讀取

Push model (Megafeed)

這是Twitter所採用的方式, 也是我以前採用過的做法, 我自己則是把它稱為Inbox model, 比較詳細的內容推薦可以參考Twiter的:

“Timelines at Scale”

先來看看他們這張架構圖

Home timeline的部分主要是中間的那個流程, 這做法比較像是E-mail一樣(所以我才稱它為inbox), 當使用者發表了一則新的動態後, 系統會根據有訂閱這則動態有那些人(也就是follow這個使用者的人), 然後把這則動態複製到各個訂閱者的Home timeline (Inbox)上

這方法的優點是, 對於讀取相當之快, 因為Home timeline已經在寫入期間就準備好了, 所以當使用者要讀取時, 不需要複雜的join就能取得, 在做pagination也相當簡單, 因為本來就是依時序排下去的

但缺點是, 很顯而易見的, 非常耗費空間, 因為每個timeline都要複製一份, 假設你被上千人follow, 就要上千份, 因此Twitter只有存ID和flag, 詳細的內容跟Meta data, 是後來才從cache去合併來的, 另外Twitter也只存了最近的八百則, 所以你不可能得無窮無盡的往前滑

另一點就是耗時, 這種寫入通常是非同步的, 使用者發布動態後, 他只知道他動態發布成功了, 但系統還需要在背後寫到各個Inbox中, 因此他不會知道別人其實可能還看不到的, 對於一個follower數量不多的不是問題, 但如果像是Lady gaga那種大人物, 有幾百萬粉絲, 那就是大問題了! 寫入幾百萬的timeline即使只寫入memcached也是相當耗時的事, 而且這會產生時間錯亂的問題, follower比較少得很快就做完了, 所以很容易看到比較熱門的人物的貼文比較晚出現

Twitter是把follower多的人另案處理, 也就是讀取時段再合併(那就是類似下面要講的multifeed了), 這樣可以省下一些空間跟時間, 另一種可行的做法(我們之前的做法), 就是不寫到所有人的timeline, 而是只cache最近有上線的人的timeline, 這樣就算Lady gaga有幾百萬粉絲, 實際上最近才有上線的可能才幾十萬或更少, 處理這部分就好了, 如果cache裡面並沒有現在上線這個人的timeline, 就在從資料庫讀取合成就好

不過總歸來說, 這方法讀取快, 但寫入慢, 耗費空間, 較適合讀比寫多上許多的應用

此外其實也有不同的變形, 像是Pinterest:

Building a smarter home feed

Pull model (Multifeed)

Facebook採用了一個完全不同的方式, 叫做Multifeed, 這方式從2009開始在Infoq就一直被提到:

  1. Facebook: Science and the Social Graph 2009, by Aditya Agarwal
  2. Scale at Facebook 2010, by Aditya Agarwal
  3. Facebook News Feed: Social Data at Scale 2012, by Serkan Piantino (Aditya Agarwal這時候應該跑到Dropbox去了)

這跟Push model有什麼不同? 其實說起來跟前面一開始用DB的方式比較像, 就是在讀取時, 才取得所跟隨的人的feed, 合併並排序, 但這樣不是讀取很沒效率嗎?先來看看圖:

  1. 在寫入時, feed資料只會寫入"一個"leaf server, 應該是根據user去分流的
  2. leaf server主要是memcached, 所以都是in memory的
  3. 在memory裡面不可能保存所有動態, 只會保存最近一段時間的 (所以不可能包含所有人所有的動態, 在做整合時就輕鬆多了)
  4. 前端跟Aggregator query後, Aggregator會去跟"所有"的leaf server問所有相關的人的feed再回來整合

因為資料存儲跟處理都在memory, 所以可以很快, 但還是要考慮到網路的部分, 因此leaf server跨區的話效率就不會高了, 自然空間需求會比Pull model來得少, 但home timeline的讀取時間就較長了(因為是read time aggregation的關係),也不會有名人問題, 不會因為follower多, 複製耗時耗空間 另一個優點是, 排序的方式控制在Aggregator, 因此很容易立刻更動規則, 不像pull model, 當home timeline組好後要去變動它就較麻煩

混搭風

當然沒有絕對的好壞, 兩種模式各有優缺, 所以也有人採用的是混合模式, 根據使用者使用頻率來決定, 這就跟穿衣服一樣, 每個人怎搭衣服都是不一樣的, 端看你要怎混搭

REST API的問題

在前面一篇多服務彙整裡有提到REST API都是輪詢(polling)的模式, 不管資料有沒更新, Client都是會常常來server查詢資料, 這對server可能會是夢靨, 因為只有1%在努力創作, 所以搞不好有很大量的查詢都是浪費的, 而這些查詢通常是造成系統多餘負擔的元兇

關於這問題, 我有兩個想法, 不過都還沒實際去實證過

  1. 增加HEAD的API, 大部分REST API是以GET直接抓取資料, 所以針對個別資源(Resource), 應可實作HEAD, 讓Client在實際去查詢資料前先確訂一下資源的更新時間, 資源的更新時間在資料更新時就可以放在cache內了, 相對的可以省傳輸的數據量跟處理時間
  2. 利用PUSH, 現在大部分的應用都在手機上, 也大多有實作PUSH, 當有資料更新且App在前景時, 利用PUSH通知有資料更新, Client收到後才會真的去抓取, 不過這比較起來感覺相對負擔較重

另外這篇也是值得去參考(只是這個還要帶入XMPP):

Beyond REST?Building data services with XMPP PubSub

Reading time ~10 minutes

出去放空玩一陣子了, 也該接下來整理一下剩下的東西了, 這篇主要要來談一下彙整式的social feed (aggregation feeds), 這功用是什麼呢? 由於現代人擁有了很多社群網路的帳號, 但如果要一個個網站或App開著看才能看到所有的動態, 未免太累了, 因此變有這種彙整式的服務出現, 讓使用者在一個地方可以看到所有的社群動態

這種形態的應用, 有幾個有代表性的, 前一篇的概念篇裡所提到的Friendfeed, 還有就是Flipboard, 另外就是HTC的Friend stream和Blinkfeed (私心提這兩個我所參與過的)

Friendfeed Flipboard

前兩者跟後兩者的差異是在於, 前兩者在彙整social feeds是在server端, 所以client僅需要從server抓取彙整過的資料下來就好, 複雜度在於服務端並不是在client app, 而Blinkfeed跟Friendstream的差異點則是在Friendstream整合了跟社群網路相關的動態, Blinkfeed則是多了新聞的部分, 後來實作的方式為了有更多的彈性, 底層架構的部分也有所改變, 這篇會稍微提到如果是在Server端實作的一些可能做法, 但主要還是著重在client端實作的問題

做這樣一個東西, 不就是去呼叫各社群網路的API抓資料, 回來全部混在一起就好了? 如果單純只是實作一個"可以用的", 那這樣可能就可以了, 但實際上還是有些問題存在, 如

  1. 各家API雖類似但個家還是有很多不同
  2. 各家server回應時間不盡相同
  3. 資料時間線交錯問題
  4. 資料更新問題
  5. 網路流量問題

在看這些東西之前, 先來看看各家API的部分

Social Feed API

很多社群網站都有提供公開的API讓你去獲取使用者的Social feeds, API定義各家各有不同, 但特色都一致的, 也就是大家都是以REST API設計為主, 採資料拉取(Pull)的方式, 分頁(pagination)的方式

REST, Polling, and Pagination

因為採用了REST API的定義方式, 所以資料傳輸上大多(幾乎是全部了啦)以JSON為主, 用REST + JSON的好處是簡單, 彈性, 資料也比較適合閱讀, 不過, 別騙人了啦, 你有多少次會直接去閱讀JSON, 除非你要做啥hacking, 這連帶的也有人在實作client直接把JSON資料拿來儲存或暫存, 不過, 帶來的壞處是, 解析JSON其實並不是很經濟(後面會再稍提一下)

前面也有提到, 這樣的API設計是以"拉取"(Pull)為主, 也就是server並不會主動給你最新的資料, 而是必須你的client自行呼叫API去取得, 因此要隨時保持有最新的動態, 必須要不斷的輪詢(polling) server, 這其實也是相當不經濟的做法, 就算在熱門如Facebook, Twitter, 使用者的Social feeds不見得隨時會有最新的動態, 因此多久的輪詢間隔才是最好的, 這會是一個很頭痛的事, 太過頻繁易造成浪費, 也會造成server的負擔, 太久則會造成使用者看到的動態並不總是會是最新的, 其實少數像是Twitter, 有提供所謂的Streaming API, 這種就不是以拉取為主, 而是server會主動更新資料

一般來說, 社群網站上面"跟隨"(Follow)了越多人, 看得到的動態越多, 總不可能每次抓取資料就從頭一筆給到最新的一筆, 這樣的話, 不但花時間, 浪費流量, 也增加了server的負擔, 所以絕大部分的API, 都是從最新的往回給一定數量(比如說25則)的內容, 這樣稱之為一頁, 因此如果使用者需要往回捲回之前的資料, 就再抓取再前面一個分頁, 這樣的設計就是分頁(Pagination), 分頁的問題點在於, 社群動態的最頂頭的部分常常會再有更新的動態加入, 導致分頁會整個位移, 像下圖, 這樣會導致client有可能抓取到重複的資料, 甚至時間線錯亂

Twitter API

先來看看Twitter API的例子, 這邊就有很詳細地解釋前述的Pagination的問題, 並且講解如何用max_id和since_id來解決這一問題

Twitter在這部分經驗豐富, 他們用的解法是以"id", 有些社群網站的since會用"時間", 用時間是不好的做法, 因為就算你時間記錄到微秒, 還是很有可能有兩則以上的動態可能是相同時間的, 這樣錯亂的問題一樣存在

Twitter在抓取使用者的social feed用的API是“GET statuses/home_timeline.json”, 回傳的資料是一個Tweets的陣列如下:

[
  {
    "coordinates": null,
    "truncated": false,
    "created_at": "Tue Aug 28 21:16:23 +0000 2012",
    "favorited": false,
    "id_str": "240558470661799936",
    "in_reply_to_user_id_str": null,
    "entities": {
      "urls": [

      ],
      "hashtags": [

      ],
      "user_mentions": [

      ]
    },
    "text": "just another test",
    "contributors": null,
    "id": 240558470661799936,
    "retweet_count": 0,
    "in_reply_to_status_id_str": null,
    "geo": null,
    "retweeted": false,
    "in_reply_to_user_id": null,
    "place": null,
    "source": "OAuth Dancer Reborn",
    "user": {
      "name": "OAuth Dancer",
      "profile_sidebar_fill_color": "DDEEF6",
      "profile_background_tile": true,
      "profile_sidebar_border_color": "C0DEED",
      "profile_image_url": "http://a0.twimg.com/profile_images/730275945/oauth-dancer_normal.jpg",
      "created_at": "Wed Mar 03 19:37:35 +0000 2010",
      "location": "San Francisco, CA",
      "follow_request_sent": false,
      "id_str": "119476949",
      "is_translator": false,
      "profile_link_color": "0084B4",
      "entities": {
        "url": {
          "urls": [
            {
              "expanded_url": null,
              "url": "http://bit.ly/oauth-dancer",
              "indices": [
                0,
                26
              ],
              "display_url": null
            }
          ]
        },
        "description": null
      },
      "default_profile": false,
      "url": "http://bit.ly/oauth-dancer",
      "contributors_enabled": false,
      "favourites_count": 7,
      "utc_offset": null,
      "profile_image_url_https": "https://si0.twimg.com/profile_images/730275945/oauth-dancer_normal.jpg",
      "id": 119476949,
      "listed_count": 1,
      "profile_use_background_image": true,
      "profile_text_color": "333333",
      "followers_count": 28,
      "lang": "en",
      "protected": false,
      "geo_enabled": true,
      "notifications": false,
      "description": "",
      "profile_background_color": "C0DEED",
      "verified": false,
      "time_zone": null,
      "profile_background_image_url_https": "https://si0.twimg.com/profile_background_images/80151733/oauth-dance.png",
      "statuses_count": 166,
      "profile_background_image_url": "http://a0.twimg.com/profile_background_images/80151733/oauth-dance.png",
      "default_profile_image": false,
      "friends_count": 14,
      "following": false,
      "show_all_inline_media": false,
      "screen_name": "oauth_dancer"
    },
    "in_reply_to_screen_name": null,
    "in_reply_to_status_id": null
  },
  {
    "coordinates": {
      "coordinates": [
        -122.25831,
        37.871609
      ],
      "type": "Point"
    },
    "truncated": false,
    "created_at": "Tue Aug 28 21:08:15 +0000 2012",
    "favorited": false,
    "id_str": "240556426106372096",
    "in_reply_to_user_id_str": null,
    "entities": {
      "urls": [
        {
          "expanded_url": "http://blogs.ischool.berkeley.edu/i290-abdt-s12/",
          "url": "http://t.co/bfj7zkDJ",
          "indices": [
            79,
            99
          ],
          "display_url": "blogs.ischool.berkeley.edu/i290-abdt-s12/"
        }
      ],
      "hashtags": [

      ],
      "user_mentions": [
        {
          "name": "Cal",
          "id_str": "17445752",
          "id": 17445752,
          "indices": [
            60,
            64
          ],
          "screen_name": "Cal"
        },
        {
          "name": "Othman Laraki",
          "id_str": "20495814",
          "id": 20495814,
          "indices": [
            70,
            77
          ],
          "screen_name": "othman"
        }
      ]
    },
    "text": "lecturing at the \"analyzing big data with twitter\" class at @cal with @othman  http://t.co/bfj7zkDJ",
    "contributors": null,
    "id": 240556426106372096,
    "retweet_count": 3,
    "in_reply_to_status_id_str": null,
    "geo": {
      "coordinates": [
        37.871609,
        -122.25831
      ],
      "type": "Point"
    },
    "retweeted": false,
    "possibly_sensitive": false,
    "in_reply_to_user_id": null,
    "place": {
      "name": "Berkeley",
      "country_code": "US",
      "country": "United States",
      "attributes": {
      },
      "url": "http://api.twitter.com/1/geo/id/5ef5b7f391e30aff.json",
      "id": "5ef5b7f391e30aff",
      "bounding_box": {
        "coordinates": [
          [
            [
              -122.367781,
              37.835727
            ],
            [
              -122.234185,
              37.835727
            ],
            [
              -122.234185,
              37.905824
            ],
            [
              -122.367781,
              37.905824
            ]
          ]
        ],
        "type": "Polygon"
      },
      "full_name": "Berkeley, CA",
      "place_type": "city"
    },
    "source": "Safari on iOS",
    "user": {
      "name": "Raffi Krikorian",
      "profile_sidebar_fill_color": "DDEEF6",
      "profile_background_tile": false,
      "profile_sidebar_border_color": "C0DEED",
      "profile_image_url": "http://a0.twimg.com/profile_images/1270234259/raffi-headshot-casual_normal.png",
      "created_at": "Sun Aug 19 14:24:06 +0000 2007",
      "location": "San Francisco, California",
      "follow_request_sent": false,
      "id_str": "8285392",
      "is_translator": false,
      "profile_link_color": "0084B4",
      "entities": {
        "url": {
          "urls": [
            {
              "expanded_url": "http://about.me/raffi.krikorian",
              "url": "http://t.co/eNmnM6q",
              "indices": [
                0,
                19
              ],
              "display_url": "about.me/raffi.krikorian"
            }
          ]
        },
        "description": {
          "urls": [

          ]
        }
      },
      "default_profile": true,
      "url": "http://t.co/eNmnM6q",
      "contributors_enabled": false,
      "favourites_count": 724,
      "utc_offset": -28800,
      "profile_image_url_https": "https://si0.twimg.com/profile_images/1270234259/raffi-headshot-casual_normal.png",
      "id": 8285392,
      "listed_count": 619,
      "profile_use_background_image": true,
      "profile_text_color": "333333",
      "followers_count": 18752,
      "lang": "en",
      "protected": false,
      "geo_enabled": true,
      "notifications": false,
      "description": "Director of @twittereng's Platform Services. I break things.",
      "profile_background_color": "C0DEED",
      "verified": false,
      "time_zone": "Pacific Time (US & Canada)",
      "profile_background_image_url_https": "https://si0.twimg.com/images/themes/theme1/bg.png",
      "statuses_count": 5007,
      "profile_background_image_url": "http://a0.twimg.com/images/themes/theme1/bg.png",
      "default_profile_image": false,
      "friends_count": 701,
      "following": true,
      "show_all_inline_media": true,
      "screen_name": "raffi"
    },
    "in_reply_to_screen_name": null,
    "in_reply_to_status_id": null
  },
  {
    "coordinates": null,
    "truncated": false,
    "created_at": "Tue Aug 28 19:59:34 +0000 2012",
    "favorited": false,
    "id_str": "240539141056638977",
    "in_reply_to_user_id_str": null,
    "entities": {
      "urls": [

      ],
      "hashtags": [

      ],
      "user_mentions": [

      ]
    },
    "text": "You'd be right more often if you thought you were wrong.",
    "contributors": null,
    "id": 240539141056638977,
    "retweet_count": 1,
    "in_reply_to_status_id_str": null,
    "geo": null,
    "retweeted": false,
    "in_reply_to_user_id": null,
    "place": null,
    "source": "web",
    "user": {
      "name": "Taylor Singletary",
      "profile_sidebar_fill_color": "FBFBFB",
      "profile_background_tile": true,
      "profile_sidebar_border_color": "000000",
      "profile_image_url": "http://a0.twimg.com/profile_images/2546730059/f6a8zq58mg1hn0ha8vie_normal.jpeg",
      "created_at": "Wed Mar 07 22:23:19 +0000 2007",
      "location": "San Francisco, CA",
      "follow_request_sent": false,
      "id_str": "819797",
      "is_translator": false,
      "profile_link_color": "c71818",
      "entities": {
        "url": {
          "urls": [
            {
              "expanded_url": "http://www.rebelmouse.com/episod/",
              "url": "http://t.co/Lxw7upbN",
              "indices": [
                0,
                20
              ],
              "display_url": "rebelmouse.com/episod/"
            }
          ]
        },
        "description": {
          "urls": [

          ]
        }
      },
      "default_profile": false,
      "url": "http://t.co/Lxw7upbN",
      "contributors_enabled": false,
      "favourites_count": 15990,
      "utc_offset": -28800,
      "profile_image_url_https": "https://si0.twimg.com/profile_images/2546730059/f6a8zq58mg1hn0ha8vie_normal.jpeg",
      "id": 819797,
      "listed_count": 340,
      "profile_use_background_image": true,
      "profile_text_color": "D20909",
      "followers_count": 7126,
      "lang": "en",
      "protected": false,
      "geo_enabled": true,
      "notifications": false,
      "description": "Reality Technician, Twitter API team, synthesizer enthusiast; a most excellent adventure in timelines. I know it's hard to believe in something you can't see.",
      "profile_background_color": "000000",
      "verified": false,
      "time_zone": "Pacific Time (US & Canada)",
      "profile_background_image_url_https": "https://si0.twimg.com/profile_background_images/643655842/hzfv12wini4q60zzrthg.png",
      "statuses_count": 18076,
      "profile_background_image_url": "http://a0.twimg.com/profile_background_images/643655842/hzfv12wini4q60zzrthg.png",
      "default_profile_image": false,
      "friends_count": 5444,
      "following": true,
      "show_all_inline_media": true,
      "screen_name": "episod"
    },
    "in_reply_to_screen_name": null,
    "in_reply_to_status_id": null
  }
]

眼花撩亂了吧? 這邊先不細部探討每個部分的意義, 你只需要先知道, 這雖然看來很複雜, 但有一大半你做client時"並用不上!!!" 通常只會需要內文, 連結, 回文數量, 喜愛數量, 使用者基本資料(大概就ID, 名字, 圖像就已經差不多了)

Facebook API

Facebook有相當多的功能, 因此相較於Twitter, 他的API自然複雜很多, 這邊要看的還是只有User Feed這部分, 不過似乎Facebook Graph API已經不再允許存取home timeline了, User Feed其實只能存取自己po的文

在處理Pagination上, Facebook API並不是很一致, 從這篇來看, 有幾種分頁的形式:

  1. 游標型分頁
  2. 時間型分頁
  3. 位移型分頁

並不是所有的API節點都支援這三種分頁型態, 例如"/user/albums"用的是游標型, 但User Feed用的是時間型, 時間型的缺點就是有可能會發生有相同時間的動態的問題, 但不管是哪一個類型 在Paging的資訊都會有一個previuos跟next的連結(如下), 因此不用太擔心要根據不同型態去組出URL這部分

//游標型分頁
{
  "data":[
     
  ],
  "paging":{
    "cursors":{
      "after":"MTAxNTExOTQ1MjAwNzI5NDE=",
      "before":"NDMyNzQyODI3OTQw"
    },
    "previous":"https://graph.facebook.com/me/albums?limit=25&before=NDMyNzQyODI3OTQw"
    "next":"https://graph.facebook.com/me/albums?limit=25&after=MTAxNTExOTQ1MjAwNzI5NDE="
  }
}
//時間型分頁
{
  "data":[
    {
      "message": "真專業，還有空橋耶",
      "created_time": "2016-10-30T11:41:36+0000",
      "id": "1129283437_10210116929056272"
    },
    {
      "message": "兄弟藍瘦香菇了",
      "created_time": "2016-10-29T12:45:58+0000",
      "id": "1129283437_10210105741976602"
    },
    {
      "message": "又被拖著跑了",
      "created_time": "2016-10-29T06:39:29+0000",
      "id": "1129283437_10210103402598119"
    }
  ],
  "paging":{
    "previous":"https://graph.facebook.com/me/feed?limit=25&since=1364849754",
    "next":"https://graph.facebook.com/me/feed?limit=25&until=1364587774"
  }
}

在資料內容方面, Facebook回應的資料比起Twitter反而就相當的精簡, 這是有助於減低回應時間的(response time)

時間線回朔問題

剛提到Pagination時有講到在Client的設計上, 在使用者往回滑完一頁時必須要再獲取上一頁的資料, 這在單一資料源的時候問題不大, 但對彙整式的social feed, 尤其完全在Client端實作的, 會有這樣一個問題

先來看看下圖:

假設我們有S1, S2, S3, S4四個服務的動態要整合, 垂直每個線段是每次API call抓取到的資料的時間段(每個分頁的匙間段)

如果我們先不考慮S2-S4, 而是只有一個S1, 第一次載入的分頁內容的時間點在t1-t2間, 所以照理來說當使用者滑到快t2時, 要再發出一個新的API call抓取下一個分頁, 也就是t3-t5這段, 但如果把S2-S4列入考慮後, 會發現, 當第一次從四個服務那邊取得資料, 資料涵括的時間是從t1-t9, 如果什麼都不做處理而是照前面的邏輯來看, 必須要使用者滑到快t9時, 才會第二次抓取資料, 但由於第一次抓取時, S1缺了t2-t9間的資料, S2缺了t3之後的, S4的資料也只到t4, 因此第二次抓取資料時, 會造成這三者的資料往前回填, 這在UI顯示上會是一個比較大的災難

因此, 以這圖來說, 第一次抓取完畢後, UI上只能顯示t1-t2間的資料, 使用者滑到t2時, 就必須觸發第二次資料的抓取, 但以這例子來說, 其實第二次是不需要包含S3 的, 因為它第一次抓取的資料時間還在t5之後, 所以這邊如果能夠做省略, 而不是每次抓取資料都包含了S1-S4, 那可以省卻不少回應時間

資料格式的一致化(Data normalization)

剛剛看了Twitter, Facebook兩個API, 它的資料格式雖然都是JSON, 但內容差異很大, 但實際上來說, 以上次那篇的一張圖來做解釋:

從這張圖可以發現, 我們需要的資料並不多, 即使各家型態有所不同(例如Twitter重文字, Instagram是以圖為主), 我們還是可以歸納出我們UI所需要顯示的型態有哪些類別, 因此我們需要的也只是顯示UI所需要的部分而已, 所以我們可以把這些不同來源的資料格式一致化成同一種我們所需要的資料格式

那為何需要先一致化呢? 每次API抓回來的資料解析完直接顯示到UI上不就好了? 一般這樣的App的UI設計上, 會讓使用者一直捲頁, 因此你還是會需要把舊資料先暫存, 不管是在記憶體或是在資料庫內, 這樣使用者回捲再多也不需要再從server抓取舊資料, 但你如果把原本資料原封不動的拿來存, 像Twitter那個就會存了很多不必要的資料, 如果更偷懶直接存JSON, 那就會是效率問題了, 解析JSON過程中其實會產生不少垃圾, 效率也不高, 可能會影響UI的效能, 因此如果能夠在一開始把解析完的資料序列化到資料庫內, 會是比較理想, 因為你只需要從資料庫取相對應解析完的資料就好, 不用再一次解析JSON

背景更新

偷偷在背景更新動態是一種解決時間線回朔這個問題的方法, 因為所有資料都預先抓回資料庫, 所以也不需要煩惱什麼時後該去抓下一個分頁, 每個服務都可以獨立抓取, 丟到本地的資料庫彙整就好 ,在使用者使用程式時, 也不需要解析太多JSON, 但這帶來一個缺點是因為在背景抓資料, 會有浪費頻寬的問題, 假設使用者一天最多只看了50則動態, 但一天其實會產生一百則, 那就會有50則的資訊量是浪費了, 再加上Social API都是用輪詢(polling)的方式, 並不是會時時有資料, 所以常常很多API calls其實是不需要也浪費的

那Friendfeed的做法?

Facebook的前CTO, 也是Friendfeed創辦人之一的Brett Taylor在這篇 How do sites such as FriendFeed and Flipboard scale out their social data-aggregators? 的回答可窺知一二

在server端的做法就像背景更新差不多, 定期用crawler發api去抓取各服務的資料, 然後塞到資料庫內, 因此就沒有時間線回朔的問題了, 但問題就在於抓取的間隔, 因此在server端實作的難題就是該怎樣去取這間隔, 在OSCON 2008有一篇Beyond REST? Building Data Services with XMPP PubSub有提到:

on july 21st, 2008, they friendfeed crawled flickr 2.9 million times. to get the latest photos of 45,754 users of which 6,721 of that 45,754 visited Flickr in that 24 hour period, and could have *potentially* uploaded a photo. 
- Beyond REST? Building data services with XMPP PubSub (Evan Henshaw-Plath, ENTP.com, Kellan Elliott-McCrea, Flickr.com)

但實際上來說, 並沒有那麼多的更新, 也不需要那麼頻繁的去抓取, 但這是這類型的API先天的缺陷, 也不是Friendfeed的問題, 或許在下一篇講一下怎麼設計API來改善這狀況