WEB 開發

Web 效能優化 – 伺服端快取 (Server-Side Cache)

發表於 鄭 中勝

源伺服器 (Origin Server) 不像 Client 得發送 HTTP 請求，
那為何需要 伺服端快取 (Server-side Cache) 呢？
 
PageSpeed Insights 說明 Server 回應時間不宜超過 200 毫秒，
造成回應變慢的可能原因有很多，
必須將這些因素全部納入考量，才能加快伺服器回應時間，包括：

緩慢的 應用程式邏輯、緩慢的 資料庫查詢、
緩慢的 轉送作業、框架、程式庫、
資源 CPU 耗盡 以及 記憶體耗盡。

 
這裡假設 應用程式邏輯、框架 與 程式庫 時間複雜度皆正常，
如果用了一些 O(2n)、O(n!) 函式，誰也救不了你 😂。
 
除了基本的 HTML/CSS/JS 壓縮 (e.g., YUIcompressor、Closure Compiler)、負載平衡、
內容傳遞網路 (CDN)、影像最佳化 與 延遲載入 (lazy load)、傳輸/內容編碼…，
伺服端快取 (Server-side Cache) 更是效能提昇的中流砥柱。
 
其主要用於：

加快/消除 動態資料 的 生成速度，
以及 靜態資料 的 讀寫/轉送作業，
以減輕 Server 負載，大幅地提升效能！

 
 
如此一來，儘管是我的爛爛小 Server，
也能在 GTmetrix 或 PageSpeed Insights…等網站分析工具，拿 100 分喔！😇
 

(好啦，其實一堆懶的優化內文都超低分 😂)
 
 
以下將以 PHP 為例 (因為它最欠優化 😂)，
並帶入基礎的計算機原理，說明如何以 快取 (cache) 解決效能/負載問題，
千萬別停留在「 PHP 需為每個請求 生成 HTML 」的 錯誤觀念 😏。
 

 

頁面快取 (Page Cache)

Cache 的核心思想其一：保存執行結果，
對於 Server-side 來說，也就是：

設法將 動態內容 轉為 靜態 表示

 
 

執行腳本

例如，Server 網站目錄有一 index.php：

 
 
使用者瀏覽此頁面，則 PHP 直譯器 需掃描、解析 index.php 腳本 [ 抽象語法樹 (AST)]，
再編譯為 操作碼 (Opcode)、轉譯執行並輸出回應訊息 (e.g., HTML 頁面)，
最後交由 Web Server 設置元資料，回應此 HTML 報表文件：

 
如果同時一萬人連線呢？

Server 需重複上述步驟 一萬次！

 
AST Demo:

 
 

命中 vs. 錯失
(Hit vs. Miss)

若執行內容牽涉耗時項目 (e.g., 資料庫查詢、Disk I/O)，Server 肯定直接爆掉 😱…，
於是，一個簡單、容易實作的想法 — 保存當時產出的 HTML 頁面，
甚至是經過 內容編碼 (e.g., gzip) 的表示資料，此作法又稱 頁面快取 (Page Cache)。
 
如此一來，若 Client 訪問之頁面，已被 Server 保存過 (快取) — 快取命中 (Cache Hit)，
Server 便能直接傳輸此 靜態頁面，大大減少了負擔！
反之，快取未命中/錯失 (Cache Miss) 則得執行執行腳本，動態生成表示資料。
 
 
[註]:
頁面 是指 HTML Page，而非虛擬記憶體的分頁 (Page)，
聽起來像廢話 😂，然而，兩者的快取原理是息息相關的！
 
例如，虛擬位址 以 轉譯後備緩衝區 (TLB) 索引快取，尋找對映的實體位置，
若『分頁項目』不存在 (e.g., TLB 錯失)，才前往 分頁表 (page table) 尋找。
 

Photo by Wiki.
 
 

預先載入 (Preload)

上面提出了一個問題：
「第一個訪問的 使用者 不就很衰小？
因為頁面尚未被快取，Server 仍需執行腳本。」
 
Ans:

沒錯 ㄏㄏ，他很衰小 😃。

 
第一個 頁面 訪問者，因為 冷啟動 的 快取錯失 (cold-start misses)，
莫名得遭受 錯失懲罰 (miss penalty) –『前往 下一層 儲存體/腳本，獲取資料的時間』。
 
