Prolly Tree：Dolt 資料庫版本控制的資料結構基礎
LWN.net / DoltHub · 2026-05-01
Dolt 是一個支援 Git 風格版本控制的關聯式資料庫，可對整個資料庫做 commit、branch、diff、merge。這些操作的底層資料結構是 Prolly Tree（Probabilistic B-tree），一種結合 B-tree 結構效率與內容定址（content-addressed）分塊的複合式資料結構。LWN 最近對 Prolly Tree 的工作原理做了深入分析。
傳統 B-tree 的版本控制問題
標準 B-tree 在插入或刪除一個鍵值時，為維持平衡而重新分配節點，受影響的節點集合是不確定的（取決於樹的當前形狀）。若用內容哈希（content hash）標識每個節點（如同 Git 的 blob），任何重新平衡都會導致大量節點哈希值改變，使得 diff 計算代價高昂——幾乎等同於重新掃描整顆樹。
Prolly Tree 的分塊策略
Prolly Tree 的核心思想來自 rolling hash 技術（與 rsync 的區塊偵測類似）：節點的分裂點由資料內容本身決定，而非由樹的當前狀態決定。具體而言：
- 對一個葉節點中的鍵值序列計算滾動哈希
- 當哈希值滿足特定條件（如低 N 位為零）時，在該點分裂節點
- 由於分裂條件只取決於鍵值本身，兩個只差一個插入的資料集，其分裂點幾乎完全相同——只有插入點附近的少量節點受到影響
這使得 diff 操作只需比較哈希值有差異的節點路徑，不需掃描整顆樹，時間複雜度接近 O(差異量) 而非 O(資料量)。
結構性質
Prolly Tree 維持 B-tree 的有序性（O(log n) 的點查詢與範圍掃描）與均衡性，但節點大小不再固定，而是在期望大小附近的隨機分佈。merge 操作可以類比 Git 的三方合併：給定共同祖先（common ancestor）、分支 A、分支 B 的樹，找出各分支相對於祖先的差異集合，並在不衝突的情況下自動合併。
超越 Dolt 的潛力
LWN 的分析指出，Prolly Tree 的內容定址特性不僅適用於資料庫。任何需要「可差分、可合併、可高效共享」的大型有序資料集都是潛在應用場景，包括版本化的設定管理、可審計的稽核記錄，以及分散式系統的狀態同步。
原始來源：LWN: Version-controlled databases using Prolly trees、DoltHub: Prolly Trees
pgBackRest 終止維護：PostgreSQL 備份工具的後繼選擇
mydbanotebook.org · 2026-04-27
pgBackRest 的唯一維護者 David Steele 宣布停止一切開發工作。Crunchy Data（pgBackRest 的主要資助方）在被收購後停止了對此專案的資助，Steele 未能找到替代的雇用或獨立贊助來源。對於依賴 pgBackRest 的 PostgreSQL 生產環境，這是一個需要立即評估的轉型決策。
pgBackRest 的設計特點
pgBackRest 的核心差異在於它以還原（recovery）為設計中心，而非僅以備份為目標。它提供：備份目錄（backup catalog）管理、WAL 保留策略自動化、restore 指令（含 point-in-time recovery 參數）、備份完整性驗證（校驗和比對）。這些功能在直接替代方案中並不完整。
替代工具評估
Barman（PostgreSQL 2ndQuadrant / EnterpriseDB 維護）是目前最接近的替代方案。它提供 WAL 歸檔、備份目錄、保留管理與還原指令，功能集與 pgBackRest 高度重疊。主要限制：Barman 底層呼叫 pg_basebackup，而 pg_basebackup 的設計目標是複製執行中的叢集目錄，而非作為以還原為中心的備份工具，這帶來部分架構上的限制（如平行備份的效率）。
pg_basebackup 直接使用：缺乏 pgBackRest 的目錄管理、保留策略與驗證機制，需要手動處理這些操作層面，不適合作為獨立備份解決方案。
pg_dump：邏輯匯出工具，不支援 point-in-time recovery，不適合作為主要備份機制。
社群動向
codebase 品質良好，社群有人預期將出現 fork。在 fork 成熟前，以 Barman 為主的遷移是維運上最穩妥的路徑。對於需要 S3 相容物件儲存整合、平行備份或細粒度保留策略的場景，應在遷移前仔細評估 Barman 是否能完整覆蓋現有的 pgBackRest 配置。
PgQue v0.1：純 SQL 實現的零膨脹 PostgreSQL 訊息佇列
PostgreSQL News · 2026-05-02
PgQue v0.1 是一個完全以 SQL 與 PL/pgSQL 實作的 PostgreSQL 事件與訊息佇列，不依賴任何背景 worker 程序或外部元件。其核心設計目標是零資料表膨脹（zero bloat）——一個在基於 PostgreSQL 的佇列系統中長期存在的運維痛點。
PostgreSQL 佇列的膨脹問題
傳統的 PostgreSQL 佇列實作（如 pgmq、Oban 等）以資料表儲存訊息，透過 UPDATE 標記訊息為「處理中」、再以 DELETE 移除已完成訊息。PostgreSQL 的 MVCC 機制不會立即刪除 UPDATE 或 DELETE 的舊版本（dead tuples），需要 VACUUM 定期清理。在高吞吐量的佇列場景下，VACUUM 的執行頻率可能跟不上訊息的消費速度，導致資料表持續膨脹，進而影響查詢效能並增加磁碟使用量。
PgQue 的解法
PgQue 採用延遲刪除（deferred delete）策略：訊息確認（acknowledge）後不立即刪除，而是打上時間戳並在定期清理批次中統一刪除，搭配部分索引（partial index）確保活躍訊息的查詢仍高效。透過合理控制清理批次的執行時機與大小，dead tuple 的累積量維持在可預測的範圍內，避免 VACUUM 追趕不及的情況。
整個實作不需要 PostgreSQL extension 或 background worker，可在標準 PostgreSQL 安裝上直接部署，適合有嚴格環境控制需求的場景（如受管理的雲端 PostgreSQL 服務，不允許安裝 extension）。
v0.1 屬於早期發布，目前的功能集覆蓋基本的訊息入隊、出隊、確認與可見性逾時（visibility timeout），尚未包含優先級佇列或跨 schema 路由等進階功能。