導語：在互聯網領域, 認為90%的流量由10%的內容產生。很多技術策略也由此產生，本文作者針對這一現象做了數學論證，並對其中怎麼科學使用該結論給出方法。
張炎潑 (xp)，30 年軟件開發經驗，物理系背叛者，設計師眼中的美工，bug maker，vim 死飯，懸疑片腦殘粉。曾就職新浪, 美團。現在白山雲，不是白雲山 。
在互聯網領域, 流行著這麼一句話:
90%的流量由10%的內容產生.
緩存也由此產生: 只為最頻繁訪問的10%的內容提供更快的存儲, 就可以以很低的成本提供儘可能好的服務質量.
一般符合這種互聯網訪問模型的曲線是下圖這樣的. 對每個訪問的url做獨立計數, 並按照從訪問最多到最低排序:
這句是一個經驗結論, 從它可以得出我們的頻度分佈公式: 也就是zipf 模型.
這個公式很好, 好就好在可以直接對其左右兩邊取對數後, 直接轉換成了線性關係:
即: k的對數跟y的對數呈現線性關係. 線性太棒了, 簡單又好用!
用這個公式我們可以更好的瞭解和控制數據的訪問模型, 做更多的事情. 以下是得出這個結論的愉快的推導過程.
推導
首先我們假設, 上面那個比值是p(10%或1%或其他, 根據業務不同而不同), k個文件中, 最熱的pk個文件的訪問佔比是(1-p), 我們首先假設存在這樣一個函數來描述文件熱度到文件訪問頻率的關係: y=f(k)
那麼根據上面的統計規律, 這個函數應該滿足這樣一個方程:
因為要得到f(k)的函數, 所以對兩邊對k求個導:
好了, 這樣一個關係構成了一個數列的遞推式. 如果我們先選擇曲線上的一個點(k₀, y₀) 滿足
, 那麼根據上面的遞推式很容易得到一組都在曲線上的點(kᵢ, yᵢ):
對2個方程都取個對數消去兩組數列中的i, 得到kᵢ, yᵢ的關係:
我們再對兩邊取下指數就可以看到: 基於(k₀, y₀) 選擇的這組點是滿足
的形式. 目前我們已經可以確定曲線上有一組點集是符合我們的頻率分佈公式的了, 剩下的點再接著處理一下:
不難看出通過選擇不同的(k₀, y₀), 我們可以列出曲線上所有的點, 並且我們還可以看到, 選擇不同的(k₀, y₀), 只會性影響這裡c的值, 而不會影響a的值. a的值只跟最初選擇的p相關. 又因為我們假設整個曲線是平滑的, 直觀上就可以得出結論:
所有不同的(k₀, y₀) 確定的曲線的c值是一樣的(否則距離很近的2個k₀可以反例出不可導的情況.), 也就是說所有點都在一條
的曲線上.
在大量的數據統計中<code>s/<code>的值不是一個常量, 在比較熱的訪問中(k比較小的區域),<code>s/<code>一般在0到1之間, 在後面長尾部分,<code>s/<code>一般會大於1.
如何將訪問計數轉換成對應的zipf分佈的公式
想要用公式形式
替代原來的描點描出的曲線, 先要確定式子裡面<code>s/<code>和<code>c/<code>的值。這也很簡單, 拿到一段訪問日誌後, 首先統計獨立url計數, 然後 通過多項式迴歸擬合一條直線
例如我們使用預先準備好的url計數文件 file-access-count.txt[1] 作為例子, 使用這個 find-zipf.py[2] 腳本來擬合:
<code>python2 find-zipf.py/<code><code>6.796073 - 0.708331x/<code>
這樣我們就從日誌中得到了它的zipf 曲線公式:
整理成原來的樣子, 第k熱的對象被訪問的次數是:
標準定義
zipf在標準定義中用全量的相對佔比來描述一個對象的訪問頻率:
Zipf’s law then predicts that out of a population of N elements, the normalized frequency of elements of rank k, f(k;s,N), is:
有什麼用
合理配置緩存容量以使緩存成本和性能之間做一個準確的把控.
-
在大量日誌分析時, 通過合理近似降低計算量.
多瞭解一些東西. 說不定什麼時候就用上了.
我一直覺得, 借來100年的肉身存在在這個世界上的意義, 無非是這3個事兒:
Discover, Design, Distribute
Discover: 學習和探索, 找到新的東西;
Design: 如果發現了什麼新的東西, 就把它設計出來和實現出來;
Distribute: 如果實現了什麼新的東西, 那就把它帶給其他人, 去讓他們的生活變得更好.
原文地址：https://openacid.github.io/tech/zipf/
文中鏈接：
[1] https://openacid.github.io/post-res/cache-hit/file-access-count.txt
[2] https://openacid.github.io/post-res/cache-hit/find-zipf.py
高可用架構
改變互聯網的構建方式
閱讀更多 高可用架構 的文章
