計算機技術的進步顛覆了整個世界,而其中的很多技術不僅能解決計算機方面的問題,對很多其他方面的問題也很有啟發。今天筆者給大家介紹緩存理論,從緩存理論的角度來看待一些產品及生活上的問題,將會有許多有趣的結果,這就是今天的主題緩存理論+。筆者在此保證,本文沒有門檻,但需要耐心。

理論

如果這節看不太明白不用糾結,結合後面的例子會容易得多。

眾所周知,內存和硬盤是電腦的兩個重要部件,雖說兩者都是用來存儲數據的,特性卻大相徑庭:

  • 內存訪問速度快,容量小,斷電后無法保存數據,在計算機中充當緩存的角色。
  • 硬盤訪問速度慢,容量大,斷電后數據不丟失,用於長久地保持數據。

CPU是個急性子,每秒幾百億次計算不在話下,自然愛和內存打交道,不待見硬盤,不待見到什麼程度呢,即使CPU要讀取硬盤裡的數據,也先讓硬盤把數據交給內存,CPU再從內存讀,緩存往往就是指這樣快卻容量小的中間存儲

問題來了,內存容量小,而計算機可能會使用的數據卻很大,導致內存裝不下,只能把裝不下數據擱硬盤裡,要使用硬盤中的數據,得先讓內存清出一些暫時不用的數據,再從硬盤裡把所需數據加載到內存,這種倒騰的過程叫做置換Swap,而清出數據的操作稱為淘汰數據。從硬盤讀數據就耗時了,所以我們希望我們每次取數據時數據都在內存里,減少硬盤的訪問。

操作系統有一個很重要的任務——調整內存中的數據,目的在於減少用戶使用電腦時因讀取硬盤而造成的延遲和卡頓。調整一般發生兩種情況下,一個是電腦閑置的時候,提前將用戶可能會用到數據搬到內存中;另一個就是置換的時候,加載用戶所需數據的同時,捨棄那些比較不可能被訪問的數據。

計算機科學里把訪問數據時數據剛好在內存里的概率成為命中率。為了提升用戶體驗,減少等待,就得提高命中率,選擇合適的內存置換(淘汰)算法就顯得至關重要,內存置換算法是指在發生置換操作時,應該淘汰內存中的哪些數據,來放置新的數據,常用的算法(別怕,都很簡單)有

1、先進先出算法(FIFO,First In First Out)

淘汰最先進來的數據,這個算法非常簡單,這樣做的道理是最先進來的數據可能已經用過了,過時了。對於一次性或短期使用的數據,非常合適,但對於長期使用的數據,就不合適了。這個算法命中率並不高,常常被提起主要是用來襯托其他算法的優越性,有點類似奧特曼的小怪獸。

2、最久沒訪問算法(LRU,Least Rescently Used)

淘汰內存中最久沒有被用到的數據,這個就比FIFO合理多了,最久沒被訪問,可能真的是過時了。從邏輯上來說是相對合理的,而且比較簡單,現在流行的操作系統大多都使用它或它的變種。當然,這個算法對於那種需要被周期性訪問的數據就不合適了。

3、最不頻繁算法(LFU,Least Frequency Used)

淘汰內存中在最近一段時間內使用頻率最低的數據,這個又比LRU更合理了,就是保留最近最常用的數據,剔除最不常用的蛀蟲。它並不是操作系統的寵兒,因為它計算量比較大,自身會消耗一些內存,對於操作系統這樣的惜時(內存)如金的傢伙是不可接受的。

4、智能算法(AI)

我定義的一類算法,它泛指通過機器學習算法依據各種歷史數據,計算各個數據未來一小段時間內將會被訪問的概率,保留概率高的,淘汰低的。舉個例子,假設你白天使用電腦工作,晚上使用電腦娛樂,那麼AI算法可能會在白天盡量在內存中保留工作相關的數據。

比如一些word文檔及辦公軟件的數據,而到了晚上,工作相關的數據則優先被淘汰,內存中常駐遊戲,影音之類的數據。再比如,操作系統檢測到了我剛剛下載了一部電影,那麼這時應該將這部電影的數據及播放器的數據加載到內存中,其他類型的則可能被淘汰。AI算法的計算量顯然很大也很複雜,入不了操作系統的法眼,但在很多情況下卻非常好用。

