分布式Map中实现引用计数

简介:

前言

在《 ReferenceCountSet无锁实现 》中,详细介绍了如何在一个进程中实现一个无锁版本的ReferenceCountSet(或者说是在自己的代码里没有锁),但是最近遇到一个问题,如果是在分布式的环境中呢?如何实现这个引用计数?这个问题如果从头开始写,会是一个比较复杂的问题,在实际中,我们可以使用ZooKeeper设置时的version机制来实现,即CAS(Compare-And-Set)。这是一个本人在实际项目中遇到的一个问题,但是会更简单一些,因为在我们的项目中,我们使用GemFire,即已经有一个现成的分布式Map了(在Gemfire中叫做Region),所以问题简化成如果如何使用一个分布式Map实现引用计数?

实现

如果对ConcurrentMap接口比较熟悉的话,这个其实是一个比较简单的问题。在ConcurrentMap中最主要的就是引入几个CAS相关的操作:
public  interface ConcurrentMap<K, V>  extends Map<K, V> {
    V putIfAbsent(K key, V value);
     boolean remove(Object key, Object value);
     boolean replace(K key, V oldValue, V newValue);
    V replace(K key, V value);
}
在《 ReferenceCountSet无锁实现 》中我们只需要使用putIfAbsent就可以了,剩下的实现可以交给AtomicInteger提供的CAS来实现,因为它是在同一个进程中,但是如果在分布式的环境中就不能使用这个AtomicInteger,这个时候应该怎么办呢?其实这个时候我们就可以求助于replace方法了。replace方法的注释中这样描述:
     /**
     * Replaces the entry for a key only if currently mapped to a given value.
     * This is equivalent to
     * <pre>
     *   if (map.containsKey(key) &amp;&amp; map.get(key).equals(oldValue)) {
     *       map.put(key, newValue);
     *       return true;
     *   } else return false;</pre>
     * except that the action is performed atomically.
     *
     * 
@param  key key with which the specified value is associated
     * 
@param  oldValue value expected to be associated with the specified key
     * 
@param  newValue value to be associated with the specified key
     * 
@return  <tt>true</tt> if the value was replaced
     * 
@throws  UnsupportedOperationException if the <tt>put</tt> operation
     *         is not supported by this map
     * 
@throws  ClassCastException if the class of a specified key or value
     *         prevents it from being stored in this map
     * 
@throws  NullPointerException if a specified key or value is null,
     *         and this map does not permit null keys or values
     * 
@throws  IllegalArgumentException if some property of a specified key
     *         or value prevents it from being stored in this map
     
*/
     boolean replace(K key, V oldValue, V newValue);

在ConcurrentMap的value中我们只需要给Integer,然后用replace去不断的尝试,即自己实现一个CAS:
private  int incrementRefCount(Object key) {
     do {
        Integer curCount = distributedMap.get(key);
         if (curCount ==  null) {
            curCount = distributedMap.putIfAbsent(key,  new Integer(1));
             if (curCount ==  null) {
                 return 1;
            }
        }
        
        Integer newCount =  new Integer(curCount.intValue() + 1);
         if (distributedMap.replace(key, curCount, newCount)) {
             return newCount;
        }
    }  while ( true);
}

主要逻辑就是这样了,其实比较简单,只是之前没有遇到过这个问题,所以感觉可以记录下来。或许什么时候补充一下ZooKeeper版本的实现。

相关文章
|
存储 算法 Java
HashMap 之底层数据结构和扩容机制
HashMap 之底层数据结构和扩容机制
976 1
|
存储 算法 安全
HashMap底层实现原理
HashMap底层实现原理
168 0
|
1月前
|
存储 Java Serverless
HashMap的底层数据结构是怎样的
在Java中,HashMap是一种基于哈希表的Map接口实现,以其高效的数据存取能力而广泛使用。本文将深入探讨HashMap的底层数据结构,揭示其如何通过数组、链表和红黑树的结合来优化性能。
|
1月前
|
存储 Java Serverless
HashMap的底层数据结构
HashMap作为Java中一个核心的数据结构,以其高效的键值对存储和检索能力而被广泛使用。本文将深入探讨HashMap的底层数据结构,揭示其如何通过精巧的设计实现快速的数据访问。
30 6
|
29天前
|
存储 Java
HashMap的底层数据结构详解
在Java中,HashMap 是一个非常重要的集合类,用于存储键值对(Key-Value)。它提供了快速的数据插入、删除和查找功能。本文将深入探讨 HashMap 的底层数据结构,帮助读者更好地理解其工作原理。
|
3月前
|
设计模式 安全 Java
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
假如有T1、T2两个线程同时对某链表扩容,他们都标记头结点和第二个结点,此时T2阻塞,T1执行完扩容后链表结点顺序反过来,此时T2恢复运行再进行翻转就会产生环形链表,即B.next=A;采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。JDK8中,HashMap采用尾插法,扩容时链表节点位置不会翻转,解决了扩容死循环问题,但是性能差了一点,因为要遍历链表再查到尾部。例如15(即2^4-1)的二进制为1111,31的二进制为11111,63的二进制为111111,127的二进制为1111111。
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
|
3月前
|
存储 算法 Java
深入剖析HashMap:理解Hash、底层实现与扩容机制
【9月更文挑战第6天】在Java编程中,`HashMap`是一个常用的数据结构,其高效性和可靠性依赖于深入理解哈希、底层实现及扩容机制。哈希通过散列算法将键映射到数组索引,采用链表或红黑树处理冲突;底层实现结合数组与链表,利用2的幂次方长度加快定位;扩容机制在元素数量超过负载因子与数组长度乘积时触发,通过调整初始容量和负载因子可优化性能。
118 3
【数据结构】红黑树封装map和set(上)
【数据结构】红黑树封装map和set(上)
|
7月前
|
存储 Java Serverless
谈谈我对HashMap扩容机制的理解及底层实现
谈谈我对HashMap扩容机制的理解及底层实现
|
7月前
|
存储 编译器 测试技术
红黑树封装实现STL-map、set
红黑树封装实现STL-map、set