作者归档:yubai

[LockFree之美] 共享变量的并发读写

共享对象的并发读写

在高性能并发服务器中,对于共享对象的读写是最常见的操作之一,比如全局配置类对象的并发读取和更新,以及更复杂的如copy on write btree、堆栈等的并发读写,最基本的操作都可以简化理解为通过全局共享的指针,并发读取和更新指针所指向对象的操作。
最简单的模型如下所示,一个包含了多个字段的结构体:

struct GConf
{
  int64_t a;
  int64_t b;
  int64_t c;
};

可以通过一个全局指针struct gConf *g_conf进行访问。有多个线程会同时读取或更新这个对象,要求任何时刻读取到的内容一定是“一致的”,即读取到的a/b/c的值一定是相同一次更新的值,而不能出现读到的a是某一次更新的值,而b或c是另外一次更新的值。
我们假设研发平台为x86_64,指令级的原子操作最多是64位(实际intel提供了128bit的原子操作,但是本文后续的讨论的方法只用到64bit的原子操作),因为gConf包含三个8字节整数,无法使用原子操作指令对a/b/c一次性赋值,因此必须通过程序算法来保证并发情况下读取到的内容满足“一致性”。
下面开始从易到难讨论5种处理“共享对象并发读写”的方法。

1. 读写锁
最简单朴素的想法是为这个结构配备一个读写锁,读取操作在读锁保护下执行,更新操作在写锁保护下执行。这个方法在对象读取和更新操作都比较简单,且并发程度不高的情况下是一个不错的选择。但是由于读锁与写锁互相阻塞,在读取或更新操作比较费时的情况下,会出现更新或读取线程被阻塞的风险,在高并发的场景下,这种阻塞不可接受。一个实例是数据库系统的全局schema管理器,每次事务都需要读取schema的内容,而DDL会引起schema更新,它的内容比较复杂,更新操作比较费时,会阻塞住处理事务的线程。

2. 引用计数的问题
为了解决读写操作相互阻塞的问题,使用类似Copy on write的方式,每次更新时都构造新的对象,在更新过程中,读取操作还是读取旧的对象,更新操作完成后,原子的替换掉指针使其指向新的对象。而被替换掉的对象不能立即释放,而是要确保这个对象不再被继续使用的情况下,才能将其释放掉。因此这里使用引用计数机制,在读取前将引用计数加1,读取完毕后将引用计数减1,当引用计数减到0的时候,表示没人在使用这个对象,可以将其释放掉。
引用计数在没有并发保护情况下面临的问题是,取得全局指针g_conf和通过这个指针操作对象的引用计数这两个操作并非原子的。可能存在的情况是,一个线程T1取得g_conf的值保存到寄存器后,就被切换出去,另外一个线程T2将g_conf替换后,判断旧的对象引用计数为0,则将其释放。当T1被切换回来继续执行时,它在寄存器中保存的g_conf指向的对象已经被释放,访问对象引用计数的这一次操作就已经存在非法内存访问的风险。
下面两节讨论两种解决并发引用计数的方案。

3. 带锁的引用计数
解决第2点提出的原子性问题,一个最直接的方式是使用锁,将读写g_conf和修改引用计数两个操作放在一个独立全局锁(g_lock)的临界区执行,代码示例如下:

读取并将引用计数加1:

fetch()
{
  g_lock.rdlock();
  g_conf->inc_ref();
  ret = g_conf;
  g_lock.unlock();
}

将引用计数减1:

revert(ptr)
{
  g_lock.rdlock();
  if(0 == ptr->dec_ref())
  {
    free(ptr);
  }
  g_lock.unlock();
}

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  g_lock.wrlock()
  if (0 == g_conf->dec_ref())
  {
    free(g_conf);
  }
  new_conf->inc_ref();
  g_conf = new_conf;
  g_lock.unlock();
}

在实际场景中,通常读取g_conf的操作更多且并发量大,而替换g_conf的操作不会经常发生,因此读取g_conf时加共享锁,替换g_conf时加互斥锁。
使用锁保护引用计数的方式在高并发的情况下存在一些局限:一方面可能存在读者或写者被饿死的情况;另一方面多个写者无法并发,应用在copy on write btree等数据结构中时,多个写者相互阻塞的问题会影响到整个数据结构的并发性能。

4. 无锁的引用计数
因此,一个更进一步的设计是使用无锁的引用计数,即无论读取g_conf还是替换g_conf都不在锁中进行,如下图所示:share_obj_seq_ref

RefNode的结构包含了指向GConf对象的指针data_ptr,以及引用计数ref_cnt,自增序列号seq_id,ref_cnt和seq_id长度都为4字节且地址连续,可以经由一次8字节的原子操作进行原子性的修改和读取。每次构造新的GConf对象的要同时分配新的RefNode来保存GConf对象的地址。
RefNode对象的分配和释放由专用的分配器进行分配和重用,一旦分配就不会释放回系统。引用计数的加1和减1,操作的是RefNode对象的ref_cnt字段,当引用计数减为0时,将data_ptr指向的对象释放,并将seq_id加1,然后将RefNode对象释放给内存分配器。已释放回分配器的RefNode对象仍然可以被安全的访问到。
替代全局GConf指针,我们增加了一个被称为GNode结构体的全局对象称为g_node,它包含了指向RefNode对象的指针称为node_idx,和这个RefNode中seq_id字段的值node_seq。node_idx和seq_id长度都为4字节且地址连续,可以经由一次8字节的原子操作进行原子性的读取和替换。
读取和替换操作的代码示例如下:
将引用计数加1并返回:

fetch()
{
  GNode tmp_g_node = atomic_load(g_node);
  while (true)
  {
    if (tmp_g_node.node_idx->atomic_check_seq_and_inc_ref(tmp_g_node.node_seq))
    {
      ret = tmp_g_node.node_idx;
      break;
    }
    else
    {
      tmp_g_node = atomic_load(g_node);
    }
  }
}

