列式存储原理与数据压缩

列式存储原理

• 列式存储 vs 行式存储

  特性	行式存储（如MySQL）	列式存储（ClickHouse）
  数据排列	按行连续存储（所有字段相邻）	按列连续存储（单列数据紧密排列）
  适用场景	OLTP：频繁单行读写、事务操作	OLAP：批量读取、聚合计算、复杂分析
  I/O效率	读取整行，即使只需少量字段（I/O浪费）	仅读取查询涉及的列（减少I/O，提升吞吐）
  压缩潜力	低（不同数据类型相邻，压缩率低）	高（同列数据类型一致，重复模式多，压缩率高）

• 列式存储的核心优势

  • 减少I/O开销：仅加载必要列数据，降低磁盘和网络带宽压力。
  • 向量化处理：同列数据连续存储，可利用SIMD指令并行处理（如批量计算SUM(price)）。
  • 高效压缩：同列数据重复性高，可采用针对性的压缩算法（如字典编码、Delta编码）。
  • 延迟物化：在压缩数据上直接计算，减少内存占用（如聚合前不解压字符串）。

数据压缩机制

• 压缩算法选择

  算法	压缩速度	解压速度	压缩率	适用场景
  LZ4	极快	极快	中等	默认选择，通用场景
  ZSTD	快	极快	高	存储成本敏感，CPU资源充足
  ZLIB	慢	中等	高	历史兼容，不推荐新项目使用

• 压缩优化策略

  • 自适应压缩级别：ZSTD允许动态调整压缩级别（1-22），平衡速度与压缩率。
  • 列级压缩策略：不同列可独立配置压缩算法（如文本列用ZSTD，数值列用LZ4）。
  • 字典编码：对低基数列（如country枚举值）自动构建字典，用整数代替原始值存储。
  • Delta压缩：对有序数值列（如时间戳、自增ID），存储差值而非原始值，大幅减少存储空间。

向量化执行引擎

传统行式执行 vs 向量化执行

特性	行式执行（Row-based）	向量化执行（Vectorized）
处理单位	单行数据（逐行处理）	数据块（Block，包含多行数据的列式集合）
CPU指令优化	频繁分支跳转，无法利用SIMD指令	按列连续处理，触发SIMD指令并行计算
缓存利用率	低（随机访问不同列数据）	高（连续访问单列数据，缓存命中率高）
适用场景	OLTP（短事务、单行操作）	OLAP（批量计算、聚合分析）

• 行式执行：逐行计算price * quantity，循环次数多，无法并行。
• 向量化执行：将price和quantity两列数据分别加载到寄存器，通过SIMD指令批量计算。

ClickHouse的向量化实现

• 数据块（Block）结构

  • 处理单元：每个Block包含多行数据（如默认8192行），按列存储（与内存中的列式布局一致）。
  • 内存连续：单列数据在内存中连续排列，便于SIMD指令加载（如一次读取256位寄存器数据）。
  • 类型感知：Block内数据类型明确（如ColumnUInt32），避免运行时类型判断开销。

• SIMD指令加速

  • SIMD（Single Instruction Multiple Data）：单条指令处理多个数据，例如：

    AVX-512指令集：单指令处理16个Int32或8个Double。

    适用操作：过滤（WHERE）、聚合（SUM）、数学运算（sqrt）、哈希计算等。

  • 自动向量化：ClickHouse编译器（CLang）自动将循环展开为SIMD指令，或手动内联汇编优化关键路径。

• 零拷贝与惰性物化

  • 零拷贝（Zero-Copy） ：在Block之间传递数据时，仅传递指针而非复制数据，减少内存开销。
  • 惰性物化（Lazy Materialization） :延迟生成中间结果，仅在必要时解压或转换数据。

向量化执行的优势

• 性能提升

  • 吞吐量：相比行式引擎，向量化执行在聚合查询中可提升 5-50倍 性能。
  • 资源效率：减少CPU指令分支预测失败和缓存失效，提高计算密度。

• 典型优化场景

  • 聚合函数：sum、avg、count等统计计算。
  • 过滤操作：WHERE条件中的批量判断（如WHERE value > 100）。
  • 排序与JOIN：向量化哈希表加速JOIN，SIMD加速排序比较。

向量化执行的实现细节

• 列式内存布局

  • 列数据连续存储：每列数据在内存中连续分配，便于SIMD指令批量加载。
  • 数据类型优化：使用紧凑数据类型（如UInt8代替String枚举）提升寄存器利用率。

• 查询计划优化

  • Pipeline执行模式：将查询分解为多个Stage，每个Stage处理一个Block流，减少中间结果内存占用。
  • 并行流水线：多个Pipeline并行执行，充分利用多核CPU（如max_threads参数控制并发度）。

• JIT编译优化（实验性）

  • 动态代码生成：对热点循环（如聚合函数）生成机器码，绕过虚函数调用开销。
  • LLVM优化：使用LLVM编译器进一步优化生成的代码（需启用compile_expressions配置）。

分布式计算模型（分片与副本机制）

分片（Sharding）机制

• 目标：将数据水平拆分到多个物理节点，突破单机存储与计算瓶颈。

