[Paxos三部曲之二] 使用Multi-Paxos协议的日志同步与恢复

使用Multi-Paxos协议的日志同步与恢复

           本文是Paxos三部曲中的第二篇。在前一篇文章《使用Basic-Paxos协议的日志同步与恢复》(http://oceanbase.org.cn/?p=90)中,我们讨论了基于Basic-Paxos协议的日志同步方案,在这个方案中,所有成员的身份都是平等的,任何成员都可以提出日志持久化的提案,并且尝试在成员组中进行持久化。而在实际的工程应用中,往往需要一个成员在一段时间内保持唯一leader的身份,来服务对数据的增删改操作,产生redolog,并尝试在成员组中进行持久化。本文讨论如何利用Paxos协议选举唯一的leader,以及使用leader将redolog在成员组中进行持久化和恢复的方法。

  • Basic-Paxos协议回顾

让我们先来回顾下Basic-Paxos协议的执行流程:为了简化描述,我们假设一个Paxos集群,每个server同时担任proposer和acceptor,任何server都可以发起持久化redolog的请求,首先要向所有的server查询当前最大logID,从多数派的应答结果中选择最大的logID,加1后作为执行本次Paxos Instance的唯一标识;然后进入Paxos的prepare阶段,产生proposalID,并决定出要投票的redolog(即议案);在accept阶段对prepare阶段产生的议案进行投票,得到多数派确认后返回成功。由此我们可以看出Basic-Paxos协议的执行流程针对每条redolog都至少存在三次网络交互的延迟(1. 产生logID;2. prepare阶段;3. accept阶段)。下面我们逐个分析每个阶段的必要性:

  1. 产生logID,由于Basic-Paxos并不假设一段时间内只有唯一的proposer,因此可能由集群内的任意server发起redolog同步,因此不能由单一server维护logID,而是需要进行分布式协商,为不同的redolog分配全局唯一且有序的logID。
  2. prepare阶段,上述一阶段的分布式协商logID并不能保证并发多个server分配得到得logID是唯一的,即会出现若干条不同的redolog在同一个Paxos Instance中投票的情况,而这正是Basic-Paxos协议的基本假设,因此需要执行prepare,以决定出这个Paxos Instance内的要进行投票的redolog(即议案)。如果执行prepare决定出的议案与server自己要投票的redolog内容不同,则需要重新产生logID。
  3. accept阶段,对prepare阶段决定出的议案进行投票,得到多数派确认后表示redolog同步成功,否则需要重新产生logID。

在这三个阶段中,根据Paxos协议的约束,server应答prepare消息和accept消息前都要持久化本地redolog,以避免重启后的行为与重启前自相矛盾。因此最终可以得到使用Basic-Paxos进行redolog同步的延迟包括了3次网络交互加2次写本地磁盘。并且在高并发的情况下,不同redolog可能被分配到相同的logID,最差可能会在accept阶段才会失败重试。

 

  • Multi-Paxos协议概述

在Paxos集群中利用Paxos协议选举唯一的leader,在leader有效期内所有的议案都只能由leader发起,这里强化了协议的假设:即leader有效期内不会有其他server提出的议案。因此对于redolog的同步过程,我们可以简化掉产生logID阶段和prepare阶段,而是由唯一的leader产生logID,然后直接执行accept,得到多数派确认即表示redolog同步成功。

 

  • leader的产生

首先,需要明确的是Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志,它允许有多个“自认为是leader的server”来并发生成日志,这样的场景即退化为Basic-Paxos。

Multi-Paxos可以简单的理解为,经过一轮的Basic-Paxos,成功得到多数派accept的proposer即成为leader(这个过程称为leader Elect),之后可以通过lease机制,保持这个leader的身份,使得其他proposer不再发起提案,这样就进入了一个leader任期。在leader任期中,由于没有了并发冲突,这个leader在对后续的日志进行投票时,不必每次都向多数派询问logID,也不必执行prepare阶段,直接执行accept阶段即可。

因此在Multi-Paxos中,我们将leader Elect过程中的prepare操作,视为对leader任期内将要写的所有日志的一次性prepare操作,在leader任期内投票的所有日志将携带有相同的proposalID。需要强调的是,为了遵守Basic-Paxos协议约束,在leader Elect的prepare阶段,acceptor应答prepare成功的消息之前要先将这次prepare请求所携带的proposalID持久化到本地。

对于leader Elect过程,我们并不关心leader Elect提案和决议的具体内容,因为无论执行多少次leader Elect,从Basic-Paxos的角度来看,都是同一个Paxos Instance在对已经形成的决议反复进行投票而已。而执行leader Elect这个过程,我们最关注的是要得到最近一次形成决议的proposer是谁,以及它的proposalID。在leader Elect过程中,得到多数派accept的proposer将成为leader,而它本次所用的proposalID即成为它任期内对所有日志(包括新增日志和后文将提到的重确认日志)进行投票时将要使用的proposalID(称为leader ProposalID)。

这里还需要考虑的一个问题是,由于多个server并发执行leader Elect,可能出现两个server在相近的时间内,先后执行leader Elect都成功,都认为自己是leader的情况。因此,当选leader在开始以leader身份提供服务之前,要使用leader ProposalID写一条日志(称为StartWorking日志),得到多数派确认后,再开始提供服务。这是因为根据Basic-Paxos的约束,可以推断出:先执行leader Elect成功的leader(称为L1),它的proposalID(称为P1)一定会小于后执行leader Elect成功的leader(称为L2)的proposalID(称为P2),而经过了两轮leader Elect,机群内多数派持久化的proposalID一定是P2,而此时L1使用P1执行accept时,由于P1<P2,它将无法得到机群内多数派的accept。

 

  • Confirm日志的优化

在Paxos协议中,对于决议的读取也是需要执行一轮Paxos过程的,在实际工程中做数据恢复时,对每条日志都执行一轮Paxos的代价过大,因此引入需要引入一种被成为confirm的机制,即leader持久化一条日志,得到多数派的accept后,就再写一条针对这条日志的confirm日志,表示这条日志已经确认形成了多数派备份,在回放日志时,判断如果一条日志有对应的confirm日志,则可以直接读取本地内容,而不需要再执行一轮Paxos。confirm日志只要写本地即可,不需要同步到备机,但是出于提示备机及时回放收到日志的考虑(备机收到一条日志后并不能立即回放,需要确认这条日志已经形成多数派备份才能回放),leader也会批量的给备机同步confirm日志。出于性能的考虑,confirm日志往往是延迟的成批写出去,因此仍然会出现部分日志已经形成多数派备份,但是没有对应的confirm日志的情况,对于这些日志,需要在恢复过程中进行重确认。

在实际的工程实践中,可以使用基于logID的滑动窗口机制来限制confirm日志与对应的原始日志的距离,以简化日志回放与查询逻辑。

 

  • 新任leader对日志的重确认

如上一节所述,在恢复过程中,拥有对应confirm日志的原始日志,可以被直接回放。而没有对应confirm日志的原始日志,则需要执行一轮Paxos,这个过程被成为重确认。

此外日志中的“空洞”,也需要进行重确认,因为当前leader再上一任leader的任期内可能错过了一些日志的同步,而这些日志在其他机器上形成多了多数派。由于logID连续递增,被错过的日志就成了连续logID连续递增序列中的“空洞”,需要通过重确认来补全这些“空洞”位置的日志。

新任leader在开始执行重确认前,需要先知道重确认的结束位置,因为leader本地相对于集群内多数派可能已经落后很多日志,所以需要想集群内其他server发送请求,查询每个server本地的最大logID,并从多数派的应答中选择最大的logID作为重确认的结束位置。也即开始提供服务后写日志的起始logID。

对于每条日志的重确认,需要执行一轮完整的Paxos过程,可能有些日志在恢复前确实未形成多数派备份,需要通过重新执行Paxos来把这些日志重新持久化才能回放。这种不管日志是否曾经形成多数派备份,都重新尝试持久化的原则,我们称之为“最大commit原则”。之所以要遵守“最大commit原则”,是因为我们无法区分出来未形成多数派备份的日志,而这些日志在上一任leader任期内,也必然是“未决”状态,尚未应答客户端,所以无论如何都重新持久化都是安全的。比如A/B/C三个server,一条日志在A/B上持久化成功,已经形成多数派,然后B宕机;另一种情况,A/B/C三个server,一条日志只在A上持久化成功,超时未形成多数派,然后B宕机。上述两种情况,最终的状态都是A上有一条日志,C上没有,在恢复时无法区分这条日志是否曾经形成过多数派,因此干脆按照“最大commit原则”将这条日志尝试重新在A/C上持久化后再回放。

需要注意的是,重确认日志时,要使用当前的leader ProposalID作为Paxos协议中的proposalID来对日志执行Paxos过程。因此在回放日志时,对于logID相同的多条日志,要以proposalID最大的为准。

 

  • 幽灵复现日志的处理

使用Paxos协议处理日志的备份与恢复,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为“幽灵复现”的现象,如下图所示:

 

Leader

A

B

C

第一轮

A

1-10

1-5

1-5

第二轮

B

宕机

1-6,20

1-6,20

第三轮

A

1-20

1-20

1-20

  1. 第一轮中A被选为Leader,写下了1-10号日志,其中1-5号日志形成了多数派,并且已给客户端应答,而对于6-10号日志,客户端超时未能得到应答。
  2. 第二轮,A宕机,B被选为Leader,由于B和C的最大的logID都是5,因此B不会去重确认6-10号日志,而是从6开始写新的日志,此时如果客户端来查询的话,是查询不到6-10号日志内容的,此后第二轮又写入了6-20号日志,但是只有6号和20号日志在多数派上持久化成功。
  3. 第三轮,A又被选为Leader,从多数派中可以得到最大logID为20,因此要将7-20号日志执行重确认,其中就包括了A上的7-10号日志,之后客户端再来查询的话,会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。

对于将Paxos协议应用在数据库日志同步场景的情况,幽灵复现问题是不可接受,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。

           为了处理幽灵复现问题,我们在每条日志的内容中保存一个generateIDleader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时,因为leader在开始服务之前一定会写一条StartWorking日志,所以如果出现generateID相对前一条日志变小的情况,说明这是一条幽灵复现日志(它的generateID会小于StartWorking日志),要忽略掉这条日志。

 

  • 总结

本文介绍了在Basic-Paxos协议基础之上构建Multi-Paxos协议的几个要点:通过使用Paxos选举leader来避免对每条日志都执行Paxos的三阶段交互,而是将绝大多数场景简化为一阶段交互,并且讨论了基于Paxos协议的最大commit原则;通过引入confirm日志来简化回放处理;通过引入Start Working日志和generateID来处理幽灵复现问题。

 

Loading

有关期权股票与缴税的分享

有关期权股票与缴税的分享

本文基于作者本人的经验而写,其间难免有纰漏或错误,内容仅供大家参考。

作为一个穷二代屌丝码农,靠积攒每月的固定工资,可以说很难追上一线城市不断上涨的房价,还好我们处在一个伟大的时代,选择加入一家高速发展的公司,分得一些期权或股票,熬几年到公司上市套现,屌丝也可以逆袭

授予”与“归属”

以目前的经验来看,公司一般会以期权(option)或限制性股份单位(RSU)的形式对员工进行长期激励,也有其他形式的,比如华为的内部股票,或者蚂蚁金服的“股份收益权”不在本次讨论的范围内。所谓“长期激励”,其实就是把承诺给你的OptionRSU,拆分到N年,每年给一部分,以防止你全拿了就立即跑路。

这里就要谈到“授予”和“归属”两个概念,“授予”是一个承诺,靠谱的公司一般会明确写在offer中,承诺到未来某个时间只要你没有离职或被开除就给你多少OptionRSU;“归属”就是到了上述约定的时间,公司按照之前的承诺,将“授予”你的OptionRSU登记在你的名下。比如HR给你的发的offer可能会写“授予”你MOption,分4年“归属”,入职两年后“归属”M/2份,之后每年“归属”M/4份。在这4年期间如果你离职了,那么从你离职之日之后按计划要“归属”的Option都将失效。

期权

期权(option)就是允许你在一段时间内(一般比较长达几年)以约定的价格和数量购买公司股票的权利。归属以后才能“行权”,“行权”就是指你按照约定的价格够买股票的行为。如果公司未来股价上涨,股价与行权价相差的部分,就是你的收益,当然也存在风险即公司股价跌至行权价以下,这样的话Option就沦为废纸了。这里我们只讨论公司股价高于行权价的情况,行权需要缴纳两部分费用,第一部分就是行权本金,你要买多少股乘以行权价就是你要付出的本金;第二部分是个人所得税,用行权当日股价减去行权价,就是你的每股收益,乘以你要买的数量就是行权总收益计算个人所得税,具体缴税方式在后文说明。

一般期权归属后,会有一个有效期的,过了有效期就不能行权了,这个有效期一般会长达好几年,但是如果离职的话,一般就需要在几个月内行权,否则就会失效。

这里额外再说一下,一般来说行权价就是“授予”当时的股价,根据当时的公司的估值,以及公司发展和融资的状况,可以大概yy下几年后的股价。

限制性股份单位

限制性股份单位(RSU)简单说就是干股,也可以认为是行权价为0Option,唯一的区别是RSU不需要行权,“归属”后就变成你的股票了。但是同样需要你缴纳费用,就是个人所得税,一般是用归属当日的股价乘以归属的数量作为你的总收益计算个人所得税,具体缴税方式在后文说明。

这里需要注意的是,在公司尚未IPO的情况下,Option行权或RSU归属时的股价以公司最近一次发布的“公允价”计算;而如果已经IPO,那么就按照行权当天(或前n天的平均)收盘价计算。

股票与ADS的兑换

行权或RSU归属后,公司的股票就算是登记在你的名下了,如果在美国上市的话,还会有一个股票与ADS(美国存托股票,即资本市场上的流通股)的兑换比例,A股和H股可能也有类似的机制。所以一家上市公司给你发的offer中有股票授予的话,在你计算跳槽收益时要特别留意这个股票与资本市场上流通股的兑换比例。

关于个人所得税

有部电影曾经说过人生有两件事是逃不掉的,死亡和纳税。如上文所述,在Option行权和RSU归属的时候需要缴纳个人所得税,根据“国税函[2006]902号”,“国税函[2009]461号”,“财税[2005]35号”的规定,我总结缴纳个人所得税有三种计算方式:

  1. 发行股票的公司并未上市,这种情况下要将行权或归属的总收益与当月工资一起合并计税。
  2. 发行股票的公司(下称为A)已经上市,但是和你签署劳动合同的公司(下称为B)不是上市公司并且A公司持有B公司的股份少于30%,这种情况下计税方式与第1点一样,将行权或归属的总收益与当月工资一起合并计税。
  3. 发行股票的公司已上市,和你签署劳动合同的公司正是上市公司或被上市公司控制了超过30%的股份,这种情况下行权或归属的总收益将在本年度内平摊到12个月计税,且不与工资合并计税。说法有点绕,我们来举一个实例,比如在2014年度某个同学行权若干次,RSU归属若干次,最后算得的总收益为M元,那么他本年度需要为行权和归属缴纳的个人所得税为:(M / 12 * 适用税率 – 速算扣除数) * 12与工资没有任何关系。

分析与总结

  1. 对于未上市的公司,option的缴税比RSU更灵活,你可以在option“归属”后自由的选择时间行权,行权的收益跟当月工资合并计税,像我们这种小虾米,自己平摊到几个月行权的话,一般不会达到45%的税率;而RSU则没那么自由,在“归属”的当月就要按照收益全额缴税,比较容易就达到45%的最高税率
  2. 上市后的OptionRSU的缴税可以按照国家规定平摊到一年度12个月计税,而option还要多付出比较高的本金,因此RSU的风险更低一些;由于是与工资分开计税的,所以谈offer时如果能在现金与股票中选择的话,平衡与现金与股票数量,能最大程度的降低缴税成本
  3. 小心“个人所得税”一节第2点的坑,如果被授予OptionRSU,签署劳动合同尽量争取与上市公司或上市公司持股超过30%的公司签署
  4. 如果被授予OptionRSU,决定跳槽前注意询问股票与资本市场流通股的兑换比例
  5. offer时要求明确“归属”方案,尽量别选择那些网上流传的公司,上市后,员工连自己有多少股票都不知道

最后,努力工作和读书吧,少跳槽多拿股票,屌丝也能买得起北京的房子。

参考资料:

国税函[2006]902

http://www.chinatax.gov.cn/n810341/n810765/n812183/n812831/c1196443/content.html

国税函[2009]461

http://www.chinatax.gov.cn/n810341/n810765/n812166/n812622/c1087262/content.html

财税[2005]35

http://www.mof.gov.cn/zhengwuxinxi/caizhengwengao/caizhengbuwengao2005/caizhengbuwengao20056/200805/t20080525_42773.html

Loading

[Paxos三部曲之一] 使用Basic-Paxos协议的日志同步与恢复

使用Basic-Paxos协议的日志同步与恢复

 

           在保证数据安全的基础上,保持服务的持续可用,是核心业务对底层数据存储系统的基本要求。业界常见MySQL/Oracle的1主N备的方案面临的问题是“最大可用(Maximum Availability)”和“最大保护(Maximum Protection)”模式间的艰难抉择,其中“最大可用”模式,表示主机尽力将数据同步到备机之后才返回成功,如果备机宕机或网络中断那么主机则单独提供服务,这意味着主备都宕机情况下可能的数据丢失;“最大保护”模式,表示主机一定要将数据同步到备机后才能返回成功,则意味着在任意备机宕机或网络中断情况下主机不得不停服务等待备机或网络恢复。可见传统主备方式下,如果要求数据不丢,那么基本放弃了服务的持续可用能力。

 

           基于Paxos协议的数据同步与传统主备方式最大的区别在与Paxos只需任意超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。本文不再分析Paxos协议本身(参考原始论文,以及这篇比较通俗的分析http://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D ),而是基于Paxos协议,讨论一种在多副本上持久化数据的高可用方案。需要注意的是,本方案不考虑运行性能,只是为了帮助说清协议的工程实现。

 

           我们将数据持久化的需求抽象为:在N个server的机群上,持久化数据库或者文件系统的操作日志,并且为每条日志分配连续递增的logID,我们允许多个客户端并发的向机群内的任意机器发送日志同步请求。对于高可用的需求为:在N个server中只要有超过半数的server(majority)正常服务,并且相互通信正常,那么这个机器就可以持续的提供日志持久化和查询服务。

 

           将每条日志的持久化流程都看作一个“Paxos Instance”,不同的logID代表不同的Paxos Instance形成的“决议(decision)”。即每一个logID标识着一轮完整paxos协议流程的执行,最后形成decision。机群内的每个server同时作为paxos的acceptor和proposer。

 

           获取LogID

           Server收到客户端的持久化日志请求后,先要决定这条日志的logID,为了尽量减少后续Paxos协议流程中处理并发冲突造成的回退,要尽量分配与目前已经持久化和正在持久化中的日志不重复的logID,同步也要容忍少于半数的server宕机与网络故障。因此向所有acceptor查询它们本地目前已写盘的最大logID,而只需收集到majority返回的结果,并选择其中最大的logID+1作为本次待持久化日志的logID。从上面的描述可以看出,这里并不能保证并发提交的两条日志一定被分配到不同的logID,而是依靠后续的paxos协议流程来达到对一个logID形成唯一的decision的目的。

 

           产生ProposalID

获取LogID后,server作为proposer开始针对当前logID,执行Paxos Instance,先产生proposalID,根据paxos协议的要求,proposalID要满足全局唯一和递增序,即对同一个server来说后产生的proposalID一定大于之前产生的,这里我们使用server的timestamp联合ip作为proposalID,其中timestamp在高位,ip在低位,只要时钟的误差范围小于server重启的时间,就可以满足“同一个server后产生的proposalID一定大于之前产生的”。

 

           Prepare阶段

           Proposer准备好proposalID后,将proposalID作为 “提案(proposal)”发送给所有的acceptor。根据Paxos协议P1b的约束,这个阶段发送的proposal并不需要携带日志内容,而只需要发送proposalID。Acceptor收到proposal后,根据Paxos协议P1b判断是否要“回应(response)”:只有在这个Paxos Instance内(即针对这个logID)没有response过proposalID大于等于当前proposal的,并且也没有“接受(accept)”过proposalID大于当前proposal的,才可以response,并承诺不再accept那些proposalID小于当前proposal的。

如果已经accept过proposal,那么连同proposalID最大的日志内容一同response。为了遵守P1b的约束,在宕机恢复后也能满足,因此在response前,需要将当前proposalID写到本地磁盘。

           上述Prepare阶段的处理流程暗示,对于分配到相同logID的不同日志,由于他们的proposalID不同,acceptor在response一个较小proposalID后,是允许继续response后来的较大的proposalID的。

 

           Accept请求阶段

           Proposer收集到majority的response后,来决定后续是否将要发出的“accept请求(accept request)”,判断如果majority的response中的日志内容都为空,那么可以向所有acceptor发出accept request并携带上当前日志内容;而如果有任意的response中的日志内容有效,那么说明当前logID已经别其他日志占用,且其他日志可能已经在majority上持久化,因此需要回退,回到第一步“获取logID”重新执行。

 

           Accept处理阶段

           Acceptor收到proposer的accept request后,根据上文中“Prepare阶段”的承诺,判断当前logID下,曾经response过的最大proposalID,如果小于等于当前proposal的,则可以继续执行后续的accept处理逻辑;而如果大于当前proposal的,则说明有logID切proposalID更大的proposal在并发执行,当前proposal会被覆盖,因此回复proposer要求回退到第一步“获取logID”重新执行。

           然后Accept处理逻辑将当前proposal连同proposalID一起写到本地磁盘,给proposer回复成功。Proposer收集到majority的回复成功后,说明本条日志已经在机群上持久化成功,可以保证后续一定不会被覆盖或丢失,可以给客户端返回了。

           上述accept处理阶段的流程暗示,可能会存在针对一个logID,日志只在少于半数的acceptor上写到本地磁盘,而acceptor同时response了proposalID更大的proposal,而使得当前logID下没有任何日志在机群上持久化成功。即一个logID可能没有标识任何有效日志,这种情况是可以接受的。

 

           日志内容读取

           已经在机群上持久化成功的日志,需要能够被读取出来,一般的应用模式是按照logID的顺序依次读取并回放日志。读取的时候针对每一条logID,需要执行一轮完整的paxos协议流程,将accept处理阶段成功的日志内容返回。需要注意的是,在accept请求阶段的处理逻辑变化:Proposer收集到majority的response后,判断如果majority的response中的日志内容都为空,那么向所有acceptor发出日志内容为空的accept request;而如果有任意的response中的日志内容有效,则选择proposalID最大的日志内容放入accept request。后续收到majority的accept回复成功后,才可以返回日志内容作为读取结果。

           这里的流程暗示,针对一个logID,如果之前已经有日志内容持久化成功,那么这条日志一定会被选为accept request;而如果之前日志内容仅仅在小于半数的server上写到磁盘,那么最终这条logID的内容有可能是有效日志,也有可能内容为空。

 

           为什么读取也需要执行Paxos流程

           这是基于一致性的考虑,即针对一条logID,读取出的内容后续应该永远不变。因此如果一条logID在写入过程中,并未在majority上持久化,那么需要在读取返回结果前,将这个结果在机群上持久化成功。

Loading

[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”。

Loading

阿里技术沙龙第31期-OceanBase专场

阿里技术沙龙第31期-OceanBase专场

郁白:《OceanBase-破解数据库高可用性难题》

官方已发布ppt,我就不在外面上传了,请注意第18页堪误

2*Telect2 ==> 2*Tcycle

4*Telect2 ==> 4*Tcycle

视频地址:http://v.youku.com/v_show/id_XODU5NjE4Mzcy.html

http://v.youku.com/v_show/id_XODU5NjE4Mzcy.html

Loading

[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

Loading

[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);
}

 

Loading

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

Loading

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的管理,尽量扁平化系统设计。

 

Loading

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