第二個 同頁面 訪問者，就很幸運啦，
能直接取得 Server 為第一個使用者儲存的頁面快取，享受 🚀 咻咻咻～ 的速度。
 
基本上，讓第一個使用者衰小一下沒關係，
但若不幸，剛好是 Google BOT，這可對搜尋引擎的排名不利！
 
google-bot
 
因此，Server 能使用 預先載入 (preload) 的方式，
提早將 頁面快取 準備好 (e.g., 一個請求 for 迴圈)，
如此一來，所有人的速度都能 🚀 咻咻咻～ 啦！
 
其概念源自 計算機領域 中的 — 預先提取/預取 (prefetch)：
『 CPU 效能再怎麼高，記憶體存取速度跟不上也沒用 』 (e.g., 車很快 but 沒油)，
因此預測、載入 可能用到的資料/指令 至 快取記憶體，將大幅增進執行效率 (i.e., 防發呆 🤓)。
 
許多 源伺服器 (Origin Server)，
會不斷 預先載入 快取，並同步於 閘道 (Gateway)、CDN 等反向代理，
如此，源伺服器 甚至 不需處理任何請求。
 
這正是 計算機領域中，多層級快取 (multilevel caching) 最佳化實作 的兩大優勢之一：

較低層級快取/儲存體 (i.e., 此例的 源伺服器)，
在 閒置 (idle) 時，能做些防範 快取錯失 (cache miss) 的事。

 
 

Web Server vs. Script

頁面快取 (Page Cache) 概念很簡單 — 先判斷快取是否存在，
快取命中 (cache) 則進行轉送作業，否則，處理請求 並將 結果存入快取：

<?php

if (isCacheExist()) {
    $handler = new CacheHandler();
} else {
    $handler = new RequestHandler();
}

$handler->do();

 
最簡易的實作方式，能透過 file_exists() 檢查檔案存在情形，
使用 ob_start() 輸出緩沖區、與 file_get_contents()、fwrite() 系列的串流處理，
擅長 C 語言的朋友，應該會感到格外親切 😇。
 
例如，將一腳本產出頁面寫入檔案：
(礙於篇幅，原諒我 PHP 混 HTML 😅)

<?php ob_start(); ?>

<!DOCTYPE html>
<html>
<body>
<p>Hello, World!</p>
<p>頁面生成於: <?=date("Y-m-d H:i:s")?></p>
</body>
</html>

<?php
// 取得輸出緩衝區內容
$content = ob_get_contents();

// 發送 並 關閉 輸出緩沖區
ob_end_flush();

// 寫入檔案
$fp = fopen("index.cache", 'w');
if ($fp) {
    fputs($fp, $content);
    fclose($fp);
}

 
 
當然，不一定得在 後端程式語言 (e.g., php) 處理 ，
直接在 Web Server (e.g., Apache, Nginx) 處理將 更有效率！
例如，URL 改寫 或 直接使用現成的 快取模組。
 
或如 Nginx 使用簡單的 try_files，嘗試讀取快取檔案：
(變數 $cachefile 需自行設置)

location / {
    try_files $cachefile $uri $uri/ /index.php;
}

 
 

硬碟 vs. 記憶體

主記憶體 的效能 遠遠遠高於 硬碟，
大部分 快取 機制，偏好將 重點 資訊儲存於 記憶體 中，
(需考量 Server 性能、負載方式 與 記憶體空間)
而其他「非熱門」則存於 硬碟，以減少記憶體空間的開銷。
 

Photo by 記憶體跟硬碟有什麼不同 (Lynn).
 
許多人對 頁面快取 (Page Cache) 的 錯誤迷思 是：
「頁面需儲存於 硬碟 (disk)，因此效能低弱」。
 
如文初所述：
「加快 靜態資料 的 轉送作業」，也是快取的目的之一，
而非僅限 於保存 動態 生成的結果，
事實上，Page Cache 廣泛實現在 記憶體 上！
// 可參考 HTTP 系列 — (6-1) 快取 (Cache) 之 Varnish
 
 
待會就知道如何實作囉 😇。
 
 

WP Super Cache

