STL

STL是标准模板库。

vector

本质上就是一个数组，但是它比数组更加地好用，提供了很多实用的接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 定义一个vector
#include<vector>
vector<int> vec;

// 在尾部追加一个元素
vec.push_back(1);

// 删除尾部的元素
vec.pop_back();

// 获得vector存储数据的长度
cout<<vec.size()<<endl;

// 清空
vec.clear();

1
2
3
4
5
6
7
8
9
10
11

// 遍历
for(int i=0; i<vec.size(); i++){
    cout<<vec[i]<<endl;
}

// 迭代器 iterator
// 可以把迭代器当成一个可以移动的指针，它指向容器当中的一个元素
vector<int>::iterator it;
for(it=vec.begin(); it!=vec.end(); it++){
    cout<<(*it)<<endl;
}

1
2
3
4
5
6
7
8
9

// 插入 我们需要用到迭代器
// 在下标为2的位置插入10
vec.insert(vec.begin()+2, 10);

// 删除 
// 删除单个元素
vec.erase(vec.begin()+2);
// 删除一个区间内的元素
vec.erase(vec.begin()+2, vec.begin()+4); // [2, 4)

emplace_back()

在使用push_back函数往容器中增加新元素时，必须要有一个该对象的实例才行，而emplace_back可以不用，它可以直接传入对象的构造函数参数直接进行构造，减少一次拷贝和赋值操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class stu_info {
private:
    string name;
public:
    stu_info(const string &name) {
        this->name = name;
        cout << "stu_info(): " << this->name << endl;
    }
 
    ~stu_info() {
        cout << "~stu_info(): " << this->name << endl;
    }
 
    stu_info(const stu_info &s) {
        this->name = s.name;
        cout << "copy constructor: " << this->name << endl;
    }
};

1
2

vector<stu_info> v;
v.emplace_back("redis");

set

set是集合，是一个内部自动有序且不含重复元素的容器。

set的定义：

1
2

set<int> st; // 保存int类型的set
set<Node> st2; // 保存Node结构体类型的set

set只能通过迭代器访问：

1
2
3
4
5
6

set<int>::iterator it;
// 因为除了vector和string之外的STL容器都不支持*(it+i)的访问形式
// 只能按如下方式枚举
for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
    printf("%d\n",*it);
}

插入：

1
2

int x = 1
st.insert(x); // 将x插入，并自动排序和去重

查找：

1

set<iterator>::iterator it = st.find(1); // 查找1，返回迭代器

删除：

1
2
3
4
5
6
7

st.erase(it);// it为要删除元素的迭代器
st.erase(st.find(100)); //找到100的迭代器，然后删除100

st.erase(100); //删除100

// erase可以删除一定区间内的元素
st.erase(st.find(100), st.end()); // 删除100到set末尾之间的元素

元素个数：

1

cout<<st.size()<<endl;

清空元素：

1

st.clear();

emplace()

当使用插入时，我们创建一个对象，然后将其插入到多集中。使用emplace()，该对象就地构建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// C++ code to demonstrate difference between 
// emplace and insert 
#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    // declaring set 
    set<pair<char, int>> ms; 
      
    // using emplace() to insert pair in-place 
    ms.emplace('a', 24); 
      
    // Below line would not compile 
    // ms.insert('b', 25);     
      
    // using emplace() to insert pair in-place 
    ms.insert(make_pair('b', 25));     
      
    // printing the set 
    for (auto it = ms.begin(); it != ms.end(); ++it) 
        cout << " " << (*it).first << " " 
             << (*it).second << endl; 
  
    return 0; 
}

swap()

1

s1.swap(s2);  //交换两集合

string

可以通过下标访问和通过迭代器访问：

1
2
3
4
5
6
7
8
9

string str = "abcd";

// 下标访问
cout<<str[1]<<endl;

// 迭代器访问
for(string::iterator it=str.begin(); it!=str.end(); it++){
    printf("%c", *it);
}

1
2
3

// +号可以连接字符串
// =号 字符串赋值，
// < > != == 号 字符串比较

字符串长度

1

printf("%d %d\n", str.length(), str.size()); //两个都一样

插入：

1
2
3

int pos;
int s;
str.insert(pos, s); //pos号位置插入s字符串

删除：

1
2
3
4
5
6
7
8