将引用计数减1:

revert(node_idx)
{
  if (node_idx->atomic_dec_ref_and_inc_seq())
  {
    free(node_idx->data_ptr);
    free_list.free(node_idx);
  }
}

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  RefNode *new_node = free_list.alloc();
  new_node->ref_cnt = 1;
  new_node->data_ptr = new_conf;

  GNode new_g_node;
  new_g_node.node_seq = new_node->seq_id;
  new_g_node.node_idx = new_node;

  GNode old_g_node = atomic_store_and_fetch_old(&g_node, new_g_node);
  if (old_g_node.node_idx->atomic_dec_ref_and_inc_seq())
  {
    free(old_g_node.node_idx->data_ptr);
    free_list.free(old_g_node.node_idx);
  }
}

其中几个原子操作的作用:
1. RefNode::atomic_check_seq_and_inc_ref原子性的判断如果seq_id等于传入参数就将ref_cnt加1,并返回true,否则返回false。
2. atomic_store_and_fetch_old原子性的将第二个参数赋值给第一个参数,并返回第一个参数的旧值。
3. RefNode::atomic_dec_ref_and_inc_seq原子性的将ref_cnt减1,并判断ref_cnt如果已减为0,则将seq_id加1并返回true,否则返回false。
工程实现上,为了达到node_idx长度只能有4字节的要求,RefNode分配器设计为定长数组,node_idx为数组下标,使用定长无锁队列作为分配器来维护空闲的node指针。一般来说一个线程只会增加一次引用计数,因此对于维护GConf这样全局只有一个的对象,定长RefNode数组的长度初始化为与线程个数相等就够用了。

5. HazardPointer
引用计数基本可以解决共享对象并发读写的问题,但它仍然存在一些不足:第一,每次读取都需要使用原子操作修改全局引用计数,高并发情况下的对同一个变量的原子操作可能成为性能瓶颈;第二,管理RefNode对象的无锁分配器有额外的管理和维护成本,增加的实现复杂度;第三,针对每个共享对象都需要维护N个(N为线程个数)RefNode,如果共享对象数量较多(比如Btree节点),为节省空间,还需要额外的机制来避免大量使用RefNode。
因此再介绍一种被称为HazardPointer的思路,它由Maged M. Michael在论文“Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”中提出,基本思路是将可能要被访问到的共享对象指针(成为hazard pointer)先保存到线程局部,然后再访问,访问完成后从线程局部移除。而要释放一个共享对象时,则要先遍历查询所有线程的局部信息,如果尚有线程局部保存有这个共享对象的指针,说明这个线程有可能将要访问这个对象,因此不能释放,只有所有线程的局部信息中都没有保存这个共享对象的指针情况下,才能将其释放。
读取和替换操作的代码示例如下:

g_hp_array[N]; //保存每个线程局部信息的数组,N为线程个数

读取操作:

while(true)
{
  ret = g_conf;
  g_hp_array[thread_id] = ret;
  if (g_conf == ref)
  {
    break;
  }
  else
  {
    g_hp_array[thread_id] = NULL;
  }
}
// 读取逻辑代码…
g_hp_array[thread_id] = NULL;

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  retired_ptr = atomic_store_and_fetch_old(&g_conf, new_conf);
  found = false;
  for (i = 0; i < g_hp_array.length(); i++)
  {
    if (retired_ptr == g_hp_array[i])
    {
      found = true;
      break;
    }
  }
  if (!found)
  {
    free(retired_ptr);
  }
}

HazardPointer的设计解决了引用计数原子操作的性能瓶颈,避免了实现额外RefNode无锁分配器的复杂度。但是同时引入一个新的问题:由于回收内存的操作需要遍历查询全局数组g_hp_array,代价比较大,通常工程上的做法是将待回收的指针暂存在线程局部,等数量超过一个配置门限时,才进行批量回收。使得回收内存产生延迟,并且回收操作本身由于需要遍历数组,也会消耗较多的时间。
关于并发场景的问题,由于回收操作便利g_hp_array并不能保证原子的遍历,而HazardPointer的设计要求对象已经被放入g_hp_array后是能够安全访问的,因此可能存在如下时序:
1. 读取线程拿到g_conf指针存入局部变量ret
2. 更新线程将g_conf指针替换,扫描g_hp_array没有找到g_conf,释放g_conf内存
3. 读取线程将刚刚拿到的ret放入g_hp_array,然后开始使用ret,而此时ret指向的内存已经释放
为了处理这个问题,如上述伪代码所示,读取线程需要增加double check逻辑,判断如果从拿到g_conf到放入g_hp_array之间,可能有回收逻辑遍历过g_hp_array,则要重试。
因为替换g_conf意味着要将旧的g_conf释放,而释放意味着要先会遍历g_hp_array,因此读取线程只需要在将g_conf放入g_hp_array后,判断g_conf是否变化,如果变化了,则说明g_conf可能正好在从拿到g_conf到放入g_hp_array之间被释放了,因此需要重试。

6. HazardVersion

HazardPointer的实现简单,但是与引用计数法有着相似的不足:需要为每个共享变量维护O(N)个(N为线程个数)槽位,使用者需要仔细分析算法以尽量减少同时存在的hazard pointer 或者引入其他机制封装多个共享变量称为一个hazard pointer。这样就给使用者带来了比较大的难度,HazardPointer机制也与具体数据结构的实现比较紧的耦合在一起。

因此在HazardPointer基础上发展出了被称为HazardVersion技术,它提供类似lock一样的acquire/release接口,支持无限制个数共享对象的管理。

与HazardPointer的实现不同:首先全局要维护一个int64_t类型的GlobalVersion;要访问共享对象前,先将当时的GlobalVersion保存到线程局部,称为hazard version;而每次要释放共享对象的时候先将当前GlobalVersion保存在共享对象,然后将GlobalVersion原子的加1,然后遍历所有线程的局部信息,找到最小的version称为reclaim version,判断如果待释放的对象中保存的version小于reclaim version则可以释放。