WP Super Cache 是本站目前的 頁面快取外掛。
 

 
WP Super Cache 算蠻標準的 義大利麵程式碼，
比起其他外掛 (e.g., W3 Total Cache) Coding Style 完全不對味…。
 

 
然而，W3TC 功能齊全 卻 Bug 多多，
甚至出現開源的修補版本 w3-total-cache-fixed 😂。
 
WP Super Cache 功能單一、實作簡單，適合模組化，
玩過許多快取外掛，也 Trace 了不少 Code 後，
仍返璞歸真，以其為底 結合 Nginx X Mod 覆寫，已可符合我基本需求 😄。
 

 

編譯快取 (Compilation Cache)

然而，上例的 HTML 頁面，若只對 使用者 Jason 有效，
一旦使用者不同，還是得處理請求、動態產生…，
快取靜態頁面根本無濟於事 😭。
 
顯然地，對於較少變化的共享內容 (e.g., 首頁、文章) HTML 頁面快取 是不錯的選擇，
而對於需依不同 User 提供 客製私有內容，可說是一點 屁 用都沒有 (重點歪 😂)。
 
操作碼快取 (Opcode Cache) 或中介的 位元組碼快取 (Bytecode)，
即透過將編譯好的內容儲存，供後續使用，解決 PHP 每次都得重新解析、直譯程式碼的問題。
 
 

HHVM

Facebook 透過將 HACK or PHP 程式碼，編譯為中介的 Bytecode (位元組碼)，
並以 HHVM 虛擬機 翻譯、執行，而非如過去以 HPHPc 將 PHP 編譯為 C++ 程式碼。
 
但是，此 Bytecode 僅能透過 HHVM 執行，我們的主機並 看不懂，這會造成效率低弱，
好在，能進一步以 即時 (JIT) 編譯器，動態最佳化為 x64 機器碼 (machine code)，
提升執行效能 50% ~ 300% 😲，終於，在 2012 年末 HHVM 正式打敗 HPHPc 並沿用至今。
 

(Photo By HHVM blog)
 
 
HHVM Concept:

 
 
Ubuntu 可透過官方提供的指令安裝：

# installs add-apt-repository
sudo apt-get install software-properties-common

sudo apt-key adv --recv-keys --keyserver hkp://keyserver.ubuntu.com:80 0x5a16e7281be7a449
sudo add-apt-repository "deb https://dl.hhvm.com/ubuntu $(lsb_release -sc) main"
sudo apt-get update
sudo apt-get install hhvm

 
其他 OS 建議使用 Docker。
 
搭配 Nginx + PHP-FPM，可在 location 中加入：

root /path/to/your/www/root/goes/here;
fastcgi_pass   127.0.0.1:9000;
# or if you used a unix socket
# fastcgi_pass   unix:/var/run/hhvm/sock;
fastcgi_index  index.php;
fastcgi_param  SCRIPT_FILENAME $document_root$fastcgi_script_name;
include        fastcgi_params;

 
站在巨人的肩膀，高效 PHP 立馬完成 😇：

 
 
詳見官方 教學 與 好文 效能提升原理。
 
 

Zend OPcache

HHVM 不一定適用每個人，且可能需學習新的語法 (i.e., HACK)，
此時，不妨使用 PHP 5.5 內建的 操作碼快取 — Zend OPcache！
 
儘管 Zend OPcache 與 HHVM 相形見絀，可別小瞧「Zend」了，
PHP 7 可不輸給 HHVM，其核心正是 Zend Engine 3。
 

Photo by Zend.
 
Zend OPcache 透過預先編譯腳本為 Zend 操作碼 (Zend Opcode)，
並儲存於 記憶體 中，供後續請求直接執行，
消除了 PHP 在每個請求上讀取、解析腳本的需求，以提高 PHP 性能。
 
透過 Trace 其 原始碼，可進一步理解 PHP 底層運作方式，
例如 常見的 echo()：

#define ZEND_ECHO 40

其 VM Handler：

