注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

生命无非记忆

不要在记忆中丢失了自己

 
 
 

日志

 
 

【转载】数据库中的Halloween问题及其注意事项  

2014-02-14 13:37:17|  分类: postgreSQL[原创] |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
据说在30多年前,一个万圣节(Halloween)的晚上,所有现代关系数据库的祖先System R的开发人员觉得他们的系统总算基本上可以工作了,兴奋的想试一试,结果没想到一条语句就试出问题来了。情况是这样的,系统中有一张表EMP_TABLE记录各个员工的工资,然后他们想给所有工资小于25000的人都涨10%的工资(要是我能UPDATE一下数据库就能把我的工资涨上去就好了^_^),所以他们用了这样的UPDATE语句:
  UPDATE EMP_TABLE SET SALARY=SALARY*1.1 WHERE SALARY<25000;
当时的工资水平还比较低,大部分人的工资都是远小于25000的,按理说涨10%后,大部分人的工资还是远不到25000,但结果他们发现,执行了上面的UPDATE语句后,所有人的工资都涨到了25000以上。

这个问题真是太严重了。要知道,当时的数据库主要就是面向银行交易这类应用设计的,如果出了上面这样的问题,造成的损失可就大了。

这个问题是怎么产生的呢。虽然现在的数据库系统肯定已经解决了这个问题,所以用户通常不会感觉到这个问题的存在,可能大部分的DBA都不知道还有这样的问题。但实际上,在特殊情况下,这个问题对系统还是会造成很大影响的,因此,还是有必要作一些了解。大家知道,在数据库内部用于存储数据的数据结构通常有两个:堆文件和B+树。堆文件存储记录,B+树存储索引,当然也有直接用B+树存索引和记录的。在上面的EMP_TABLE表的SALARY列上就有一个索引,而System R在执行上述语句时,选用的是扫描SALARY的这个索引,按SALARY递增的顺序取出满足条件的记录,每取一条记录出来后,就将它的SALARY属性增加10%。问题是,在更新SALARY的时候会去更新索引,大家知道,B+树索引是有序的,这样,如果一个索引键被更新后值变大了,它在索引中的位置就会向后移动。如下图所示。假设一个人的工资是1000,从左到右扫描索引时,第一次遇到这条记录对应的SALARY索引项的位置是下面的左边第一个图。然后系统将这个人的SALARY增加10%,更新到1100,这时候,这个人对应的索引项的位置就到了原位置之后。系统继续扫描索引,又会第二次遇到这个索引项(下图中),把它更新到1210,这样索引项后向后移了移,结果系统继续扫描索引,又会第三次遇到这条记录(下图右),如此循环下去,直到这个SALARY增加到25000以上,这一过程才会结束。

数据库中的Halloween问题及其注意事项 - 风轻扬 - 风轻扬
上面所说的只是Halloween问题的一种。更严重的Halloween问题可能会导致系统进入死循环,比如上面的语句中如果没有了"SALARY<25000"的条件,变成:
  UPDATE EMP_TABLE SET SALARY=SALARY*1.1;
这个语句就会持续不断的将每个人的SALARY都增加10%,永远不会中止(当然,由于计算机表示数字时精确有限,一个大的正数再增加10%会变成负数,更新后位置在扫描位置之前,这个过程还是会中止的)。

还有一种情况是如下的INSERT语句:
  INSERT INTO some_table SELECT * FROM some_table;

一般情况下,数据库的处理是流水化的,也就是对"INSERT...SELECT..."之类的语句,数据库总是执行SELECT,一般SELECT返回一行,就执行INSERT插入这一行。但如果SELECT访问的表和INSERT插入的表是同一个表的话,就有可能会出问题了。记录在数据库里通常是用堆文件存储的,基本上就是记录一个挨一个存着。对于上面的语句,如果还是按普通的"INSERT ... SELECT ..."语句那样处理的话,数据库的做法是先对some_table进行扫描,每扫描到一条记录,就再插入到some_table中。假设表some_table有两个字段,表中原来只有1条记录(100,1)。按理说上述语句执行之后,表中应该有两条记录才对。但如何按上面所说的流程执行就玩完了。堆中初始情况如下图左所示,这时系统对堆进行扫描,扫描到(100,1)后,按上述流程,会把这条记录再插入到堆中。这样堆的结构就成了下图中的样子,系统继续扫描堆,结果扫描到了刚插入的记录,结果又插入了一次(下图右)。如此死循环下去,直到把磁盘撑爆掉为止。

数据库中的Halloween问题及其注意事项 - 风轻扬 - 风轻扬

Halloween问题有很多种表现形式。还有一种比较常见的是表的自联接UPDATE,比如设有表t(a, b),进行如下语句:
  UPDATE t SET a = (SELECT b FROM t AS t2 WHERE t2.a = t.b);
设表中所有两条记录:  (1, 2),  (2, 1)。正确的结果应该是更新成:  (1, 1), (2, 2)。对于(1, 2)这条记录,对应的t2记录是(2, 1),因此更新后的结果是(1, 1)。同样的道理,(2, 1)应该被更新成(2, 2)。但这个语句若还是按上述的流水化处理就又错了。(1, 2)会被更新成(1, 1)没错,但接下来更新(2, 1)时,这时找到对应的t2记录已经变成了(1, 1)了,这样结果就被更新后了(2, 1)。

总之,如果一个表或索引在被扫描的同时也会被更新的话,Halloween问题就有可能会出现。那这个问题怎么解决呢?方法有两个:
1. 数据库的底层使用多版本技术,保证读取操作读到的是语句刚开始时的已提交数据。对于更新SALARY的那个例子,一个SALARY被更新后,新的SALARY索引项就会被系统忽略。对于表自联接UPDATE那个例子,虽然(1, 2)已经被更新成(1, 1),但这时系统中有这个记录的两个版本,原来的(1, 2)和更新后的(1, 1),系统在处理第二条记录时会读取原来的(1, 2)这个版本。
2. 延迟更新法。即用一个临时文件或临时表存放要插入、更新或删除的元组,直到语句执行完成后才批量进行真正的插入、更新或删除动作。比如对于INSERT那个例子,系统就会先扫描some_table,把所有数据临时保存起来,然后再把临时存在的这些记录再插入到some_table中。对于UPDATE那个例子,系统会把所有记录更新之后的结果先缓存起来,计算出所有记录更新后的结果后,再来批量更新。

由于文中开头所述的一段历史渊源,现在这一类问题都被统称为Halloween问题。当然,现在的数据库都不会有这样的问题存在了。但作为一般的DBA,还有是必要知道您所用的系统是不是用延迟更新法来解决Halloween问题的。如果是的话,那在执行上述的语句时就要注意为系统准备好存放临时数据的空间。比如对那个自联接UPDATE的例子,因为只是UPDATE了一个定长字段,大部分人都会觉得这个语句不会导致数据库占用的磁盘空间增长。但实际上如何你要UPDATE非常多的记录,缓存更条记录更新结果就会占用很多空间,虽然这些临时空间在语句完成之后会被释放,但如果磁盘上没有足够空间,可能就会导致操作过程中由于磁盘空间不足而失败。
  评论这张
 
阅读(107)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017