读取和替换操作的代码示例如下:

g_version; //全局GlobalVersion
g_hv_array[N]; //保存每个线程局部信息的数组,N为线程个数

读取操作:

g_hv_array[thread_id] = g_version;
ret = g_conf;
// 读取逻辑代码…
g_hv_array[thread_id] = INT64_MAX;

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  retired_ptr = atomic_store_and_fetch_old(&g_conf, new_conf);
  retired_ptr->set_version(atomic_fetch_and_add(&g_version, 1));
  reclaim_version = INT64_MAX;
  for (i = 0; i < g_hv_array.length(); i++)
  {
    if (reclaim_version > g_hv_array[i])
    {
      reclaim_version = g_hv_array[i];
    }
  }
  if (reclaim_version > retired_ptr->get_version())
  {
    free(retired_ptr);
  }
}

可以看到,读取操作先保存了GlobalVersion到线程局部,然后去读取g_conf指针,虽然可能同时发生的回收操作遍历g_hv_array并不保证原子性,但是即使一个更小的hazard version被放入g_hv_array而错过了遍历,也不会有风险。

因为回收操作是先更新g_conf指针后遍历g_hv_array,而读取操作是先更新g_hv_array后读取g_conf指针,所以最坏情况下读取操作与回收操作同时发生,且读取操作放入g_hv_array的hazard version被回收操作遍历时错过,那么读取操作读到的g_conf一定是被回收操作更新之后的,本次不会被回收,可以安全的访问。

HazardVersion相对HazardPointer,在用法上更加简单,无需针对具体的数据结构进行分析,局限是需要在被管理的对象中保存version。其次,与HazardPointer一样,由于遍历g_hv_array比较费时,因此也需要引入类似的延迟回收机制。需要注意的是,它的缺点也比较明显,一旦出现一个线程长时间不释放HazardVersin时,会阻塞住后面更大Version对象的释放。

7. 总结
本文讨论了“读写锁”、“带锁的引用计数”、“无锁的引用计数”、“HazardPointer”、“HazardVersion”五种方法来处理共享对象的并发读写问题,在实际工程领域,“带锁的引用计数”比较常见,在特定场景下优化读写锁可以得到不错的性能,并且很易于理解和实现;“无锁的引用计数”实现复杂但并发读写性能卓越,在已开源的OceanBase版本中也有实践;“HazardPointer”实现简单,但是理解和使用都较复杂;“HazardVersion”是一种基于“HazardPointer”的创新思路,有一定的局限性,凭借简单易用的接口,可以在很多场景替代“HazardPointer”。

[linux奇技淫巧] 用户态线程coroutine

Coroutine即教科书上提到的“协程”,可以认为是用户态的线程,在它看来thread就是CPU。

在一个thread内可以启动任意多个协程,它们放佛是在同一个“CPU”上运行的多个线程,而与线程的最大不同是,它并非”抢占式“的,因此它让出“CPU”的唯一方式是自己主动放弃执行,保存现场后跳转到其他协程执行。

协程的切换开销远远小于内核对于线程的切换开销,因此对于IO密集型的程序,使用协程的优势在于用户可以像写同步IO一样,无需关心IO异步接口的细节。封装等待IO返回的逻辑,跳转到coroutine库进行调度。减小使用多个线程做同步IO带来的内核大量线程切换的开销。

linux下的swapcontext系列函数提供了协程上下文创建和切换的封装,使用这一组函数可以自己实现简单的coroutine库,使用一个协程作为调度器,其他协程让出“CPU”时都先跳转到调度器,由调度器决定跳转到哪个等待调度的协程继续工作,以此实现包括启动、切换、退出协程的逻辑。

swapcontext的问题是内部调用了内核的锁,造成性能不佳,这里可以使用_longjmp替代swapcontext来优化性能,但是由于_longjmp并未提供创建协程上下文的封装,自己手动构建的过程极其反人类,一个取巧的办法是使用makecontext/swapcontext来构建协程上下文并执行第一次跳转,后续的跳转则使用_longjmp。

一个简单的coroutine例子可以参考我的github。

https://github.com/kayaklee/uthread

[C/C++奇技淫巧] 变长宏参数的个数

备忘一个宏的奇技淫巧,类似打印日志,RPC封装等无法使用C++0x变长模板参数的情况下,是个不错的选择

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define ARG_COUNT_P1_(\
  _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, N, ...) \
  N

#define ARG_COUNT_P2_ \
  9, 8, 7, 6, 5, 4, 3, 2, 1, 0

#define ARG_COUNT_(...) \
  ARG_COUNT_P1_(__VA_ARGS__)

#define ARG_COUNT(...) \
  ARG_COUNT_(_, ##__VA_ARGS__, ARG_COUNT_P2_)

#define M_CAT(a, b) M_CAT_(a, b)
#define M_CAT_(a, b) a##b

#define VA_F(...) \
  M_CAT(func, ARG_COUNT(__VA_ARGS__)) (__VA_ARGS__)

#define func(a)   fprintf(stdout, "arg:%ld\t", a);
#define func0()   fprintf(stdout, "func end\n\n");
#define func1(a)  func(a); func0();
#define func2(a, ...) func(a); func1(__VA_ARGS__);
#define func3(a, ...) func(a); func2(__VA_ARGS__);
#define func4(a, ...) func(a); func3(__VA_ARGS__);
#define func5(a, ...) func(a); func4(__VA_ARGS__);
#define func6(a, ...) func(a); func5(__VA_ARGS__);
#define func7(a, ...) func(a); func6(__VA_ARGS__);
#define func8(a, ...) func(a); func7(__VA_ARGS__);
#define func9(a, ...) func(a); func8(__VA_ARGS__);
#define func10(a, ...) func(a); func9(__VA_ARGS__);

int main(int argc, char **argv)
{
  fprintf(stdout, "arg=%ld\n", ARG_COUNT());
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5,6));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5,6,7));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5,6,7,8));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5,6,7,8,9));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5,6,7,8,9,10));
  fprintf(stdout, "arg=%ld\n", ARG_COUNT(1,2,3,4,5,6,7,8,9,10,11));

  VA_F();
  VA_F(1);
  VA_F(1,2);
  VA_F(1,2,3);
  VA_F(1,2,3,4);
  VA_F(1,2,3,4,5);
  VA_F(1,2,3,4,5,6);
  VA_F(1,2,3,4,5,6,7);
  VA_F(1,2,3,4,5,6,7,8);
  VA_F(1,2,3,4,5,6,7,8,9);
  VA_F(1,2,3,4,5,6,7,8,9,10);
  //VA_F(1,2,3,4,5,6,7,8,9,10,11);
}

 