ZEND_VM_HANDLER(40, ZEND_ECHO, CONST|TMPVAR|CV, ANY)
{
    USE_OPLINE
    zend_free_op free_op1;
    zval *z;

    SAVE_OPLINE();
    z = GET_OP1_ZVAL_PTR_UNDEF(BP_VAR_R);

    if (Z_TYPE_P(z) == IS_STRING) {
        
	   ... 略 ...

 
 

配置

這是我結合官網的慣用配置 (php.ini)：

; OPcache 記憶體大小 (MB)
opcache.memory_consumption=128

; 慣用字串記憶體大小
opcache.interned_strings_buffer=16

; 可快取的最大檔案數量 (php)，值需大於檔案總數
opcache.max_accelerated_files=7963

; 快速釋放記憶體，取代分批釋放
opcache.fast_shutdown=1

; 用於 CLI PHP 測試、調整
opcache.enable_cli=1

 
至於，上述的 max_accelerated_files，
可透過 find 指令，查看專案的 php 檔案數量：

find /路徑/專案/ -name '*.php' | wc -l

 
或透過 正規表達式 (使用 $ 匹配結尾，預防類似 xxx.php.gzip 的檔名)：

find /路徑/專案/ -regex '.*\.php$' | wc -l

 
或者，以管線命令 grep 來做：

find /路徑/專案/ | grep '.*\.php$' | wc -l

 
另外，也可以使用 opcache.file_cache=目錄路徑，
開啟檔案快取 (硬碟) 做為備選快取層級，
詳見 官網 設置 、 鳥哥 find 與 管線命令 grep 教學。
 
 

OPcache GUI

開源專案 opcache-gui，提供了乾淨、響應式的 Zend OPcache 資訊介面，
包含 相關設定和快取情形，並提供即時更新 (使用 jQuery 和 React)。
 

 
 
安裝方式非常簡單，執行 wget 指令，
從 GitHub 下載其 index.php 即可：

wget -O index.php https://raw.githubusercontent.com/amnuts/opcache-gui/master/index.php

當然，也能直接到 opcache-gui 複製/貼上、下載/上傳。
 
 

Composer

另一安裝方式是使用 PHP 套件依賴管理工具 — Composer，
進入 Composer 下載頁 執行安裝指令後，
會在當前目錄下產生 PHP 歸檔 (archive) — — composer.phar。
 
可將其 移動 (mv) 到 $PATH，以供全域使用：

sudo mv composer.phar /usr/local/bin/composer

 
鍵入 composer 指令就能看到選項列表啦！

 
 
接著，執行以下指令，Composer 便會自動下載最新的 opcache-gui 元件：

composer require amnuts/opcache-gui

 
 

監控 OPcache

大功告成！

 
使用瀏覽器，便能看到主機、平台、OPcache 版本，
還有 快取 的使用情形 (e.g., 快取命中、空間佔用)，
甚至有貼心的 Reset cache 功能，幫你清除快取！
 
最後，Server 別忘了配置存取權限 (e.g., 授權子請求、OAuth2、JWT)，
以防三不五時被別人清理一下 😂，例如 HTTP 基本驗證：

location ~* /目錄名稱 {
    auth_basic           "提示字串";
    auth_basic_user_file conf/htpasswd;
}

 
或指定特定 IP：

location / {
    deny  192.168.1.1;
    allow 192.168.1.0/24;
    allow 10.1.1.0/16;
    allow 2001:0db8::/32;
    deny  all;
}

 

 

查詢快取 (Query Cache)

執行腳本時 (無論是否有編譯快取)，多少免除不了 資料庫查詢… 等 Disk I/O，
這也是過往常見的 Web 效能瓶頸 (尤其對 線上交易處理)。
 
幸好，大部分資料庫都提供了 查詢快取 (Query Cache)，例如 MySQL Query Cache，
顧名思義，將 查詢的 語句 與 結果 儲存起來 (通常以 Hash 維護)，
以供後續相等查詢語句覆用，而非再次解析、執行查詢。
 
這並非甚麼新鮮東西 (十幾年前就有了)，但為何仍存在大量 DB 瓶頸？
 
Ans:

Query Cache 僅適用於 不常更動的資料表，
以及 Server 會使用許多相同查詢 的環境。

 
當資料表發生改變 (e.g., 新增、刪除、修改)，會使 Query Cache 的快取無效，
一旦更新的頻繁，快取操作反而帶來了效能延遲。
 
因此，是否啟用 Query Cache 功能，需考量自身需求而定，
像是不常更新 blog 的我，可能就很適用 😂。
 

 

物件快取 (Object Cache)

物件快取 (Object Cache) 是最普遍的快取機制之一，
就像 Linux 萬物皆檔案 的概念，
無論是 常用變數、Server 設定檔、遞迴函式的執行結果 (見 動態規劃 DP)，
甚至上述提及的 HTML 頁面 以及 資料庫查詢結果 (e.g., ORM)，
都可藉由 反序列化 為物件來進行存取。
 
 

資料庫快取

物件快取 (Object Cache) 應用於 資料庫查詢結果，
又稱為 資料庫快取 (Database Cache)。
 
與上述的 查詢快取 (Query Cache) 不同的是：
省去 了 資料庫連線、[物件關聯對映]…，
最重要的是：加快了 資料 的 讀寫/轉送作業。
 
 
當 資料存取層 與 應用層 隸屬於不同 主機 (Host)，
物件快取 能有效地減少網路流量，優勢尤其明顯。
 
然而，並不建議使用「資料庫快取」一詞，
易與 原生資料庫查詢快取 產生混淆。
 
 

Redis

物件快取 一樣支援 硬碟 與 記憶體，
而說到高效能的 記憶體 物件快取，Redis 與 Memcached 更是其中的佼佼者 ！
 
Redis (REmote DIctionary Server) 是 in-memory 的資料結構儲存體，
能用作 key-value 資料庫、快取 或 訊息中間人 (broker)…，
也支援 定時寫入硬碟 (RDB) 或 記錄指令日誌 (AOF) 達到 資料持久化 (Persistence)！
 

 
總之，個人大推 😇。
 
 

Redis Server

安裝方式再簡單不過，直接進入 官網 下載即可，
個人建議使用 Docker，叢集部署、開發測試… 會更方便 😇！
 
Docker 只需一行命令：

docker run -p 6379:6379 --name MyRedisServer -d redis

(使用 TCP 6379 port、容器名稱 MyRedisServer、背景執行 redis)
 
便能秒開 Redis Server：

 
更多 redis image 用法，詳見 官網。
 
 

Redis Client

有了 Redis Server，便能透過各種 Client 進行操作囉！
官網 彙整了各種開源 Redis Client，可自行選擇最喜愛的語言與實作 😊。
 
最普遍的是 SET 命令 (設定 name 為 “Jason”)：

> SET name "Jason"
OK

 
與 GET 命令 (取得 name 的值)：

> GET name
"Jason"

 
如果您仍在觀望，推薦以 Try Redis 服務進行線上體驗 (儘管其鮮少維護)，
接著，以開源的 Redis PHP Client 套件 — predis 示範：
 
 

安裝 predis

接續上述的 Composer 體驗，一行指令，predis 來相見：

composer require predis/predis

 
太神啦！
 
Photo by Composer.
 
 

使用 predis

在開始之前，記得在要使用 Predis 的腳本 (.php) 開頭，
導入 Composer 幫我們做好的 元件 自動載入器 (Autoloader)：

<?php
require __DIR__ . '/vendor/autoload.php';

 
接著，便如同上例，對 Redis Server 下命令 (e.g., SET、GET) 啦！
差別只在於，將 命令 改為 method：

// 實例 (P)redis 客戶端
$client = new Predis\Client();

// SET 命令
$client->set('foo', 'bar');

// GET 命令
$value = $client->get('foo'); // 得到 bar

 
或許，你會想用方便的 累加指令 (e.g., i++) — INCR：

$counter = $client->incr("counter");

println("Visits: $counter");

 
一個具有 瀏覽人次 的小網頁就完成啦！
(重新整理頁面，counter 值會遞加)

 
更多命令列表，詳見 Redis 官網，
真的很貼心，每個 命令 都提供了時間複雜度 🤗。
 
 
[註]:
我寫了個 Closure 小函式，
可在執行其他方法的同時，印出其方法名稱、參數、回傳值，
並依不同背景顏色區分 (如範例)，覺得漂漂的話可去 GitHub 中拿喔 😆。
 
 

Docker 群集

群集模式 是一項 Docker 功能，其提供內建容器協調流程功能，
包括 Docker 主機的原生叢集和容器工作負載的排程。
一組 Docker 主機在其 Docker 引擎於「群集模式」中一起執行時，即構成「群集」叢集。
— Microsoft

 
我已將上述範例，製為 Docker 映像檔 — jasonnn331/predis-demo，
您或許會想嘗試以 docker swarm init 指令，初始化 本機/其他主機 為 群集管理員，
並在 節點 (主機) 準備完畢後，對 群集管理員 下達：
docker stack deploy -c docker-compose.yml my-app-name 以進行部署。
 
記得！先儲存此「docker-compose.yml 」檔：

version: "3"
services:
  web:
    image: jasonnn331/predis-demo
    deploy:
      replicas: 5
      restart_policy:
        condition: on-failure
      resources:
        limits:
          cpus: "0.1"
          memory: 50M
    ports:
      - "9487:80"
    networks:
      - webnet
  redis:
    image: redis
    ports:
      - "6379:6379"
    volumes:
      - .:/data
    deploy:
      placement:
        constraints: [node.role == manager]
    networks:
      - webnet
networks:
  webnet:

 
恭喜！秒速完成 容器負載平衡，
流量提升也不怕！再次提升伺服器回應時間：

(擁有 5 個 PHP Server Container、1 個 Redis Server 的群集)
 
老樣子，訪問方式不變，打開瀏覽器，訪問 localhost:9487 即可：

 
 
上述範例，已展示 Redis 實作 記憶體快取 的雛形 (e.g., 瀏覽人次 ++)，
延伸為 頁面快取 或 資料庫快取，也是相同概念 — 「先查有沒有 (快取)，再看做不做」，
相信對各位已是輕而易舉 😇：

 

 

多層級快取 (Multilevel Cache)

既然 主記憶體 速度這麼快，我們當然想將所有快取置於其中，
然而，如下圖所示，較上層的 記憶體階層 空間較小 (而且差距遠大於圖例)，
因此，考量 快取 的 生命週期、置放策略 與 一致性 尤其重要。
 

Photo by 記憶體跟硬碟有什麼不同 (Lynn).
 
接下來，將結合本篇種種快取的概念，摻在一起做撒尿牛丸。
 
 

快取性能

一個我很喜歡的延伸想法：
『 不討論傳輸介質，而是將 CPU 處理的所有資料來源，
視為 單體式系統 的不同儲存階層。 』
這也是為何 — 許多 計算機領域知識，到最後都是相通的。
 
概念圖：

 
 

計算機

John Hennessy 告訴我們：
計算機組織中，改善快取效能 主要的兩種面向：

  1. 降低錯失率: 增加快取 命中率 (hit rate)。
  2. 降低錯失懲罰: (當快取未命中/錯失) 減少前往 下一層 儲存體，獲取資料的時間。

 
回到文初所述，Server-side Cache 主要用於：

加快/消除 動態資料 的 生成速度，
以及 靜態資料 的 讀寫/轉送作業。

 
正是對應了此二點！
我們使用 預先載入 (preload) 與 CDN、共享代理…，增加了 快取命中率，
使用 Redis 快取資料庫結果，減少前往 DB 的 I/O 時間…。
 
並且：

上一層的未命中，可能是下一層的命中。

 

權衡

快取的實現，全仰賴 區域性原則 (principle of locality)：

  1. 時間區域性 (temporal locality): 一筆資料若被存取，則可能很快地再次被存取。
  2. 空間區域性 (spatial locality): 一筆資料若被存取，其附近的資料也有即將被存取的傾向。

然而：

記憶體空間是固定的。

 
記憶體中的 Page、OPcode 與 Redis…等快取，僅能佔用 有限的空間，
其中一方佔據過大的空間，貌似利用了 空間區域性 (spatial locality) 降低了錯失率，
實則不一定，若搶奪到了其他快取機制的可配置空間，
將造成它們的錯失率上升，甚至增加了 錯失懲罰，以致效能降低。
 
老話一句：

沒有銀彈 (No Silver Bullet)。

 
「提升 A 卻產生了 B」的問題，在計算機領域比比皆是，
例如，增加記憶體容量 雖是非常有效的作法，
卻也增加了快取命中/查找的時間 和 荷包的損失 😭。
 
權衡利弊，是多層級快取效能的核心，
策略可能隨時因層級變化而跟著改變。
 
因此，需考量不同層級間的特性，決定最有效率的組合。
也就是 John Hennessy 所述的 硬體設計原則之一：

好的設計，需要好的折衷。
Good design demands good compromises.

 
 

快取生命週期

適時的清除快取是必要的，除了可能有逾期的內容，
上述提到的「有限記憶體」也是考量之一，
以下將簡單說明「清除」的時機點。
 
 

時間

以 WP Super Cache 的 頁面快取 (Page Cache) 為例，
就是設定個時間，並定時檢查，刪除檔案/釋放記憶體：

 
引用其建議快取策略：

 
 

EXPIRE

資料庫的 查詢快取 (Query Cache) 很單純，因此不提 (e.g., 增刪改 時清除)，
而 Redis 則提供了 EXPIRE 命令，能設置 Key 的 逾期時間，並在過期後 自動刪除：

> SET name Jay
OK
> EXPIRE name
(integer) 1

 
EXPIRE 回傳 (integer) 1 代表 True，逾時設置成功，
EXPIRE 回傳 (integer) 0 代表 False，此 鍵 (key) 不存在。
 

TTL

你可以隨時以 TTL (time to live) 命令，檢索 鍵 (key) 的 逾期時間：
(一秒後)

> TTL name
(integer) 9

(六秒後)

> TTL name
(integer) 4

 
(一百秒後)

> TTL name
(integer) -2

 
Q：哪泥！？ 怎麼不是 10 – (100) = -90？
 
Ans：

TTL 回傳 (integer) -2，代表 鍵 (key) 不存在，而非 過期 2 秒；
TTL 回傳 (integer) -1，代表 鍵 (key) 存在，但沒有設置相關逾期時間。

 
 

揮發性 (volatile)

當一個 鍵 (key) 有設置相關逾期時間，在 Redis 中稱作:
— — 具有 揮發性 (volatile) 的。
 
[註]:
不只和 揮發性記憶體 (Volatile memory) 具有類似含義，
也可使其與 Java 雙重檢查鎖 (Double-checked locking) 單例模式中，
常用於確保 執行緒安全 的 Volatile 修飾符，添上 異曲同工之妙，
然而這種做法衍生了新的問題：Redis 主機當機了怎麼辦？
 
當設置了 鍵 (key) 的逾期時間，可透過各種 *STORE (儲存) 命來來清除：
(e.g., DEL, SET, GETSET )

完整的 EXPIRE 指令用法，詳見 Redis 官網。
 
 

空間

以 Google 的 Web Server 優化模組 PageSpeed 為例，
大部分快取機制可限制其容量上限，並設置排程自動清除：

 
 
Redis 也可以使用設定檔 redis.conf，
設置快取的容量上限，與 置換策略，例如：

maxmemory 2mb
maxmemory-policy allkeys-lru

 
 

LRU 演算法

上方提到快取的一大重點 — 置換策略 (Replacement Policy)。
也就是當快取容量上限滿時，或清理排程欲釋放空間時，該清除誰呢？
 
有 先進先出 (FIFO) 的 佇列法、後進先出 (LIFO) 的堆疊法
維基百科 列出了詳盡的 快取置換策略，有興趣可以把它讀完 😵。
 
這裡要介紹的是最普遍的 最近最少使用演算法 (Least Recently Used, LRU)，
其優勢在於，同時考量到 時間區域性 與 空間區域性，
原理很簡單：「最少看的書，通常放在最下面；最少穿的衣服，通常放在 (衣櫥) 最裡面」。
 

 
試想，我們每此會將看完的書放在最上層，
某天要用中間層的書，也會用「快速抽取大法」，在上層不倒的情況下抽出來，
久而久之，最少被看到的書，自然就落在最下方啦！
 
人能夠輕易在最上方『增加節點』，
並使用「快速抽取大法」輕易實踐『刪除中間節點』，程式呢？
 
Ans:

靈活的 雙向鏈結串列 (Doubly Linked Lists)

 
 

雙向鏈結串列 + 雜湊表

由於 雙向鏈結串列 在不需要搜尋的情況下，能以 O(1) 的靈活性，
執行 head 與 tail 的插入、刪除。
 
其結合 雜湊表 維護鍵值對資料，成為 LRU 最普遍的實作方式，
LeetCode 給出了簡單實用的範例！
 
值得一提的是，此實作建立了 偽 head 與 偽 tail，
能輕易的記錄邊界，因此更新過程中不需要去檢查空節點，
程式碼簡潔的同時，又增進了性能，非常值得學習！
 
實作關鍵 get、put：

public int get(int key) {

    DLinkedNode node = cache.get(key);
    if (node == null) {
        return -1; // should raise exception here.
    }

    // move the accessed node to the head;
    this.moveToHead(node);

    return node.value;
}


public void set(int key, int value) {
    DLinkedNode node = cache.get(key);

    if (node == null) {

        DLinkedNode newNode = new DLinkedNode();
        newNode.key = key;
        newNode.value = value;

        this.cache.put(key, newNode);
        this.addNode(newNode);

        ++count;

        if (count > capacity) {
            // pop the tail
            DLinkedNode tail = this.popTail();
            this.cache.remove(tail.key);
            --count;
        }
    } else {
        // update the value.
        node.value = value;
        this.moveToHead(node);
    }
}

 
使用範例：

public class Main {

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2 /* capacity */);

        cache.set(1, 1);
        cache.set(2, 2);
        cache.get(1);       // returns 1
        cache.set(3, 3);    // evicts key 2
        cache.get(2);       // returns -1 (not found)
        cache.set(4, 4);    // evicts key 1
        cache.get(1);       // returns -1 (not found)
        cache.get(3);       // returns 3
        cache.get(4);       // returns 4
    }
}

 
 

