分布式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版本的实现。

相关文章
|
7月前
|
存储 Java
map中存储的是引用,而不是对象本身
该内容是关于Java编程中验证Map存储引用而非复制对象的示例。创建大型List导致内存增加,说明List确实占用空间。通过Person类示例,将不同对象放入Map,改变一个对象的属性后,比较原对象与Map中的键值对,发现两者相等,证明Map保存的是对象引用。
103 5
|
7月前
|
NoSQL API Redis
数据对象的底层实现方式你都了解吗?
上一小节我们提到的五种数据类型其实就是 Redis 的数据对象,我们先来看看数据对象的类型:Redis 的 key 都是 string 类型的,以上各类型说的其实都是 value 的类型,以下是对象的几个优点:
58 0
数据对象的底层实现方式你都了解吗?
|
存储 算法 Java
HashMap 之底层数据结构和扩容机制
HashMap 之底层数据结构和扩容机制
931 1
|
6月前
|
算法 Java 程序员
Python内存管理用引用计数(对象的`ob_refcnt`)跟踪对象,但循环引用(如A-&gt;B-&gt;A)可导致内存泄漏。
【6月更文挑战第20天】Python内存管理用引用计数(对象的`ob_refcnt`)跟踪对象,但循环引用(如A-&gt;B-&gt;A)可导致内存泄漏。为解决此问题,Python使用`gc`模块检测并清理循环引用,可通过`gc.collect()`手动回收。此外,Python结合标记清除和分代回收策略,针对不同生命周期的对象优化垃圾回收效率,确保内存有效释放。
46 3
|
存储 安全 Java
HashMap底层结构、扩容机制实战探索
HashMap底层结构、扩容机制实战探索
HashMap底层结构、扩容机制实战探索
|
7月前
|
存储 NoSQL 关系型数据库
图解 Redis String 底层数据结构 SDS 与计数器实战
图解 Redis String 底层数据结构 SDS 与计数器实战
365 0
|
7月前
|
机器学习/深度学习 索引
认真研究HashMap的初始化和扩容机制
认真研究HashMap的初始化和扩容机制
208 0
|
存储 Java 对象存储
一文搞清楚ES6新增数据结构 Symbol Map WeakMap Set WeakSet(二)
一文搞清楚ES6新增数据结构 Symbol Map WeakMap Set WeakSet
122 0
再谈HashMap:使用map优化代码,你得学我这样做
我并没有和HashMap杠上,想着重新开始写点技术的东西,就拿HashMap开头了。最近开始重新学习数据结构和算法,其中有些东西学完之后,对于HashMap的理解和运用又有新的认识。虽然之前运用HashMap也有这样用过,但是知道了方法论,才发现这样使用的好处。 上一期我写过HashMap,写的是JDK8之前的Hash,现在都JDK15了,大家有兴趣可以去看一下源计划之从HashMap认识数据结构
|
存储 缓存 Java
Java内存缓存-通过Map定制简单缓存
缓存 在程序中,缓存是一个高速数据存储层,其中存储了数据子集,且通常是短暂性存储,这样日后再次请求此数据时,速度要比访问数据的主存储位置快。通过缓存,可以高效地重用之前检索或计算的数据。 为什么要用缓存 场景 在Java应用中,对于访问频率高,更新少的数据,通常的方案是将这类数据加入缓存中,相对从数据库中读取,读缓存效率会有很大提升。
1919 0