Oceanbase内存事务引擎

摘要 OceanBase是一个分布式可扩展的关系数据库,采用基线静态数据与动态增量数据分离存储的架构设计.其内存事务引擎提供了动态数据的存储、写入和查询服务,用户写入的数据被存储在内存中称为Memtable的数据结构中.Memtable及其周边的事务管理结构共同组成了内存数据库引擎,来实现事务的ACID特性.在事务引擎中,通过多版本的并发控制技术实现读写相互不阻塞,实现只读事务满足“快照隔离”级别;通过经典的行锁方式实现多个写之间的并发控制,实现最高满足“已提交读”的事务隔离级别.

关键词关系数据库   分布式系统   事务   互联网

Abstract: OceanBase is a distributed scalable relational database.Its storage architecture is designed by separating baseline static data and increment dynamic data, whose memory transaction engine, namely Memtable, provide dynamic data storage, write, and query, clients wrote data to the in-memory data structure. Memtable and some transaction management structures together form the in-memory database engine, which can achieve the transaction ACID properties. By based multi-version concurrency control techniques to prevent reading and writing from blocking each other to achieve read only transactions to meet the“snapshot isolation”level; Provide multi-write concurrency control by using classic row lock technology to meet the“read committed”transaction isolation level.

Key wordsrelational database system   distributed system   transaction   internet

http://xblk.ecnu.edu.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=25015

Lease与最长宕机时间分析

先看简单的情况,单点rootserver负责updateserver选主,与ups保持lease,设lease时间为L,可以知道ups最长不可服务的情况是,rs刚刚授予ups lease后,ups就意外宕机,rs要等lease超时后,才能重新选主,所以rs不宕机的情况下ups的最长不可服务时间就是L

 

L大小的选择也不是越小越好,因为过小的L会使得rs宕机重启影响到upslease,我们期望rs宕机重启的过程不影响到upslease。这里假设upsrs renew lease的间隔是TT<L,即每隔T秒,ups就来renew lease,把lease时间顺延),那么只要rs的宕机重启时间(称为D)小于L-T,就可以保证不会中断upslease

 

而最差情况是,rs刚刚授予ups lease后,ups就宕机;然后待ups lease差一点点要过期时rs宕机,所以在这种最差情况下ups最长不可服务时间是L+D

 

因此按如下方法进行推算:

设第i层系统的lease时间为L(i),最长不可服务时间为D(i)Lease renew间隔为T(i)

D(i) = L(i) + D(i-1)

D(i-1) <= L(i) – T(i) 按照最小lease算,则D(i-1) = L(i) – T(i)

推导:

L(i) = D(i-1) + T(i)

= L(i-1) + D(i-2) + T(i)

= L(i-1) + L(i-1) – T(i-1) + T(i)

= 2*L(i-1) – T(i-1) + T(i)

T(i-1)T(i) 近似相等,因此可以得出L(i) = 2*L(i-1),工程实现上包含必要的误差和通信代价后,通常使用L(i) = 2.5*L(i-1),即下一级lease是上一级lease时间的2.5

 

所以lease层级越多,下层系统lease的时间越长,宕机停服务的时间越长,比如如果rs依赖zookeeper选主,rslease10s,那么依赖rs选主的ups lease时间就要是25s,而ups的最长不可服务时间长达(35s+zookeeper不可以服务时间)

 

使用election的情况稍有不同,rs内置election进行选主,ups依赖rs进行选主,rs的最长不可用时间为2*Tcycle,为了保证D(i-1) <= L(i) – T(i)upslease时间L要大于2*Tcycle+T,由此可以推算出,最差情况下,ups的不可服务时间为4*Tcycle+T

 

所以我们的设计中要尽量避免多机lease的管理,尽量扁平化系统设计。

 

Oracle number类型分析

Oracle number类型分析

Oracle使用number类型表示定点数,使用两个参数来确定number的位数和小数部分精度,如number(p, s),其中p表示precision,s表示scale。

scale是小数位数的限制:s大于零时,表示精度限制在小数点后s位,超过s位后面的小数将被四舍五入;s小于等于0时,小数部分被舍去,且小数点前-s位,将被四舍五入,即小于10的-s次方的数将被四舍五入为零。

precision与scale的差值是整数位数的限制:p-s大于零时,表示整数部分的位数不能超过p-s,否则将报错;p-s小于等于零时,表示整数部分必须为0,小数点后-(p-s)位也必须为0,否则将报错。

举例说明如下:

number(3, 2) 1.2345 ==> 1.23 小数部分四舍五入保留2位

12.3 ==> Error 整数部分大于1位

number(3, -2) 345.6 ==> 300 小数点前2位被四舍五入

45.6 ==> 0 小数点前2位被四舍五入

123456.7 ==> Error 整数部分大于5位

number(2, 3) 1.2 ==> Error 整数部分不为0

