java - 在Java中构建 "isolated"和 "automatically updated"缓存(java.util.List)

Question

对于任何感兴趣的人:我已经实现了我正在寻找的行为的代码，并将其在谷歌代码上开源。在这里得到它! pojo-mvcc

--

大家好，

我正在尝试编写一个框架，其中包含许多从长期缓存创建的短期缓存。这些短期缓存需要能够返回其完整内容，这是原始长期缓存的克隆。

实际上，我正在尝试为短期缓存构建一定程度的事务隔离。用户应该能够修改短期缓存的内容，但不应传播对长期缓存的更改(也存在应推送更改的情况，具体取决于缓存类型)。

我会尽力尝试解释:

主缓存包含:[A、B、C、D、E、F]使用状态 [A,B,C,D,E,F] 创建的临时缓存

1) 临时缓存添加项目 G: [A,B,C,D,E,F]2) 临时缓存删除项目 B: [A,C,D,E,F]

主缓存包含:[A、B、C、D、E、F]

3) 主缓存添加项目 [X,Y,Z]: [A,B,C,D,E,F,X,Y,Z]

临时缓存包含:[A,C,D,E,F]

当项目中的值可以更改并且不应该总是更新时，事情会变得更加困难(因此我什至无法共享底层对象实例，我需要使用克隆)。

我已经实现了一种简单的方法，即使用 ArrayList 上的标准 Collection 构造函数创建一个新的 List 实例，但是当您达到大约 200,000 个项目时，系统就会耗尽内存。我知道 200,000 的值对于迭代来说太大了，但我试图稍微强调一下我的代码。

我原以为它可能能够以某种方式“代理”列表，因此临时缓存使用主缓存，并存储所有更改(实际上是更改的备忘录)，但这很快就变成了当您想要迭代临时缓存或检索特定索引处的项目时，这是一场噩梦。另外，考虑到我希望对列表的内容进行一些修改(取决于临时缓存的类型，无论它是否是“自动更新”)，我完全超出了我的能力范围。

任何指向技术或数据结构或只是尝试和研究的一般概念的指示都将不胜感激。

干杯，

艾多斯

Answer 1

这就是您想要执行的操作。类似于所谓的 MVCC(多版本货币控制)。

简单地说，您需要将事务 ID 与缓存元素相关联。

所以缓存条目看起来像这样:

public class CacheEntry {
    long transactionId;
    boolean deleted;
    Object value;
}

您的缓存条目以相反的 transactionid 顺序存储在列表中。

当您获取缓存元素时，您会查找列表(在 HashMap 中)。然后，您搜索具有小于或等于您的交易的交易 ID 的最高交易 ID 的值。

所以，让我们考虑一下 DELETE 问题。

您有事务 10，正在寻找“ABC”。我们假设 ABC 已经在缓存中，并且是由事务 5 放入的。

因此，T10 获取 ABC 的条目列表，向下搜索列表并发现在 T5 处有值“123”。 T5是小于或等于T10的最高交易。 T10 将 ABC 的值从 123 更改为 456。

现在 T12 出现了，它正在寻找 ABC。它会从 T10 中找到该值为 456。 T12决定删除ABC，因此T12的“已删除”缓存条目被放置在缓存条目列表中。如果T10再次尝试查找ABC，它会找到456，因为12 > 10，并且最高事务<= 10是T10，所以它看不到删除。

T14出现，搜索ABC，找不到它(因为它被“删除”)，并插入一个新值789。如果T12查找，它仍然会被删除，如果T10查找，它仍然是456 .

所以，最后，您的缓存列表如下所示:

{tid: 14 deleted: false value: 789}
{tid: 12 deleted: true  value: nul}
{tid: 10 deleted: false value: 456}
{tid:  5 deleted: false value: 123}

您遇到的下一个问题是处理开放事务中的可见性。即另一个事务可以看到来自另一个未提交的打开事务的数据。但这并不太难，因为它只是在扫描版本列表以寻找合适的候选者时调整标准。您还可以保留事务 ID 列表及其状态(打开、已提交、回滚)。

最后你必须想出一个机制来清理 Unresolved 问题。提交两个事务后，如果没有其他打开的事务，则可以删除较旧的记录。

例如，如果您拥有来自 T5 和 T10 的数据，如果两者都已提交，则没有人能够再次“查看”T5 的数据，因为 T10 的数据现在是“当前”状态。所以，T5行可以删除。

这可能最好通过简单地迭代缓存并删除过时的事务条目来完成。

这就是要点，显然细节决定成败。