如何解決看起來不可能的工程問題？
Scalyr 是一個基于云的服務器日志監控工具。其官方博客曾發表過一篇 文章 ，描述如何使用 蠻力方法 實現數十GB日志數據的秒級查詢。在對所有日志進行實時探索性分析時，那是個行之有效的方法，但無法實現Scalyr某些功能（如儀表板、預警）所需要 的、TB級數據的秒級查詢。近日，前谷歌員工、Scalyr創建者Steve Newman撰文介紹了他們如何遵循如下兩個原則解決該問題：
- 常用的用戶行為對應簡單的服務器行為；不常用的用戶行為則可以對應復雜的服務器行為 。
- 尋找一種可以簡化關鍵操作的數據結構 。
Steve指出，重定義可以讓一個看似不可能的挑戰變得容易處理，而這兩個原則有助于尋找一種合適的重定義方法。
“不可能”的問題
Scalyr提供了許多服務器監控和分析工具。為了支撐這些工具，他們將每項功能都實現為一個通用數據集上的一組查詢。有些功能需要多個查詢。例如，儀表 板可以包含任意數量的圖表，每個圖表又包含多條曲線，而每條曲線對應一個復雜的日志查詢。假如一個自定義的儀表板容包含十二個圖表，每個圖表4條曲線，用 戶選擇了一個時間跨度為一周的儀表板視圖，而他們每天生成的日志量為50GB，那么，就需要在350GB的數據上執行48個查詢。沒有哪個蠻力算法可以在 零點幾秒內提供查詢結果。同樣，預警功能也會產生大量的查詢。Scalyr的 日志預警 可以觸發非常復雜的條件，比如，過去10分鐘內99%的Web前端響應時間超過800毫秒。單個用戶可能有成百上千的預警，它們每分鐘就需要計算一次。而通常，預警查詢對延遲很敏感，需要在幾毫秒內響應。
重定義問題
綜上所述，儀表板和預警都會產生大量的查詢，但都不能接受太長的查詢執行時間。所幸，它們有一個共同點：查詢事先已知，查詢很常用，而新查詢很少。按照上文提出的原則，他們需要一種可以簡化儀表板和預警查詢的數據結構，哪怕創建查詢變得復雜也可以接受。
Scalyr支持多種輸出結果，包括文本、數值、直方圖和鍵/值數據。不過，儀表板和預警查詢總是生成一個數組。每個查詢定義了一個時間上的數值 函數，可能是“每秒產生的錯誤信息”、“服務器X上的空閑磁盤空間”等。執行查詢就意味著使用函數求值，計算結果為數值序列，每個數值對應一個特定的時間 區間。
他們通過預計算來簡化函數求值過程。他們采用的數據結構非常簡單：每個查詢對應一個數組。查詢每隔30秒執行一次，并輸出一個數值。他們將那個數組稱為“ 時間序列 （timeseries）”。例如，用戶儀表板上有一張圖表，上面顯示了Web服務器池產生5xx錯誤的速率。為此，他們創建了一個時間序列，每30秒記錄一個錯誤數：
這樣，他們就可以快速生成任意時段的圖表（為了生成更長時段的圖表，他們還以逐步增大的時間間隔存儲一些冗余數組）。
時間序列維護
當有日志消息到達時，他們需要對每個相關時間序列進行增量更新。例如，如果一個新的Web訪問消息包含有介于500-599之間的狀態碼，那么他 們就需要增加對應特定時間間隔的“5xx錯誤”時間序列的計數器。這里有個問題，就是針對一個新消息，如何確定哪些時間序列需要更新。由于儀表板和預警查 詢通常使用相同的字段進行過濾，如主機名、指標名，所以他們使用這些字段構建了一棵決策樹，通過它快速確定與日志消息匹配的候選時間序列列表。
Steve舉了一個例子。假如有十二個時間序列，遵循下面的消息選擇標準：
host="frontend1" && metric="memfree" host="frontend1" && metric="diskfree" host="frontend2" && metric="memfree" host="frontend2" && metric=diskfree" host="backend1" && metric=memfree" host="backend1" && metric=diskfree" host="backend2" && metric="memfree" host="backend2" && metric="diskfree" pool="webapp" && status >= 400 && status <= 499 pool="webapp" && status >= 500 && status <= 599 pool="api" && status >= 400 && status <= 499 pool="api" && status >= 500 && status <= 599
這些時間序列可以組織成下面這樣一棵決策樹：
如果收到了下面這樣一條消息：
host=frontend1 metric=memfree value=194207
則該消息會從決策樹的根節點開始匹配，首先會進入 host=“frontend1” 和 host=[any] 節點。從 host=“frontend1” 向下，可以進入 metric=“memfree” 節點，并匹配到該節點下的時間序列（ host="frontend1" && metric="memfree" ）；從 host=[any] 節點向下，未能找到匹配的分支，不再向下匹配。就是說，在這種情況下，只需要檢查時間序列 host="frontend1" && metric="memfree" 是否需要更新。而對于消息 host=frontend1, metric=memfree, pool=webapp ，則需要檢查3個時間序列。
決策樹生成算法
決策樹生成采用了一個簡單的貪婪算法：
- 找出所有用于
==檢驗并在至少一個時間序列中出現的字段名（比如，上例子中的 host 、 metric 和 pool ）。 - 根據每個字段名劃分時間序列。如果一個時間序列無法匹配該字段值域中的某個值，那么就將其劃分到[any]組。計算每個組中時間序列的數量，并找出最大的組。在上例中， host 字段產生了4個大小為2的組和一個大小為4的組（[any]組）。因此，最大組的大小為4。
- 創建一棵樹，其根字段要能夠使最大組最小化。在上例中，如果以 host 和 metric 字段為根節點，則最大組的大小均為4；如果以 pool 字段為根節點，則最大組為[any]，大小為8。因此，可以使用 host 和 metric 的其中一個作為根節點，而不使用 pool 。
- 在每棵子樹上遞歸執行步驟3。
在Steve舉的一個例子中，與蠻力算法相比，該算法帶來了33倍的性能提升。在實際的生產環境中，它對性能的提升更明顯。
另外，Steve還列舉了一些具體的實現細節，此處不再一一贅述。感興趣的讀者可以查看 原文 。