月度归档:2013年12月

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这个限制的原因。

Loading

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与多对一唤醒器

Loading

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对象的妙用

弱类型的应用

宏的变长模板

Loading