// 通过迭代器删除单个元素
str.erase(str.begin()+4); // 删除下标为4的元素

// 删除[first, last)区间内所有的元素,first为首元素迭代器，last为末尾迭代器
str.erase(str.begin()+2, str.end()); // 从2号元素删除到最后

// 删除从下标2开始的5个元素
str.erase(2, 5);

清空：

1

str.clear();

子串：

1
2
3

int pos=2;
int len =5;
str.substr(pos, len);// 返回从2开始的长度为5的子串

查找：

1
2
3
4
5
6
7
8
9

string str2;
int pos;
//从pos位置开始找子串，返回第一个找到的子串的下标
// 如果没有找到，返回string::npos（这是在string中定义的常量）
// 比如:str="abcd abcd abcd", str2="abcd"
//  str.find(str2, 4)会返回5
if(str.find(str2, pos) != string::npos){
    cout<<str.find(str2)<<endl;
}

替换:

1
2
3
4
5

int pos = 3;
int len = 5;
string str2;
// str中从pos开始的len长度的子串替换为str2
str.replace(pos, len, str2);

map

map是映射，定义了从一个key到value的映射，其中map中保存的所有key, value对中，key不能重复，但是value可以重复

1

map<typename1, typename2> mp; // 从typename1类型到typename2类型的映射

1
2

map<string, int> mp; // 从string类型的key到int类型的value的映射
map<int, int> mp2; // 从int类型的key到int类型的value的映射

访问:

1
2
3
4
5
6
7
8
9
10

// 下标访问
map<char, int> mp;
mp['c'] = 20; // 保存从'c'到20的映射
mp['c'] = 30; // 20被覆盖
printf("%d\n", mp['c']); // out: 30

// 迭代器访问
for(map<char, int>::iterator it=mp.begin(); it!=mp.end(); it++){
    printf("the key is %c, the value is %d\n", it->first, it->second);
}

查找：

1
2
3
4

// find返回对应key value对的迭代器
// 查找key为'c'的key value对的迭代器
map<char, int>::iterator it = mp.find('c'); 
cout<<it->first<<" "<<it->second<<endl;

删除：

1
2
3
4
5
6
7
8

// 迭代器删除单个元素
// erase返回下一个元素的迭代器
map<char, int>::iterator it = mp.find('b');
map<char, int>::iterator it2 = mp.erase(it); // 删除key为'b'的key value对

// 通过key删除
map<char, int>::iterator it2 = mp.erase('b'); // 删除key为'b'的key value对

map长度

1
2

// size函数获取mp的key value对个数
cout<<mp.size()<<endl;

priority_queue

https://www.cnblogs.com/yalphait/articles/8889221.html

右值引用与移动构造

参考：[c++11]我理解的右值引用、移动语义和完美转发

引用

http://www.cplusplus.com/reference/

论文网址

https://hpides.github.io/viper/

介绍

However, simply drop-in replacing existing storage with PMem does not yield good results, as block-based access behaves differently in PMem than on disk and ignores PMem’s byte addressability, layout, and unique performance characteristics.

要解决如何正确地将KV持久化到PM中；要利用好字节存取能力和它特殊的性能特征。

In this paper, we propose three PMem-specific access patterns and implement them in a hybrid PMem-DRAM KVS called Viper.

三种访问模式；hybrid PMem-DRAM KVS

We employ a DRAM-based hash index and a PMem-aware storage layout to utilize the random-write speed of DRAM and efficient sequential-write performance PMem.

将Hash索引存储到DRAM中，因为DRAM的随机写性能很好；再利用PM的很好的顺序写性能。

“我感觉这篇文章比较有意思的点在与它通过存储布局设计把不同threads的读写操作都尽量均衡的分配到了不同的DIMM上，并且把粒度（VPage）设为4kb（实测中这样的offset在顺序写时候Latency最低），Viper没有做缓存设计（因为实际测试中DRAM和PMem的顺序写入的Latency差不多）”

讨论

由于这篇论文应用了PM的顺序写性能，而且openGauss的日志也是顺序写的，因此可以参考这篇论文来探讨如何将PM应用于openGauss的日志系统。

在spitfire论文中，探讨了dram-pm-ssd的三层存储结构，其实在openGauss中应该也可以用这种结构来实现日志系统。如果单纯地使用PM持久化日志，由于日志过于庞大，全部存储在PM中不太合适，我想最终还是要dump到磁盘当中的。

