Cloudera发表的kudu论文详解
Kudu: Storage for Fast Analytics on Fast Data
kudu：为 快数据的快分析 而生的存储架构
近年来，Hadoop生态系统丰富的组件被很多公司采用来搭建大数据平台。
在Hadoop生态系统中，结构化存储主要由两种实现方式：
- 一种是以静态的数据集方式存储，典型的是数据以二进制数据格式，如Apache Avro或者ApacheParquet格式存储在HDFS上
- 优点：顺序读的吞吐性能好，
- 缺点：它们很难支持单条记录的修改和高效的随机访问；
- 另一种是以可修改的数据集形式存储，典型的是以半结构化形式存储在Apache HBase或者ApacheCassandra中
- 优点：它们可以提供高效的单条记录读写操作，
- 缺点：它们的顺序读吞吐性能大大落后于静态的数据集形式
- 顺序的读吞吐性能在很多SQL分析和机器学习应用中很重要
HDFS上静态数据集可以很好的支持分析，HBase和Cassandra则有低延迟和行记录随机读写的能力；当一个应用同时需要这两种访问模式的时候，就需要开发一个新的复杂结构来弥补HDFS和HBase之间的缺陷（在Cloudera官方的博客上，对于Kudu的描述是：一个弥补HDFS和HBase之间的缺口的新型的存储，它能够更有效的利用现代硬件的CPU和IO资源，既能够支持分析，又能够支持更新、删除和实时查询）。
很多Cloudera的客户都开发了这样的数据流水线，先将数据流收集到HDFS，并实时更新到Hbase，然后周期性的将表导出Parquet，后续进行分析。这样的架构具有以下缺陷：
- 在两个系统之间，要写复杂的代码区管理数据流和数据同步
- 管理员必须在多个系统之间保持一致性的备份、安全策略、监控
- 这样的架构会导致非常大的延迟，between the arrival of new data into the HBase “staging area” and the time when the new data is available for analytics.
- 这样的架构会浪费集群资源（HBase和HDFS多份存储、同时多个组件间数据导入导出会浪费计算资源）。
新存储系统kudu的设计与实现就是为了彻底弥补高吞吐顺序读写系统HDFS和低延迟随机访问系统HBase之间的差距。当然，HDFS和HBase在特定的场景中任然具有优势，kudu只是提供了一种折中的可选方案来简化架构。特别是，kudu提供了
- 简单的API用于行级的插入更新删除操作，快速的随机访问，满足查询的需求
- 与Parquet相同的读吞吐性能，快速的数据scan一种静态文件常用的列式格式，来满足分析要求
这篇文章主要介绍kudu的架构：
- 第2部分从使用者的角度来描述kudu系统，介绍了数据模型，APIs，可视化操作构图；
- 第3部分描述kudu的架构，包括如何分区，如何在节点间传递副本，故障恢复和一些常规的操作；
- 第4部分解释kudu是如何在磁盘中存储数据来保证快速访问和高效分析性能的；
- 第5部分讨论如何将kudu与hadoop其他组件集成。第6部分展示了kudu在测试工作量时的主要性能。
2 从上层看kudu（使用者角度）
2.1 创建一个表：Tables和schemas
从使用者的角度，kudu是以表的形式进行结构数据存储的存储系统：
- 一个kudu集群有多个表，每个表都是由schema进行定义，由有限个列（属性）组成。
- 每列有一个名字及类型(例如INT32或STRING)，并且可以选择是否支持空值。
- 这些列的一些有序的列可以定义为表的主键，主键必须是唯一的(at most one row may have a given primary key tuple)，并且做为一行有效删除和更新的唯一索引。
这些数据模型与传统的关系型数据库非常的相似，但是与Cassandra,mongodb,riak,bigtable等分布式数据存储却非常的不同。
与使用关系型数据库一样，kudu的用户必须要先在创建 表时给定表的schema。
- 如果插入没有事先定义过的列会报错，如果违反主键唯一性约束也会有相应的错误。
- 用户可以通过alter table来增加或者删除列，但是主键列不能够被删除。
我们决定为每列明确的指定类型，而与NoSQL的“一切都是byte”的形式明显不同，这样做的动机是
- 显示指定类型这可以高效的使用类型相关的列编码方式，such as bit-packing for integers.
- 显示指定类型可以向上层分析系统暴露SQL似的数据元信息，such as commonly used business intelligence or data exploration tools.
虽然采用类似于关系型数据库的表设计，不过Kudu的设计不支持二级索引，这个限制和HBase是一样的。目前，kudu要求每个表必须定义一个主键列；将来的版本，我们期望kudu具有代理键自动生成特性。
2.2 写操作APIs
创建了表以后，用户通过insert,update,delete 这三个APIs来修改这个表，即插入、修改和删除数据。以上三个API操作，用户都必须指定主键，predicate-based 删除或者修改必须使用更高级的访问机制（见第5部分）。deletions or updates must be handled by a higher-level access mechanism (see section 5).
kudu提供java和C++的APIs，支持python的API处于试验阶段。The APIs allow precise control over batching and asynchronous error handling to amortize the cost of round trips when performing bulk data operations (such as data loads or large updates).目前，和HBase一样，kudu没有支持跨行级别事务的APIs：each mutation conceptually executes as its own transaction, despite being automatically batched with other mutations for better performance.Modifications within a single row are always executed atomically across columns.。
2.3 读操作
kudu只提供了一个scan操作来从表读取数据，不过用户可以给定一些条件来过滤结果。目前，kudu支持两种条件，一种是用一列和一个常量进行比较，另外一种是给定主键的范围。These predicates are interpreted both by the client API and the server to efficiently cull the amount of data transferred from the disk and over
the network.
除了给定条件，用户还可以指定一个scan的projection，这个projection由要返回的部分列组成，即用户可以指定只返回部分列。因为Kudu的实际在磁盘上存储是列式的存储，指定返回列可以在分析场景中大幅度的提高性能。
2.4 其他APIs
除了以上data path APIs，kudu的client库还提供其他有用的功能。In particular, the Hadoop ecosystem gains much of its performance by scheduling for data locality. Kudu provides APIs for callers to determine the mapping of data ranges to particular servers to aid distributed execution frameworks such as Spark, MapReduce, or Impala in scheduling.
2.5 一致性模型
一致性模型，默认支持snapshot ，这个可以保证scan和单个客户端 read-you-writes一致性保证。更强的一致性保证，提供manually propagate timestamps between clients或者commit-wait。
kudu为多个clients客户端提供了两种一致性模型的选择。默认的一致性模型是快照一致性。一个scan保证产生一个没有异常的快照，这个因果上可能有点说不通（目前处于测试版的kudu这种一致性支持还没有完全实现，然而，本文重在描述系统的架构和设计，尽管还存在一些与一致性有关的bugs）。同样地，这种模式也保证单个client的read-your-writes一致性。（主要是如何协调多个client端读写时的先后顺序以及加锁操作等）
默认情况下，kudu不提供外部的一致性保证。这就是说，如果一个client客户端执行一个写操作，然后与另一个client通过外部的机制（即信息总线）进行通信，这个client也执行一个写操作，两次写操作之间的因果依赖关系不会被获取到。第三个阅读的客户端只会看到第二次写的快照，并没有第一次写的。
根据我们（Cloudera）对其他系统的支持经验，比如HBase，也不提供外部一致性保证的，这在很多应用场景中已经是足够的了。然而，对于需要更强保证的用户，kudu提供了手工在多个客户端之间传递时间戳的选择：执行完一次写操作后，用户可向client library请求一个时间戳token。这个token将会通过外部信道传播给另一个client，另一方面将会传给kudu API，因此这个过程保留两个client写操作之间的因果关系。？？
如果传递token太复杂了，kudu也可以选择采用像spanner的commit-wait的模式。。。。。
2.6 时间戳
和hbase反向设计，写不支持时间戳，避免用户乱用。读可以加时间戳读取过去一个时间的快照。这一点上感觉各有优劣吧，对读更加友好
尽管kudu使用内部的时间戳去实现并发控制，kudu并不允许一次写操作的时间戳手工设定。这与HBase和Cassandr等系统的机制不同
3 架构
3.1 集群的角色
延续bigtable和GFS的设计主从架构（hbase和hdfs都采用这种开源架构），kudu也是一个master服务器负责元数据，多个tablet服务器负责数据。Master Server可以通过复制来是先容错和故障恢复。
3.2 分区
像大多数分布式数据库系统，kudu中的表示水平分区的。kudu，就像bigtable，称这些水平分区为tablets。每一行都会根据它的主键唯一的映射到一个tablet上，这样保证了随机访问的操作如插入或更新只影响单个tablet。对于超大的表，吞吐量的要求是比较高的，我们推荐一个大表可以分为10到100个tablets，每个tablet差不多可以是10G大小。
Kudu可以支持三种分片方式：横向切分、Hash分片、横向分片和Hash分片的组合。用户可以提供分片函数来指导Kudu对数据进行分片。但是在目前的实现中，Kudu要求用户在建表时就定义分片信息，不能对分片进行动态的分裂和拼接。
不像bigtable只基于key-range的分区方式，不像Cassandra用类似基于hash的分区方式，kudu支持一个灵活的分区方案。当创建一个表的时候，用户为这个表指定分区的schema。这个分区的schema扮演一个从主键多元组到二进制分区键的映射函数。每个tablet都包含一个连续的分区键范围。因此，当执行一个读或者写操作时，客户端可以很容易的确定哪个tablet可以持有给定的key，然后将请求沿路发过去。
这个partition schema是由0个或者多个hash分区规则以及一个可选的范围分区规则组成：
- hash分区规则由主键列的子集列和分区bucket数量构成，例如：用sql语言表达就是DISTRIBUTE BY HASH(hostname, ts) INTO 16 BUCKETS这些规则通过拼接指定列的值来转换键的多元组成为二进制键，然后计算以bucket数量为模产生的字符串的hash码。对桶数求余，然后生成一个32位的整形作为结果的分区key。
- 范围分区规则是基于有序的主键列，将列的值按照能够保持顺序的编码进行处理，然后将数据进行相应的分区。
相对于目前大部分的NoSQL系统来讲，Kudu的分区策略还是比较完善的，更像是传统的数据库或者MPP数据库。
3.3 备份
为了保证在大规模商业集群上运行的高可靠性，kudu会在多台机器上备份所有的表数据。当创建一个表的时候，用户要指定备份数（replication factor），一般是3、或者5份，这个量取决于the application’s availability SLAs。master会管理这些备份，并努力确保备份的数量（见3.4.2）。
kudu采用Raft一致性算法来复制这些tablets。尤其是，kudu用Raft算法去让每个tablet的操作（例insert/update/delete）日志达成一致。当客户端client想要去执行一个写操作，会先去找到leader replice（见3.4.3）同时发送一个写的RPC通信给这个replice。
- 它会拒绝这个请求，client会让当前的信息失效，并且更新元数据缓存，然后再重新发送请求给新的leader。
- 如果这个replica是leader，它会使用一个本地锁记录这个操作（it employs a local lock manager to serialize the operation），阻止其他的并行操作，通过MVCC时间戳机制来管理读写并发，leader会通过Raft将这个操作送到到followers。
- 如果大多数replicas都接受了这个写操作，而且leader replica主备份机器上写完了wal（对于磁盘写“成功”，kudu提供两种模式供用户选择——写入buffer cache或者一定要调用fsync才算成功），这个写就可以被提交给其他备份。但是kudu并不是强制leader必须写一条操作到日志后再去提交commit这个操作，避免因为leader的磁盘慢导致整体性能问题。
- 如果少数replica失败了，leader可以继续propose和commit操作到相应的tablet的replicated log。
- 如果leader自己挂掉，Raft算法会迅速选择一个新的leader。默认情况下，kudu采用500毫秒心跳间隔，1500毫秒选举超时；因此，当一个leader挂掉以后，一个新的leader会在几秒钟选举出来。
Kudu采用了Raft协议来实现表数据的复制，kedu对Raft算法进行了一些改进：
在Leader选举失败时，采用指数算法(Exponential Backoff)来重试，指数级的回退机制，保障在集群繁忙时的选举效率
当一个新的leader在联系一个follower时，如果follower的log与自己不相同，kudu会立即跳回到最后的committedIndex，这能够大大减少在网络上传输的冗余的操作，而且实现起来简单，并且能够保证不一致的操作在一次往返后就被抛弃掉。
另外，kudu的复制不是复制磁盘上的存储的表的数据，而是复制操作日志。表的每个副本的物理存储是完全解耦的，它带来了如下的好处：
- 当一个副本在进行后台的一些物理层的操作（flush或者compact，见第4部分)时，其他节点不会同时对同一个tablet也在进行操作。因为Raft协议的提交是过半数副本应答，这样后台物理层操作对于提交的影响将会降低，从而避免对集群的冲击以及额外的性能损耗。In the future, we anticipate implementing techniques such as the speculative read requests described in to further decrease tail latencies for reads in concurrent read/write workloads.
- 在开发过程中，kudu团队遇到过一些罕见的物理存储层竞争race condition情况，因为副本间物理存储的松耦合（物理存储并不会被复制），这些race condition都没有造成数据不可恢复的错误。我们可以探测到任何一个备份的错误，并对其做修复。
这一点来说kudu避开了操作的复杂复制，因为对主备份数据的操作具有事物的复杂性，这些再同步到从备份代价就很大了。hbase因为底层采用hdfs所以不存在此问题。所以从kudu的角度来看这确实是一个好的设计。
另一层原因可能是kudu底层假设目前的物理存储硬件并没有那么脆弱，恢复并不是一个经常性事件。区别于hdfs认为失效是常规事件(上万台服务器硬盘故障的频率和吃饭没两样，廉价硬件堆出来存储)。kudu明显是高富帅方案，既然要告诉分析也不能用太差的硬件吧。另外还特别和intel合作优化享受最新硬件IO方面的性能提升。
3.3.1 配置变更
主要讲了新增备份数，以及减少备份或者server配置的一些操作，还ok。没有太特别的
3.4 kudu Master
Kudu的中枢级的Master进程，它主要的职责包括：
- 作为一个catalog manager目录管理器跟踪维护的信息有，tables的机器是哪个, tablets是否存在，以及创建table的schema，复制的级别，以及其他的一些元数据。当创建、alter、删除表，master都会向tablets协调这些操作并保证最终完成。
- 作为集群的协调者，跟踪集群中server哪些存在，哪些是存活的；在某个server死掉后对数据进行重新分布。
- 作为tablet directory，跟踪哪个tablet server存储哪个tablet的副本（每个tablet都存储在哪些server上）
Kudu采用集中式、可复制的master设计，而非P2P模式设计简化实现，debuging以及操作
主从式设计目前来看是实现简单，效率最高的一种方式。只要把master元信息做备份master快速恢复，几乎能解决大部分问题。
3.4.1 目录管理器
master自己会保存一个单tablet的表，这个表用户不能直接访问。master会在内存中读写目录信息到这个tablet中，采用内存write-through cache来维护catalog（catalog信息也是一个tablet，类似hbase里的meta表）。当前商业硬件已具备大量的内存空间，每个tablet小量的元数据存储，kudu团队认为在目前的硬件架构下并不会成为扩展瓶颈。如果未来可能成为瓶颈，把它缓存到页cache中将是一个简洁的架构升级。
又一次证明通过硬件来简化软件设计的思路，这种简化并不能说是退步，感觉bigtable已经把存储系统设计到极致了，kudu的改进尽量通过硬件能力来弥补，同时带来效率和性能的提升
目录表管理器存储了系统中每个表的部分状态信息，尤其是table schema 的当前版本，表的状态（creating, running, deleting等），哪些tablet属于这个table。创建表时，
- 会先到master的catalog table中写一个数据，更新为CREATING state。
- 并且异步选择tablet servers存储tablets的副本，
- 在master端建好tablet元数据信息，
- 再异步请求每个tablet server去创建副本。
- 如果大多是replica创建失败或者超，tablet可以被安全删除，然后新的tablet及其副本将被重新创建，即master可以回滚重做。
- 如果在这个过程中master自己挂了，表记录会表明需要回滚了，master可以从停止的地方重新开始。
除了创建表，schema改变和删除操作时，master都会执行相似的过程，以确保向自己所维护的catalog table中写入新的状态之前，改变操作以及传递给了相关的tablet服务器。以上所有的情况，每个操作信息从master传到tablet servers都被设计为幂等的，也就是可以反复重做，所以每次宕机或者重启，他们会被安全地重新发送。(应该是server端简单判断下发的重复消息，然后做出忽略操作)
catalog的信息的物理存储也是tablet，master可以方便的采用Raft协议将存储的信息复制到候补的master进程，从而实现高可靠性。目前，候补的master扮演一个Raft followers的角色，并不会与client交互。根据Raft算法即将被选为leader的候补master，会scans它的catalog table，并加载到内存缓存中，开始扮演一个活跃的master。
由于catalog table也是Kudu的一个tablet，故master信息很好被重载到另外一个master接管这一切。 这里设计和hbase比较像，hdfs中的namenode需要引入一个外部存储来做ha也是增加了复杂性。只要记住最初的几个备份就行，不过hdfs有个特殊就是元数据信息可能很大，一两个block也存不下。不像hbase、kudu元信息大小可控好存。
3.4.2 集群协调
在kudu集群中，每一个tablet servers对于kudu master来说都是静态的主机名配置列表。集群启动时，
- tablet servers向mater注册，
- 然后发送tablet reports，内容是他们持有的所有tablets。
- 第一次发送的tablet reports包含所有的tablets信息
- 以后发送的tablet reports，只会报告新创建、删除或修改的信息(e.g. processed a schema change or Raft configuration change)
kudu设计的最关键的是，master server是目录信息的唯一来源，但是对于集群的动态状态信息，master server只是观察者。tablet server来负责tablet副本的位置，当前的Raft配置信息，以及tablet当前的版本信息等等。由于tablet的副本通过Raft协议来达到状态变化的一致，每个状态变化会在被提交的地方映射到一个指定的Raft操作索引中。这就允许master可以保证所有tablet的变更是幂等的，and resilient to transmission delays:master可以简单比较一个tablet的状态变更Raft操作索引，并舍弃掉老旧的索引。
这种设计选择让tablet server的server承担更多的责任。例如，kudu不是让master去检测tablet server是否崩溃，而是委托任意一个tablet的Raft协议选出的leader副本去负责崩溃机器上的副本：
- leader保持追踪分别与每一个follower最后一次成功地通信，
- 如果leader有一段时间与follower通信失败，就可以宣布这个follower挂掉了，
- leader会提议修改Raft配置，将这个联系不上的follower从Raft配置中驱逐出去。
- 当这个配置变更成功的提交了，剩下的tablet servers会发布一个tablet reports给master去告知master这个leader修改配置的决议。
为了恢复期望的副本数，基于master对整个集群的观察，master会选择一个tablet server去持有新的副本去增加副本数。在选择了新的server之后，
- master会建议这个tablet的leader副本去修改配置。master是没有权利去修改tablet配置的，必须等leader副本提出并提交配置变更操作，此刻master根据tablet report得知配置变更成功。
- 如果master建议失败了，可能信息丢失，他就会定期地顽固地重复操作直到成功。因为这些操作是被降级的配置的唯一索引所标记的，他们是等幂的和不冲突的，尽管master发布一些冲突的建议，as might happen soon after a master fail-over.
master会响应tablets额外的副本。如果master接收到了tablet report中显示，这是一个已经被tablet配置移除的副本，master就会坚持发送DeleteTablet RPCs给这个已经被移除的节点，直到RPC通信成功。为了保证最终将多余的节点清理干净，甚至在master自己crash的情况下，master也会发送这个RPCs去响应这个tablet report which identifies that a tablet server is hosting a replica which is not in the newest committed Raft
configuration.
master会关注大局，比如有些本该删除的备份还依然汇报心跳，他就会出面发出deleteRPC。check最终结果没问题，避免leader replica有时候出些岔子。 master充分授权(replica leader)，制定规则(Raft)，但是最后结果检查并且兜底。感觉是一个好的技术管理模式，分布式系统到最后和团队管理都有点像了。
3.4.3 tablet目录
为了有效的执行读写操作without intermediate network hops，client向master请求tablet位置，并在本地缓存中维护元数据信息，包括了每一个以前访问过的tablet最近的信息，有tablet的分区key范围、Raft配置。任何一个时间点，client缓存中的数据都可能是过时的；如果client企图去发一个写操作到已经不是那个tablet的leader的服务器，服务器就会拒绝这个请求。然后，client会联系master去了解最新的leader。这种情况，client与假的leader通信中，会收到一个网络错误，此时tablet很可能选了一个新的leader，也是同样的策略。？？
这样的设计可以减少了client对master请求的压力。对于不经常改变的信息这种快速失败重试的机制是很ok的。
将来，如果client联系一个非leader的副本，kudu团队计划让这个错误响应携带当前的Raft配置。因为follower副本的服务器上都有最新的Raft配置信息，这就可以防止leader选举后，client要与master额外进行通信了。
由于master在内存中维护所有tablet分区范围信息，每秒有大量的请求，响应保持低延迟。目前kudu在270节点的cluseter，跑一个几千个tablets的业务，一次tablet location 查询99.99%在3.2ms内，95%在374微秒，75%在91微秒。kudu开发者认为当前集群的大小，这个不会成为瓶颈，后续也可以通过再把location信息做分区，给几个不同的机器来提供服务。
走hbase的metatable路线，做起来也没什么问题
4 tablet存储设计
在tablet server上，每个tablet副本都做为一个完全独立的实体，从而与上层的分布式副本系统（3.3的描述）和分区（3.2的描述）进行解耦。在kudu的开发过程中，我们发现这样的设计有利于kudu发展独立于上层分布式系统的存储层，实际上我们很多功能的和单元的测试都完全运行在一个tablet的应用范围内。
由于这种解耦设计，这样kudu就可以自由的开发基于table、基于tablet或者基于replica的存储层，当前还只是有一个存储层。Due to this decoupling, we are exploring the idea of pro-
viding the ability to select an underlying storage layout on a
per-table, per-tablet or even per-replica basis { a distributed
analogue of Fractured Mirrors, as proposed in [26]. However,
we currently o er only a single storage layout, described in
this section.
4.1 概述
在Kudu的tablet存储设计中，主要考虑如下几个因素：
- 快速的列扫描：能够达到可以媲美Parquet和ORCFile的类似的性能，从而可以支撑分析业务，
- 低延时的随机更新：在随机访问时，希望达到Olog(n)的时间复杂度
- 性能的一致性
为了同时达到以上三个痛点，kudu没有采用现有的存储引擎，而是从头设计了一个全新的混合列式存储架构。
kudu自己设计了一套列存架构，是kudu的核心亮点，列存在目前有好多优秀设计，自己设计一套符合kudu独特架构的，也确实是有必要。
4.2 RowSets
tablets在kudu中被细分为更小的单元，叫RowSets。一些RowSets只存在内存中，称为MemRowSets，其他的在内存或磁盘中，称为DiskRowSets。任何一条存活的数据记录都只属于一个RowSet；因此，RowSets来自互相独立的行。但是，不同RowSets的主键区间可能交叉。
在任意时刻，每个tablet都只有一个唯一的MemRowSets，用于存储最近插入的行，有一个后台线程定期会flush MemRowSets到磁盘。flush的时间安排会在4.11中详细描述。
当一个MemRowSets被flush时，一个新的空的MemRowSets会被创建来替换它，而被flush的MemRowSets则会变成一个或者多个DiskRowSets。Flush过程是完全并行的，MemRowSets正在flush时，读操作还可以在MemRowsets上进行；而更新和删除行操作则会被记录下来，在flush完成后，更新到磁盘上。
4.3 MemRowSet的实现
MemRowSets的实现是一个支持并发的内存B-Tree，借鉴了MassTree的实现，并且做了一些修改：
- 不支持在树上进行元素的删除，而是采用MVCC记录删除的信息。因为MemRowSets最终会flush到磁盘，因此记录的删除可以推迟，在系统的其他部分进行删除。
- 不支持在树上对记录（元素）的任意的修改，而只是在值的修改不改变值占用的空间大小时才支持：this permits atomic compare-and-swap operations to append mutations to a per-record linked list.
- 叶子节点的连接是通过一个next指针来实现，这样可以显著提高顺序scan的性能。
- kudu并没有实现完整的trie of trees，仅仅是一个单一的tree，因为我们不关心非常高的随机访问吞吐性能compared to the original application.
为了提高随机访问的scan的性能，kudu采用了比较大的节点的空间大小，每个是4个CPU cache-lines的大小（256字节）。
不像其他数据在kudu中的存储，MemRowSets存储行使用行式设计。这样设计提供了很好的性能，因为数据在内存中。尽管选择了行式存储，为了最大化吞吐量，我们使用SSE2预取指令集去预取一个叶子节点在我们的scanner之前，以及LLVM编译优化来提高树的访问性能。
memRowSet按照行存储数据，采用了LLVM、JIT-complile、memcmp等一些特殊技术来家属查询，当然这种查询可以是根据主键范围(更快)或者根据独立的字段查询。
4.4 DiskRowSet的实现
DiskRowSets的实现同样做了很多实现的优化来提高性能
MemRowSets flush到disk之后，他们就变成了DiskRowSets。当flush一个MemRowSets的时候，IO达到32MB就滚动DiskRowSet，即按照32MB一个来flush一个到磁盘上。这个大小是保障每个DiskRowSet不会太大，而且能支持不断增长的compaction需求。因为MemRowSet是排序好的，被flush到磁盘的DiskRowSets将也会是排序好的，每一个滚动的部分将有一个互不相交的主键范围。
按照primary的范围分段，互补重叠。这个和hbase类似，但是kudu是预先划定好partition的，所以基本上可以认为这个划分和memRowSet中能很好对应上。
DiskRowSets在实现时被分成了两个部分，一个基础的数据部分(base data)以及一个变化存储（delta stores)。Base data是采用列式存储来存储数据，每一列被切分成一个连续的数据块写到磁盘，每列分成小的页来支持更细粒度的随机访问。它还包含一个内嵌的B-Tree索引，从而方便定位页，这是基于rowset有序的offset（这种存储在加上B-tree索引让row可以被快速查询到）。Column pages列存储采用一种encoding，比如dictionary encoding，bitshuffle或者front coding也可选，压缩采用LZ4，gzip，bzip2。这种每一列的编码和压缩可能被用户明确地指定（用户可以根据列内容需要去定制每一列），例如text列应该用gzip，存储小的integers型数字应该按bit-packed来，kudu用parquet来支持一些页面格式，实现方法参考了Impala和Parquet的设计和代码。
除了会将用户指定的 列数据flush到磁盘，Kudu还在磁盘写入了一个主键索引列，存储了每一行的主键编码，同时还flush了一个布隆过滤器到磁盘，从而根据他的主键编码方便判断一行是否存在。
因为列编码想要update非常困难，所以base data在flush到磁盘后就不会再改变。更新和删除操作会被追踪记录在delta stores中进行存储。delta stores即使在内存的DeltaMemStores也是在磁盘上的DeltaFiles。DeltaMemStore也是一个支持并发的B-Tree。DeltaFiles是一个二进制的列式数据块。delta stores包含了列数据的所有的变化（里面存储了row_offset和修改时间timestamp），维护了一个从（row_offset,timestamp)数组到RowChangeList记录的映射。
- row的offset仅仅是RowSet的顺序的索引，例如最低主键的行的offset是0。有点类似SET column id = ‘foo’ 或者delete。
- timestamp是最初的写操作MVCC的时间戳标记的
- RowChangeList行变化的二进制编码列表，例如指示SET column id = ‘foo’ 或者delete
当要更新DiskRowSet上的数据时，要首先查询主键索引列。通过内嵌的B-tree索引，可以有效的包含目标行的page页。使用page级的元数据，我们可以确定这个page第一个单元的行偏移offset。通过在page中搜索（例如 内存二进制搜索），可以计算出目标行在整个DiskRowSet中的偏移量offset。确定了偏移量之后，就可以向DeltaMemStore的行集中插入新的delta记录。
4.5 Delta Flushes
因为DeltaMemStore是内存存储的，容量是有限的。DeltaMemStore数据flush到磁盘的过程与MemRowSets flush的过程由相同的后台进程。当flush一个DeltaMemStore的时候，老的DeltaMemStore将会被新的存储单元替换，那个已经存在的DeltaMemStore被写入磁盘变成DeltaFile。一个DeltaFile是一个简单的二进制列，里面保存了与DeltaMemStore在内存中一样的数据。
4.6 INSERT path 插入过程
如之前所述，每一个tablet有一个MemRowSet保存最近插入的数据，但是，它不足以简单地直接写所有的插入到当前的MemRowSet中，因为kudu强制使用一个主键唯一约束。换句话说，不像很多nosql的存储方式，kudu区分insert和upsert。
为了强制唯一约束，kudu必须在插入一个新的行前问询所有存在的DiskRowSets。因为每个table可能会有成百上千的DiskRowSets，这个问询过程做的高效是非常重要的，选择需要问询DiskRowSets的个数和在一个DiskRowSet中查询的效率。
为了选择一套DiskRowSets去询问在insert操作的时候，每个DiskRowSet存储一个已存在的键的Bloom过滤器。 因为新的key不会插入到已经存在的DiskRowSet中，这个Bloom过滤器是静态的数据。Bloom过滤器块成为4KB的pages，每一个块对应一个小范围的键，用一个不变的B-tree结构索引那些pages。这些page和一些索引被缓存在服务器的LRU page页缓存中，确保大多数Bloom过滤器访问不需要物理磁盘的搜索。
此外，每一个DiskRowSet，保存最小的和最大的主键，使用键的边界在一个区间树中索引DiskRowSet。
对于insert可以直接保存，对于upsert会查询原有记录中是否存在。所以这也是overwrite和append的坑 。再就是由于唯一键的设计导致每次插入都要查询下这个键是否存在于历史数据中。。。这一点决定了写入速度不可能比hbase快呀。而且特别是对于同一个主键的反复写性能就更加局限了，因为无法扩展。醉了
kudu提出了两个补救方案：1、缩减查找的DiskRowSet范围；2、加速单个DiskRowSet的查找效率
Bloom filter再加上LRU page cache，做到1.；通过index+page cache来做到2 (hbase也同样做了这两个，但是插入时不用look up是绝对优势)
4.7 Read path 读方法
读操作经常是批量的，KUDU每次只读一个列。找到row对应的列值，并读取。
DeltaCompaction，RowSetCompaction这些和hbase非常类似了，就不再细写了。总的来说当前的存储如何支撑sql查询
4.8 Lazy Materialization
Kudu存储的实现对于列数据采用Lazy Materializtion从而提高读取的性能。