計算機中很多問題都會涉及存儲。在任何時候，成為一個好的計算機工程師都需要了解計算機的存儲結構。與存儲相關的理論和技術可以大致從兩個維度來討論：數據使用的特點和存儲設備的特點，以及存儲系統本身的層次結構。

7.1 訪問：順序 vs. 隨機#

順序訪問#

  • 從頭到尾依次訪問一批數據，類似排隊買火車票
  • 適合於讀取或寫入大量數據，例如看完整部電影、調整全部工資單
  • 磁帶和錄像帶時代的主要訪問方式

隨機訪問#

  • 能夠直接訪問任意特定的數據，而不需要從頭開始
  • 類似銀行叫號系統，不用關心前後是誰
  • 需要給存儲單元編號（地址），有了地址，隨機訪問才成為可能

高頻單詞二元組問題#

這是一道 Google 面試題：如何用一台服務器從 1TB 的數據中，統計出出現頻率最高的 100 萬個單詞二元組？

解題過程展現了順序訪問和隨機訪問的權衡：

  • 方法一（直接存二維大數組）：空間不可行，20 萬個詞的二維數組需要 160GB
  • 方法二（稀疏矩陣壓縮存儲）：統計前不知道非零元素的分布，不方便動態調整
  • 方法三（哈希表）：理論上正確但空間仍然太大（需要 1/4 到 1/2 TB 的存儲空間，因為大部分二元組只出現一兩次，符合齊普夫定律）
  • 最終方案：採用分治算法
    • 將 1TB 數據分為 1000 份（每份 1GB），用哈希表統計每份的二元組頻率
    • 將結果按單詞編號排序寫入磁盤，按照編號歸併合併
    • 用中值分割算法找出最高頻的 100 萬個二元組
    • 這本質上就是 MapReduce 的單機版

要點：計算機中的某些存儲設備只方便順序訪問，不方便隨機訪問。在進行海量數據處理時，要爭取在掃描數據時將所有該做的工作做完，避免反覆讀/寫數據。

7.2 層次：容量 vs. 速度#

從 CPU 高速緩存到雲存儲#

計算機的存儲系統是分層次的，越靠近計算單元，容量越小、訪問時間越短；越遠離計算單元，容量越大、訪問時間越長。

  • L1 高速緩存：每個核 64KB，訪問只需 4 個時鐘周期
  • L2 高速緩存：每個核 256KB，訪問需 10 個時鐘周期
  • L3 高速緩存：四核共享 8MB，訪問需 35 個時鐘周期
  • 內存（DRAM）：通常 100 個時鐘周期以上，容量為 GB 級別
  • 硬盤：容量為 TB 級別，但隨機訪問延時約 10 毫秒（比 L1 慢 1000 萬倍以上）
  • 雲存儲：傳輸速率受限於網絡，比服務器內部慢一個數量級

緩存命中率的影響#

  • 假定緩存命中時每個時鐘周期執行一條指令，未命中時需要額外 100 個時鐘周期
  • 當未命中率 m=3% 時，程序執行效率 e = 1/(1+100m) = 25%，即處理器 75% 的性能都沒有發揮出來
  • 提高緩存命中率的關鍵是讓程序和數據具有局部性（locality）

兩個真實案例#

案例一：Google 搜索提示功能

  • 根據用戶輸入的部分搜索關鍵詞提示完整的搜索關鍵詞串
  • 初始實現佔用了 90% 以上的運行時間在 N 元組查找上，因為 N 元組列表太大，無法放在高速緩存中
  • 改進方案：
    • 根據用戶輸入的首字母引導到不同服務器
    • 將最常見的短語做成很小的模塊，適合放入高速緩存
    • 結果：查找速度提高一個數量級，節省了 80% 的服務器（約 80 萬美元）

案例二：雲計算公司的存儲問題

  • 一家公司使用 Hadoop 開源軟件搭建雲計算系統，效率非常低
  • 原因是他們試圖提高雲存儲中文件系統的隨機訪問效率
  • 但雲存儲系統（如 Google GFS、Hadoop）是為順序訪問而設計的，根本不可能像內存那樣做到高效的隨機訪問
  • 正確做法是使用類似 Google BigTable 的工具，在內存中建立索引

要點：計算機的存儲系統是分層次的。越靠近計算單元，容量越小，訪問時間越短；越遠離計算單元，容量越大，訪問時間越長。計算機存儲系統應做到能夠兼得外圍海量存儲設備的容量，同時在大部分情況下按照內部快速存儲器的速度訪問數據。

7.3 索引：地址 vs. 內容#

索引的基本概念#

  • 索引是將原本需要順序訪問的內容變成可以隨機訪問的最常用工具
  • 類似書籍的目錄和關鍵詞索引，讓讀者可以快速找到特定內容

兩種建立索引的方法#

  • 有序索引：按照被索引的內容（如數值）排序，可以通過折半查找在 log N 次內找到，適合範圍查詢
  • 哈希表索引：可以在 O(1) 的時間內找到相應內容，適合精確查找，但不方便範圍查詢

範圍查詢的挑戰#

  • 哈希表擅長精確匹配，但要想找到一定範圍內的所有數值就不管用了
  • 有序索引可以通過折半查找先定位邊界，然後順序掃描範圍內的數據
  • 在現實中，很多看似簡單的範圍查詢（如找股價在特定範圍的股票）在工程上實現起來頗為困難

內容檢索#

  • 人臉識別、圖片搜索等問題通常稱為內容檢索（content based search）或匹配
  • 難點在於如何將不同的內容變成可以檢索的特徵
  • 今天 Google 的搜索引擎中索引了幾萬億張圖片，可以根據圖片內容進行搜索
  • 關鍵在於是否有辦法建立有效的索引，從存儲器中訪問到想要找的內容

存儲的地址本質#

  • 在計算機中，數據需要編號存放和訪問，設備也需要編號（如打印機 001、鍵盤 010）
  • 這些編號被稱為地址，和存儲的地址性質相同

要點：對順序存儲的數據實現隨機訪問常用的方法就是建立索引。在存儲中，重要的是弄清楚隨機訪問和順序訪問的關係。計算機程序設計的藝術就在於能夠將一部分原本需要隨機訪問的問題，變成順序訪問能夠解決的問題。