引用

Tidb中文简介：https://link.zhihu.com/?target=https%3A//pingcap.com/docs-cn

Tidb最佳实践等ppt: https://eyun.baidu.com/s/3huniXE0?errmsg=Auth+Login+Sucess&errno=0&ssnerror=0&#sharelink/path=/

开源项目地址：https://github.com/pingcap/tidb

校园地助学贷款简介

本专科贷款金额不超过12000元，研究生不超过16000元。

网址

https://zizhu.ecnu.edu.cn/Notice/Details/2080

申贷流程概述

9月9日-9月18日，领取《借款凭证》与办理银行卡（如果没有上海市中国银行一类卡，才去办理银行卡），到大学生活动中心504整。

9月27日-10月9日，贷款办网站（华东师范大学资助网站）填写相关材料，自行打印。为什么这么晚，因为要等到困难认定结果出来。

10月18日-10月21日，到贷款办递交相关材料，签订合同。

12月上旬，贷款到校。

贷款办网站填写指南

这里联系人不能写父母，只能写朋友亲戚。

关于有邮箱，最好不要填学校邮箱，填QQ邮箱

贷款的还款

https://zxjcarrot.github.io/publication/spitfire/spitfire.pdf

introduction

our approach

Since the CPU is capable of directly operating on NVM-resident data, Spitfire does not eagerly move data from NVM to DRAM. We show that lazy data migration from NVM to DRAM ensures that only hot data is promoted to DRAM.

要决定怎么eager，怎么lazy。

background

NVM-aware Optimizations in Hymem

Data Migration Policy

the four critical decisions in the data migration policy adopted by Hymem include: DRAM admission, DRAM eviction, NVM admission, and NVM eviction：

1. dram admission：数据要么从NVM读到DRAM，要么从SSD读到DRAM；
2. DRAM eviction：解决数据要evict的话，要evict到NVM还是SSD。
   如果page在admission queue里面，则从admission queue中删除这个page，然后将page放到NVM中；
   否则，将page加入到admission queue中，然后evict到SSD中。

Cache-line-grained Loading

我们使用一个DRAM page来存储正在访问的NVM page，但并不是把这个NVM page的所有cache line都加载进来。在DRAM page中有header，存储page的元信息，其中resident表示DRAM page中256个cache line中第几个是已经从NVM page的对应cache line加载进来的，nvm表示这个DRAM page对应哪个NVM page；接下来，有256个cache line，至于哪些是从NVM page加载进来的，这要看resident位了。以上就是所谓的cache-line-grained page。

如果只加载了NVM page中的很少几个cache line怎么办，不能这样DRAM page中的256个cache line中会剩下很多cache line没有用，造成了空间浪费，于是我们决定使用mini page，只有16个cache line，只存储加载进来的cache line，比如figure 2(b)中，count=3表示目前只加载了3个cache line，slots数组中存储了这个3个cache line分别对应NVM page中的哪些cache line。

NVM-Aware Data Migration

Once a page is selected for eviction or promotion, Spitfire uses the probabilistic data migration policy for determining the storage tier to which the page must be migrated.

spitfire相对于Hymem的不同点是它采用概率技术来决定当要evit的时候，到底evict到哪里。

We now describe how Spitfire leverages the additional data flow paths introduced by NVM (❼,❽,❾,❿) to minimize the performance impact of NVM and to extend the lifetime of the NVM and SSD devices:

1. 最小化NVM的performance impact，也就是最大化发挥NVM的性能优势
2. 提高SSD和NVM的使用寿命

之后介绍的data migration是基于两个原则的：

1. 不要破坏DRAM中原有的热数据
2. 不要破坏NVM中原有的温数据

Bypass DRAM during Reads(Dr)

Let Dr represent the probability that Spitfire moves data from NVM to DRAM during read operations.

在读数据的时候有好几种可能（不包括CPU cache）：

1. 直接在DRAM中找到数据
2. 如果在DRAM中找不到 并且 在NVM中找到了，就把数据从NVM迁移到DRAM（对应figure3 的2路径）
3. 如果在DRAM中找不到 并且 在NVM中找到了，就直接读取数据（对应figure3中的7路径）
4. 如果在DRAM中找不到 并且 在NVM中找不到，就把数据从SSD中迁移到NVM（对应figure3中的1路径）
5. 如果在DRAM中找不到 并且 在NVM中找不到， 就把数据从SSD中迁移到DRAM（对应figure3中的9路径）