再介紹一個概念:多級緩存,後面將會用到。

其實在電腦中,內存並不是讀取速度最快的存儲介質,還有更快的,叫CPU緩存。如果你看CPU的參數,經常能看到(L1/L2/L3緩存,他們共同組成CPU緩存),它是CPU的一部分,你們在看CPU規格時常常會看到,它離CPU計算核心更近,訪問速度更快,但容量更小。CPU緩存和內存的關係 與 內存和硬盤的關係是一毛一樣的。其實CPU緩存中還能細分,“ L1緩存 ”是“ L2緩存 ”的緩存,“L2緩存”是“L3緩存”的緩存,“L3緩存”是內存的緩存,如下圖所示,這樣不斷嵌套的緩存結構就叫多級緩存。

緩存還有另外一個作用,緩衝

計算機中的例子不太好說,舉個拉麵店的例子。

有個拉麵店只賣一種拉麵,顧客時多時少,有時一次性來好幾個人,師傅現做的話肯定有顧客等很久,如果提前做很多的話又有可能做多賣不出去,那麼師傅想了這麼一個策略,提前做好一些拉麵,放在一個固定的桌子上,如果桌子上的拉麵達到2碗,師傅就慢着點做,如果一直沒賣出去,桌上的面達到4碗,就完全不做了,如果某個時段生意旺賣很快,桌上的面可能會少於2碗,或者賣完,甚至還有人等,那麼師傅就要開足馬力做面了。

那麼,這裏就把桌子當作緩存,通過緩存策略,給師傅一定的緩衝時間,一定程度上抵消人流波動帶來的影響。

緩衝可以從兩個角度解釋,一個是任務發送者,另一個是任務處理者。在發送者和處理者之間設置緩存,來協調任務發送速度與處理速度不一致。當任務發送速度大於處理速度時,任務在緩存中堆積,發送者減慢發送速度,處理者提高處理速度;如果緩存中任務非常少了,則提高發送速度,減慢處理速度。如果處理是一次性的,緩存能減少處理的頻率。

舉個例子:垃圾桶是一種緩存,如果家裡沒有垃圾桶,我們一旦有垃圾就得扔到外頭的垃圾桶,垃圾桶的存着可以減少我們處理的頻率。

產品例子

緩存理論不僅在計算機領域應用廣泛,而且在生活和產品中也常常用到。我們先對理論進行抽象:

  • 緩存/內存,泛指那些使用方便又非常有限的容器。
  • 硬盤,那些使用不方便但容量非常大的容器。
  • 數據,放在容器中的物體。
  • 算法,上面的算法大多都是說怎麼淘汰,而下面往往說的是怎麼保留,怎樣選擇,其實本質是一樣的。從保留數據的角度重新解釋上面的算法:FIFO,保留最後進入內存的;LRU,保留最近用過的;LFU,保留近期使用最頻繁的;AI,保留未來最可能用到的。

下面舉例:

我們的電腦桌面就是一個“緩存”,你可以在上面放文件及程序,它非常方便,觸手可及,但是它容量非常有限,而資源管理器(我的電腦)則像是“硬盤”。桌面空間有限,東西多了也容易造成混亂,所以必須有所取捨,熵君在整理電腦桌面時一般會將最常用的放在桌面上,不常用的淘汰,這其實就是LFU算法 。

我們的手機桌面的首屏也可以當做“緩存”,一打開就能用到,而最下面一排的快捷欄則是更高級的緩存。我一直期望手機有這樣一個功能,自動把最常用(LFU)的應用放首屏,省得我去整理。

chrome的首頁就有很多標籤卡,都是你最常打開的網站(LFU),非常方便。

網站的首頁也是一個緩存,就拿電商網站來說,首頁資源是非常珍貴的,過去,這個首頁往往是死的,把一些熱門的商品放在首頁,而現在都是使用推薦算法為每個用戶定製首頁,這就是上面所說的AI算法。新聞網站也很類似,以前都是編輯根據經驗人工調整的首頁,現在往往會引入智能算法(AI),結合用戶個性化,新聞時效性等綜合因素來安排首頁內容。

