内存事务如何选择加锁协议,乐观好还是悲观好?

标签: 内存 选择 协议 | 发表时间:2011-09-30 00:00 | 作者:[email protected] yuanxinz
出处:https://www.sunchangming.com/blog/

最近我用 Multiverse STM做了一点东西。在开始动手之前,我专门测了multiverse的性能,发现它可以达到每秒2000多万次事务(每个CPU),于是我觉得它所带来的overhead应该是极小的,于是就放心大胆的用了。可是后来用profile工具看,我的程序始终是在openForRead这样的函数上占据了绝大部分时间。为什么? 这就涉及了multiverse STM是如何实现事务的。

Multiverse的核心是Ref这个类。这个这个类,把普通的对象引用,转换成一个事务引用。例如

Ref<Integer> i=StmUtils.newRef(Integer.valueOf(10));

通过这种方式,可以给原有的Object加一些metaInfo,比如version。

数据库最初的validate based algorithm,是这样,读的时候直接从全局数据里读(并且是同一个版本),写的时候写到事务本地的buffer里,提交的时候重新验证所有读过的信息是否在这个事务执行的过程中被更新了。TL2算法就属于此类。TL2算法在读一个全局数据的时候根本不用加锁,只需要一个tryLock。下次读的时候,先检查本地的read set。

那么,比较一下,如果采用悲观锁呢(例如我以前在完美用的xdb)?读一个变量的时候,首先要加这个锁,拿不到就等着。逻辑很简单。

从这点上来说,TL2这种乐观并发控制,相比于XDB那种老土的悲观并发模式,并不能提高性能。为什么?在首次载入一个变量的时候,乐观的(TL2)用tryLock,悲观的用lock,但是在没有冲突的时候,这两个的消耗是一样的啊!都是一个CAS。在NUMA系统上,都会逼迫CPU扔掉cache,强制刷store buffer。

事务下次再读这个变量的时候,略有区别。multiverse需要在本地的readset里面先查一遍,如果查到就用,就不必tryLock了。对mutilverse而言,如果一个事务所用到的变量的个数是不一定的(大多数情况都是如此),它会用一个Hash Table来管理这些变量。于是每次openForRead都会需要做一次hash查找。这个hash table采用的是闭散列,在冲突发生的上下位置找一个空的。

do {
           final int offset = goLeft ? -jump : jump;
           final int index = (hash + offset) % array.length;
 
           GammaRefTranlocal current = array[index];
           if (current == null) {
               array[index] = tranlocal;
               return;
           }
 
           final int currentHash = current.owner.identityHashCode();
           goLeft = currentHash > hash;
           jump = jump == 0 ? 1 : jump * 2;
       } while (jump < array.length);

很悲剧,这段代码有问题,那个index经常算出来是负数,于是在这里抛异常。如果你看出这段代码哪里有问题,请告诉我。我认为应该在index = (hash + offset) % array.length后面加上if(index<0) break;

然后比较写。无论以什么样的方式实现事务,它只有两种版本管理模式:

1、eager version management:直写型。必须要有undo log。(如XDB)

2、lazy version management:延迟更新。所有的修改在提交前都是针对当前事务私有的。(如Multiverse)

如果采用了第二种,那么当需要修改变量的某个字段的时候该怎么办?在Multiverse中,有两种选择:

1、把Object的所有字段都做成final的,压根不允许改。这些字段可以是基本类型,如int。也可以是任意的复杂类型,但是必须也是像这样的,不可被修改的,如String。但是这种方式会因为增加内存Copy次数而造成性能显著降低。否则为什么要有StringBuilder这个类?

2、把Object的每个字段都做成事务型的引用。但是这种方式会显著增加openForRead的调用次数。ArrayList、Hashmap等Collection都是采用这样的方式实现。否则对于size比较大的Collection,修改操作的代价简直巨大无比。

而xdb是直写型。直写型并不需要Object是像String那样的immutable的,但是写的时候还是有一个额外的开销,需要查一下事务本地的write set,如果已经有这个字段的undo log,那么就不要再写了。这个操作和multiverse的openForRead一样,也需要做hash查找(in Savepoint)。但是,亲爱的,你再仔细想一想,一个事务,是读的多,还是写的多?!

另外,如果是采用的直写型,那么我就不必做到字段级别。可以让几百KB的对象共用一个锁。无非就是rollback的时候需要多写一些嘛。可是亲爱的,rollback会经常发生吗?!

OK,总结一个Table,把各个操作最耗时的地方罗列出来:

XDB Multiverse STM
事务开始 基本不用做什么 读global clock
首次读 lock 查一次hash table,并且trylock
再次读 通常不用做什么 查一次hash table
首次写 查一次hash table,copy这个字段原有的值。 与读相同
再次写 查一次hash table 与读相同
commit 释放锁(很多个CAS) 很复杂。也是很多个CAS。
rollback 用日志做回滚 基本不用做什么
整体复杂度 给普通人解释不清楚