下图是读数据的路线图。

Dr的数值对应的就是figure3中路径2的概率，也即把数据从NVM迁移到DRAM的概率。如果Dr是1，那就意味着eager migration，每次都要经过DRAM；“when Dr = 0.01, Spitfire moves a page from NVM to DRAM only once every hundred times，Otherwise, it directly serves the read operation using the page residing on NVM”

They are beneficial when the capacity of DRAM is smaller than that of NVM. A lazy migration strategy ensures that warm pages on NVM do not evict hot pages in DRAM.

那么这个Dr就是一个参数了，需要调优，怎么调整才好呢？文章中的思想是采用机器学习的思路，也就是让set fits within DRAM的工作集采用较大的Dr，让不那么fit的工作集采用较小的Dr。This strategy ensures that only hot data is stored in DRAM。（不懂）

即使采用了lazy migration，如果对一个page频繁访问的话，这个page也迟早会放到DRAM中，这就保证了hot data会最终在DRAM中。

Bypass DRAM during Writes(Dw)

在传统的系统中，“ As transactions tend to generate multiple log records that are each small in size, DBMSs use the group commit optimization to reduce this I/O overhead”；但是，“Unlike SSDs, the CPU is capable of directly persisting data on NVM via write operations (❽) . Spitfire leverages this path to provide synchronous persistence with lower overhead”。其实，直接将日志之类的信息持久化到NVM中，可以减少总体的延迟，而且也避免了evict DRAM中的hot data。

Dw表示写数据到DRAM中的概率，也即figure3中路径8的概率。我们可以直观地知道，如果对于日志之类的信息，Dw肯定要很小，也就是lazy policy。

“Our evaluation demonstrates that this optimization improves Spitfire’s performance on write-intensive workloads”

Bypass NVM During Reads(Nr)

Spitfire instead makes use of the data flow path from SSD to DRAM (❾). When it observes that a requested page is not present in both the DRAM and NVM buffers, it copies the data on SSD directly to DRAM, thus bypassing NVM during read operations.

这个情况对应于读数据的第4种或第5种可能性。

但是具体使用哪一种，是由超参数Nr决定的。Nr表示从SSD读数据时copy到NVM的可能性，这个Nr越大，就意味着越不lazy。

When a page is fetched from SSD and later evicted from DRAM, an eager policy necessitates two writes to NVM: once at fetch time and again when it is evicted from DRAM. With a lazy policy (e.g., Nr = 0.01), Spitfire installs a copy of a modified page on NVM only after it has been evicted from DRAM. This eliminates the first write to NVM when Spitfire fetches the page from SSD.

如果Nr比较大的话，我们就可能有两次写NVM的操作，第一次是在从SSD读数据的时候，写到了NVM中，第二次是把数据从DRAM evict到NVM的时候。如果Nr比较小的话，就可以避免了第一次操作NVM的可能性，但是文章中没有提到省略第一个NVM写和不省略第一次NVM写之间有什么trade-off，我猜测是这种情况：如果省略第一个NVM写的话，只能把数据存到DRAM中，这就导致了如果这个数据是冷数据，就会evict掉DRAM中的热数据；如果不省略第一个NVM写的话，虽然多了一个NVM写，但是后续的读写会直接读写NVM，避免了DRAM中热数据的eviction。

虽然作者没有明说上述的trade-off，但是后面一段也能推出这个思想。

It employs: a lazy policy for migrating data from NVM to DRAM (Dr = 0.01), and a comparatively eager policy while moving data from SSD to NVM (Nr = 0.2). While this scheme increases the number of writes to NVM compared to the lazy policy, it enables Spitfire to deliver higher performance than Hymem。

Hymem采用的是直接将SSD中的数据迁移到DRAM中，也就是完全的lazy策略。但是spifrie没有那么lazy，它有一定的可能性将数据从SSD复制到NVM中，虽然也不是很大，但也不是完全lazy。这样可以使得CPU 直接读写NVM有较大的可能。

Bypass NVM During Writes(Nw)

By bypassing NVM during writes, Spitfire ensures that only pages frequently swapped out of DRAM are stored on NVM. （不懂）

