2011ICDE-ES2: A Cloud Data Stora

作者: Caucher | 来源:发表于2021-05-21 21:10 被阅读0次

标题：一个云数据存储系统同时支持OLAP和OLTP
本文是分布式数据库Epic的存储引擎部分详细设计说明，Epic文章在2010WISE-Providing Scalable Database Services on the Cloud
Epic(elastic power-aware data-intensive Cloud computing platform)基本架构图如下，本文只讲ES2：

image.png

编者的思考

作为云平台的设计，实验的数据集太小了，最多也就几百GB，还不够证实作为云平台的方案；
P2P通用的索引框架设计是一个创新点，从实验看下来扩展性很强，但是未在本篇中阐述细节；
meta-data的分布式存储，一致性级别分离的设计方案效率证实也很不错，也是一个创新点；
OLAP CBO在2011年是一个新概念，尤其是依赖于表histogram算代价的思路，尽管如此，代价的计算还是较简单；
muli-version timestamp的分发有可能构成单点瓶颈，而且对于传统的事务处理、隔离性保障、ACID特征，本文都没有讲到具体是如何做的；
复杂性查询处理性能如何没有提到，比如RDBMS的瓶颈问题：多表join是否能解决，如何解决的？有可能在E3计算引擎中有讲到，但是目前看来在存储引擎里没有发现提供了特殊支持。
HDFS的吞吐量是否可能成为瓶颈？尤其作为云平台在数据量较大的时候，单机瓶颈问题。

I. INTRODUCTION

为了避免OLAP的高计算成本影响OLTP的前台query性能，因此分割成独立系统（可以满足决策需求）：

OLAP: 数据仓库模型 OLTP：RDBMS模型/NoSQL模型

OLAP与OLTP的分开研究会导致很多问题：

数据新鲜度不够
数据冗余存储
系统启动投资大，运维难度高

为了解决OLTP中的扩展性、可用性、响应时间（削弱一致性、吞吐量）：BigTable, Cassendra, Dynamo
为了解决OLAP中的大数据处理效率：Hadoop, Hive, Pig
也有主存HTAP方案，没有得到广泛应用。

对于Epic来说：

OLAP、OLTP用同一套数据访问接口(ES2提供)
OLAP处理：并行化顺序扫描
OLTP处理：索引+优化器
大量廉价机器构成系统
有水平分区(region)+垂直分区(列族)：类Hbase

ES2设计了通用的索引框架，基于这种框架在分布式数据库上设计了多种分布式索引以适应不同workload。

III. SYSTEM OVERVIEW

Data Model：采用的是关系型数据建模方式。一方面OLAP普遍都采用关系型建模，传统OLTP自然不必说。新型的Nosql建模就是k-v型数据库，如bigtable,cassendra等，也将设计重点放在了事务处理上，因此关系型建模可以满足所有需求。
Data Partition：
- 垂直分区（列族）
  将经常一起访问的列聚集在一起，以单独的物理表进行存储，每个列族都会保留主键；
  OLAP经常只访问部分列；
  OLTP通知只修改部分列。
- 水平分区（region）
  列族内部也会被分割成几个部分进行物理存储；
  分割是精心设计过的，以减少不同节点间的依赖，简化事务处理过程。
Transaction Management：
复制只用于负载均衡和可靠性保证，多版本事务管理用于支持两种负载。具体来说，OLTP访问最新数据，OLAP访问一个最近的一致快照。

下图是ES2的整体架构图，分成三个模块。

image.png

数据导入控制模块的功能是复杂数据的批量导入和导出。在ES2中写入数据有两种方式，一种是bulk-loading，一种是通过事务操作来写入。该模块有两个部分，import manager实现多种协议，负责和外部数据源交互，write cache充当一个写入buffer的角色。
物理存储模块负责数据存储。由三个部分组成，DFS，元数据目录，分布式索引。ES2的可扩展性和可用性主要依赖于DFS的容错和负载均衡的能力，DFS可以稍作更改，就使用HDFS。元数据目录一方面存表的相关元信息，一方面作细粒度的统计信息给计算引擎做准备。对于选择率很低的查询，无论OLAP还是OLTP，索引是最好的方案（而不是并行顺序扫描）。水平分区可以基于hash或者基于范围，但总归是基于一部分列或主键，如果用户不筛选这部分数据，那就需要二级索引。
数据访问模块负责OLAP和OLTP的数据访问需求。数据访问接口负责parse和转化为中间表示，数据操纵器其实就是优化器，负责制定查询计划（索引/扫描/混合）。

IV. DATA IMPORT AND PHYSICAL STORAGE

A. Import Manager

Import Manager可以有三种类型的数据源：

DBMS
扁平的(txt,csv)或半结构化数据(xml,html)
实时数据（E3产生的数据结果，外部数据流）

对于每个数据源，import manager都会创建一个data adaptor负责与数据源交互，和一个data importer负责其余工作，具体来说：