生活中也有很多例子。筆者在整理房間的時候就會使用緩存理論,我會劃定一些緩存。

比如桌面,或者其他一些觸手可及的地方;我也會製造緩存,比如指定衣櫃中的某個格子為緩存,規定放在這個格子里的衣服可以隨意堆放。這些“緩存”常常會溢出,比如桌上太多東西了,影響我工作了;或者衣櫃里的緩存區衣服太滿,衣服不好找了。

這時我就會清理,我會把不常用的物品清出緩存區,並規整地放在它應該放的地方。這樣就避免了頻繁整理常用的物品,而這些常用的物品常常在你整理后又會使用到,那麼之前就白整理了。這裏也用到了緩存的緩衝功能。

這樣的例子還有很多,比如微信的首屏也是個緩存,显示最近的對話,顯然是使用LRU算法。當你在某個場景抽象出了緩存,那麼下一步就是選取合適的算法,一般情況下LFU/LRU這樣的簡單算法就夠用了,如果緩存資源非常珍貴,那麼就應該求助你們的算法工程師做一套AI算法了,這就是緩存理論+

緩存理論與電商物流

如何利用緩存理論分析網購物流的未來呢?

購物模式

如果把網購當做一次數據訪問,那麼我們可以把商品當做數據,把發貨的倉庫當做硬盤,緩存則可以有很多種,那麼我們將得到以下幾種購物模式:

模式一

從硬盤直接讀取數據,不經過緩存。也就是網購,並送貨上門。

(1)優點:直接,不需要顧客奔波。

(2)缺點

  1. 慢;
  2. 無法確定派送時間。很多時候顧客在派送的時候不在目的地,或者由於其他原因無法接收,這樣要麼限制了顧客自由,要麼降低了快遞員的效率。

模式二

先從硬盤讀取數據到緩存/內存,再從緩存讀取數據。也就是網購,送貨到自提櫃再由用戶自提,自提櫃就是緩存。

(1)優點:用戶收貨不再受到快遞派送時間的制約。

(2)缺點:

  1. 要自己取,如果自提櫃遠還不順路就更費勁了;
  2. 慢;
  3. 很多地方沒有自提櫃;
  4. 自提櫃的空間無法充分利用,如果自提櫃很密集,那麼空置率肯定很高。

模式三

數據已經提前從硬盤加載到內存,直接訪問內存就可以了。這就便利店的模式,便利店也是一種緩存,老闆進貨就是從硬盤加載數據到緩存的操作。

(1)優點:快。

(2)缺點

  1. 要自己取;
  2. 商品有限,很多東西都買不到。

從緩存理論的角度分析

從緩存理論的角度,以上這幾種購物方式其實是可以互相轉換的。如果僅僅從緩存的角度,如何分析這幾種模式?

  • 模式一:沒有緩存,每次從硬盤加載,慢。
  • 模式二:有緩存,但是每次仍然從硬盤加載數據,緩存只起到了緩衝的作用,相當於命中率為0的緩存。無法確保緩存被充分利用,當自提櫃密度提高時更甚。如果你把自提櫃的空間比作便利店的貨架,這相當於便利店的貨架很大部分沒擺放商品。
  • 模式三:有緩存,緩存利用率高,但緩存算法並不是最優化,這是由店老闆決定的,因此命中率還有提高的空間。緩存就像一潭死水,無法變化,緩存中沒有的數據(店裡沒有的商品)無法獲取。