Besides reducing the number of writes to NVM, this optimization also ensures that only warm pages are stored in the NVM buffer. If Spitfire employs a lazy policy while copying data from NVM into DRAM (Dr = 0.01), this optimization prevents colder DRAM-resident pages from polluting the NVM buffer.

Lower values of Nw reduce downward data migration into NVM. Such a lazy policy is beneficial when the capacity of DRAM is comparable to that of NVM since it ensures that colder data on DRAM does not evict warmer data on NVM.

如果随便就把数据从DRAM迁移到NVM中，本身NVM空间也不是很大（和DRAM差不多大），那么NVM中的warm数据很容易被evict掉。所以要采用从DRAM到NVM迁移的lazy模式比较好。

Adaptive Data Migration

以上的参数组合P: {Dr, Dw, Nr, Nw}应该是什么，才能对一个工作任务达到最好的效果呢？文章中有说。

Cost Function

这里spitfire运用了机器学习的思路，来在一段时间内收集系统运行的数据，然后观察吞吐量，最后计算损失函数，找到参数P使得损失函数最小。

The crux of our approach is to periodically track a set of target metrics, and then adapt P in the background. Spitfire evaluates a candidate policy across millions of buffer pool requests to ensure that its impact on the target metrics is prominently visible to the search algorithm. Over time, the search algorithm automatically optimizes P for the target workload and storage hierarchy.

transactional throughput (T) metric to guide the adaptation mechanism.

Search Algorithm

Spitfire adapts the policy using simulated annealing (SA，模拟退火) [21]. This iterative search technique finds a policy Popt that minimizes the cost function.

采用了模拟退火算法来minimize损失函数。

System Architecture

Multi-tier buffer management

With this configuration, Spitfire seeks to keep the hot, warm, and cold database pages on DRAM, NVM, and SSD, respectively. Since the CPU is capable of directly operating on both the DRAM and NVM buffers, Spitfire maintains a mapping table on DRAM to bound latency. This mapping table serves to keep track of pages buffered in DRAM and NVM.

As shown in Figure 4, Spitfire maintains a shared page descriptor for every logical page P in the mapping table. The descriptor contains latches for thread-safe data migration and pointers to the DRAM and NVM page descriptors.

device-specific page descriptors contains:

1. number of users of the page
2. a bit indicating whether the page is dirty
3. a physical pointer to the page freme residing on the device

Similar to Hymem, Spitfire adopts the CLOCK cache replacement policy to reclaim space in the DRAM and NVM buffers.

Concurrency Control and Recovery

为了实现并发操作，利用了下面的数据结构和协议：

1. concurrent hash table for managing the mapping from logical page identifiers to shared page descriptors
2. concurrent bitmap for the cache replacement policy
3. multi-versioned timestamp-ordering (MVTO) concurrency control protocol
4. ) concurrent B+Tree for indexing with optimistic lock-coupling
5. lightweight latches for thread-safe page migrations

现在有很多问题：什么是optimistic lock coupling；latch和lock有什么区别；复习一下B+Tree，现在参考【2】【3】【4】

Concurrent Index

由于NVM的存在，IO开销减少了，因此computational overhead asscociated with index lookups所占的比例增大了，这就是为什么使用B+Tree with optimistic lock-coupling的原因，因为乐观锁耦合技术减少了与悲观锁耦合相关的争用开销。

Thread-Safe Page Migration

引用

【1】论文阅读:Spitfire：https://zhuanlan.zhihu.com/p/355572739

【2】《乐观锁耦合：扩展性强且高效的通用同步方法》https://www.jianshu.com/p/32cb5f107a01

【3】《论文解读：optimistic lock coupling》https://zhuanlan.zhihu.com/p/269533719

【4】lock和latch的区别：https://github.com/sdg-sysdev/bdb-study/blob/master/btree_locking.txt

每天都要阅读一些技术类的文章，但是如果把所有这些文章都做笔记是不太现实的，但是如果把这些文章都只想过眼云烟一样读一下，又很快忘了，所以在这个文章里记录每个月读的文章链接，标题，以及自己的一点想法。

2021.9

数据库读写分离

https://www.cnblogs.com/findbetterme/p/10820590.html

