如何恢复全局INDEX

一般来说,当需要分配全局惟一id时,一般都会有一个变量来记录当前最新的id值,比如叫INDEX变量。

每次需要分配id时,只要简单的自增一下INDEX变量,然后INDEX的值即为当前分配出去的ID的值。

为了最大可能的延迟复用已经分配过的id,一般来说不会去特殊处理INDEX变量,即每次自增INDEX,并允许回绕情况的发生。

但是最近碰到问题就是,我有一堆分配过的id,如何重新恢复出INDEX的值。具体场景如下:

struct obj {
        unsigned int id;
        time_t createtime;
        ...
}

每一个obj对象都需要有一个全局惟一id和创建时间(createtime字段)与其关联,因此每new一个obj对象就需要为其分配一个不重复的全局id。

obj可以被人为删除,也会被过期删除,因此无法保证在任何时间所有还存活着的obj对象id是连续的。这些obj对象会被定时写入数据库。

一旦进程被重启,程序会从数据库加载所有还存活着的obj对象,以便可以恢复现场,使重启进程这一操作透明。要保证整个逻辑正确性,还必须要能正确的恢复出INDEX变量。

那么问题来了,而由于某种原因,INDEX并不方便被存入数据库中。

因此必须要根据现有的存活obj对象来恢复出在进程重启前的INDEX的值。

第一反应,肯定是遍历一之后找到obj对象中最大的id即为原来的INDEX,但是这里有一个陷阱就是INDEX会回绕,一旦INDEX会回绕之后,这个算法就不正确了。

考虑这样一种情况,进程运行了数月都没有重启,这时残留的obj对象id可能就只剩下0xfffffffe,0xffffffff,0,1,3,5这些了,重启之后采用上述算法无法重新恢复出重启前INDEX的值为5.

再一看,还有一个createtime用作参考,只要取obj对象中createtime最大的那个对象的id为INDEX就行了。

然而,由于createtime是以秒为单位的,逻辑上无法保证1秒只创建一个obj对象,问题再次绕回到第一个算法所遇到的困境。

因此,看起来,想要正确恢复出INDEX的值就必须解决回绕的问题。

要解决这个问题,就必须要有一种大小比较算法,这种算法即使在回绕时,也能正确判断大小。比如在0xfffffffe,0xffffffff,0,1,3,5这一堆id中,此算法会认为5是最大值,而在3,5,7,9这一块id中认为9才是最大值。

那么究竟有没有这种算法呢?比较巧的是,还真有这种算法。

假设有A,B,C三个32位无符号值,C=(A+B) % 4G。那么只要B大于0且小于2G,C – A就一定大于0。不过这里有一个陷阱,如果A和C是无符号变量,那么一定要将C-A的值转换为int之后再使用。

再回到设定场景中去,虽然我们1秒可以new很多个obj对象,但是绝不可能new出2G个之多。

有了这个事实和算法,答案就呼之欲出了,其中一种实现如下:

unsigned int id = 0;
time_t time = 0;
for (auto const &obj:objs) {
        if (obj.createtime < time)
                continue;
        if (obj.createtime > time) {
                time = obj.createtime;
                id = obj.id;
        } else if ((int)(id - obj.id) < 0) {
                 id = obj.id
        }
}
//now we got the final INDEX value

ps. 在阐述这个blog之前,我曾请教了几个人,但似乎并没有其他更好的做法,觉得这个实现还算精巧,就做个笔记.



发表评论