@原创文章，转载请注明: 转载自 镜中影的技术博客
本文链接地址: Apache Arrow源码分析（一）——简介和框架
URL:http://blog.csdn.net/linkpark1904/article/details/50980464

背景

列存储在数据库领域中早已被提出，列存储数据结构在分析型事务上表现优异，大数据分析引擎，诸如Spark-SQL，Impala 均采用列存储作为其中间数据表示形式，那么Apache Arrow就是这样一种内存列式数据结构。

在众多分布式系统中，每个系统都有自己内部的内存格式，70-80%的CPU浪费在序列化和反序列化过程，类似功能在多个项目中实现，没有一个标准。那么Arrow就是为解决这一问题而提出了。Arrow基于列存储的数据组织方式，能够很好的适应CPU的Cache，以及现代CPU SIMD (Single input multiple data) 技术，并且提供良好的序列化和反序列化性能。更值得一提的是，Arrow提供良好的扩展性，既有C++版的实现，又有java版的实现，是一个很值得学习的数据结构库。

基本思想

Arrow 基本思想就是把向量在内存中的布局给紧凑话，说白了，就是把之前按行表示的数据按列进行组织。

举一个很简单的例子，对于一个字符串向量{“a”, “bb”, “”, “”, “ccc”}，通常在c++中我们采用vector进行存储vector strings = {"a", "bb", "", "", "ccc"};， 采用这种存储方式，其内存布局大致如下图所示：

由于STL容器string中存储字符串的空间在堆上分配，那么每一个string对象会单独在堆上申请内存空间，存储字符串，这就可能导致在内存中，vector 存储空间并非连续的。这样的存储会带来两个问题，其一在于，不能很好的适应CPU cache，其二在于序列化和反序列化代价较大。

那么Apache Arrow将vector进行变形，转换成如下的存储方式：

引入一个Offset向量，以及连续内存空间的buffer，对外提供和vector类似的接口。其中，对于string 的访问接口实现如下所示：

  const uint8_t* GetValue(int64_t i, int64_t* out_length) const {                                                                
      int32_t pos = offsets_[i]; 
      *out_length = offsets_[i + 1] - pos; 
      return raw_bytes_ + pos; 
    } 

    std::string GetString(int64_t i) const { 
      const uint8_t* str = GetValue(i, &nchars);
      return std::string(reinterpret_cast<const char*>(str), nchars);
    } 

引入偏移量向量来对连续的buffer空间进行索引，从而对外提供和vector类似的取值接口。

框架和类图

Apache Arrow类的设计采用建造者模式，封装了基础类array，buffer，以及arraybuilder，具体类图如下图所示：

参考资料：

https://github.com/apache/arrow
http://www.uml.org.cn/itnews/2016030208.asp