《大规模分布式存储系统》第9章 分布式存储引擎【9.3】

javazx

9.3　UpdateServer实现机制
/ i# P) _. \3 p5 U& X* o( {1 tUpdateServer用于存储增量数据，它是一个单机存储系统，由如下几个部分组
成：
●内存存储引擎，在内存中存储修改增量，支持冻结以及转储操作；
  C  ]) V' k+ `# W●任务处理模型，包括网络框架、任务队列、工作线程等，针对小数据包做了专
门的优化；
2 X  d  M* ]/ V( ~4 ^$ O" F●主备同步模块，将更新事务以操作日志的形式同步到备UpdateServer。
1 s7 T+ c& {( E& |6 iUpdateServer是OceanBase性能瓶颈点，核心是高效，实现时对锁（例如，无锁
1 d0 l: E8 r" C4 ~+ L数据结构）、索引结构、内存占用、任务处理模型以及主备同步都需要做专门的优
化。
9.3.1　存储引擎
  d9 v( R5 p& `- T: ]UpdateServer存储引擎如图9-3所示。
7 K8 b8 Z( o9 b* M# U* M8 A图　9-3　UpdateServer存储引擎
5 v# U7 B  B1 Q" b- O" XUpdateServer存储引擎与6.1节中提到的Bigtable存储引擎看起来很相似，不同点
在于：
  K" W4 v: K$ D. n9 @+ n! k●UpdateServer只存储了增量修改数据，基线数据以SSTable的形式存储在
1 q: N$ b) O. w* a$ {6 e! Y  iChunkServer上，而Bigtable存储引擎同时包含某个子表的基线数据和增量数据；
; ]) f9 g6 l9 D) s" e●UpdateServer内部所有表格共用MemTable以及SSTable，而Bigtable中每个子表
的MemTable和SSTable分开存放；
●UpdateServer的SSTable存储在SSD磁盘中，而Bigtable的SSTable存储在 GFS
7 I( a+ `7 p1 ~# Q) \4 T* [5 m) y中。
  i( O$ t! a$ B- @5 qUpdateServer存储引擎包含几个部分：操作日志、MemTable以及SSTable。更新
操作首先记录到操作日志中，接着更新内存中活跃的MemTable（Active
MemTable），活跃的MemTable到达一定大小后将被冻结，称为Frozen MemTable，同
9 ?3 P8 s; k/ G% D& h5 [时创建新的Active MemTable。Frozen MemTable将以SSTable文件的形式转储到SSD磁
& _: m, s) m$ s8 R4 X, P, c盘中。
1.操作日志
+ P! j' H: \8 K6 ?OceanBase中有一个专门的提交线程负责确定多个写事务的顺序（即事务id），
: V4 k$ `9 g) x$ I4 v2 B将这些写事务的操作追加到日志缓冲区，并将日志缓冲区的内容写入日志文件。为
9 U) J& a  f0 {了防止写操作日志污染操作系统的缓存，写操作日志文件采用Direct IO的方式实现：
class ObLogWriter
{
public:
7 r9 c3 {" ?" q. e5 d//write_log函数将操作日志存入日志缓冲区
4 O4 e) _- W" Y6 pint write_log(const LogCommand cmd,const char*log_data,const int64_t
data_len);
//将日志缓冲区中的日志先同步到备机再写入主机磁盘
; O( I0 w& z/ ?; r1 t1 b9 Oint flush_log(LogBuffer＆tlog_buffer,const bool sync_to_slave=true,const bool
/ Y$ E9 ~1 j; N" p$ A4 uis_master=true);
, i: p. q# h+ m+ n% I. Z};
每条日志项由四部分组成：日志头+日志序号+日志类型（LogCommand）+日志
7 w8 a7 }6 V7 {内容，其中，日志头中记录了每条日志的校验和（checksum）。ObLogWriter中的
; ?( c- M* o3 c/ Y( Vwrite_log函数负责将操作日志拷贝到日志缓冲区中，如果日志缓冲区已满，则向调
用者返回缓冲区不足（OB_BUF_NOT_ENOUGH）错误码。接着，调用者会通过
flush_log将缓冲区中已有的日志内容同步到备机并写入主机磁盘。如果主机磁盘的最
% O+ S1 A7 h3 H% ?5 u后一个日志文件超过指定大小（默认为64MB），还会调用switch_log函数切换日志
文件。为了提高写性能，UpdateServer实现了成组提交（Group Commit）技术，即首
先多次调用write_log函数将多个写操作的日志拷贝到相同的日志缓冲区，接着再调
/ ~7 q' d% A( x% t6 q; w0 G用flush_log函数将日志缓冲区中的内容一次性写入到日志文件中。
2.MemTable
: u$ ~% t& @( hMemTable底层是一个高性能内存B树。MemTable封装了B树，对外提供统一的读
2 D5 s4 I) R' q写接口。
B树中的每个叶子节点对应MemTable中的一行数据，key为行主键，value为行操
作链表的指针。每行的操作按照时间顺序构成一个行操作链表。
+ g1 e* t7 {5 Z4 i如图9-4所示，MemTable的内存结构包含两部分：索引结构以及行操作链表，索
5 h' K! m) O2 p8 P引结构为9.1.2节中提到的B树，支持插入、删除、更新、随机读取以及范围查询操
7 ^7 }' {  ^' \' T: o% S作。行操作链表保存的是对某一行各个列（每个行和列确定一个单元，称为Cell）的
修改操作。
. v0 C9 ?) L8 E/ G% w) m图　9-4　MemTable的内存结构
; ]  @' ~( o  D3 I例9-3　对主键为1的商品有3个修改操作，分别是：将商品购买人数修改为
8 L4 ]5 O' H1 u5 `2 k& t  W4 r100，删除该商品，将商品名称修改为“女鞋”，那么，该商品的行操作链中将保存三
0 ]0 m( l/ Z1 h5 ^9 W: ?个Cell，分别为：＜update，购买人数，100＞、＜delete，*＞以及＜update，商品
名，“女鞋”＞。
MemTable中存储的是对该商品的所有修改操作，而不是最终结果。另外，
MemTable删除一行也只是往行操作链表的末尾加入一个逻辑删除标记，即＜delete，
*＞，而不是实际删除索引结构或者行操作链表中的行内容。
MemTable实现时做了很多优化，包括：
●哈希索引：针对主要操作为随机读取的应用，MemTable不仅支持B树索引，还
支持哈希索引，UpdateServer内部会保证两个索引之间的一致性。
●内存优化：行操作链表中每个cell操作都需要存储操作列的编号
& d& i: ]4 D" |; U1 a$ N（column_id）、操作类型（更新操作还是删除操作）、操作值以及指向下一个cell操
( N3 ], c  B* X" I/ Y. j作的指针，如果不做优化，内存膨胀会很大。为了减少内存占用，MemTable实现时
会对整数值进行变长编码，并将多个cell操作编码后序列到同一块缓冲区中，共用一
6 Q% ?5 p9 R3 |- P9 k个指向下一批cell操作缓冲区的指针：
5 a0 Q) d0 Q: `2 Q" j& i% \struct ObCellMeta
{
const static int64_t TP_INT8=1;//int8整数类型
const static int64_t TP_INT16=2;//int16整数类型
const static int64_t TP_INT32=3;//int32整数类型
const static int64_t TP_INT64=4;//int64整数类型
  h4 ^0 _( x) Tconst static int64_t TP_VARCHAR=6;//变长字符串类型
& }& c7 q: V% W: ?, D1 Q& b  n" @const static int64_t TP_DOUBLE=13;//双精度浮点类型
const static int64_t TP_ESCAPE=0x1f;//扩展类型
const static int64_t ES_DEL_ROW=1;//删除行操作
};
& F7 ]0 o4 N" Q8 a8 r$ Z- sclass ObCompactCellWriter
: j) A5 l2 [+ g7 P+ X! }{
public:
) z2 m4 H. V! l' G# r: a( _//写入更新操作，存储成压缩格式
int append(uint64_t column_id,const ObObj＆value);
//写入删除操作，存储成压缩格式
( ^1 ?+ Z: h0 `) q% zint row_delete();
% V% Y( g# x2 r};
MemTable通过ObCompactCellWriter来将cell操作序列化到内存缓冲区中，如果为
更新操作，调用append函数；如果为删除操作，调用row_delete函数。更新操作的存
储格式为：数据类型+值+列ID,TP_INT8/TP_INT16/TP_INT32/TP_INT64分别表示8
* k1 C6 r( w6 K  ?" s+ |位/16位/32位/64位整数类型，TP_VARCHAR表示变长字符串类型，TP_DOUBLE表示
双精度浮点类型。删除操作为扩展操作，其存储格式为：
TP_ESCAPE+ES_DEL_ROW。例9-3中的三个Cell：＜update，购买人数，100＞、＜
delete，*＞以及＜update，商品名，“女鞋”＞在内存缓冲区的存储格式为：
第1～3字节表示第一个Cell，即＜update，购买人数，100＞；第4～5字节表示第
; N$ G( t, T+ `  @* ?二个cell，即＜delete，*＞；第6～8字节表示第三个Cell，即＜update，商品名，“女
鞋”＞。
MemTable的主要对外接口可以归结如下：
) p+ b. k& C4 m' s4 u; Q. O//开启一个事务
//@param[in]trans_type事务类型，可能为读事务或者写事务
5 Y/ j- m( [% b# J  \! E//@param[out]td返回的事务描述符
int start_transaction(const TETransType trans_type,MemTableTransDescriptor＆
td);
//提交或者回滚一个事务
//@param[in]td事务描述符
//@param[in]rollback是否回滚，默认为false
+ L4 f$ a) E  g) U5 V0 W3 L* Tint end_transaction(const MemTableTransDescriptor td,bool rollback=false);
" U+ M# R% ~! O' M) \/ }# _//执行随机读取操作，返回一个迭代器
1 Y# Q3 J0 q3 i//@param[in]td事务描述符
//@param[in]table_id表格编号
//@param[in]row_key待查询的主键
//@param[out]iter返回的迭代器
int get(const MemTableTransDescriptor td,const uint64_t table_id,const
ObRowkey＆row_key,MemTableIterator＆iter);
//执行范围查询操作，返回一个迭代器
//@param[in]td事务描述符
0 f; P, h' A) d- X//@param[in]range查询范围，包括起始行、结束行，开区间或者闭区间
. C! V$ u+ X- N6 w1 e( ]5 W2 f//@param[out]iter返回的迭代器
int scan(const MemTableTransDescriptor td,const ObRange＆
range,MemTableIterator＆iter);
. `& ]4 I2 Q4 l8 y) [6 |- o3 _0 ]# g1 U//开始执行一次修改操作
//@param[in]td事务描述符
int start_mutation(const MemTableTransDescriptor td);
//提交或者回滚一次修改操作
7 @* |4 i( a- \2 \$ B2 s$ W6 t//@param[in]td事务描述符
) X( N0 i$ p$ v1 R//@param[in]rollback是否回滚
8 ^/ [. K( z! V$ Fint end_mutation(const MemTableTransDescriptor td,bool rollback);
+ m: K# G" }5 X7 G6 p; E  G//执行修改操作
9 i, H, L; R8 j: y/ S1 A//@param[in]td事务描述符
//@param[in]mutator修改操作，包含一个或者多个对多个表格的cell操作
6 r9 ]% T1 {1 w" @int set(const MemTableTransDescriptor td,ObUpsMutator＆mutator);
对于读事务，操作步骤如下：
1）调用start_transaction开始一个读事务，获得事务描述符；
8 w7 N) y3 N0 S7 s3 }  R$ |% P$ z2）执行随机读取或者扫描操作，返回一个迭代器；接着可以从迭代器不断迭代
数据；
3）调用end_transaction提交或者回滚一个事务。
class MemTableIterator
{
2 a! ^$ j7 z% ~9 }public:
" k! T" E/ A9 V//迭代器移动到下一个cell
int next_cell();
//获取当前cell的内容
//@param[out]cell_info当前cell的内容，包括表名（table_id），行主键（row_
key)，列编号(column_id)以及列值(column_value)
! x& S- K- q. i9 E/ hint get_cell(ObCellInfo**cell_info);
//获取当前cell的内容
- i. ^/ G; h& \//@param[out]cell_info当前cell的内容
//@param is_row_changed是否迭代到下一行
int get_cell(ObCellInfo**cell_info,bool*is_row_changed);
};
读事务返回一个迭代器MemTableIterator，通过它可以不断地获取下一个读到的
cell。在例9-3中，读取编号为1的商品可以得到一个迭代器，从这个迭代器中可以读
5 z8 V( {7 ~7 j$ Z4 Y. X: k1 w出行操作链中保存的3个Cell，依次为：＜update，购买人数，100＞，＜delete，*
( I9 \. A/ I, G9 j＞，＜update，商品名，“女鞋”＞。
$ k9 q1 q3 E# ~8 D% n写事务总是批量执行，步骤如下：
1）调用start_transaction开始一批写事务，获得事务描述符；
2）调用start_mutation开始一次写操作；
3）执行写操作，将数据写入到MemTable中；
4）调用end_mutation提交或者回滚一次写操作；如果还有写事务，转到步骤
2）；
9 U2 S# ~. ]: r. W/ i! u0 t5 S5）调用end_transaction提交写事务。
* J4 {" Z6 o$ ~' `7 e! q3.SSTable
8 [6 y9 h, u7 Y$ O3 C1 I8 R当活跃的MemTable超过一定大小或者管理员主动发起冻结命令时，活跃的
MemTable将被冻结，生成冻结的MemTable，并同时以SSTable的形式转储到SSD磁盘
中。
; T5 ]. q; t9 b8 O1 F% nSSTable的详细格式请参考9.4节ChunkServer实现机制，与ChunkServer中的
SSTable不同的是，UpdateServer中所有的表格共用一个SSTable，且SSTable为稀疏格
& T& ?9 I8 u1 y式，也就是说，每一行数据的每一列可能存在，也可能不存在修改操作。
另外，OceanBase设计时也尽量避免读取UpdateServer中的SSTable，只要内存足
+ Y9 E9 o) Q4 ]够，冻结的MemTable会保留在内存中，系统会尽快将冻结的数据通过定期合并或者
数据分发的方式转移到ChunkServer中去，以后不再需要访问UpdateServer中的
SSTable数据。
+ C0 u. h' E+ Z" o3 k$ |8 \& r. Q当然，如果内存不够需要丢弃冻结MemTable，大量请求只能读取SSD磁盘，
4 P7 T( f* i) @& Y- XUpdateServer性能将大幅下降。因此，希望能够在丢弃冻结MemTable之前将SSTable
的缓存预热。
UpdateServer的缓存预热机制实现如下：在丢弃冻结MemTable之前的一段时间
/ s+ S( O. Z& N. K" t（比如10分钟），每隔一段时间（比如30秒），将一定比率（比如5%）的请求发给
# r) v7 h6 p! y9 w) J" PSSTable，而不是冻结MemTable。这样，SSTable上的读请求将从5%到10%，再到
15%，依次类推，直到100%，很自然地实现了缓存预热。
, x. M/ w; p6 k- d9.3.2　任务模型
任务模型包括网络框架、任务队列、工作线程，UpdateServer最初的任务模型基
' ?& e% D& ?+ R; O/ j于淘宝网实现的Tbnet框架（已开源，见http://code.taobao.org/p/tb-common-
utils/src/trunk/tbnet/）。Tbnet封装得很好，使用比较方便，每秒收包个数最多可以达
9 ]( d; ]" x) k8 r到接近10万，不过仍然无法完全发挥UpdateServer收发小数据包以及内存服务的特
点。OceanBase后来采用优化过的任务模型Libeasy，小数据包处理能力得到进一步提
& [& @6 g  j# v6 g升。
$ B% t* o; U! u/ |/ D5 e1.Tbnet
( f# u  b/ q' {# N$ A4 D如图9-5所示，Tbnet队列模型本质上是一个生产者—消费者队列模型，有两个线
8 l# X: Z$ @& C* {程：网络读写线程以及超时检查线程，其中，网络读写线程执行事件循环，当服务
器端有可读事件时，调用回调函数读取请求数据包，生成请求任务，并加入到任务
队列中。工作线程从任务队列中获取任务，处理完成后触发可写事件，网络读写线
8 O$ c; S/ A3 l$ O6 P$ h程会将处理结果发送给客户端。超时检查线程用于将超时的请求移除。
6 {; T: i& _* C6 Z  T" A0 V8 Z+ d% e, n6 A图　9-5　Tbnet队列模型
* d: \. K$ S. O; VTbnet模型的问题在于多个工作线程从任务队列获取任务需要加锁互斥，这个过
程将产生大量的上下文切换（context switch），测试发现，当UpdateServer每秒处理
包的数量超过8万个时，UpdateServer每秒的上下文切换次数接近30万次，在测试环
3 [' X* R3 O% h% W1 M境中已经达到极限（测试环境配置：Linux内核2.6.18，CPU为2*Intel Nehalem
E5520，共8核16线程）。
2 Z" ]6 v4 L% C2.Libeasy
5 ~. `/ a! H2 _4 ]5 I为了解决收发小数据包带来的上下文切换问题，OceanBase目前采用Libeasy任务
& Z2 {2 @9 i( V模型。Libeasy采用多个线程收发包，增强了网络收发能力，每个线程收到网络包后
立即处理，减少了上下文切换，如图9-6所示。
, s( e- t% }: g& W% P+ S图　9-6　Libeasy任务模型
UpdateServer有多个网络读写线程，每个线程通过Linux epool监听一个套接字集
4 `6 b; R& N' G; F, z7 ^: q& v合上的网络读写事件，每个套接字只能同时分配给一个线程。当网络读写线程收到
# |( d0 B, }+ x, M- L- n网络包后，立即调用任务处理函数，如果任务处理时间很短，可以很快完成并回复
客户端，不需要加锁，避免了上下文切换。UpdateServer中大部分任务为短任务，比
如随机读取内存表，另外还有少量任务需要等待共享资源上的锁，可以将这些任务
, J" e! U& z! A* F. Q6 L; V) Z加入到长任务队列中，交给专门的长任务处理线程处理。
& |2 H/ t. c* S3 v- {由于每个网络读写线程处理一部分预先分配的套接字，这就可能出现某些套接
& X$ [1 u, R: }" l字上请求特别多而导致负载不均衡的情况。例如，有两个网络读写线程thread1和
thread2，其中thread1处理套接字fd1、fd2，thread2处理套接字fd3、fd4，fd1和fd2上每
  C4 }4 X( w! A/ o秒1000次请求，fd3和fd4上每秒10次请求，两个线程之间的负载很不均衡。为了处理
这种情况，Libeasy内部会自动在网络读写线程之间执行负载均衡操作，将套接字从
负载较高的线程迁移到负载较低的线程。
5 y" V% C( d8 b/ U4 Z) Q8 j9.3.3　主备同步
8.4.1节已经介绍了UpdateServer的一致性选择。OceanBase选择了强一致性，主
UpdateServer往备UpdateServer同步操作日志，如果同步成功，主UpdateServer操作本
地后返回客户端更新成功，否则，主UpdateServer会把备UpdateServer从同步列表中
剔除。另外，剔除备UpdateServer之前需要通知RootServer，从而防止RootServer将不
一致的备UpdateServer选为主UpdateServer。
如图9-7所示，主UpdateServer往备机推送操作日志，备UpdateServer的接收线程
7 O- w  l1 _2 E7 l/ o接收日志，并写入到一块全局日志缓冲区中。备UpdateServer只要接收到日志就可以
回复主UpdateServer同步成功，主UpdateServer接着更新本地内存并将日志刷到磁盘
9 ^6 R0 P) z9 K) r1 R1 h, r文件中，最后回复客户端写入操作成功。这种方式实现了强一致性，如果主
, _2 Z. R/ L* K+ p, [; @! G+ @UpdateServer出现故障，备UpdateServer包含所有的修改操作，因而能够完全无缝地
' X1 T: Q( Q6 x  j8 M0 I切换为主UpdateServer继续提供服务。另外，主备同步过程中要求主机刷磁盘文件，
6 U% a% ?, q  J+ @7 B备机只需要写内存缓冲区，强同步带来的额外延时也几乎可以忽略。
图　9-7　UpdateServer主备同步原理
, f) E( f. I) y, n* s0 F% c正常情况下，备UpdateServer的日志回放线程会从全局日志缓冲区中读取操作日
志，在内存中回放并同时将操作日志刷到备机的日志文件中。如果发生异常，比如
$ {1 R! _2 x- M& b备UpdateServer刚启动或者主备之间网络刚恢复，全局日志缓冲区中没有日志或者日
7 h1 Q" z: v: [! b) u1 W4 T志不连续，此时，备UpdateServer需要主动请求主UpdateServer拉取操作日志。主
UpdateServer首先查找日志缓冲区，如果缓冲区中没有数据，还需要读取磁盘日志文
( f3 M5 E2 F' E* x# f3 G/ ^- i9 a件，并将操作日志回复备UpdateServer。代码如下：
8 S/ F! v# ?" hclass ObReplayLogSrc
{
5 ?; Y; L  Q" ]! _  \public:
# M+ |4 D+ z2 l8 P& A//读取一批待回放的操作日志
( i% M  l: T+ z, `3 a//@param[in]start_cursor日志起始点
9 V) w6 C' g  a, a5 ]//@param[out]end_id读取到的最大日志号加1，即下一次读取的起始日志号
//@param[in]buf日志缓冲区
//@param[in]len日志缓冲区长度
//@param[out]read_count读取到的有效字节数
int get_log(const ObLogCursor＆start_cursor,int64_t＆end_id,char*buf,const
int64_t len,int64_t＆read_count);
};
class ObUpsLogMgr
  F% F! z- }: I; o{
public:
enum WAIT_SYNC_TYPE
{
WAIT_NONE=0，
  e  M6 P6 Q) C7 IWAIT_COMMIT=1，
WAIT_FLUSH=2，
* _7 i. N: U- b};
public:
//备UpdateServer接收主UpdateServer发送的操作日志
3 x/ O4 A5 e6 Z% m; H9 B" k3 Rint slave_receive_log(const char*buf,int64_t len,const int64_t
wait_sync_time_us,const WAIT_SYNC_TYPE wait_event_type);
2 B2 I) E9 _% O3 Y  J//备UpdateServer获取并回放操作日志
int replay_log();
/ c* s. i8 C9 B, u- ^};
备UpdateServer接收到主UpdateServer发送的操作日志后，调用ObUpsLogMgr类的
$ h# ]- p  k4 y- }2 g- |$ N6 Oslave_receive_log将操作日志保存到日志缓冲区中。备UpdateServer可以配置成不等待
1 d" m6 y# n  o; O% u: X（WAIT_NONE）、等待提交到MemTable（WAIT_COMMIT）或者等待提交到
MemTable且写入磁盘（WAIT_FLUSH）。另外，备UpdateServer有专门的日志回放线
程不断地调用ObUpsLogMgr中的replay_log函数获取并回放操作日志。
' ~  \, o# L' a- j/ v备UpdateServer执行replay_log函数时，首先调用ObReplayLogSrc的get_log函数读
取一批待回放的操作日志，接着，将操作日志应用到MemTable中并写入日志文件持
, y$ o9 E# v0 z" d# a' g久化。Get_log函数执行时首先查看本机的日志缓冲区，如果缓冲区中不存在日志起
, C; ]" o6 k4 |5 a9 x2 i始点（start_cursor）开始的操作日志，那么，生成一个异步任务，读取主
1 L! Z; v7 O; S4 |; d4 h. ^UpdateServer。一般情况下，slave_receive_log接收的日志刚加入日志缓冲区就被
get_log读走了，不需要读取主UpdateServer。


& \8 X6 d2 B' L0 ?) R$ t! I