0.1 ==> Error 小数部分前1位不为0

0.02345 ==> 0.023 小数部分超过3位后面的被四舍五入

Number的内存格式,以最优的比较计算速度为设计原则,对于不同精度不同大小的数值使用变长方式存储,做到能够使用memcmp直接进行数值大小的比较。因此设计number存储格式如下图所示:

其中:

1. length表示了其后面byte数组的长度;

2. 符号位(sign bit)和指数位(exponent)一起存储在byte数组的第一个元素:

(1) 其中sign bit为1表示非负数,sign bit为0表示负数,这样保证了在比较第一个byte时就能够比较出定点数值负数小于非负数;

(2) 指数位使用类似的编码方式(后面详细说明),保证了在符号位相同的情况下,指数位的大小直接反映了定点数值的大小;

3. 假设底数为B,后面每个byte存储一个大小为[0, B-1]的整数,做到在符号位和指数位都想同的情况下,使用memcmp依次比较每个digit即可反映数值的比较结果

考虑内存格式利用率和容易理解的折中,我们设底数B为100,每个digit保存0~99,使每个digit乘以100的n次方后,相加后即是最终的定点数值,举例如下(当然底数也可以是128或其他值,2整数次方的底数可能在计算时有更快的位运算方式,但是其内存格式不直观不易理解,且对小数的表示很难做到直接的memcmp比较,因此没有采用):

31415.009=3*100^2 + 14*100^1 + 15*100^0 + 0*100^-1 + 9*100^-2

 

指数位的设计,在第一个byte中,最高位用于存储sign bit,可以使用剩下的7个bit存储指数位,对于正数来说,使用0x80~0xFF总共可以表示128个指数值,因此使用第二个bit保存指数位的符号,非负指数符号位为1,负指数符号位为0,使得非负指数天然大于负指数。即[0x80, 0xbf]表示负指数,[0xc0, 0xff]表示非负指数,选择0xc0作为正负指数的分界点,减去0xc0,即为指数值。

但是考虑到oracle中定点数正数的表示范围是1 x 10-130 to 9.99…9 x 10125,要表示1e-130,指数值最小要到-65(编码为128),因此调整分界点为0xc1(128-x=-65,x=193),保证小数的表示范围满足需求。

如123.0,将被存储为(示例仅仅为演示指数位的设计,非最终设计):

len=3, 0xc2, 1, 23

还原定点数值的算法为:

123.0 = 1*100^(0xc2-0xc1) + 23*100^(0xc2-0xc1-1)

再比如0.123,将被存储为(示例仅仅为演示指数位的设计,非最终设计):

len=3, 0xc0, 12, 30

还原定点数值的算法为:

0.123 = 12*100^(0xc0-0xc1) + 30*100^(0xc0-0xc1-1)

而对于负数来说,0x00~0x7f总共可以表示128个指数值,与正数不同的是:指数值越大,实际定点数值约小。因此使用第二个bit保存指数位的符号,但是非负指数符号位为0,负指数符号位为1。即[0x00, 0x3f]表示非负指数,[0x40, 0x7f]表示负指数,选择0x40作为正负指数的分界点,被0x40减,即为指数值。

但是考虑到oracle中定点数负数的表示范围是-1 x 10-130 to -9.99…9 x 10125,要表示-1e-130,指数值最小要到-65(编码为127),因此调整分界点为0x3e(x-127=-65,x=62),保证小数的表示范围满足需求。

如-123.0,将被存储为(示例仅仅为演示指数位的设计,非最终设计):

len=3, 0x3d, 1, 23

还原定点数值的算法为:

-123.0 = -1*100^(0x3e-0x3d) – 23*100^(0x3e-0x3d-1)

再比如-0.123,将被存储为(示例仅仅为演示指数位的设计,非最终设计):

len=3, 0x3f, 12, 30

还原定点数值的算法为:

-0.123 = -12*100^(0x3e-0x3f) – 30*100^(0x3e-0x3f-1)

 

digit的设计,从第二个byte开始依次存储,主要考虑 符号位和指数位相同时如何实现memcmp比较。因为在符号位不同的情况下,可以自然的比较出非负数大于负数;而在符号位相同的情况下,指数位也可以直接反映出定点数的大小。所以对于digit的设计,只需要考虑符号位和指数位都相同的情况,因此只需要分别考虑定点数值为正数,负数和0这三种情况。正数的情况比较简单,digit保存[0, 99],直接按byte比较即可反映定点数值大小;负数的情况比较特殊,因为-1>-99,所以1在byte上编码后要大于99,我们使用100减去digit作为编码后的值,如1被编码为99,99被编码为1。举例如下:

-10023.0,将被存储为(示例仅仅为演示指数位的设计,非最终设计):

len=4, 0x3c, 99, 100, 77

还原定点数值的算法为:

-10023.0 = -(100-99)*100^(0x3e-0x3c)

                  – (100-100)*100^(0x3e-0x3c-1)

                  – (100-77)*100^(0x3e-0x3c-2)

但是这个编码存在一个问题,考虑-10023.0和-10023.1,在上面描述的存储格式中,使用memcmp比较,-10023.0将小于-10023.1,原因是与正数不同,在定点数值为负的情况下,后面越多的小数位,将使得定点数值越小。因此在定点数值为负的情况下,需要增加一个byte结束符,保证这个结束符大于有效的digit,而digit有效值范围是0~100,因此使用101作为定点数值为负情况下的结束符。

-10023.0,存储格式如下(示例仅仅为演示指数位的设计,非最终设计):

len=5, 0x3c, 99, 100, 77, 101

而oracle还考虑到了’\0’存储可能造成字符串结束符歧义的问题,因此digit存储的数字范围整体+1,即对正数用1~100表示[0, 99],对负数用2~101表示[99, 0],避开了存储’\0’。同时结束符也要修正为102。

10023.0,最终存储格式如下:

