翻譯：王學姣
審校：李浩、宇亭
責編：宇亭
設計：Yeekin
導語
本篇是StoneDB學術分享會專欄的第七篇，在上一期裡，我們分享了 SAP 在 2012 年發表的《The SAP HANA Database – An Architecture Overview》論文，主要是介紹了 SAP HANA 列式存儲引擎的架構設計，該列存引擎利用現代硬體（多 CPU 核心、大容量主記憶體和緩存），支援資料壓縮、資料庫核心并行最大化，提供層次結構（hierarchy）專用的資料結構、用于特定領域的語言支援等企業應用所需的資料庫擴充。
本期，我們将帶大家讀一讀這篇《Efficient Transaction Processing in SAP HANA Database – The End of a Column Store Myth》，瞧瞧，這個标題就起得很有火藥味，SAP 提出列式存儲引擎的時候，市面上敢用行列混存做 HTAP 資料庫的基本沒幾個，但是人家竟然敢直接跟你說，SAP HANA 資料庫，就是為了結束人們對列式存儲的偏見而生的，誰說列式存儲不能做事務型工作（OLTP）的？我們 SAP HANA 證明給你看~（當然了，現在列式存儲的資料庫其實已經很多了，我們的 StoneDB 團隊自研的 Tianmu 引擎就是列式存儲引擎）
是不是還挺橫的？一衆資料庫界的大佬也坐不住了：你們 SAP 到底哪來的底氣？别急，今天就帶大家看看這篇經典論文，揭開 SAP HANA 資料庫的神秘面紗。
摘要
SAP HANA 資料庫是 SAP 新推出的資料管理平台的核心。SAP HANA 資料庫的總體目标是為事務型查詢和分析型查詢場景提供一個通用的、強大的系統，且在高度可擴充的執行環境中為不同的查詢場景提供相同的資料表示。本文重點介紹了 SAP HANA 資料庫差別于傳統關系型資料庫引擎的主要特性。是以，在本文中，我們首先概述了 SAP HANA 的總體架構和設計标準。其次，SAP HANA 挑戰了人們關于列存資料結構的偏見，即列存儲資料結構隻在分析型工作負載中表現優異，并不适合事務型工作負載。我們概述了如何通過管理記錄（record）生命周期來使用不同的格式存儲不同階段的同一記錄。除了提供概念的解讀外，我們還深入探讨了如何在記錄的生命周期中對其進行高效同步，以及如何将資料庫條目從寫優化的存儲格式轉移到讀優化的存儲格式的一些細節。總之，本文旨在說明 SAP HANA 資料庫如何實作同時在分析型和事務型工作負載環境中進行高效工作。
簡介
現代商業應用中的資料管理是當今軟體行業面臨的最具挑戰性的課題之一。現如今，資料不僅推動着業務發展，還為新業務理念或業務案例的發展提供了基礎。各種各樣的資料管理已經成為企業的核心資産。此外，資料管理作為推動和發展目前業務的主要工具，已經引起了高層管理者的極大關注。在系統方面，資料管理場景變得極其複雜，難以管理。一個高效、靈活、穩健、低成本的資料管理層成為了大量應用場景的核心，而這些應用場景則是當今商業環境中不可或缺的部分。
起初，傳統 ERP 系統被用為處理這些應用場景的資訊進行中樞。從資料庫系統的角度來看，ERP 系統的 OLTP 工作負載通常需要處理成千上萬的并發使用者和事務，而這些事務常常伴随着高更新負載和選擇性極強的點查詢（point query）。另一方面，資料倉庫系統（對應于 OLTP 系統）要麼對基于大量資料進行聚合查詢，要麼通過計算統計模型來分析存儲在資料庫中的内容。然而，新應用的出現，例如用于識别資料流或ETL/資訊內建任務中的異常的實時分析，對資料管理層提出了新的需求和挑戰。這些需求和挑戰要求一個能夠處理現代業務應用的資料管理層。
Stonebraker 等人為上述問題提供了一個答案。他們在 2007 年【13】提出了“The End of an Architectural Era (It's Time for a Complete Rewrite)”的觀點，表明傳統的資料庫管理系統不再能夠滿足變化多樣的市場需求。市場需要不同的資料庫管理系統用于解決不同的問題。從本質上來說，此觀點證明了如下現狀：大型資料管了解決方案是一個包含各種系統的集合。這些系統适用于不同的應用場景。例如，行存儲仍然主要應用于 OLTP 領域。使用基于實體（entity-based）的互動模型能夠在記錄中維護邏輯實體和實體表示之間的 1:1 關系。按列組織的資料結構在分析領域獲得了越來越多的關注。這種資料結構可以避免查詢列的投影（projection），并可以提供更好的壓縮效率。鍵值存儲（key-value store）正在逐漸成為商業資料管了解決方案的一部分，用于處理海量資料以及為程式性的代碼提供并行執行的平台。此外，分布式檔案系統提供了一種經濟的存儲機制以及雲彈性般靈活的并行度，使鍵值存儲成為了資料管理領域的“頭等公民”。行存儲、列存儲以及鍵值存儲完善了大型資料庫管理方案，使之能夠處理各種模式（schema）的資料和支援基于圖形的資料組織形式。由于模式是伴随資料而出現的，系統通常會提供高效的方法來顯式地利用實體之間的模型化關系（modeled relationship），運作分析型圖算法（analytical graph algorithm），并展示弱實體的倉庫（repository）。在市場進行性能嘗試初期，專用系統（specialized system）可能被認為是明智之舉，但包含各種專用系統的大型資料庫解決方案需要解決各個系統之間的連接配接、資料複制和同步任務問題，以及在多個系統間編排查詢場景，使得此類解決方案變得及其複雜。此外，為這類解決方案進行環境配置和維護不僅操作複雜且極易出錯，而且總擁有成本（TCO）也十分高昂。
概括來講，我們對目前形勢進行了如下幾方面的觀察：
使用角度：我們認為 SQL 不再是現代業務應用唯一适用的互動模型。使用者要麼被應用層這個屏障完全隔開，要麼希望直接與其資料庫進行互動。在第一種情況下，我們發現需要用緊耦合機制來實作對應用層的最佳支援。在第二種情況下，我們發現需要針對特定領域使用具有内置資料庫特性的腳本語言，如用于統計處理的 R（【4】）或用于 Hadoop 安裝的 Pig。我們還觀察到對特定領域和專有查詢語言的全面支援的需求，例如 SAP 提供的用于金融規劃場景的 FOX （【7】）。最後，我們還發現了一個巨大的市場需求：從程式設計的角度考慮并行性，市場需要直接使能使用者的機制。
成本意識：我們觀察到一個很明确的需求，市場需要一個從硬體到安裝成本，再到營運和維護成本，為整個資料管理體系提供更低TCO 的解決方案，一個針對不同工作負載類型和使用模式（usage pattern）的融合解決方案。
性能、性能、還是性能（【16】）：我們認為性能仍然是使用專用系統的主要原因。目前所面臨的挑戰是提供一個在任何時候都能夠根據需求靈活地應用專門的運算符或資料結構的解決方案。
需要指出的是，不同的工作負載特征并不能完全證明包含各類專用系統的大型資料管了解決方案的合理性。我們過去處理業務應用的經驗讓我們成為了特定算子集合需求假設的支援者。我們對具有獨立生命周期和管理設定的單獨系統（individual system）存在偏見。我們的目标并不是提供一個單一的封閉系統，而是提供一個使用通用服務原語的、靈活的資料管理平台。目前SAP HANA 資料庫的可用功能是 SAP HANA 裝置的核心部分（【2】），可被視為這種工具包的一個具體展現。
貢獻和概述
本文旨在描述 SAP HANA 資料庫平台的全貌，并深入解釋一些為處理事務型工作負載而做的工作細節。我們首先概述了 SAP HANA 的整體架構和設計準則，強調了其與傳統關系資料庫管理系統的不同之處，尤其是SAP HANA 資料庫在典型業務應用範圍内的以下顯著特征：
SAP HANA 資料庫包含一個多引擎查詢處理環境。該環境提供支援不同結構化程度的資料的資料抽象，包括高度結構化的關系型資料、到不規則的結構化資料圖（irregularly structured data graphs）、再到非結構化的文本資料。處理引擎的整個使用範圍基于一個公共表抽象，作為底層實體資料表示，進而保證互操作性以及允許不同類型之間的資料組合。
SAP HANA 資料庫支援在資料庫引擎中直接表示特定于應用的業務對象（如 OLAP cube）和邏輯（特定領域的函數庫）。這允許通過底層資料管理平台實作應用語義（application semantics）交換，進而提高查詢效率，減少單個應用到資料庫的往返次數以及資料庫和應用之間傳輸的資料量。
SAP HANA 資料庫針對資料管理層和應用層之間的通信進行了性能優化。例如，SAP HANA 資料庫原生支援 SAP 應用伺服器的資料類型。此外，還計劃将新的應用伺服器技術直接內建到 SAP HANA 資料庫叢集的基礎架構中，以支援應用邏輯和資料庫管理功能的交叉執行。
SAP HANA 資料庫通過利用實作高度優化的面向列的資料表示，支援在同一實體資料庫上對事務性和分析性工作負載進行高效處理。該功能的實作依賴于複雜的多步驟記錄生命周期管理（multi-step record lifecycle management）。
前三個特征我們已經在【2】中進行了探讨，最後一個特征将在本文的第二部分進行讨論。此處我們概述了與統一表結構（unified table structure）和傳播機制相關的一些細節，以便通過可控的生命周期管理流程在系統内移動記錄（record）。具體來講，我們首先使用不同資料結構來儲存處于生命周期中不同階段的資料。然後我們重點關注如何高效地實作不同資料結構之間的傳播步驟，進而能夠将資料從寫優化存儲中移動到主記憶體結構（main memory structure）中。寫優化存儲非常适合處理插入、更新和删除操作，而主記憶體結構中的資料是高度壓縮的資料，适合處理 OLAP 查詢。順便一提，SAP HANA 資料庫還提供了運作 SAP ERP 系統等企業關鍵型應用所需的技術。例如，SAP HANA 資料庫展示了 SAP HANA 叢集中各個節點的容錯能力，即如果一個節點出現故障，其他節點會自動接管負載。在這種情況下，查詢處理既不會被阻塞也不會停止，而是由分布式查詢執行架構以一種對使用者透明的方式重新進行路由。SAP HANA 資料庫也支援備份和恢複等功能。從事務行為來看，SAP HANA 資料庫使用多版本并發控制（multi-version concurrency control, MVCC）來實作不同級别的事務隔離。SAP HANA 資料庫支援事務級和語句級快照隔離。不夠由于篇幅限制，我們不會就該點進行展開說明。
SAP HANA 資料庫的分層架構
如【2】中所述，SAP HANA 産品已經上市，由一個帶有不同元件的裝置模型組成，可為資料分析場景提供現成的解決方案。這是SAP HANA 邁出的第一步，旨在在資料集市場景中讓客戶接受并習慣以列為導向、以主記憶體為中心的 SAP HANA 資料庫的全新理念。截至目前，SAP 正在為 SAP Business Warehouse 産品提供原生支援，以顯著加快查詢和轉換場景，同時允許完全跳過單個物料化步驟。為了提供這種能力，SAP HANA 擁有資料加載和轉換工具以及模組化工作室，以建立和維護進出 SAP HANA 的複雜資料流。SAP HANA 資料庫是SAP HANA 産品的核心元件，負責高效和靈活的資料存儲和資料查詢場景（【11，12】）。
圖1：SAP HANA 裝置概述
SAP HANA 資料庫本身遵循嚴格的分層架構，如圖 2 所示。與傳統系統類似，SAP HANA 資料庫區分資料庫請求的編譯時（compile time）和運作時（runtime）。此圖并未包含 SAP HANA 資料庫的所有元件，例如交易管理器（transaction manager）、授權管理器（authorization manager）、中繼資料管理器（metadata manager）等均未展現。
圖2： HANA 資料庫分層架構概述
除了純粹的資料處理性能之外，我們還發現應用層和資料管理層之間缺乏恰當的耦合機制。這是目前最先進系統的主要缺陷之一。這成為了驅動我們将 SAP HANA 資料庫設計為可針對不同查詢語言進行擴充的平台的一個主要因素。如圖 2 所示，不同查詢語言可以通過普通連接配接和會話管理層進入系統，實作同外部的交流。在第一步中，查詢字元串被翻譯成優化之後的内部表示（類似于抽象文法樹），這對于每一種領域特定（domain-specific）的語言而言都是本地實作的。第二步，查詢表達式被映射到一個“計算圖（calculation graph）”，進而構成了邏輯查詢處理架構（logical query processing framework）的核心。
2.1 計算圖模型
“計算圖模型”遵循經典資料流圖（data flow graph）的原則。源節點（source node）是持久表結構或其他計算圖的結果表示。内部節點（inner node）表示消耗一個或多個傳入資料流并産生任意數量的傳出資料流的邏輯運算符。此外，計算圖操作符集可以分成兩組操作符類型。一方面，計算圖模型定義了一組内置運算符（intrinsic operator），包括聚合（aggregation）、投影（projection）、連接配接（join）、聯合（union）等。SQL 可以完全映射到這類操作符。另一方面，計算圖模型提供了實作核心業務算法（例如貨币轉換和月曆功能）的操作符。此外，計算圖模型支援以下類型的運算符：
動态 SQL 節點（dynamic SQL node）：計算圖模型運算符可以對傳入的資料流執行完整的 SQL 語句。該語句可以是參數，并且在計算圖運作時被編譯和執行，進而産生了一種“嵌套計算”模型的形式。
自定義節點（custom node）：出于性能原因，可以使用自定義節點在 C++ 中實作特定領域的運算符。例如，使用 SAP 專有語言 Fox【6】的規劃場景可以利用特殊的“分解（disaggregate）”運算符來原生支援财務規劃情況【7】。另一個例子是通過專有的 WIPE graph 語言在資料圖中進行圖周遊和分析優化。
R 節點（R node）：R 節點（【4】）可用于将傳入的資料集轉發到 R 執行環境。作為參數給出的 R 腳本将在 SAP HANA 資料庫之外執行，并将結果移回到計算圖中進行進一步處理。
L 節點（L node）：語言 L 代表 SAP HANA 資料庫的内部運作時語言。語言 L 被設計成 C 語言的安全子集。通常情況下，終端使用者或應用設計者不能直接通路。語言 L 是所有的不能直接映射到資料流圖的領域專用語言的結構（constructs）的合集。換言之，語言L 即各種指令式控制邏輯。
除了一組功能操作符之外，計算圖模型還提供了“拆分（split）”和“組合（combine）”的運算符，以動态定義和重新配置設定資料流分區，作為支援應用定義（application-defined）的資料并行化的基礎構造。
各領域專用語言的編譯器都試圖優化從查詢腳本到計算圖的映射。對于 SQL，映射的基礎是有明确定義的、查詢表達式的邏輯表示。在一般情況下，映射可以使用啟發式或者基于代價的政策，這取決于輸入資料的預估大小等因素。例如，編譯器可能會決定将循環展開成正常資料流圖，或者為特定表達式生成 L 代碼【6】。在正常 SQL 的情況下，這是迄今為止最大和最複雜的部分，取自 SAP P*Time1 系統（【1】），内部表示直接映射到關系運算符以捕獲SQL 語句的意圖。
圖 3 描繪了一個計算圖模型示例。計算圖模型可以通過特定領域語言的編譯器間接建立，也可以使用 SAP HANA Studio進行可視化模組化，并在 SAP HANA 資料庫的應用級内容倉庫中注冊為計算視圖（calculation view）。這一過程背後的總體思想是定制複雜業務邏輯場景的特定段（segment），這些段可以在多個資料庫場景中進行微調和重用，與實際的查詢語言無關。換言之，計算圖模型可以以虛拟表的形式在任何領域特定語言堆棧中被消費。計算圖模型的集合也稱為 SAP HANA content，并擁有獨立的産品生命周期流程。圖3 所示的計算模型概述了 SAP HANA 資料庫與标準關系型資料庫系統在正常查詢計劃方面的差異。例如，從應用的角度來看，一個操作符的結果可能會有多個消費者（consumer）需要優化共享的公共子表達式。其次，标記為“script”的節點包含了來自計算模型設計器或由特定領域查詢編譯器生成的指令性語言片段。最後，節點“conv”顯示了使用内置業務函數來執行特定應用的轉換例程，例如貨币轉換或機關轉換。
圖3：SAP HANA 計算模型圖示例
2.2 計算圖的編譯和執行
一旦使用者定義的查詢表達式或查詢腳本被映射到計算圖模型中的資料流圖，優化器就會運作經典的基于規則或代價的優化步驟，将邏輯計劃重構并轉換為實體計劃，然後由分布式執行架構執行。執行架構繼承自之前的 SAP 産品 SAP BWA（業務倉庫加速器）和SAP Enterprise Search，用于處理實際資料流和實體操作符的分布式執行。在優化過程中，邏輯資料流圖的片段被映射到“引擎層”提供的實體運算符。引擎層本身由一組不同的實體操作符組成。這些實體操作符有着一些局部優化邏輯，進而使全局計劃的片段能夠适應實際實體操作符的特性。值得說道的是，SAP HANA 資料庫提供了以下一套運算符：
關系運算符：關系運算符用于典型的關系查詢圖處理。如第3.1小節所述，關系運算符擁有不同的特征，例如，equi-join（【5】）等運算符直接利用統一表（unified table）的現有字典。
OLAP 運算符：OLAP 運算符針對具有事實表和次元表的星形連接配接（star-join）方案進行了優化。一旦優化器識别出這種類型的場景，與之對應的查詢計劃片段到 OLAP 運算符的映射就會被枚舉為具有相應代價估計的可行實體計劃（【8】）。
L 運作時間：内部語言的運作時反映了用于執行在指定計算圖的L節點中的表示L代碼的構造塊（building code）。使用“拆分（split）群組合（combine）”運算符對時，可以在預定義的分區上并行調用L運作時。
文本運算符：文本搜尋分析操作符集包括 SAP Enterprise Search 産品中可用的功能集，以提供從相似性度量到實體解析能力的綜合文本分析特性（【14】）。
圖形運算符：圖形運算符最終為基于圖形的算法提供支援，以實作複雜的資源規劃場景或社會網絡分析任務。
由于資料流圖不僅分布在多個伺服器執行個體（通常運作在不同實體節點上）之間，還分布在不同類型的運算符上，是以 SAP HANA 提供了一個工具箱，用于保證最佳的資料傳輸和交換格式。盡管所有計算符都需要實施标準的資料傳輸協定，但不同“集合”内外的個别運算符可能擁有高度專業化的通信協定。例如，關系運算符和 OLAP 運算符以高度壓縮的專有格式進行資料交換。此外，R 節點提供了一個到 R内部資料幀格式的映射。
除了“橫向”交流之外，不同實體運算符直接可以通過一個通用接口接入到統一表層（unified table layer）。SAP HANA 資料庫提供了一個抽象的表格視圖，允許不同的計算符通過多種方法進行通路。這一點我們将在下一部分進行詳細介紹。該通用表格結構實作了資料實體的完整生命周期，其主要構成部分為行存儲和列存儲的組合，用于捕獲最近的資料修改效果。由于 SAP HANA 資料庫中的表可以标記為“曆史（historic）”，是以表層（table layer）實作了用于捕獲活躍實體（active entity）的過去值的曆史表（history table），并提供了通路時間旅行查詢（time travel query）的方式。
最後，SAP HANA 的持久層（persistence layer）保證了系統的可恢複性。即使在主記憶體中的資料庫狀态丢失的情況下，系統也依然能夠實作快速恢複。虛拟檔案（virtual file）是持久層的基礎。虛拟檔案對可視化頁面的可配置大小進行了限制。采用 SAP MaxDB 系統的概念，持久層依靠頻繁産生的儲存點（savepoint）以非常低的資源開銷提供一緻快照。更多相關細節，将在下一部分介紹。
2.3 總結
與傳統資料庫系統相比，SAP HANA 資料庫旨在利用平台的靈活性來支援多種（專有）領域特定的語言。靈活的資料流模型（計算圖模型）提供了概念上的系統核心：一方面，查詢表達式或查詢腳本被映射到模型執行個體。另一方面，所有不同實體運算符都使用相同的表層接口（table layer interface），對單個記錄實施完整的生命周期管理。日志和資料區被用于在持久存儲中維護主記憶體資料庫的事務一緻性副本。
資料庫記錄的生命周期管理
如圖 4 所示，統一表結構（unified table structure）允許所有适用的實體運算符進行資料通路。統一表結構的内在實質是系統為資料庫記錄提供了生命周期管理。在我們看來，統一表技術是系統能夠高性能地同時處理基于掃描的聚合查詢和極具選擇性的點查詢的關鍵。這成為 SAP HANA 差別于傳統（行存）資料庫的一個關鍵差異點。在就地更新（update-in-place）風格的資料庫系統中，記錄從概念層面來看，在其整個生命周期中保持在同一位置，而 SAP HANA 通過實體表示的不同階段對記錄實作了概念上的傳播。雖然是作為一個一般概念設計的，如圖 4 所示，在一個正常表中，記錄根據生命周期被劃分為以下三個階段：
圖4：統一表概念概述
L1-delta：L1-delta（L1-增量）結構接受所有資料傳入請求，并以寫優化的方式存儲這些請求，即 L1-delta 保留記錄的邏輯行格式。該資料結構針對快速插入和删除、字段更新和記錄投影進行了優化。此外，L1-delta 結構不會對資料進行壓縮。根據經驗，單個節點資料庫執行個體中，L1-delta 結構可以存儲10,000到100,000行資料。這一容量因資料庫執行個體的工作負載特征和可用記憶體大小而異。
L2-delta：L2-delta（L2-增量）結構代表了記錄在生命周期中的第二個階段，以列存格式組織資料。與L1-delta 相比，L2-delta 采用字典編碼來優化記憶體利用。然而，出于性能考慮，字典是未排序的，需要使用二級索引結構來實作對點查詢通路模式（access pattern）的最佳支援，例如快速執行唯一限制檢查。L2-delta 非常适合存儲量超過1000萬行的場景。
Main store：最後，main store（主存儲）表示采用各種不同壓縮方案的最高壓縮率的核心資料格式。預設情況下，一列中的所有值都通過排序字典中的位置來表示，并以位打包（bit-packing）的方式存儲，以便實作各個值的密集打包（【15】）。雖然字典總是使用各種字首編碼方案進行壓縮，不同壓縮技術的組合——從簡單的遊程編碼方案到更複雜的壓縮技術——也被應用于進一步減少占用的主記憶體（【9，10】）。
由于 SAP HANA 資料庫最初是為複雜且高容量加載場景的 OLAP 密集型用例而設計的，是以該系統針對高效批量插入提供了特殊處理，這使得此類操作會繞過 L1-delta 直接進入 L2-delta。與輸入位置無關，任何輸入記錄的行 ID（RowId）都在行（row）輸入系統時生成。并且，該行的日志在該行第一次出現時生成，無論是在适合正常更新/插入/删除操作的 L1-delta 中，還是在适合大容量裝載操作的 L2-delta 中。
3.1 統一表通路
不同資料結構共享一組通用資料類型。統一表通路通過一個帶有行疊代器和列疊代器的公共抽象接口實作。兩個疊代器都可以是基于字典（dictionary-based）的疊代器。此外，在遵循經典的 ONC 協定【3】,支援流水線操作，并盡可能減少中間結果的記憶體需求的基礎上，一些實體計算符可以逐記錄或者以矢量化的方式（即逐塊）拉取記錄。其他實體計算符采用“materialize all”政策，以避免查詢執行期間的計算符切換所産生的成本。優化器根據邏輯計算圖模型來決定如何對不同種類的計算符進行混合使用，即被采用的不同類型的實體運算符将會被無縫內建到最終的查詢執行計劃中。
對于使用排序字典的操作符，統一表通路接口還通過全局排序字典公開表内容。在 L1-delta 結構的字典完成計算和 L2-delta 結構的字典完成排序後，兩種 delta 結構的字典會被立刻合并至 main store 的字典中。為了實作唯一性限制的有效性驗證，統一表為兩種 delta 和 main store 提供了反向索引（inverted index）。
記錄的生命周期采用的組織方式将單個記錄在系統中進行異步傳播，而不幹擾目前正在事務控制範圍内（transactional sphere of control）運作的資料庫操作的組織方式。目前的 SAP HANA 資料庫系統提供兩次轉換，我們稱之為“合并步驟（merge step）”：
L1-to-L2-delta Merge：從 L1-delta 到 L2-delta 的轉換意味着資料從按行組織變成了按列組織。L1-delta 中的行被拆分成它們對應的列值，然後被逐列插入到 L2-delta 中。在接收端，系統會執行一次 lookup 來識别出字典結構中可能丢失的值，并且可以選擇在字典的末尾插入新條目以避免在字典中進行任何重大的重構操作。在第二步中，使用字典編碼（append-only 結構）将相應的列值添加到值向量中。這兩個步驟可以并行執行，因為要移動的元組的數量是已知的，使得能夠在實際插入它們之前在新字典中保留編碼。在第三步中，從 L1-delta 中移除已經傳播的條目（propagated entry）。所有運作中的操作要麼看到的是完整的 L1-delta 和舊的 end-of-delta 邊界，要麼看到具有 L2-delta 擴充版本的 L1-delta 結構的截斷版本（truncated version）。從設計角度來看，從 L1-delta 到 L2-delta 的轉換本質上是增量式的，即記錄的轉換對目标結構的資料重組沒有任何影響。
L2-delta-to-main Merge：一個新的 main store 是基于 L2-delta 和現有的 main store 産生的。雖然 L1-to-L2-delta Merge 對運作事務的影響很小，但 L2-delta-to-main Merge 是資源密集型任務，必須在實體級别上仔細安排并進行高度優化。一旦L2-delta-to-main Merge 開始，目前的L2-delta 就會被關閉用于執行更新操作。與此同時，系統會建立一個新的、空的 L2-delta 結構用來作為 L1-to-L2-delta Merge 的目的端。如果 L2-delta-to-main Merge 失敗，系統仍然使用新的 L2-delta 用于L1-to-L2-delta Merge，并繼續嘗試使用舊版本的 L2-delta 和現有的main 進行合并。第 4 章将詳述核心算法以及不同的優化技術，例如 4.2 小節會介紹按列合并（column-wise merge），4.3 小節會介紹部分合并（partial merge）。
上述兩個合并步驟都不會對持久存儲産生直接影響，并且獨立于重新開機或備份日志重放。
3.2 持續性映射
雖然 SAP HANA 資料庫是一個以記憶體為中心的資料庫系統，但其全面的 ACID 支援保證了持久性、原子性，以及系統在定期關閉或系統故障後能夠重新開機恢複。SAP HANA 資料庫考慮了多種持久化觀點來構架其持久性。一般來說，持久存儲無需細粒度的 UNDO 機制，因為隻有像新版本的 main 結構這種量級的批量更改（bulk change）才會傳播到持久存儲，并且在系統故障後必須復原。如圖 5 所示，SAP HANA 的持久性是基于臨時 REDO 日志和短期恢複或長期備份的 save pointing 的組合實作的。
圖5：統一表的持久性機制概述
當一條新資料進入系統時，無論是在 L1-delta 還是在 L2-delta （批量插入）進行，都隻會為其建立一次 REDO 日志。當一條記錄的新版本進入 L1-delta 時，系統會為該新版本建立日志。從 L1-delta 到 L2-delta 的增量傳播過程中所發生的資料變化不會被寫入至REDO 日志中。反而是字典和 value index（值索引）中的變化會被添加到各個資料頁中的資料結構中，這些資料結構最終被移入至下一個儲存點的持久存儲中。顯然，合并事件被寫入日志，以確定重新開機後資料庫狀态的一緻性。
圖 6 描繪了合并的細節。字典和值索引這兩種結構都是基于分頁存儲布局（paged storage layout）。該布局由底層存儲子系統進行管理。無論是具有附加條目的現有頁或新頁，但凡是髒頁都會被存儲子系統清理掉。該功能由儲存點基礎架構（save pointing infrastructure）來控制。盡管 L2-delta 中的資料是按列組織的，但是系統可以在單個頁面記憶體儲多個 L2-delta 的片段，以便優化存儲器消耗。特别是對于小而寬的表，這一設計尤為合理。
圖6： L1-to-L2-delta Merge 的細節圖
在儲存點之後，REDO 日志可以被截斷。在恢複過程中，系統重新加載 L2-delta 的最後一個快照。與之類似，main store 的一個新版本會被持久化至穩定存儲中，并可用于重新加載統一表的 main store。總之，因為先前版本的映像仍然存在，無論是 L2-delta 還是main store 的變化都不會寫入日志。傳統的日志方案僅适用于 L1-delta。
3.3 總結
SAP HANA 資料庫中的表的實體表示分為三個層級：
L1-delta：用于高效捕獲插入、更新和删除請求的行式存儲；
L2-delta：用于将寫優化存儲和讀優化存儲進行解耦的中間結構，是一個列式存儲；
Main store：該結構不僅非常适合類似于 OLAP 的查詢，并且還使用反向索引對點查詢性能進行了針對性調優。
一條記錄在其“一生”之中，最開始通過異步複制儲存至更新效率最高的存儲中，然後被複制到讀取效率最高的存儲中度過“餘生”。
合并優化
統一表方法的基本思想是通過将記錄從寫優化的存儲結構以透明的方式傳播至使用 L2-delta 索引的讀優化的存儲結構中，進而實作讀寫存儲之間的解耦。雖然從 L1-delta 到 L2-delta 的轉換不會對現有的資料結構産生太大破壞，但 L2-delta 合并至 main store 的操作需要對表格内容進行重大重組。
4.1 經典合并
在經典合并（classic merge）操作的第一步中，L2-delta 的字典條目會被編譯到 main 的字典中，進而實作為特定列生成一個排序後的新的 main 字典。新字典僅包含新的 main 的有效條目，丢棄所有被删除和修改過的記錄的條目。按字典順序排序不僅為最佳壓縮提供了先決條件，也為特殊計算符能夠直接處理字典編碼列打下了基礎。
圖7顯示了一次合并步驟涉及到的主要階段。在第一階段，系統基于使用未排序字典的 L2-delta 和使用排序字典的舊 main，生成一個新的排序字典，并儲存條目新舊位置的映射。新位置為條目在新字典中的位置；舊位置則為條目在 main 和 L2-delta 内的位置（非顯式存儲）。如圖所示，一些條目同時存在于 L2-delta 和 main 的字典中，例如“Los Gatos”；還有一些條目僅出現在一個詞典中，例如“Campbell”在 L2-delta 中的位置為 4，在 main 的字典映射表中的值為 -1。在第二階段，系統會參考現有條目和新增條目在新字典中的位置建構新的 main index（主索引）。如圖7 中的示例所示，“Daily City”的條目被轉移到新 main 中，位置為 4。“Los Gatos”也從 L2-delta 中的位置 1 和舊 main 中的位置 5 映射到了新位置 6。新 main（字典和值索引）寫入磁盤，同時舊的資料結構被釋放。在任何情況下，系統都必須在主記憶體中儲存列（字典和main index）的新舊兩個版本，直到所有引用該列的舊版本的開放事務的資料庫操作都已執行完畢。
圖7：L2-delta-to-main Merge 的細節圖
由于合并操作的初始版（naive version）非常耗費資源，SAP HANA 資料庫對其進行了許多優化。例如，如果 L2-delta 的字典是 main 的字典的子集，那麼會直接跳過用于生成字典的第一階段，進而形成了 main 條目的穩定位置。另一種特殊情況是 L2-delta 字典的值大于 main 字典中的值，例如存在增加的時間戳。在這種情況下，如果對字典值進行編碼的位數（number of bits）足以應對擴充基數（extended cardinality），則 L2-delta 字典可以直接添加到 main 字典中。
SAP HANA 資料庫還使用了正交技術（orthogonal technique）來實作更為複雜的優化，例如下面即将介紹到的重排序合并（re-sorting merge）和部分合并（partial merge）政策。
4.2 重排序合并
L2-delta 和 main 之間的經典合并（詳情請參考 4.1）需要條目的新舊位置之間的映射關系。這些位置用于對位打包值索引（bit-packed value index）内的實值（real value）進行編碼，即，用 C 來表示一個列中的值去重後的數量，系統需要使用 ⌈ld(C)⌉ 數量的位（bit）來對該位置進行編碼。合并操作會将舊的 main 值映射到新字典中的位置上（具有相同或增加的位數），并在新的 value index 的末尾添加 L2-delta 的條目。
合并操作的擴充版本（extended version）旨在重新組織整個表的内容，将所有列進行重新布局，以提供更高的壓縮潛能。由于 SAP HANA 資料庫列存儲使用了位置尋址方案，是以第 k 條記錄中的值必須位于每一列的第 k 個位置。對表中某列進行重新排序會直接影響表中其他列的壓縮潛能。根據【9】中讨論的概念，系統在建立新的 main 之前，會根據 main 和 L2-delta 結構的統計資訊計算列的“最佳”排序順序。
圖8：Delta-to-main 重排序合并
圖 8 展示了必要的資料結構（data structure）。除了用于字典的映射表（mapping table）将舊字典位置翻譯成新字典中的位置之外，重排序合并（re-sorting merge）的版本還建立了行位置的映射表，進而能夠在合并和重新排序某行的各個列之後重構該行。圖8 顯示了合并過程之前和過程中的同一張表中的列，其中列“City”和“Prod”已經合并，其餘列（如“Time”）仍然反映合并前的狀态。是以，main 的舊版條目對應于舊字典中的位置，例如“City”列的條目“Los Gatos”在舊字典中用值5 編碼，而在合并後的版本中用值6 編碼。一般來說，在對“City”列進行合并後，新的 main index 顯示新詞典的位置以及對行進行重新排序。如圖 8 中突出顯示的那樣，現在可以在第二個位置找到第7 行。“Prod”列也被合并，但沒有建立字典，保留了字典位置值。然而“Time”欄還沒有合并，仍然是指舊字典和舊的排序順序。如果需要具有已經合并的列的行構造，則對尚未合并的列的任何通路都需要通過行位置映射表采取額外步驟。在所有列的合并完成之後，可以消除行位置映射表。雖然系統可以通過“堆疊（stacking）”行位置映射表在概念上延遲不經常通路的列的合并，但是系統總是在開始新的合并生成之前完成整個表的合并操作。
是以，是否使用重新排序還需要基于成本考慮，用于平衡在所有列的合并期間用于列通路的額外位置映射的開銷，以及由此産生的更高壓縮率的可能性。将合并應用于各個列的排序标準還取決于多個因素，例如點對範圍通路的比率、壓縮潛力的提高等。
4.3 部分合并
經典合并或重排合并的主要缺點在于建立一個新版本的 main 所帶來的開銷。對于大型表或分區，要計算出一個新的字典并重新生成 main index 的确會占用額外的 CPU 和磁盤資源。而部分合并（partial merge）則通過使用以前的算法來緩和這個問題。部分合并政策展現了在字典中新條目數量較少的情況下，列的最佳壓縮潛能。
部分合并的核心思想是将 main 拆分成兩個或更多的獨立 main：
消極 main（active main）：main store 中的穩定部分，通常不參與合并過程。
積極 main（passive main）：列中可動态伸縮、參與和 L2-delta 的合并的部分。
圖9：部分合并概覽
從概念上來看，部分合并政策中的合并間隔始于一個空的積極 main。消極 main 通過分類詞典和相應的值索引（values index）來反映正常 main 結構。當一個合并操作開始執行時，L2-delta 将合并至仍然為空的積極 main，而消極 main 保持不變。與完全合并（full merge）相比，部分合并有一個細微的不同之處。積極 main 的詞典以 n+1 的詞典位置值開始，而消極 main 的詞典則以 n 結束。盡管系統現在有兩個帶有本地排序字典的 main 結構，但是各個 main value index 結構的編碼并不重疊。顯然，積極 main 的字典隻儲存消極 main 的字典中尚未涵蓋的新值。
圖10 顯示了部分合并後一個消極 main 和一個積極 main 的示例情況。積極 main 的字典編碼從 n+1 = 6 開始，進而可以延續消極 main 的編碼方案。雖然消極 main 字典對應的value index 結構僅儲存對消極main 字典中條目的引用，但是積極 main 字典的 value index 也可以展示main 字典的編碼值，使得積極 main 字典依賴于消極 main 字典。
圖10：積極 main 和消極 main 的範圍查詢執行
點通路（point access）在消極字典中被解析。如果找到了所請求的值，則相應的位置被用作消極和積極 main 的 value index 的編碼值。執行并行掃描以找到相應的條目。但是，如果沒有找到所請求的值，則查詢積極 main 的字典。如果該值存在，則隻掃描積極main 的 value index，識别出所需的行的位置。對于範圍通路（range access），範圍會在積極 main 和消極 main 的字典中解析，并且範圍掃描在兩個 main 上被執行。對于積極 main 的字典，掃描分為兩個部分範圍（partial range），一個是消極 main 的字典的編碼範圍值，另一個是積極 main 的字典的編碼範圍值。圖 10 展示了值在C%和L%之間的範圍查詢的合并過程。為了保證事務的一緻性，查詢處理還要求與 L1-delta 和 L2-delta 進行類似的合并。
當系統運作時，積極 main 可能會動态地收縮和增長，直到一次完全合并被安排好。這種做法的主要優點是将完全合并延遲到負載較低的時候執行，并且降低了 L2-delta 到 main 或者積極 main 的合并成本。此外，該優化政策可以通過以下方式部署為經典合并的方案：将積極 main 的最大尺寸設定為 0 來強制在每個步驟中進行（經典）完全合并。顯然，該過程可以輕松地擴充到多個消極 main 結構，這些消極 main 結構形成了和本地字典的依賴性相關的邏輯鍊。這種配置非常适合那些字典變化極少或者字典很穩定的列（例如“Customer”表中的“Country”列）。不過對于大多數列來說，系統将僅維持一個消極 main。
從概念上來講，部分合并優化政策在 SAP HANA 資料庫統一表概念的記錄生命周期中增加了一個步驟。越接近傳輸的末端，對記錄的重組就越複雜、越耗費時間和資源，最終形成以傳統列存儲的高度壓縮和讀取優化格式。此外，SAP HANA 資料庫提供了曆史表（historic table）的概念，可以透明地将記錄的曆史版本移動到單獨的表結構中。是以，在建表時，就必須将表定義為“historic”類型。此外，從應用的角度來看，分區（partitioning）概念的應用可以将最近的資料集與穩定的資料集分隔開來。
4.4 總結
如上所述，SAP HANA 資料庫通過對記錄進行生命周期管理，為事務型和分析型工作負載提供高效通路。圖 11 對比了所讨論的不同存儲格式和傳播的特征。L1-delta 針對更新密集型工作負載進行了優化，并且可以頻繁地将增量資料合并到 L2-delta 結構中。L2-delta 結構已經針對讀取操作進行了很好的調優，但是與高度讀取優化的 main 結構相比，它産生了更大的記憶體占用。然而，L2-delta 特别适合作為 L1-delta 行或者批量插入的目标。如前所述，main 結構可以被分為積極 main 和消極 main，表現出極高的壓縮率，并且針對基于掃描的查詢模式（query pattern）進行了優化。由于資源密集型重組任務，與積極 main 結構的合并，尤其是建立新的 main 結構的完全合并的頻率非常低。相比之下，L1-delta 到 L2-delta 的合并可以通過将資料附加到 L2-delta 的字典和 value index 中遞增進行。
結論
衆所周知，列存儲系統可以為 OLAP 型工作負載提供卓越的性能。通常而言，列式資料布局極其适合那些涉及數百萬行卻僅僅需要其中幾列資料的聚合查詢。但是，使用不同的系統處理 OLAP 和 OLTP 查詢的方案不再滿足現代業務應用的最新需求。主要原因可歸納為兩方面：一方面，營運系統将越來越多的即時業務決策統計操作嵌入到個人業務流程中；另一方面，傳統的資料倉庫基礎設施需要捕獲事務流（transactions feed）以進行實時分析。在本文中，我們基于 SAP HANA 資料庫的經典列存儲架構，概述了涵蓋查詢轉換、計劃生成和不同專用引擎互動模型的查詢處理環境。此外，我們更詳細地解釋了通用統一表資料結構。這種由不同狀态組成的資料結構為消費查詢引擎提供了一個通用接口。本文的總體目标是介紹一些在 SAP HANA 資料庫中實施的優化措施，使得列存儲适用于大規模事務處理，糾正人們關于列存技術僅用于 OLAP 型工作負載的偏見。
緻謝
我們真誠感謝位于沃爾多夫、首爾、柏林和帕洛阿托的 SAP HANA 資料庫團隊，感謝他們讓 HANA 的故事成為現實。