提到了最终一致性。在分布式系统中，对于某些对实时性要求不高的场合里，可以放弃一些一致性，比如采用读写分离的方式，将一些读操作放在从服务器上执行，虽然慢了点，但是等个几分钟也不是不可以。比如，我刚在github.io上发布了新的博客，总是要刷新好几遍才会出来我更新的东西，这就是读写分离。

为什么选择Rust

https://www.techug.com/post/why-we-choose-rust-to-dev.html

这篇文章对Rust和C++，go语言进行了比较，解释了为什么在大型项目中选择Rust语言。

Optimistic Lock Coupling

乐观锁与悲观锁

参考：https://www.hollischuang.com/archives/934
https://baijiahao.baidu.com/s?id=1604426171880146821&wfr=spider&for=pc

悲观锁就是大学时学的那种常见的锁，在做任何更新之前都要获取锁，因为它总是悲观地认为在修改过程中会有别的进程也要修改同样的数据；在乐观锁中，不会获取锁，以提高并发度。

• 数据版本,为数据增加的一个版本标识。当读取数据时，将版本标识的值一同读出，数据每更新一次，同时对版本标识进行更新。当我们提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的版本标识进行比对，如果数据库表当前版本号与第一次取出来的版本标识值相等，则予以更新，否则认为是过期数据。
• 乐观锁适用于多读应用类型
• 但是有个问题是：在高并发地对同一行数据进行修改时，乐观锁会导致大量进程的更新失败。

在MySQL中，悲观锁的使用是select for update；乐观锁的应用是：

1
2
3
4
5

update order_table set status = ‘取消’ where order_id = 001 and status = ‘待支付’ and ....;

update order_table set status = ‘已发货’ where order_id = 001 and status = ‘已支付’ and ....;   

# 在实际应用中我们在更新数据的时候，更严谨的做法是带上更新前的“状态”

perf

如何读懂火焰图

火焰图官方

2021.12

“十四五”数据库发展趋势与挑战

这个文章介绍了数据库前沿的概览，但是我根本不理解这里面的很多东西，只是能记住一些名词，比如云原生数据库，分布式数据据，新型硬件，openGauss等自治数据库。值得注意的是，里面说NVM 数据库的事务管理机制、页面设计机制也都与传统数据库大相径庭，因为我是做NVM的，所以想知道传统的事务管理机制和NVM数据库的事务管理机制的区别，传统事务的页面设计和NVM数据库的页面设计有什么区别。

引用

读写冲突问题

参考【1】

更新丢失

更新丢失（Lost Update）：当两个或多个事务选择同一行，然后基于最初选定的值更新该行时，由于每个事务都不知道其他事务的存在，就会发生丢失更新问题 —— 最后的更新覆盖了其他事务所做的更新。如何避免这个问题呢，最好在一个事务对数据进行更改但还未提交时，其他事务不能访问修改同一个数据。

当一个事务A正在修改X数据时，但是还没提交，事务B也修改了X数据，这个情况下就是更新丢失。

• 在使用锁解决冲突的情况下，事务A在修改X之前获得了X的X-lock，那么事务B是不可能更新X的。
• 在使用MVCC解决冲突的情况下，事务B也会由于可见性判断看不到事务A做出的更新，最多只能看到旧值。

脏读

脏读（Dirty Reads）：一个事务正在对一条记录做修改，在这个事务并提交前，这条记录的数据就处于不一致状态；这时，另一个事务也来读取同一条记录，如果不加控制，第二个事务读取了这些尚未提交的脏数据，并据此做进一步的处理，就会产生未提交的数据依赖关系。这种现象被形象地叫做 “脏读”。

不可重复读

不可重复读（Non-Repeatable Reads）：一个事务在多次读取某些数据时可能会看到数据已经更新或删除，这种现象叫做“不可重复读”。

幻读

幻读（Phantom Reads）：一个事务按相同的查询条件重新读取以前检索过的数据，却发现其他事务插入了满足其查询条件的新数据，这种现象就称为 “幻读”。

隔离性级别

参考【2】

数据库是一个服务器／客户端架构的软件，对于同一个服务器来说，可以有若干个客户端与之连接，每个客户端与服务器连接上之后，就可以称之为一个会话（Session）。我们可以同时在不同的会话里输入各种语句，这些语句可以作为事务的一部分进行处理。不同的会话可以同时发送请求，也就是说服务器可能同时在处理多个事务，这样子就会导致不同的事务可能同时访问到相同的记录。我们前边说过事务有一个特性称之为隔离性，理论上在某个事务对某个数据进行访问时，其他事务应该进行排队，当该事务提交之后，其他事务才可以继续访问这个数据。但是这样子的话对性能影响太大，所以设计数据库的大叔提出了各种隔离级别，来最大限度的提升系统并发处理事务的能力，但是这也是以牺牲一定的隔离性来达到的。