• 分片键：通过分片键（如用户ID、时间戳）决定数据分布策略，支持以下两种模式：

  • 显式分片：用户手动指定数据分布规则。
  • 隐式分片：通过哈希函数自动分配数据（如rand()随机分布）。

• 分片策略

  分片类型	实现方式	适用场景
  哈希分片	对分片键（如user_id）计算哈希值，按模运算分配节点。	数据分布均匀，避免热点。
  范围分片	按分片键的范围（如时间范围2023-01-01 ~ 2023-06-30）分配节点。	时序数据，按时间分区查询。
  自定义分片	通过用户定义的规则（如user_id % 10 < 5）将数据映射到指定分片。	复杂业务逻辑（如多租户隔离）。

• 分片写入与查询

  • 写入流程：

    客户端向任意节点发送写入请求。

    分布式表根据分片键计算目标分片节点。

    数据路由到对应节点的本地表（如local_table）存储。

  • 查询流程：

    查询发送到协调节点（任意节点）。

    协调节点将查询分发到所有相关分片。

    各分片并行执行查询，返回中间结果。

    协调节点汇总结果并返回最终数据。

副本（Replication）机制

• 副本的核心思想

  • 目标：在多个节点保存相同数据副本，实现高可用与故障恢复。
  • 实现方式：基于异步复制，通过ReplicatedMergeTree引擎实现数据同步。

• 副本工作机制

  • 依赖组件：ZooKeeper（存储元数据与复制日志，协调副本间状态）。

  • 数据同步流程：

    写入请求发送到主副本节点。

    主副本将操作日志（如插入、合并）写入ZooKeeper。

    从副本监听ZooKeeper日志，拉取并应用变更。

    副本间周期性校验数据一致性。

MergeTree引擎的底层逻辑

数据写入与存储结构

• 数据写入流程

  • 内存缓冲：数据先写入内存缓冲区（Memory引擎的临时结构）。
  • 生成数据块（Part） ：缓冲区满或手动触发时，数据按列压缩并写入磁盘，形成独立的数据块（Part）。

  • 数据块特征：

    每个Part包含数据文件（.bin）、索引文件（.idx）和元数据（checksums.txt）。

    Part按写入顺序命名（如20231001_1_2_0），命名规则为{partition_id}_{min_block}_{max_block}_level。

• 存储目录结构

  # 示例表目录结构
  /user_behavior/
  └── 20231001_1_1_0/         # 数据Part
      ├── event_time.bin      # 列数据文件（压缩）
      ├── event_time.mrk2     # 列标记文件（定位数据位置）
      ├── primary.idx         # 主键索引文件
      └── checksums.txt       # 校验和元数据
  

数据合并机制（Merge）

• 合并触发条件

  • 后台线程周期性触发：默认每10分钟检查一次可合并的Part。
  • 合并规则：合并相邻的、时间范围重叠的Part；合并后生成更大的有序Part，减少碎片化。

• 合并过程

  • 选择候选Part：选取多个小Part（如20231001_1_1_0和20231001_2_2_0）。
  • 重新排序：按主键（ORDER BY字段）重新排序数据，生成全局有序的新Part。
  • 更新元数据：旧Part标记为过期，新Part生效（原子性操作）。

• 合并策略优化

  • 层级合并（Leveled Merge） ：level值表示合并次数（如20231001_1_2_1中的1）；高层级Part优先合并，减少合并次数。
  • TTL（Time to Live） ：自动删除过期数据（如保留最近30天数据）。

主键索引与数据查询加速

• 主键（PRIMARY KEY）设计

  • 主键定义：通过ORDER BY字段隐式定义主键（默认与ORDER BY相同，可独立指定）。
  • 主键作用：确定数据在磁盘上的物理排序顺序；生成稀疏索引（.idx文件），加速范围查询。

• 稀疏索引原理

  • 索引粒度（index_granularity） ：默认每8192行生成一个索引条目。
  • 索引结构：存储每个索引粒度的主键最小值（如event_time的最小值）。
  • 查询流程：根据查询条件定位主键索引的起始和结束位置；跳过不满足条件的数据块（Mark文件定位具体列数据位置）。

跳数索引（Skipping Index）

• 跳数索引的作用

  • 辅助过滤：在主键索引基础上，进一步加速非主键字段的查询（如event_type）。
  • 索引类型：支持minmax、set、bloom_filter等算法。

• 索引工作原理

  • 生成阶段：在数据合并时生成跳数索引。
  • 查询阶段：根据索引快速判断数据块是否包含目标值（如event_type = 'click'）。

分区管理（PARTITION BY）

• 数据裁剪：按分区字段（如时间）快速过滤无关数据块。

• 生命周期管理：按分区删除过期数据（如ALTER TABLE ... DROP PARTITION）。

最佳实践

• 主键设计：选择高频查询字段，确保主键前缀能覆盖大多数查询条件；避免主键过多字段（1-3列），减少索引冗余。

• 分区策略：按时间分区（如PARTITION BY toYYYYMM(event_time)）；单个分区数据量控制在10GB-100GB，避免分区过多。

• 跳数索引优化：高基数字段（如user_id）使用bloom_filter索引；低基数字段（如status）使用set或minmax索引。

• 监控与维护：定期检查system.parts表，合并小Part（OPTIMIZE TABLE FINAL）；定期清理过期数据。