len=4, 0xc3, 2, 1, 24

-10023.0,最终存储格式如下:

len=5, 0x3c, 101, 102, 78, 102

 

0值digit的舍去,根据上面多次示例的定点数值还原算法,可以看到digit为0的情况下对计算结果没有影响,可以考虑舍去以节省空间,但是位于digit数组中间的0不能舍去,因为还原算法需要遍历数组并依次为每个digit计算对应的指数值。因此对于定点数值非负的情况将digit数组末尾的0舍去,而对于定点数值为负的情况则将结束符101前的100舍去,距离如下:

10000,最终的存储格式如下:

len=2, 0xc3, 1

-10000,最终的存储格式如下:

len=3, 0x3c, 99, 101

 

定点数值为0的特殊处理,使用非负数中最小的:len=1, 0x80作为0的编码。

 

定点数的表示范围,oracle中对定点数的范围限制:

  • Positive numbers in the range 1 x 10-130 to 9.99…9 x 10125 with up to 38 significant digits

  • Negative numbers from -1 x 10-130 to 9.99…99 x 10125 with up to 38 significant digits

sign bit,exponent和digit组成的byte数组。其中一个byte用来保存符号位和整数,在处理负数时额外用1个byte保存结束符。因此对于正数最多使用20byte来保存,对于负数最多使用21byte来保存。因此byte数组中最多有19个byte可以用于保存定点数的有效位,即精度(precison)范围为[1, 38]。

而oracle规定的刻度(scale)范围[-84, 127],限制了定点数值上限为9.99…9 x 10121 与不设定scale情况下number类型的上限9.99…9 x 10125 相差4个数量级,但是暂时不清楚oracle这个限制的原因。

Oceanbase代码有关语言和编译器的奇技淫巧(二)

Oceanbase代码有关语言和编译器的奇技淫巧(二)

–to_cstring的Sfinae魔术

我安装了代码高亮的插件,看上去会爽一些了。

这次的奇技淫巧是关于打印日志的,先提一个需求:有一个int类型的ipv4地址,想按照点分字符串的形式打印到日志中。很常见的需求,在收到网络请求或者处理分布式调度的时候可能需要把网络地址打印出来,也许你和我一样第一次会先写出下面这样的代码:

TBSYS_LOG(INFO "addr=%d.%d.%d.%d",
(ip & 0xFF),
(ip >> 8) & 0xFF,
(ip >> 16) & 0xFF,
(ip >> 24) & 0xFF);

每当我写代码需要打印某个ipv4地址的时候,就会去找这段代码,把它复制粘贴。当这种事情做多了以后,我开始变得不耐烦了,是时候需要封转一个函数来帮我搞定这件事了,就起名叫ip2str好了,不过当我开始写这个函数的时候,又遇到一个新的问题,任何stl的容器在oceanbase项目中都是不被允许的,std::string也在其列,因此不能使用std::string传递结果,当然在ip2str里使用一个static char数组作为结果返回也是不被允许的,这意味着你放弃了线程安全性。所以一个名为ip2str_r的函数诞生了,它的签名如下:

int ip2str_r(const int ip, char *buffer, const int length);

当我需要打印多个ip地址时,才发现它的难用程度令人发指:

char buffer1[32];

char buffer2[32];

ip2str_r(ip1, buffer1, 32);

ip2str_r(ip2, buffer2, 32);

TBSYS_LOG(INFO, "addr1=%s addr2=%s", buffer1, buffer2);

那么有没有办法在保证线程安全的情况下实现一个这样的函数呢:

const char *ip2str_r(const int ip);

这里又要轮到上次提到的static __thread出场了,先来看看代码:

const char *ip2str_r(const int ip)
{
            static const int64_t BUFFER_SIZE = 32;
            static __thread char buffers[2][BUFFER_SIZE];
            static __thread uint64_t i = 0;
            char *buffer = buffers[i++ % 2];
            buffer[0] = '\0';
            unsigned char *bytes = (unsigned char *) &ip;
            snprintf(buffer, BUFFER_SIZE, "%d.%d.%d.%d",
            bytes[0], bytes[1], bytes[2], bytes[3]);
            return buffer;
}

每个线程维护一个buffer数组用来处理在一行日志中打印多个ip地址的需求,不过这里也有一个局限性,当你需要在一行日志中打印超过2个ip地址的话,依赖于snprintf的压栈顺序,多个ip地址会被相互覆盖,最终只能显示出两个有效结果。要想简单处理这种情况就把buffer的数组增大吧,4个、8个或更多,相信你在一行日志里也不会打印太多的地址。

打ipv4地址的需求解决了,下面让我们再来看看一个更复杂的需求,在我们的代码中,除了有把ip地址转化为字符串的需求外,还有很多对象也希望能够方便的打印出内部信息以方便调试或跟踪,譬如解析SQL后产生的物理执行计划是由一个一个的物理运算符对象嵌套而成的,我们希望将整个物理执行计划以文本方式展现出来,这就需要每个物理运算符都实现类似to_string的方法将自己的信息和嵌套的物理运算符都打印出来。我们当然可以在每个物理运算符都用上述static __thread的方法实现to_string,但是又意味着众多被复制粘贴的重复代码,我们希望抽出重复逻辑,让每个需要打印文本信息的类都只实现格式化打印的代码,而将buffer的维护抽取到公共的逻辑中。

由于历史原因,有些类实现了签名如下的to_string方法:

int64_t to_string(char *buffer, const int64_t buffer_size);

而有些类实现了如下的to_cstring方法:

const char* to_cstring();

而不同类打印出文本串的长度也不尽相同,可能打印在一行日志中的个数也不相同。

总结需求如下:实现一个to_cstring的模板方法,传入T类型的对象。第一,如果T实现了to_cstring就直接调用;否则就使用线程局部buffer调用to_string方法;第二,buffer长度和个数可使用默认值,但是如果T以某种方式指定了buffer长度和个数,则使用指定的值。下面只分析第一个需求,搞清楚了sfinae的原理,对于第二个需求请同学们去看oceanbase开源的代码库即可明白。