请求元数据(scheme)，进行scheme映射；
确定数据分区，提醒索引更新；
收集统计信息放入元数据目录。

对于每一个物理表，实际上就是每个列族的每一个region，都会有对应的内存write cache，作为写入缓冲。
导入过程的并行性体现在两方面，第一个可以多用户同时导入，第二个单用户也可以并行导入多个表。

B. Write Cache

write cache有以下几个好处：

和磁盘数据布局格式一致存储，利于写入；
索引和统计信息都可以批量更新，锁的占用时间降低；
对DFS的调用频率降低。

PAX页数据布局：数据都是以二进制流的格式写入和存储的，PAX是将region分成多页存储，每一页中各个列占据不同的部分。
由于data import过程存在并行性，所以会有多个write cache共享一块内存，涉及调度问题。调度过程是动态的，根据表大小和数据导入速率决定；内存不足时也会有和磁盘换入换出的操作。

C. Meta-data Catalog

元数据目录存储三种信息：scheme/statistics/runtime statistics。
元数据的一致性非常重要，为了避免更新称为瓶颈，元数据也是分布式存储的，但是对不同元数据的一致性级别是不一致的，比如对于scheme就要严格一致性，对于runtime statistics可以弱一致。

V. DISTRIBUTED INDEXING

选择分布式索引而非单机的理由：

数据量太大（云平台），即使是索引，单机也存不下；
高并发环境下，单机索引容易成为瓶颈。

index nodes和data nodes用同一个集群，但是索引和其对应的数据可以不在同一个机器上。当访问数据时首先check元数据，决策是否要用索引加速，如果是，则要定位到相应的索引节点，索引中包含page id，访问索引可以得到数据所在的page id，然后选择合适的副本进行访问。ES2也支持物化索引或物化视图，对于小表是可以显著加速的。
分布式索引都是两层的结构，一层是本地的基于磁盘的索引，上层是P2P的路由层，peer之间通过长TCP连接，每个节点都有connection manager管理连接。为了让所有分布式索引能够共享类似的P2P路由层，作者设计了一个通用的索引框架，每个索引去实现这个框架要求的接口就可以了，这些接口里有路由协议和关键的分配策略。P2P层的实例有管理器进行管理，目前系统内置实现了分布式bitmap，哈希，B+树，kd树。索引可以缓存进buffer manager。

VI. DATA ACCESS PROCESSING

data manipulator需要处理数据的物理存储，因此可能成为性能瓶颈，但是可以将其复制到多个节点上去以负载均衡。

A. Data Access Interface

定义了OLAP和OLTP两套数据访问接口。
OLTP：

image.png

OLAP：MR的数据访问主要是并行化的数据扫描，在map阶段进行数据过滤。ES2额外有索引的支持，因此上层计算引擎E3可以下推筛选和投影操作以利用索引，甚至还可以对复杂计算操作提供辅助（预聚合、排序等）。

image.png
open操作让manipulator去寻找数据位置,next去迭代数据块，close做清理工作。

B. Data Manipulator

1) OLAP and OLTP Isolation

OLAP和OLTP必须要隔离，因为OLAP的高计算强度会使得OLTP吞吐量大幅下降，可以同时进行计算，但是不能互相竞争一些数据的访问。用锁是不太现实的，OLAP有可能会大规模的锁表锁索引让OLTP无法访问，因此采用了多版本时间戳的方案。每条记录都有一个时间戳，记录版本，更新操作实际上仍然是append，每条记录的总数是有限制的，如果更新太多会把之前的废弃掉。
时间戳也并不是真实时间戳，是epoch的概念，由Timestamp authoryity(TA)定期向节点发布。TA是一个单独的服务器，有热备。当一个OLAP query到来时，获得一个当前时间戳，查询只查这个时间戳以前的数据。如果某条记录被废弃了，那就读最新的，但是时间戳可能更大，因此存在不一致的可能，此时要提醒用户。
通过以上方法，所有写操作和所有读操作就不互斥了。

2) Data Access Optimizer:

无论是OLTP还是OLAP，对数据的访问本质上都是一样的，方式统一就两种，索引访问或者并行扫描。多个Region可以同时并行扫描。对于数据筛选度小的query，索引也未必是合适的，因为第一未必有索引，第二DFS上随机访问太慢了。虽然随机访问数据很慢，但是给定一组offset，连续随机访问数据的速度就快了很多，因此会把多个查索引的query组合起来，一起查。引入一个optimizer，基于代价进行选择。

image.png

各种访问方式的速度代价，会定期通过一些micro-benchmark进行动态更新。代价最终以Query延迟作为衡量指标。
在并行顺序扫描的情况下，f(Q)就是访问表的size总和；index情况下，是匹配的记录的size总和，这种估计是基于直方图的。
顺序扫描下：第一项是一个节点有多少个chunks