从这个表中看不出multiverse有什么性能优势。我越来越佩服lch,他真是个天才!

我现在暂时想不到怎么去除掉multiverse的那次讨厌的hash查找,既然Transaction做成ThreadLocal,那么把这个Hash Table调整的非常非常大,比如数组长度为10M,来存GammaRefTranlocal对象,避免动态的增长table,同时因为size比较大,查找速度也接近于O(1)。但是我看了一下,这家伙这真占内存啊,一个GammaRefTranlocal居然有14个字段。

总之无法避免的硬伤就是需要把同步的颗粒做的很细,因此会多带来很多倍的CAS消耗。比如我现在有一个二维数组(500x500)存地图数据,本来我只需要一个锁来管理它,但是现在,我需要25万个锁,遍历它的时候需要25万次CAS操作……肿么办!肿么办!我是哪里错了?

相关 [内存 选择 协议] 推荐:

内存事务如何选择加锁协议,乐观好还是悲观好?

- yuanxinz - Changming的blog
最近我用 Multiverse STM做了一点东西. 在开始动手之前,我专门测了multiverse的性能,发现它可以达到每秒2000多万次事务(每个CPU),于是我觉得它所带来的overhead应该是极小的,于是就放心大胆的用了. 可是后来用profile工具看,我的程序始终是在openForRead这样的函数上占据了绝大部分时间.

如何选择开源许可协议

- - 膘叔
如何为自己的项目选择一份开源许可协议. 什么GPL,LGPL,APACHE,MIT,BSD,等等,你都明白吗. 阮一峰在博客里这样写的:http://www.ruanyifeng.com/blog/2011/05/how_to_choose_free_software_licenses.html,他画了一个图,比较直观:.

小米智能家庭套装为什么选择 ZigBee 协议?

- - 极客公园-GeekPark
作者: Rubberso 在刚刚过去的 2015 年极客公园创新大会上,小米首次在非官方平台上发布了新款产品:小米智能家庭套装. 小米智能家庭套装由多功能网关、人体传感器、门窗传感器和无线开关四个产品组成,它们有一个共同的特点就是均支持 Zigbee 协议. 目前众多智能设备都采用了 Wifi 和蓝牙技术,小米为什么看上了并不是很主流 ZigBee 协议呢.

LLVM的调用协议与内存对齐

- chacoo - C++博客-首页原创精华区
在设计一门语言与其他语言交互的API与ABI(Application Binary Interface,二进制接口)时,调用协议和内存对齐是两个无从回避的问题. 本文将讨论如何在LLVM上生成正确的内存对齐和调用协议的代码. 在这里为了方便和标准起见,假定应用LLVM的语言的Extending和Embedding的对象都是C.

memcached协议

- - 开源软件 - ITeye博客
旧版: http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt. 新版: https://github.com/memcached/memcached/blob/master/doc/protocol.txt.

https协议

- - 互联网 - ITeye博客
SSL 协议的握手过程   .       为了便于更好的认识和理解 SSL 协议,这里着重介绍 SSL 协议的握手协议. SSL 协议既用到了公钥加密技术(非对称加密)又用到了对称加密技术,SSL对传输内容的加密是采用的对称加密,然后对对称加密的密钥使用公钥进行非对称加密. 这样做的好处是,对称加密技术比公钥加密技术的速度快,可用来加密较大的传输内容,公钥加密技术相对较慢,提供了更好的身份认证技术,可用来加密对称加密过程使用的密钥.

http2协议

- - 企业架构 - ITeye博客
http2协议的草案已经出来了,阅读了一下网上的中文版,http2尽可能的兼容http1.1. 改进了http1.1协议的不足. http1.0和http1.1的缺点:. 1.http1.0只允许在一个连接上建立当前未完成的请求. 2.http1.1管道只部分处理了请求并发和包头堵塞问题,客户端多建立TCP连接,减少延迟.

PPP协议

- - CSDN博客推荐文章
PPP(Point-to-Point Protocol点到点协议)是为在同等单元之间传输数据包这样的简单链路设计的链路层协议. 这种链路提供全双工操作,并按照顺序传递数据包.   PPP是目前使用最广泛的数据链路层协议,不管是低速的拨号猫连接还是高速的光纤链路,都适用PPP协议. 因特网用户通常都要连接到某个ISP 才能接入到因特网.

转载 选择

- bravusliu - caowumao的博客

CSS4 选择器

- iVane - 幸福收藏夹
CSS3 还没完全用上,CSS4 已经提上日程. 官方发布了 update to the working Selectors Level 4 spec,对选择器做了一些升级. 前端最大的优点就是技术更新快,可以经常学到新东西;最大的缺点也是技术更新快,要跟上潮流还真不是那么简单. 不过,这次更新有像“父选择器”这样让人兴奋的内容,让我们先睹为快,了解一下吧:.