(本文作者温少,首发于博客园,转载请注明)

非阻塞算法的关键思想就是CAS,CAS是compare and set的缩写,也常被称为lock-free或者wait-free,通过把compare和set两个操作原子化,使得不需要使用锁,但是能够解决并发 中的资源争用问题。由于CAS常常是一个回退算法+死循环,所以又被称为spin-lock。由于CAS没有使用锁,线程持续执行,又称为非阻塞算法 (non-blocking)。术语不统一,但是都差不多表示同一个东西,我都列在这里,方便大家理解。

CAS通常并发性能会更好,原因有二:
1、CAS由硬件提供指令支持
2、整个思路属于乐观锁定,而不同于其他类型的锁所采用的悲观锁定,大多数并发程序,冲突发生时间较少,所以乐观锁定更高效。

非 阻塞算法是当前的一个研究热点,也越来流行。其显著的优势在于避免了锁带来的问题,而其主要缺点在于与等价的有锁算法比较而言,非阻塞算法的实现要复杂一 些。在Java中,doug lea为我们带来util.concurrent包,CAS在整个并发框架中深入应用,不单提高了效率(atomic),而且提高了接口可用性(例如 CurrentMap的putIfAbsent)。

有人说,CAS这种技术底层框架提供,不需要了解,其实不然,CAS思想可以应用任何地方,包括数据结构、服务接口、数据库应用等等。我这篇文章要讲的内容就是在关系数据库应用中使用CAS思想。

闲话少说,言归正传!

关 系数据库数据库提供了"update T set FState = xx where FState = xx",执行这样的SQL,会返回一个更新行数,在jdbc或者odbc或者ADO .NET中都可以获得更新行数。上面的SQL,如果更新行数>0,则是更新成功,否则是没有进行任何更新,这是很典型的CAS。可以说,关系数据库 原生支持CAS。

例如,现在有一个表:
Create Table T_COUNTER (FName VARCHAR, FCOUNT INT)

这个表存储一些计数器,程序需要对其中的一个计数器进行increment的操作,实现如下:
// incremnt的实现算法在这个方法里
public int getAndIncrement(String name) {
    
for (;;) {
        
int expectValue = getCurrentValue((name);
        
int updateValue = expectValue + 1;
        
if (updateCounter(name, expectValue, updateValue)) return expectValue;
    }
}

public boolean updateCounter(String name, int expectValue, int updateValue) {
    String sql 
= "UPDATE T_COUNTER SET FCOUNT = @updateValue WHERE FName = @name AND FCOUNT = @expectValue";
    
int updateCount = executeUpdate(sql);
    
return updateCount > 0;
}

public int getCurrentValue((String name) {
    
// SELECT FCOUNT FROM T_COUNTER WHERE FNAME = @name
    
// TODO 执行这段SQL,返回FCOUNT的值
    return 0;
}

private int executeUpdate(String sql) {
    // TODO 执行SQL,返回更新行数
    return 0;
}


这 样的实现,避免SQL Server中使用locking hints,Oracle、DB2、MySQL中使用select for update长时间锁定T_COUNTER表,性能更好,也更通用。要知道使用locking hints,不同厂商的数据库的实现是不一样的,Oracle和Microsoft SQL Server就相差很大。

这样做的优点:
1、性能更好
2、锁表时间更短
3、基于标准SQL,不同的关系数据库通用
4、上述实现并不复杂

(本文作者温少,首发于博客园,转载请注明)
posted on 2007-11-13 06:33 温少的日志 阅读(1440) 评论(4)  编辑  收藏
Comments
  • # re: 非阻塞算法思想在关系数据库应用程序开发中的使用
    liigo
    Posted @ 2007-11-13 13:59
    for (;;) {
    int expectValue = getCurrentValue((name);
    int updateValue = expectValue + 1;
    if (updateCounter(name, expectValue, updateValue)) break;
    }

    以上代码中,如果有其它线程在getCurrentValue()之后修改了计数值(FCOUNT),则期望值(expectValue)永远不满足,updateCounter()总是返回假,死循环了……

    不知道理解的对不对,请指正  回复  更多评论   
  • # re: 非阻塞算法思想在关系数据库应用程序开发中的使用
    sitinspring
    Posted @ 2007-11-13 19:08
    留个记号先.  回复  更多评论   
  • # re: 非阻塞算法思想在关系数据库应用程序开发中的使用
    温少的日志
    Posted @ 2007-11-13 21:34
    @liigo,我改了一下示例代码,不过意思还一样的。
    回答你的问题,通常都是执行一次就会退出循环了  回复  更多评论   
  • # re: 非阻塞算法思想在关系数据库应用程序开发中的使用
    wd
    Posted @ 2007-11-14 12:56
    这不就是hibernate中乐观锁的实现吗?

    很好的文章,终于搞清楚CAS是什么意思了,多谢多谢哦:)  回复  更多评论   

只有注册用户登录后才能发表评论。


网站导航: