头像

chxlD


访客:6884

离线:14天前


新鲜事 原文

chxlD
1个月前
有在学习和使用clickhouse的同学吗? 最近准备写一些这个方面的文章。



chxlD
2个月前

事务隔离级别和MVCC

从我们开始连接 Mysql server 开始,也就开启了一个 session 。在每一个会话中我们可以发起事务,但是对于 server 来说,可能就是多个事务在进行,从我们的角度上看,事务在访问数据的时候,其他需要访问该数据的事务等待,该事务提交之后,其他事务就可以访问。但是对于 server 这是损耗性能的,所以又要做到 隔离性,又要性能,这个就要舍弃一些 隔离性

隔离性问题

我们先来看看不串行执行,事务访问的数据会发生什么:

  • Dirty write:一个事务修改了另一个未提交事务修改过的数据;【脏写】
  • Dirty read:一个事务读到了另一个未提交事务修改过的数据;【脏读】

  • Non-Repeatable Read :一个事务可以马上读到另一个已经提交的事务修改过的数据,并且其他事务每对该数据进行一次修改并提交后,该事务都能查询得到最新值;【不可重复读】

SessionB 中有几次隐式事务提交,而 SessionA 中都能查到最新的值

sessionA sessionB
Begin;
select from trace where key = '20041';【’key’】
uptate trace set typeof = 'buttonkey' where key = '20041'
select from trace where key = '20041';【’buttonkey’】
uptate trace set typeof = 'mainkey' where key = '20041'
select from trace where key = '20041';【’mainly’】
  • Phantom:一个事务条件查询出一些记录,之后另一个事务又向表中插入了符合这些条件的记录,原先的事务再次按照该条件查询时,能把另一个事务插入的记录也读出来;【幻读】
sessionA sessionB
Begin;
select keyv from trace where id > 0;【‘20041’】
insert into trace(keyv, typeod) value('20036', 'key')
select * from trace where id > 0;【‘20041’, ‘20036’】

注意这里是读到了之前没有读到的记录,而不是反而读不到之前的记录,那对于先前已经读到的记录,之后又读取不到这种情况?其实这相当于对每一条记录都发生了不可重复读的现象。幻读只是重点强调了读取到了之前读取没有获取到的记录。

标准的四种隔离级别

上面说的四种事务并发执行问题,从严重级别上:

脏写 > 脏读 > 不可重复读 > 幻读

而设计隔离级别,隔离级别越低,越严重的问题就越可能发生。下面4种隔离级别:

  • READ UNCOMMITTED:未提交读;
  • READ COMMITTED:已提交读;
  • REPEATABLE READ:可重复读;
  • SERIALIZABLE:可串行化。

下面列出各种隔离级别下可能发生的问题:

隔离级别 脏读 不可重复读 幻读
READ UNCOMMITTED
READ COMMITTED
REPEATABLE READ
SERIALIZABLE

脏写实在是太严重了,哪种隔离级别都不允许脏写发生。

MVCC

总体来说,MVCC使用了一种乐观锁的实现形式,借助undo log的可见性来控制数据库的并发操作

mvcc中有两种读:

  • 快照读:读取的是当前事务的可见版本。最简单的select操作;
  • 当前读:读取的是当前版本。显示带lock的读操作,Insert/Update/Delete操作

版本链

之前的 undo log 看到链表的连接,形式就像版本链可以进行数据追溯。而对于InnoDB的表,聚簇索引记录中都包含两个必要的隐藏列:

  • trx_id:事务对某条聚簇索引记录产生改变时,会把事务id赋值在trx_id
  • roll_pointer:改动聚簇索引记录会把数据旧的版本写入undo logroll_pointer相当一个指针指向这个undo log,从而形成一个可追溯的链表;
trx389 trx399
begin;
begin;
update trace set type = 'mainkey' where key = '20041'
update trace set type = 'buttonkey' where key = '20041'
commit;
update trace set type = 'key' where key = '20041'
update trace set type = 'buttonkey' where key = '20041'
commit;

上图为什么没有在事务之间对同一条记录进行操作呢?

这不就是一个事务修改了一个未提交事务的数据 ===> 【脏写】。这个在任何一个隔离级别都是不允许的。

InnoDB会通过对记录加锁,另一个事务更新就需要等待之前的事务提交释放锁才能提交。

每对记录产生改动,就会生成一个undo log,然后把旧值放到这条undo log中,也就是这条记录一个旧版本。随着我们的修改继续,所有曾经的版本就会被roll_pointer串成一个链表,这个版本链的头节点就是当前记录最新的值。

ReadView

从名字上看:读视图。这个是mysql创建视图的必要条件。其实readview由三部分组成:

  • m_ids:当前活跃的事务id列表。如:[2,3]
  • min_trx_id:生成readview时当前活跃事务中最小事务id
  • max_trx_id:生成readview时,即将分配给下一个事务id

还有一个需要注意的就是:create_trx_id 生成该readview事务id

之前说过:只有在对表中的记录做改动时(INSERT、DELETE、UPDATE)才会为事务分配事务id。

  • Insert undo log:当事务提交之后可以直接丢弃;
  • Update undo log:长事务会产生很多老的视图导致undo log无法删除而占用大量存储空间。

如果只是一个只读事务,则不会分配trx_id,故事务id都默认为0。

说完结构了,讲讲为什么需要这个吧:对应4种隔离级别,在读的时候能读到哪一步的记录是关键:

  • READ UNCOMMITTED:可以读到未提交事务修改过的记录,也就是记录的最新情况是可以获取的;
  • SERIALIZABLE:加锁来实现串行读;
  • READ COMMITTED:必须保证读到已提交事务修改过的记录,也就是说如果另一个事务已经修改了记录但是尚未提交,是不能直接读取最新版本的记录;
  • REPEATABLE READ:同上;

