0

我正在阅读不同的并发模型和不同的并发特性,但没有文字谈论如何实现简单的 MVCC 数据结构。假设我必须实现一个简单的基于数组的数据结构,它提供基于 MVCC 的并发性。我的代码应该是什么样子?

我理解MVCC基本上意味着:(多版本并发控制)

1) 读隔离——你的写不应该阻塞读

2) 基于时间戳的排序,用于建立先发生关系/排序。

我需要记住任何其他方面吗?

此外,我下面的代码处理第一个要求,但如何实现时间戳排序?

class MVCCArray{

    private int[] arr;

    MVCCArray(int n){
        arr = new int[n];
    }


    //unblocking reads
    public int getItem(int index){
        return arr[index];
    }

    //blocking writes
    public synchronized void setItem(int index, int value){
        arr[index]=value;
    }

}


PS:我想了解它是如何以通用方式实现的。请不要解释它是如何在特定数据库中实现的。

4

1 回答 1

1

我在模拟中编写了一个多版本并发实现请参阅模拟运行器。我的模拟模拟了 100 个线程,它们都试图读取和写入两个数字 A 和 B。它们希望将数字增加 1。我们在模拟开始时将 A 设置为 1,将 B 设置为 2。

期望的结果是在模拟结束时 A 和 B 应设置为 101 和 102。只有在由于多版本并发控制而存在锁定或序列化时才会发生这种情况。如果您没有并发控制,由于数据争用,此数字将小于 101 和 102。

当线程读取 A 或 B 时,我们会遍历密钥 A 或 B 的版本以查看是否存在 <= transaction.getTimestamp() 的版本。如果成功,它将将该值的读取时间戳设置为最后读取该值的事务。rts.put("A", 交易)

在提交时,我们检查rts.get("A").getTimestamp() < committingTransaction.getTimestamp()。如果此检查为真,我们将中止事务并重试。

我们还检查是否有人在事务开始后提交——我们不想覆盖他们的提交。

平均而言,系统在大约 4000-11000 次交易中止后达到 101 和 102。

于 2021-06-22T16:51:32.650 回答