首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

行列Rollback的设计

2012-09-08 
队列Rollback的设计有一个队列包含了N个block,每个block是队列中的一个元素。block很大,一个block中可以容

队列Rollback的设计

有一个队列包含了N个block,每个block是队列中的一个元素。block很大,一个block中可以容纳M个item(M>1)。

这个队列的基本使用模式就是:不断的有item过来,往block里面填充,一旦block满,就创建一个新的block,后继item都填往新block。

rollback的定义:最后一个item填充到block中后,由于出现了某种错误(如超出最大使用内存限制),需要把这个item删除掉,将队列恢复到删除前的状态。

有这么几种场景需要考虑:

1. 队列为空,插入第一个item后就需要回滚,插入前后队列中新增了一个block

2. 某个block插入第x个item后需要回滚,插入前后并没有创建新的block

3. 某个block插入第x个item时发现block满,新建一个block,将item插入到新block后回滚,插入前后队列中新增了一个block


2这种场景比较容易处理,只要插入前记录下rollback_pos,需要回滚的时候,将block中的pos恢复到rollback_pos即可。

1、3两种场景逻辑上很相似,编程上略有区别:1中队列头指针为NULL,3中队列头指针不为NULL,需要分别处理。

场景1的处理办法:发现需要回滚,free新建的block,令队列头指针为NULL,pos为0

场景3的处理办法:插入前记录rollback_block和rollback_pos,发现需要回滚,free新建的block,令队列头指针=rollback_block,pos=rollback_pos


这里最复杂的部分是free新建的block,如果能不去free block,问题会简单很多,三个场景可以用一个通用的算法解决:

插入前记录rollback_block和rollback_pos,发现需要回滚,令队列头指针=rollback_block,pos=rollback_pos

热点排行