Zim*_*oot 4 java algorithm multithreading snapshot data-structures
我正在尝试创建一个ConcurrentHashMap支持“快照”的迭代器，以提供一致的迭代器，并且想知道是否有更有效的方法来做到这一点。问题是，如果同时创建两个迭代器，那么它们需要读取相同的值，而并发哈希映射的弱一致迭代器的定义并不能保证这种情况。如果可能的话，我还想避免锁定：地图中有数千个值，处理每个项目需要几十毫秒，并且我不想在这段时间内阻止写入者，因为这可能会导致写入者阻塞一分钟或更长时间。
到目前为止我所拥有的：
ConcurrentHashMap's是字符串，其值是实例ConcurrentSkipListMap<Long, T>putIfAbsent，会分配一个新的跳表，并通过 来添加该对象skipList.put(System.nanoTime(), t)。map.get(key).lastEntry().getValue()返回最新值。要查询快照（例如使用迭代器），我使用map.get(key).lowerEntry(iteratorTimestamp).getValue()，其中是初始化迭代器时调用iteratorTimestamp的结果。System.nanoTime()map.get(key).put(timestamp, SnapShotMap.DELETED)，其中 DELETED 是静态最终对象。问题：
ConcurrentHashMap合适ConcurrentSkipListMap更合适？我的键是可比较的，因此也许某种并发树比并发哈希表更好地支持快照。我该如何防止这个东西继续增长？在 X 上或之前初始化的所有迭代器完成后，我可以删除键小于 X 的所有跳过列表条目（映射中的最后一个键除外），但我不知道有什么好方法来确定何时已经发生了这种情况：当迭代器的方法返回 false 时，我可以标记该迭代器已完成hasNext，但并非所有迭代器都一定会运行完成；我可以将 a 保留WeakReference为迭代器，以便可以检测它何时被垃圾收集，但除了使用一个迭代弱引用集合然后休眠数次的线程之外，我想不出一个好的方法来检测它。分钟 - 理想情况下，线程会阻塞WeakReference，并在包装的引用被 GC 时收到通知，但我不认为这是一个选项。
ConcurrentSkipListMap<Long, WeakReference<Iterator>> iteratorMap;
while(true) {
long latestGC = 0;
for(Map.Entry<Long, WeakReference<Iterator>> entry : iteratorMap.entrySet()) {
if(entry.getValue().get() == null) {
iteratorMap.remove(entry.getKey());
latestGC = entry.getKey();
} else break;
}
// remove ConcurrentHashMap entries with timestamps less than `latestGC`
Thread.sleep(300000); // five minutes
}
编辑：为了消除答案和评论中的一些混乱，我目前正在将弱一致性迭代器传递给公司另一个部门编写的代码，他们要求我增加迭代器一致性的强度。他们已经意识到我不可能做出 100% 一致的迭代器，他们只是希望我尽最大努力。他们更关心吞吐量而不是迭代器一致性，因此粗粒度锁不是一个选择。
您需要特殊实现的实际用例是什么？来自ConcurrentHashMap的 Javadoc （强调部分已添加）：
检索反映了最近完成的更新操作在其开始时的结果。...迭代器和枚举返回反映迭代器/枚举创建时或创建后某个时刻哈希表状态的元素。它们不会抛出 ConcurrentModificationException。然而，迭代器被设计为一次只能由一个线程使用。
所以常规的ConcurrentHashMap.values().iterator()将为您提供一个“一致”的迭代器，但仅供单个线程一次性使用。如果您需要多次和/或通过多个线程使用相同的“快照”，我建议制作地图的副本。
编辑：根据新信息和对“强一致”迭代器的坚持，我提供了这个解决方案。请注意，使用 ReadWriteLock 具有以下含义：
一致性是通过序列化写入并在每次写入时复制当前值来实现的。持有对“过时”快照的引用的读者可以继续使用旧快照，而不必担心修改，并且一旦没有人再使用旧快照，垃圾收集器就会回收旧快照。假设没有要求读者
由于快照可能在多个并发线程之间共享，因此快照是只读的且无法修改。此限制也适用于从快照创建的remove()任何实例的方法。Iterator
import java.util.*;
import java.util.concurrent.locks.*;
public class StackOverflow16600019 <K, V> {
private final ReadWriteLock locks = new ReentrantReadWriteLock();
private final HashMap<K,V> map = new HashMap<>();
private Collection<V> valueSnapshot = Collections.emptyList();
public V put(K key, V value) {
locks.writeLock().lock();
try {
V oldValue = map.put(key, value);
updateSnapshot();
return oldValue;
} finally {
locks.writeLock().unlock();
}
}
public V remove(K key) {
locks.writeLock().lock();
try {
V removed = map.remove(key);
updateSnapshot();
return removed;
} finally {
locks.writeLock().unlock();
}
}
public Collection<V> values() {
locks.readLock().lock();
try {
return valueSnapshot; // read-only!
} finally {
locks.readLock().unlock();
}
}
/** Callers MUST hold the WRITE LOCK. */
private void updateSnapshot() {
valueSnapshot = Collections.unmodifiableCollection(
new ArrayList<V>(map.values())); // copy
}
}
| 归档时间： |
|
| 查看次数： |
4565 次 |
| 最近记录： |