说到这里,本次要介绍的关键特性sfinae就要出场了,它是一个C++的语言特性,全称是Substitution failure is not an error,直译就是替换失败并非错误,即在匹配重载函数的时候,使用类型T匹配函数参数时发现类型错误(如T的某个成员不存在),不认为是编译错误,而是将这个重载函数从备选列表中去掉,再去尝试匹配下一个重载函数。有关sfinae词条,wikipedia有比较详细的说明,不过我认为那上面的第一个示例并不典型,判断类是否包含某个typedef类型的需求可以用另外一种称为traits的技术来实现,不一定非要用sfinae,所以我修改了一下,举例如下:

template <typename U, U>
struct type_check;

template <typename T>
bool have_con_member(type_check<const int*, &T::CON> *)
{
  printf("T has a const int member named CON\n");
  return true;
}

template <typename>
bool have_con_member(...)
{
  printf("T does not have any const int member named CON\n");
  return false;
}

struct Test
{
  static const int CON = 10;
};

struct Test1
{
  static const int64_t CON = 1;
};

int main()
{
  have_con_member<Test>(0);
  have_con_member<Test1>(0);
  have_con_member<int>(0);
}

这段代码的作用是检查调用函数f的时候,模板参数类型是否包含一个名为CON的整数型常量成员,根据检查结果分别打印不同的信息。对于Test类型作为模板参数,可以正确的匹配替换,绑定第一个f函数;而对于Test1类型为模板参数时,由于两个模板参数类型不一致,无法具现化type_check类型,因此将第一个f函数从备选函数中删除,继续看第二个f函数,发现可以匹配,编译通过;再看int类型为模板参数时,不存在int::CON,同样也无法具现化type_check类型。

到此为止,在编译期静态检查某个类型有没有包含指定成员的功能已经实现。现在我们有了这个功能后,如何应用在上面提到的实际需求中呢,先回顾下需求,实现to_cstring函数,在T类型有to_cstring方法时就直接调用,否则调用另一个称为to_string的方法。对上面示例代进行少量修改,我们应该比较容易的写出bool have_to_cstring_func<T>()这样的模板函数:

template <typename U, U>
struct type_check;

template <typename T>
bool have_to_cstring_func(type_check<const char* (T::*) (), &T::to_cstring> *)
{
  return true;
}

template <typename>
bool have_to_cstring_func(...)
{
  return false;
}

调用这个函数是可以通过返回值来判断结果,但是调用函数返回的结果是程序运行期间的变量,要执行这个函数才行,所以你可能会写出这样的代码:

template <typename T>
const char *to_cstring(T &obj)
{
  if (have_to_cstring_func<T>(0))
  {
    return obj.to_cstring();
  }
  else
  {
    static char __thread buffer[4096];
    obj.to_string(buffer, 4096);
    return buffer;
  }
}

但是很遗憾,这段代码是没法通过编译的,它要求T类型即要包含to_cstring函数,也要包含to_string参数,因为它没有办法在编译期知道针对某个T类型一定会进入哪个分支。既然不能通过函数的返回值绑定,那么我们就换个思路,用函数的返回类型来区分到底哪个重载函数被调用了,定如下模板类型BoolType,修改重载函数返回值类型,第一个返回BoolType<true>,第二个返回BoolType<false>。实现to_cstring模板函数如下:

template <bool c>
struct BoolType
{
  static const bool value = c;
};

template <class T>
const char *to_cstring(T &obj, BoolType<true>)
{
  return obj.to_cstring();
}

template <class T>
const char *to_cstring(T &obj, BoolType<false>)
{
  static char __thread buffer[4096];
  obj.to_string(buffer, 4096);
  return buffer;
}

template <class T>
const char *to_cstring(T &obj)
{
  return to_cstring(obj, have_to_cstring_func<T>(0));
}

好了,现在使用宏来整理一下这段代码,你就能得到一个通用的HAS_XXX_MEMBER宏了,我就不再粘代码了,想到具体实现的同学可以去copy oceanbase开源代码库中src/common/utility.h来找完整的to_cstring实现。

这是一个奇技淫巧的系列,后续内容预告一下:

大小为0对象的妙用

弱类型的应用

宏的变长模板

epoll与多对一唤醒器

Oceanbase代码有关语言和编译器的奇技淫巧(一)

Oceanbase代码有关语言和编译器的奇技淫巧(一)

–TSI Factory懒人利器

在oceanbase各个server的读写请求处理逻辑中,经常会遇到需要某个临时对象来保存中间参数或中间结果,比较典型的是线程在处理请求时需要将收到的buffer反序列化到类似ObScanParam这样的对象中,然后再将对象传给到具体的处理方法,执行得到的结果也是要通过类似ObScanner这样的对象传出,序列话到buffer中,再传递给网络线程回包。因此这样对象的作用域仅仅限于网络请求的处理函数中,调用伪代码示意如下:

  1. void handlePacket(ObPacket &pkt)  
  2. {  
  3.         ObScanParam scan_param;  
  4.         ObScanner scanner;  
  5.         scan_param.deserialize(pkt.get_req_buffer());  
  6.         handle_scan(scan_param, scanner);  
  7.         scanner.serialize(pkt.get_res_buffer());  
  8.         response(pkt);  
  9. }  

其中scan_param和scanner做为handlePacket函数的栈对象是比较合理,而ob最初版本的代码也确实是这样写的,但是当我们做性能测试的时候发现这里会有问题,这两个对象要对buffer执行序列化和反序列化,因此他们本质上是内存容器,这就意味着在他们的生命周期中要使用额外的内存,因此它们要么在使用的时候临时申请和释放内存,要么就把对象本身做大尽量使用栈上空间,避免每次都从堆上申请内存。但是无论怎么做都因为这种在栈上使用临时对象的做法,都有比较大的构造和析构成本。有没有简单的办法重用这样的对象呢,TSIFactory因此而诞生,先来看看它的使用方法:

  1. ObScanner *scanner = GET_TSI(ObScanner);  