所以关键就是可以在版本链上读到哪个记录,哪个事务修改的记录对于当前事务是可见的。

可见性

借用一下kafka的高水位的概念,一图入魂:

整体分析

下图举个3个事务在线的🌰:

此时看trx_id300的两次select,两次产生的readview是不一致的。

这里就说出READ COMMITTEDREPEATABLE READ的区别:

MySQL中,READ COMMITTEDREPEATABLE READ隔离级别的的一个非常大的区别就是它们生成ReadView的时机不同。

  • READ COMMITTED —— 每次读取数据前都生成一个ReadView

  • REPEATABLE READ —— 在第一次读取数据时生成一个ReadView

所以上图的所呈现的是在READ COMMITTED隔离级别下的情况。然后根据可见性分析,两次查询的寻链也就清晰

REPEATABLE READ

从名字上就知道可重复读,再结合上面的生成readview的时机和次数。不言而喻,两次查询所得到的结果都是一样,而且以第一次为准,之后的结果都是重复第一次

总结

所谓MVCC,指的就是在使用READ COMMITTDREPEATABLE READ这两种隔离级别事务在执行普通的SELECT操作时访问记录的版本链,其中借助undo log,可见性算法,以及readview来完成整个过程。

所谓的MVCC只是在进行普通的SEELCT查询才生效,其他一些不普通的之后再讲。




chxlD
3个月前
func canBeEqual(target []int, arr []int) bool {
    count := make(map[int]int, len(target))
    for _, item := range target {
        count[item]++
    }

    for _, item := range arr {
        count[item]--
    }

    for _, num := range count {
        if num != 0 {
            return false
        }
    }
    return true
}


活动打卡代码 LeetCode 9. 回文数

chxlD
3个月前
func isPalindrome(x int) bool {
    if x == 0 {
        return true
    }
    // itob(x) && itob(x % 10) == false
    if x <= 0 || x & x % 10 == 0 {
        return false
    }
    t := 0
    for t <= x {
        t = t * 10 + x % 10
        if t == x || t == x / 10 {
            return true
        }
        x = x / 10
    }
    return false
}

func itob(i int) bool {
    return i != 0
}



chxlD
3个月前
func lengthOfLongestSubstring(s string) int {
    var res int
    count := make(map[string]int, len(s) + 1)
    n := len(s)
    for i, j := 0, 0; i < n; j = j + 1 {
        if j == len(s) {
            break
        }
        count[string(s[j])]++
        for count[string(s[j])] > 1 {
            count[string(s[i])]--
            i = i + 1
        }
        res = max(res, j - i + 1)
    }
    return res
}

func max(a int, b int) int {
    if a > b {
        return a 
    } else {
        return b
    }
}


活动打卡代码 LeetCode 1. 两数之和

chxlD
3个月前
func twoSum(nums []int, target int) []int {
    var res []int
    pair := make(map[int]int)
    for i := range nums {
        another := target - nums[i]
        if _, ok := pair[another]; ok {
            res = append(res, pair[another], i)
            break
        }
        pair[nums[i]] = i
    }
    return res
}


活动打卡代码 LeetCode 2. 两数相加

chxlD
3个月前
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    res := &ListNode{Val: -1}
    cur := res
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := If(l1), If(l2)
        sum := n1 + n2 + carry
        carry = sum / 10
        cur.Next = &ListNode{Val: sum % 10}
        cur = cur.Next
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    if carry != 0 {
        cur.Next = &ListNode{Val: 1}
    }
    return res.Next
}

func If(l *ListNode) int {
    if l != nil {
        return l.Val
    } else {
        return 0
    }
}



chxlD
6个月前
// 使用现有数据结构实现一个队列【两个栈实现一个队列】
class MyQueue {
public:
  stack<int> stk, cache;
  MyQueue() {}

  void push(int x) {
    stk.push(x);
  }

  int pop() {
    cp(stk, cache);
    int res = cache.top();
    cache.pop();
    cp(cache, stk);
    return res;
  }

  int peek() {
    cp(stk, cache);
    int res = cache.top();
    cp(cache, stk);
    return res;
  }

  bool empty() {
    return stk.empty();
  }

  void cp(stack<int> &a, stack<int> &b) {
    while (a.size()) {
      b.push(a.top());
      a.pop();
    }
  }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */




chxlD
7个月前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root, sum);
        return res;
    }

    void dfs(TreeNode* root, int sum) {
        if (!root) return;
        path.push_back(root->val);
        sum -= root->val;
        // 已经到叶子节点 && 从root到当前的和为sum
        if (!root->left && !root->right && !sum) res.push_back(path);
        dfs(root->left, sum), dfs(root->right, sum);
        // 回溯到root,也就是回复到原始的状态,开始下一个状态的推测
        path.pop_back();
    }
};



chxlD
7个月前
class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        if (seq.empty()) return true;
        return dfs(0, seq.size() - 1);
    }

    bool dfs(int l, int r) {
        if (l >= r) return true;
        int k = l;
        int root = seq[r];
        // 找到root节点的左右子树的边界点
        while (k < r && seq[k] < root) k++;
        // 验证这个点是不是符合规范
        for (int i = k; i < r; i++) {
            // 从边界点到r,都应该是>root的
            if (seq[i] < root) return false;
        }
        // 由这个点分出左右子树来递归
        return dfs(l, k - 1) && dfs(k, r - 1);
    }
};