未提交读（READ UNCOMMITTED）

如果一个事务读到了另一个未提交事务修改过的数据，那么这种隔离级别就称之为未提交读（英文名：READ UNCOMMITTED），示意图如下：

如果是READ UNCOMMITTED隔离级别，这种隔离级别就太低了，可能会发生读写冲突问题中的更新丢失和脏读问题。

已提交读（READ COMMITTED）

如果一个事务只能读到另一个已经提交的事务修改过的数据，并且其他事务每对该数据进行一次修改并提交后，该事务都能查询得到最新值，那么这种隔离级别就称之为已提交读（英文名：READ COMMITTED）。

在READ COMMITTED隔离级别下，可能会发生不可重复读的读写冲突，比如：

我们在Session B中提交了几个隐式事务，这些事务都修改了id为1的记录的列c的值，每次事务提交之后，Session A中的事务都可以查看到最新的值。这种现象也被称之为不可重复读。

可重复读 REPEATABLE READ

在一些业务场景中，一个事务只能读到另一个已经提交的事务修改过的数据，但是第一次读过某条记录后，即使其他事务修改了该记录的值并且提交，该事务之后再读该条记录时，读到的仍是第一次读到的值，而不是每次都读到不同的数据。那么这种隔离级别就称之为可重复读（英文名：REPEATABLE READ）

串行化 SERIALIZABLE

即使是可重复读，也会遇到串行化的问题，这个问题在《数据库系统概念》【3】中有非常详细的理论，包括冲突环的讲解。

一般情况下不会要求这么高的隔离性级别，毕竟串行化的并发度不是很好。

MVCC：解决冲突问题

第一次解出到MVCC，是postgresql的MVCC机制，可以参考【4】。还有一篇文章【2】也讲解了MVCC，这个可能是MySQL的MVCC机制。我觉得【2】文章写的很不错。

引用

【1】mysql处理读写冲突的MVCC：https://blog.csdn.net/cumtmonster/article/details/106669873

【2】MySQL事务隔离级别和MVCC：https://juejin.cn/post/6844903808376504327

【3】《数据库系统概念（计算机科学丛书）》

【4】interdb是postgresql的内幕讲解。https://www.interdb.jp/pg/pgsql05.html

事务内存

【1】

DUDETM: Building Durable Transactions with Decoupling for Persistent Memory

Introduction

undo logging

In undo logging, the original (old) values are stored to a log before they are modifified by a transaction. Having its old value preserved in the log, the data can be modified in-place. Therefore, a memory load can directly read the latest value without being intercepted and remapped to a different address.

为何undo logging可以避免很大的开销呢，因为针对一个数据写入，它先写入日志，再写入状态机，这样的话，数据读可以直接读到最新的数据（不像redo logging，当把全部数据写入的日志都持久化之后，才写入状态机）；但是undo logging有一个问题：

To enforce this order, the system uses the persist operation, which is implemented by a sequence of instructions , for every update.

redo logging

However, since the data updates are buffered in the log, the reads of them in a transaction must be remapped to the log to obtain the latest values.

The dilemma between undo and redo logging is essentially a trade-off between persist ordering cost and update redirection cost.

The key insight of our solution is decoupling a durable transaction into three fully asynchronous* steps.

(1) Perform: execute the transaction in a shadow memory , and produce a redo log for the transaction.

(2) Persist: flflush the redo log of each transaction to persistent memory in an atomic manner.

(3) Reproduce: modify original data in persistent memory according to the persisted redo log. It is essential that we never directly write back dirty data from shadow memory to persistent memory – all the updates are realized via the redo log.

问题

1. 为什么“However, since the data updates are buffered in the log, the reads of them in a transaction must be remapped to the log to obtain the latest values.”

引用

【1】初识事务内存（Transactional Memory）：https://zhuanlan.zhihu.com/p/151425608

引用

【1】持久内存开发资料汇总：https://zhuanlan.zhihu.com/p/391107604