筆者的理想模式是怎麼樣的呢?讓我們通過改造模式二(自提櫃)來獲得:

  • 增加自提櫃的密度,要比便利店還更密,提供更好的覆蓋度及體驗。
  • 發展自提櫃快遞員這種職業,和普通快遞員不同,他們的任務是由顧客直接指派,並且快速響應,派送距離很短,一般1公里以內(由自提櫃的密度決定),解決懶人的最後一公里。其實這個不一定有必要,更多的是想告訴你,通過這樣,模式2可以取代模式1,並解決模式1的時間問題。
  • 預先加載,在顧客購買之前,就將商品緩存到自提櫃,這樣,自提櫃就和便利店就很相似了。這樣就能充分利用自提櫃的空間(緩存)。Android手機中有很多優化軟件,在你內存佔滿時會讓你清理內存,而這與Android的內存策略背道而馳,因為當內存佔滿時內存才是被充分利用的,這樣能提高命中率,如果需要加載新的數據,那麼Android會自動捨棄些不常用的數據。
  • 使用AI算法對緩存(自提櫃中提前加載的貨物)進行安排,利用機器學習算法結合用戶數據,預測某個自提櫃附近的顧客們將會購買的商品,並將這些商品預先緩存好。當用戶在電商網站購物時,發現自己想要的商品已經在附近的自提櫃中,這樣,購物體驗就接近便利店了。

一些電商公司有過近似的嘗試,但還是離理想模式有差距。

亞馬遜是個奇葩公司,總是有很多驚人的想法,其中有一個是擅自派送商品到顧客家,而顧客甚至沒有訂購,如果顧客覺得這個不是他想要的,可以拒收。這個想法的邏輯和前面提的預先加載是一致的,雖然兩者是類似,但是亞馬遜這個做法是不可行的,因為它沒有緩存,目標是某個用戶,這就要求算法得精確到個人,難度太大。而通過緩存(自提櫃)的緩衝作用,目標可以擴大為附近的顧客,這樣對算法的要求就大大降低。

每年的雙十一阿里都搞得風風火火,快遞的效率一年比一年高,爆倉的情況已經好了很多,這裏的秘訣就是阿里依據AI算法將商品提前緩存到各地的倉庫,這樣就對物流網絡起到了緩衝的作用,同時也減少了用戶等待的時間。

倉庫也是一種緩存,那麼倉庫是緩存,自提櫃又是什麼呢?這其實並不衝突,上面提過了多級緩存這個概念,明顯,自提櫃是最末端的緩存,而倉庫則是上一級緩存,其實倉庫本身也是多級緩存,比如北京市朝陽區的倉庫是北京市倉庫的緩存,北京市倉庫又可能是河北省倉庫的緩存。阿里做的這個工作已經非常接近了,但是還停留在解決具體問題的階段,沒有去抽象升華。

  • 菜鳥驛站,這個看着非常相似,實則差十萬八千里。它沿襲了阿里輕資產,分流風險,做平台的風格。菜鳥驛站對各個快遞代售點沒有控制力,體驗很差,如果把各個代售點當做緩存,阿里無法對緩存做任何安排。總的來說還不如現在的自提櫃。當然它成本低,發展速度快是優點。
  • 順豐嘿客,似乎是網購體驗店與自提櫃的合體,發展並不順利,還沒完全摸透意圖。不過沒有強大的電商無法完全實現理想模式。

有些讀者可能會有疑問:這樣大肆租店/場地成本一定很高吧?是的,成本確實很高,但你想想,便利店都能支撐起這樣的店租,而緩存算法及機制更為先進的理想模式肯定能創造更多價值,所以不用擔心。

電商公司及快遞公司,怎樣能更快地到達理想模式?

  • 發展(收購)便利店,慢慢將貨架自提櫃化。
  • 將自動售貨機與自提櫃結合,取代貨架,進一步無人化。
  • 利用數據及算法優化便利店緩存(貨架/自提櫃/自動售貨機)上的貨品,提高命中率。
  • 鏈接倉庫與自提櫃,形成多級緩存,隨着自提櫃數量的提升,增加倉庫的數量。
  • 將物流標準化自動化,進一步提升物流速度和效率。
  • 在少數城市試錯。

理想模式不可能完全取代商店,但作為一種理論上更先進模式,我相信它會消滅大部分商店,而商店存在的意義更多將是展示、體驗還有服務。

一不小心又寫多了,科學並不像大家想象的那麼死板,經過理解與抽象,很容易應用到生活和產品中,今天的緩存理論,希望你喜歡。

 

作者:熵君,公眾號/微博:@熵君

本文由 @熵君 原創發佈於人人都是產品經理。未經許可,禁止轉載。