1. REDO, UNDO, checkpoint

Write Ahead Logging (WAL) is a standard approach to transaction logging. Briefly, WAL's central concept is that changes to data files (where tables and indexes reside) must be written only after those changes have been logged - that is, when log records have been flushed to permanent storage. When we follow this procedure, we do not need to flush data pages to disk on every transaction commit, because we know that in the event of a crash we will be able to recover the database using the log: any changes that have not been applied to the data pages will first be redone from the log records (this is roll-forward recovery, also known as REDO) and then changes made by uncommitted transactions will be removed from the data pages (roll-backward recovery - UNDO). [1]
已commit但未apply的, 执行REDO, 而由 未commit的事务 的修改 需要执行UNDO.

------------------

Its transaction recovery log contains log records of the following form:
<txnId, objectId, beforeValue, afterValue>

有如下log:

1 <T1 BEGIN>
2 <T1, X, 1, 2>
3 <T2 BEGIN>
4 <T3 BEGIN>
5 <T2, Y, 1, 2>
6 <T2 COMMIT>
7 <T1, Y, 2, 3>
8 <T3, Z, 1, 2>
9 <CHECKPOINT>
10 <T1, X, 2, 3>
11 <T1, Y, 3, 4>
12 <T3, Z, 2, 3>
13 <T3 COMMIT>
14 <T1, Z, 3, 4>

1. 背景

为理解raft, 参照2018年的 https://pdos.csail.mit.edu/6.824/labs/lab-raft.html 进行其中的lab 2A 和 2B.

2. 代码实现/协议细节

2.1 文章摘录

https://thesquareplanet.com/blog/students-guide-to-raft/

• you might reasonably reset a peer’s election timer whenever you receive an AppendEntries or RequestVote RPC, as both indicate that some other peer either thinks it’s the leader, or is trying to become the leader. Intuitively, this means that we shouldn’t be interfering. However, if you read Figure 2 carefully, it says:

  If election timeout elapses without receiving AppendEntries RPC from current leader or granting vote to candidate: convert to candidate. ​

• many would simply reset their election timer when they received a heartbeat, and then return success, without performing any of the checks specified in Figure 2. This is extremely dangerous. By accepting the RPC, the follower is implicitly telling the leader that their log matches the leader’s log up to and including the prevLogIndex included in the AppendEntries arguments. Upon receiving the reply, the leader might then decide (incorrectly) that some entry has been replicated to a majority of servers, and start committing it. 接收到心跳, 不能简单地返回成功, 而应该 对比leader发过来的prevLogIndex 和 自己(follower)已有的log. 这样, 可以应对如下情况: 当某个节点网络断开, 重新加入集群时, 就能够及时地更新自身数据到最新状态.

1. 没有锁保护

有如下结构体:

struct your_obj {
    struct hlist_node obj_node_hlist;
    struct rcu_head rcu_head;   
    atomic_t refcnt;
    int id;
};

错误写法:

hlist_del_init_rcu(&your_obj->obj_node_hlist);  

正确写法:

spin_lock(&obj_hash_lock[hash]);
hlist_del_init_rcu(&your_obj->obj_node_hlist);
spin_unlock(&obj_hash_lock[hash]);

1. 使用 python 提取出 interval

# -*- coding: utf-8 -*

#添加相应trace_printk, ftrace输出类似:
#           <...>-3084  [000] 352166.459260: your_func_01: your_point_01
#           <...>-2892  [000] 352166.459529: your_func_02: your_point_02

read_point_start = 1
f_in=open('interval.ftrace', 'r')
f_out = open("interval.dat", "wb")
line_no = 1

while 1:
    line = f_in.readline()
    if not line:
        break
    #print line

    if read_point_start == 1:
        if "your_func_01" in line:
            val_point_start=line.split(":")[0].split(" ")[-1]
            read_point_start = 0
            print val_point_start,
    elif "your_func_02" in line:
            val_point_end=line.split(":")[0].split(" ")[-1]
            print val_point_end,
            interval = int((float(val_point_end) - float(val_point_start)) * 1000 * 1000)
            print interval
            f_out.write(str(line_no) + " " + str(interval)+'\n')    
            line_no+=1
            read_point_start = 1

f_out.close()