再談 Redis

當 Redis 做為快取使用時，能在新增資料時，
自動、方便地清除舊資料，並提供了許多快取置換策略。
其中，allkeys-lru，正是一種 類 (Approximated) LRU 演算法。

maxmemory-policy allkeys-lru

 
由於 LRU 本身的特性：『需以某種形式，記錄最久沒用到的資料』，
這可能造成較多的記憶體開銷，或增加尋訪時間。
 
Redis LRU 演算法，能以最接近 LRU 結果的前提，
更改樣本數設定，調整演算法精準度，以提升效率：

maxmemory-samples 5

 
而 PageSpeed 也使用了 Redis 與 LRU，以提升物件的存取效能，
詳見 官網
 
 

隨機置換

另一種常見的置換法是 隨機置換 (random replacement)，
當所有 鍵 (key) 的覆用率差不多時，這是優選的置換策略！
在 Redis 中需設置為：

maxmemory-policy allkeys-random

 
至於，為什麼不使用聽起來很合理的 LRU 就好了？
 
Ans:

效能

 
這就像問 陣列 vs. 鏈結串列 的差異一樣，
若 LRU 使用鏈結串列實作，其不支援 隨機存取，而是 循序存取 (Sequential access)，
起碼也要 O(n) 時間複雜度，若彼此重要性差不多，何不 O(1)？
 

Photo by Redis.
 
完整實作 LRU 的昂貴代價，不僅發生在 Redis，
計算機的硬體實作問題，更比比皆是 (e.g., 多路 集合關聯式 快取)。
 
例如，由於 分頁錯失/未命中 的懲罰時間很大，
虛擬記憶體 時常以各種 LRU 變形 (e.g., LRU–K、ARC) 做為分頁置換演算法，
Stack Overflow 此篇有趣的 討論，頗值得一看。
 
 

作者: 鄭中勝
喜愛音樂，但不知為何總在打程式 ? 期許能重新審視、整理自身所學，幫助有需要的人。

在《Web 效能優化 – 伺服端快取 (Server-Side Cache)》中有 6 則留言

  4. 其實我才看了『前言』，就很衝動地想來留言。
    這一定是一篇非常完整也非常棒的介紹。
    因為以往都只能爬國外的資料，專有名詞、語意思考邏輯的差異，往往讓初學者摸不著頭緒。
    偶爾爬到中文的介紹，絕大多數僅止於淺談，初學者還是霧裏看花。
    我願意花大把的時間閱讀你的文章，謝謝妳無私且用心的分享，相當感激！

    回覆

發表迴響