不同线程通过GET_TSI调用得到的是不同的实例,而在一个线程内部每次调用得到的都是同一个对象,在线程退出的时候自动析构,因此上述代码通过使用TSIFactory简单改造,可以实现对象的重用:

  1. void handlePacket(ObPacket &pkt)  
  2. {  
  3.         ObScanParam *scan_param = GET_TSI(ObScanParam);  
  4.         scan_param->reset();  
  5.         ObScanner *scanner = GET_TSI(ObScanner);  
  6.         scanner->reset();  
  7.         scan_param->deserialize(pkt.get_req_buffer());  
  8.         handle_scan(*scan_param, *scanner);  
  9.         scanner->serialize(pkt.get_res_buffer());  
  10.         response(pkt);  
  11. }  

下面来看看GET_TSI的实现,宏GET_TSI封装了对一个模板函数的调用:

  1. template <class T>  
  2. T *get_instance()  
  3. {  
  4.   static __thread T *instance = NULL;  
  5.   if (NULL == instance && INVALID_THREAD_KEY != key_)  
  6.   {  
  7.     ThreadSpecInfo *tsi = (ThreadSpecInfo*)pthread_getspecific(key_);  
  8.     if (NULL == tsi)  
  9.     {  
  10.       tsi = new(std::nothrow) ThreadSpecInfo();  
  11.       pthread_setspecific(key_, tsi);  
  12.     }  
  13.     instance = tsi->get_instance<T>();  
  14.   }  
  15.   return instance;  
  16. }  

代码比较简单,这里使用了gcc的特性,“static __thread”。有关它的特性,直接摘一段别人的中文说明如下(摘自http://blog.csdn.net/liuxuejiang158blog/article/details/14100897):

__thread是GCC内置的线程局部存储设施,存取效率可以和全局变量相比。__thread变量每一个线程有一份独立实体,各个线程的值互不干扰。 __thread使用规则:只能修饰POD类型(类似整型指针的标量,不带自定义的构造、拷贝、赋值、析构的类型,二进制内容可以任意复制memset,memcpy,且内容可以复原),不能修饰class类型,因为无法自动调用构造函数和析构函数,可以用于修饰全局变量,函数内的静态变量,不能修饰函数的局部变量或者class的普通成员变量,且__thread变量值只能初始化为编译器常量(值在编译器就可以确定const int i=5,运行期常量是运行初始化后不再改变const int i=rand())。

通过上面的说明,可以理解为什么只能用__thread声明指针而不是对象本身了,那么随之而来的就是另一个问题,什么时候释放这个对象。这里就靠代码中的ThreadSpecInfo来解决对象释放的问题,通过注册pthread specific的回调函数来在线程退出时析构这些tsi对象,而这里想要想清楚,如何管理多个不同类型对象的释放问题,如果保存不同类型的指针?如何调用他们的析构函数?还是来看一段代码:

  1. class TSINodeBase  
  2. {  
  3.   public:  
  4.     TSINodeBase() : next(NULL)  
  5.     {  
  6.     };  
  7.     virtual ~TSINodeBase()  
  8.     {  
  9.       next = NULL;  
  10.     };  
  11.     TSINodeBase *next;  
  12. };  
  13.   
  14. template <class T>  
  15. class TSINode : public TSINodeBase  
  16. {  
  17.   public:  
  18.     explicit TSINode(T *instance) : instance_(instance)  
  19.     {  
  20.     };  
  21.     virtual ~TSINode()  
  22.     {  
  23.       if (NULL != instance_)  
  24.       {  
  25.         instance_->~T();  
  26.         instance_ = NULL;  
  27.       }  
  28.     };  
  29.   private:  
  30.     T *instance_;  
  31. };  

看了代码应该基本清楚了,既然需要保存不同类型的指针,那么就用一个基类包来成链表,不同对象的指针分别用不同的TSINode来保存,析构的时候只需要调用每个TSINodeBase的析构函数就好了。

到此为止TSIFactory的实现原理已经清楚了,最后还有一点值得提一下,目前位置实现的TSIFactory管理的对象不能有构造函数参数,这个能不能实现呢,这里的一个难点是既然要支持构造函数参数,那么参数的数量就是不确定的,如何做呢?还是先来看代码:

  1. #define GET_TSI_ARGS(type, args…) \  
  2.     ({ \  
  3.       type *__type_ret__ = NULL; \  
  4.       Wrapper<type> *__type_wrapper__ = GET_TSI(Wrapper<type>); \  
  5.       if (NULL != __type_wrapper__) \  
  6.       { \  
  7.         __type_ret__ = __type_wrapper__->get_instance(); \  
  8.         if (NULL == __type_ret__) \  
  9.         { \  
  10.           __type_wrapper__->get_instance() = new(std::nothrow) type(args); \  
  11.           __type_ret__ = __type_wrapper__->get_instance(); \  
  12.         } \  
  13.       } \  
  14.       __type_ret__; \  
  15.     })  

如果要求T类不做任何修改,要实现变长参数的无障碍传递,用宏来处理最简单(当然我也没相出来其他办法)。然后就是使用无构造函数参数的Wrapper来包装T类的指针,在第一次使用的时候new出T的对象。

最后解释一下,TSI是什么意思,作者当初写这段代码的时候正在看车,研究大众很给力的TSI发动机,正好也可以解释成thread static instance,就取了这个名字…

这是一个奇技淫巧的系列,后续内容预告一下:

to_cstring的Sfinae魔术

大小为0对象的妙用

弱类型的应用

宏的变长模板