0%

「被讨厌的勇气」真是一本好书,希望大家都能看一看。

这里开始简单记录书中一些我认为很有意义的话。

  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. 是的,我们并不缺乏能力,只是缺乏“勇气”。一切都是“勇气”的问题。

  27. 在相信他人的时候不附加任何条件。即使没有足以构成信用的客观依据也依然相信,不考虑抵押之类的事情,无条件的相信。这就是信赖。

  28. 你现在认为“无条件地信赖别人只会遭到背叛”。但是,决定背不背叛的不是你,那是他人的课题。你只需要考虑“我该怎么做”。

  29. 你现在一味地担心“被背叛”,也只关注因此受到的伤痛。但是,如果不敢去信赖别人,那最终就会与任何人都建立不了深厚的关系。

  30. 他者贡献并不是舍弃“我”而为他人效劳,它反而是为了能够体会到“我”的价值而采取的一种手段。

  31. 任何情况下都只是攻击我的“那个人”有问题,而绝不是“大家”的错。

  32. 只不过是以工作为借口来逃避其他责任。本来家务、育儿、交友或兴趣应该全都给予关心,阿德勒不认可任何一方面突出的生活方式。

  33. 对人而言,最大的不幸就是不喜欢自己。对于这种现实,阿德勒准备了极其简单的回答——“我对共同体有益”或者“我对他人有用”这种想法就足以让人体会到自己的价值。

  34. 青年:您是说,只要有了共同体感觉认可欲求就会消失吗?

    哲人:会消失。不再需要他人的认可。

  35. 如果人生是一条线,那么人生规划就有可能。但是,我们的人生只是点的连续。计划式的人生不是有没有必要,而是根本不可能。

  36. 请你这样想。人生就像是在每一个瞬间不同旋转起舞的连续的刹那。并且,蓦然四顾时常常会惊觉:”已经来到这里了吗?“

  37. 在舞蹈中,跳舞本身就是目的,最终会跳到哪里谁都不知道。当然,作为跳的结果最终会到达某个地方。因为一直在跳动所以不会停在原地。但是,并不存在目的地

  38. 如果把强烈的聚光灯对准”此时此刻“,那就会既看不到过去也看不到未来。

  39. 过去发生了什么与你的”此时此刻“没有任何关系,未来会如何也不是”此时此刻“要考虑的问题。

  40. 人生中最大的谎言就是不活在”此时此刻“。

  41. 所以阿德勒再说了”并不存在普遍性的人生意义“之后还说:”人生意义是自己赋予自己的。

  42. 无论你过着怎么的刹那,即使有人讨厌你,只要没有迷失”他者贡献“这颗引导之星,那么你就不会迷失而且做什么都可以。即使被讨厌自己的人讨厌着也可以自由的生活。

  43. 世界不是靠他人改变而只能靠”我“来改变。

在现代社会,公众对艾滋病人的接纳,其实也是一个非常奢侈的话题。虽然每一年,我们都有一个专门的日子,我们来表达对艾滋病人的关心。但是,仅仅有这个日子是不够的。

人们对于疾病总是有一种本能的恐惧。不要说艾滋病了,甚至乙肝病毒携带者,甚至白血病,等等都在社会中备受歧视。新闻就曾经报道过,有些白血病的孩子入学,被拒绝。所以在这样一种背景下,各位可以想象,艾滋病患呢,也很难走出歧视,并因为这个歧视,可能他们滋生对社会的仇恨和苦毒。

社会文明程度很大程度上它体现为对弱者的尊重。即便你跌入谷底,社会也应该为你提供基本的保障。当然话虽如此,同理心,始终是人们最匮乏的一种品质。

对于每个个体,如果我们无法真正的接纳弱者,这不也是我们道德上的免疫缺陷吗?

全局锁、表锁、行锁、间隙锁。

全局锁:flush tables with read lock

表级锁:

  1. 表锁:lock tables ... read/write
  2. MDL(metadata lock):server层,增删改查DML语句添加读锁,修改表结构定义DDL语句加写锁。更加详细的可以看这个链接https://blog.csdn.net/q2878948/article/details/96430129

间隙锁为了解决幻读,比较不同。

比如行锁,分成读锁(共享锁)和写锁(排他锁)。下图就是这两种类型行锁的冲突关系。

也就是说,跟行锁有冲突关系的是“另外一个行锁”。

但是间隙锁不一样,跟间隙锁存在冲突关系的,是“往这个间隙中插入一个记录”这个操作。间隙锁之间都不存在冲突关系。

这句话不太好理解,举个例子:

这里session B并不会被堵住,因为表t里并没有c=7这个记录,因此session A加的是间隙锁(5,10)。而session B也是在这个间隙加的间隙锁。它们有共同的目标,即:保护这个间隙,不允许插入值。但,它们之间不是冲突的。

间隙锁和行锁合称 next-key lock,每个 next-key lock 是前开后闭区间。也就是说,我们的表 t 初始化以后,如果用 select * from t for update 要把整个表所有记录锁起来,就形成了 7 个 next-key lock,分别是 (-∞,0]、(0,5]、(5,10]、(10,15]、(15,20]、(20, 25]、(25, +supremum]。

备注:这篇文章中,如果没有特别说明,我们把间隙锁记为开区间,把 next-key lock 记为前开后闭区间。

你可能会问说,这个 supremum 从哪儿来的呢?

这是因为 +∞是开区间。实现上,InnoDB 给每个索引加了一个不存在的最大值 supremum,这样才符合我们前面说的“都是前开后闭区间”。

间隙锁和next-key lock的引入,帮我们解决了幻读的问题,但同时也带来了一些“困扰”。

在前面的文章中,就用同学提到了这个问题。我把他的问题转述一下,对应到我们这个例子的表来说,业务逻辑是这样额:任意锁住一行,如果这一行不存在的话就插入,如果存在这一行就更新它的数据,代码如下:

1
2
3
4
5
6
7
8
9
begin;
select * from t where id=N for update;

/*如果行不存在*/
insert into t values(N,N,N);
/*如果行存在*/
update t set d=N set id=N;

commit;

可能你会说,这个不是insert .. on duplicate key update 就能解决吗?但其实在有多个唯一键的时候,这个方法是不能满足这位提问同学的需求的。至于为什么,我会在后面的文章中再展开说明。

现在,我们就只讨论这个逻辑。

这个同学碰到的现象是,这个逻辑一旦有并发,就会碰到死锁。你一定也觉得奇怪,这个逻辑每次操作前用 for update 锁起来,已经是最严格的模式了,怎么还会有死锁呢?

这里,我用两个 session 来模拟并发,并假设 N=9。

你看到了,其实都不需要用到后面的update语句,就已经形成死锁了。我们按语句执行顺序来分析一下:

  1. session A执行select ... for update 语句,由于id=9这一行并不存在,因此会加上间隙锁(5,10;
  2. session B执行select ... for update 语句,同样会加上间隙锁(5,10),间隙锁之间不会冲突,因此这个语句可以执行成功;
  3. session B试图插入一行(9,9,9),被session A的间隙锁挡住了,只好进入等待;
  4. session A试图插入一行(9,9,9),被session B的间隙锁挡住了。

至此,两个session进入互相等待的状态,形成死锁。当然,InnoDB的死锁检测马上就发现了这对死锁关系,让session A的insert语句返回了。

你现在知道了,间隙锁的引入,可能会导致同样的语句锁住更大的范围,这其实是影响了并发度的。其实,这还只是一个简单的例子,在下一篇文章中我们还会碰到更多、更复杂的例子。

你可能会说,为了解决幻读的问题,我们引入了这么一大串内容,有没有更简单一点的处理方法呢。

今天和你分析的问题都是在可重复读隔离级别下的,间隙锁是在可重复读隔离级别下才会生效的。所以,你如果把隔离级别设置为读提交的话,就没有间隙锁了。但同时,你要解决可能出现的数据和日志不一致问题,需要把 binlog 格式设置为 row。这,也是现在不少公司使用的配置组合。

比如说,大家都用读提交,可是逻辑备份的时候,mysqldump 为什么要把备份线程设置成可重复读呢?(这个我在前面的文章中已经解释过了,你可以再回顾下第 6 篇文章《全局锁和表锁 :给表加个字段怎么有这么多阻碍?》的内容)

然后,在备份期间,备份线程用的是可重复读,而业务线程用的是读提交。同时存在两种事务隔离级别,会不会有问题?

进一步地,这两个不同的隔离级别现象有什么不一样的,关于我们的业务,“用读提交就够了”这个结论是怎么得到的?

加锁规则的经验总结

首先说明一下,这些加锁规则我没在别的地方看到过有类似的总结,以前我自己判断的时候都是想着代码里面的实现来脑补的。这次为了总结成不看代码的同学也能理解的规则,是我又重新刷了代码临时总结出来的。所以,这个规则有以下两条前提说明:

  1. MySQL 后面的版本可能会改变加锁策略,所以这个规则只限于截止到现在的最新版本,即 5.x 系列 <=5.7.24,8.0 系列 <=8.0.13。
  2. 如果大家在验证中有发现 bad case 的话,请提出来,我会再补充进这篇文章,使得一起学习本专栏的所有同学都能受益。

因为间隙锁在可重复读隔离级别下才有效,所以本篇文章接下来的描述,若没有特殊说明,默认是可重复读隔离级别。

我总结的加锁规则里面,包含了两个“原则”、两个“优化”和一个“bug”。

  1. 原则 1:加锁的基本单位是 next-key lock。 next-key lock 是前开后闭区间。
  2. 原则 2:查找过程中访问到的对象才会加锁。
  3. 优化 1:索引上的等值查询,给唯一索引加锁的时候,next-key lock 退化为行锁。
  4. 优化 2:索引上的等值查询,向右遍历时且最后一个值不满足等值条件的时候,next-key lock 退化为间隙锁。
  5. 一个 bug:唯一索引上的范围查询会访问到不满足条件的第一个值为止。

参考

感谢丁奇老师的专栏,摘录部分,如有不妥,请通知我立即删除。https://time.geekbang.org/column/article/75659

Prim算法是一种Greedy算法。它从一个空的生成树开始。其想法是维护两组顶点。第一组包含已经在MST中的顶点,另一组包含尚未在的顶点。在每一步,它都会考虑连接两组的所有边,并从这些边中挑选出最小权重的边。选取边后,它将边的另一个顶点移动到包含MST的集合中。

在图论中,连接两组顶点的一组边被称为切边(cut)。所有,在Prim算法的每一步,我们都要要找到一个cut(关于这两个集合的,一个包含已经在MST中的顶点,另一个包含其余的顶点),从cut中挑选出最小权重的边,并将这个顶点包含到MST集合(包含已经在MST中的顶点)中。

Prim's Algorithm是如何工作的?Prim算法背后的思想很简单,一颗生成树意味着所有顶点必须是连接的。所以,两个不相干的顶点子集(上面讨论的)必须连接起来,才能组成一个生成树。而且它们必须用最小的权重边连接起来,才能使之成为一颗最小生成树。

算法:

  1. 创建一个集合mstSet,用来跟踪已经包含在MST中的顶点。
  2. 给输入图中的所有顶点分配一个键值。初始化所有的键值为infinity。为第一个顶点分配键值为0,这样它就会被首先选中。
  3. while mstSet不包含所有的顶点
    1. 选取一个在mstSet中没有的顶点u,并且其键值最小。
    2. 将u加入到mstSet中。
    3. 更新u的所有相邻顶点的键值,更新键值时,要遍历所有相邻顶点。对于每一个相邻顶点v,如果边u-v的权重小于v的前一个键值,则更新键值为u-v的权重。

使用键值的想法是为了从cut中挑选出最小权重的边。键值只用于尚未包含在MST中的顶点,这些顶点的键值表示连接它们与MST中包含的顶点集的最小权重边的权重。

集合mstSet开始的时候是空的,并且每个顶点键值时{0, INF, INF, INF, INF, INF, INF, INF},INF表示无穷大。现在,选出一个拥有最小键值的顶点。顶点0被选出,将其放入mstSet。所以mstSet成为了{0}。在包括进mstSet之后,更新相邻顶点的键值。0的相邻顶点是1和7。1和7的键值被更新为4和8。下面的子图显示了顶点和它们的键值,只有有有限键值的顶点展示了出来。在MST中的顶点用绿颜色表示了出来。

选出有最小键值的顶点并且还没有被包括进MST(还不在mstSet)。顶点1被选出来,并且被加入mstSet。所以mstSet成为了{0, 1}。更新1的相邻顶点的键值。顶点2的键值变成了8。

选出具有最小键值的顶点,并且还没有包含在MST中(不在mstSet中)。我们可以选择顶点7或者2,我们让7被选中。所以mstSet现在变成了{0, 1, 7}。更新7的相邻顶点的键值,顶点6和8的键值变成了有限的(分别为1和7)。

选出具有最小键值的顶点,并且还没有包含在MST中(不在mstSet中)。顶点6被选中。所以mstSet现在为{0, 1, 7, 6}。更新6的相邻顶点的键值。5和8的键值被更新。

我们重复上面的步骤直到mstSet包含了给定图中所有的顶点。最终,我们得到了如下的图。

如何实现上面的算法?

我们用一个布尔数组mstSet[]表示MST中包含的顶点集合。如果一个值mstSet[v]为true,那么顶点v就在MST中,否则就不是。数组key[]用来存储所有顶点的键值。另一个数组parent[]用来存储MST中父节点的索引。parent数组是输出数组,用来显示构建的MST。

上面算法的时间复杂度为O(V^2)。如果使用邻接表表示输入图,那么在二叉堆的帮助下,Prim算法的时间复杂度可以降低到O(ElogV)。

并查集是一种数据结构,它跟踪一个集合的元素被分割成若干不相干(不重叠)的子集。union-find算法是一种对这种数据结构执行两种有用操作的算法:

Find:确定一个特定的元素在哪个子集里。这可以用来确定两个元素是否在同一个子集中。

Union:将两个子集连接成一个单一的子集。

在这篇文章中,我们将讨论并查集的应用。这个应用就是检查一个给定的图是否有环。

UnionFInd算法可以检查一个无向图是否有环。注意到我们已经讨论过一种检查环的方法。这是另一种使用并查集的防范。这个方法假设图中没有自环。

我们可以在一个1D数组中跟踪子集,我们称它为parent[]。

我们考虑如下图:

对于每条边,用边的两个顶点做子集。如果两个顶点都已经在同一个子集中,就发现了一个环。

初始化时,parent的所有槽位都初始化为-1(意味着每个子集中只有一个项目)。

1
2
0   1   2
-1 -1 -1

现在逐一处理所有的边。

边0-1:找到顶点0和1所在的子集。由于它们在不同的子集中,我们对它们进行union操作。为了取union,可以让结点0作为节点1的父结点,或者反之。

1
2
0   1   2    <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})
1 -1 -1

边1-2:1已经在subset 1中,2在subset 2中,所以取union

1
2
0   1   2    <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})
1 2 -1

边0-2:0在subset 2中,2也在subset 2中。因此,包括这条边形成了一个环。

为什么0的子集和和2相同?

0->1->2 // 1是0的父结点2是1的父结点。

根据以上解释,下面是实现。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# undirected_graph.py
from collections import defaultdict


class UnionFind:
def __init__(self, k):
self.uf = [-1] * (k + 1)
self.sets_count = k

def find(self, p):
if self.uf[p] < 0:
return p
self.uf[p] = self.find(self.uf[p])
return self.uf[p]

def union(self, p, q):
p_root = self.find(p)
q_root = self.find(q)
if p_root == q_root:
return
if self.uf[p_root] > self.uf[q_root]:
self.uf[q_root] += self.uf[p_root]
self.uf[p_root] = q_root
else:
self.uf[p_root] += self.uf[q_root]
self.uf[q_root] = p_root
self.sets_count -= 1

def is_connected(self, p, q):
return self.find(p) == self.find(q)


class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.uf = UnionFind(vertices)

def addEdge(self, u, v):
self.graph[u].append(v)

def isCyclic(self):
for i in self.graph:
for j in self.graph[i]:
if self.uf.is_connected(i, j):
return True
self.uf.union(i, j)


def main():
g = Graph(3)
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 0)
print(g.isCyclic())


if __name__ == '__main__':
main()

上一篇中介绍了旅行商问题,并讨论了该问题的朴素和DP解决方案。这两种解决方案都是不可行的。事实上,这个问题没有多项式时间的解决方案,因为这个问题是一个已知的NP-Hard问题。不过有近似算法可以解决这个问题。近似算法只有在问题满足三角形不等式的情况下才有效。

三角形不等式:从顶点i到顶点j的最短路径总是直接从i到达j,而不是通过其他顶点k,即dist(i, j)总是小于等于dist(i, k) + dist(k, j)。三角形不等式在很多情况下都是成立的。当成本函数满足三角形不等式时,我们可以为TSP设计一个近似算法,该算法返回的旅游成本永远不会超过最优旅游成本的两倍。其思想是使用最小生成树(Minimum Spanning Tree, MST)。以下是基于MST的算法。

算法

  1. 让1成为销售员的起点和终点。
  2. 用Prim's Algorithm以1为根构建MST。
  3. 列出构造的MST的前序遍历中所访问的顶点,并在最后添加1.

让我们考虑下面的例子。第一张图是给定的图,第二张图是以1为根构建的MST。MST的前序遍历是1-2-4-3。在末尾加1,得到1-2-4-3-1,这就是这个算法的输出。

这种情况下,近似算法会产生最优线路,但未必在所有情况下都能产生最优路径。

这个算法是如何2倍近似的?上述算法产生的输出成本永远不会超过最佳可能输出成本的两倍。我们来看看上述算法是如何保证这一点的。

让我们定义一个术语"full walk"来理解这个问题。一个full walk是当一个顶点被前序遍历访问访问时列出它们,并且当某个顶点的子树被返回时也列出这些顶点。上面树的full walk将是1-2-1-4-1-3-1。下面是证明2-近似性的一些重要事实。

  1. 最好的旅行商路线的成本绝不小于MST的成本。(MST的定义说,它是连接所有顶点的最小成本树。)
  2. full walk的总成本最多是MST成本的两倍(MST的每条边最多被访问两次)。
  3. 上述算法的输出小于full walk的成本。在上面的算法中,我们打印出preorder walk作为输出。在前序遍历中,full walk的两条或多条边被一条边所取代。例如,2-1和1-4被一条边2-4所取代。所以,如果图形遵循三角形不等式,那么这条结论总是对的。

从以上三句陈述中,我们可以得出结论,近似算法产生的输出成本永远不会超过最佳可能解成本的两倍。

我们讨论了一个非常简单的旅行商问题的2-近似算法。对于这个问题还有其他更好的近似算法。例如Christofides算法是1.5近似算法。我们将很快把这些算法作为单独的文章来讨论。

参考

https://www.geeksforgeeks.org/travelling-salesman-problem-set-2-approximate-using-mst/?ref=lbp

事务

和数据库打交道的时候,我们总是会用到事务,最经典的例子就是转账,你要给朋友小王转100块钱,而此时你的银行卡只有100块钱。

转账过程具体到程序里会有一系列的操作,比如查询余额、做加减法、更新余额等,这些操作必须保证是一体的,不然等程序查完之后,还没做减法之前,你这100块钱完全可以借着这个时间差再查一次,然后再给另外一个朋友转账,如果银行这么整,不就乱了么?这时就要用到”事务“这个概念了。

简单来说,事务就是要保证一组数据库操作,要么全部成功,要么全部失败。在MySQL中,事务支持是在引擎层实现的。你现在知道,MySQL是一个支持多引擎的系统,但并不是所有的引擎都支持事务。比如MySQL原生的MyISAM引擎就不支持事务,这也是MyISAM被InnoDB取代的重要原因之一。

隔离性与隔离级别

提到事务,你肯定会想到ACID(Atomicity、Consistency、Isolation、Durability,即原子性、一致性、隔离性、持久性),今天我们就来说说其中I,也就是”隔离性“。下面是ACID的简单定义。

  1. 原子性

    事务被视为不可分割的最小单元,事务的所有操作要么全部提交成功,要么全部失败回滚。

    回滚可以用回滚日志(Undo Log)来实现,回滚日志记录着事务所执行的修改操作,在回滚时反向执行这些修改操作即可。

  2. 一致性

    数据库在事务执行前后都保持一致性的状态。在一致性状态下,所有事务对同一个数据的读取结果都是相同的。

  3. 隔离性

    一个事务所做的修改在最终提交以前,对其他事务是不可见的。

  4. 持久性

    一旦事务提交,则其所做的修改将会永远保存到数据库中。即使系统发生崩溃,事务执行的结果也不能丢失。

当数据库上有多个事务同时执行的时候,就可能出现脏读(dirty read)、不可重复度(non-repeatable read)、幻读(phantom read)的问题,为了解决这些问题,就有了”隔离级别“的概念。

在谈隔离级别之前,你首先要知道,你隔离的越严实,效率就会越低。因此很多时候,我们都要在二者之间巡展一个平衡点。SQL标准的事务隔离级别:读未提交(read uncommitted)、读提交(read committed)、可重复度(repeatable read)和串行化(serializable)。下面我逐一解释:

  • 读未提交是指,一个事务还没提交时,它做的变更就能被别的事务看到。
  • 读提交是指,一个事务提交之后,它做的变更才会被其他事务看到。
  • 可重复读是指,一个事务执行过程中看到的数据,总是跟这个事务在启动时看到的数据是一致的。当然在可重复度隔离级别下,未提交变更对其他事务也是不可见的。
  • 串行化,顾名思义是对于同一行记录,”写“会加”写锁“,读会加”读锁“。当出现读写锁冲突的时候,后访问的事务必须等前一个事务执行完成,才能继续执行。

其中”读提交“和”可重复读“比较难理解,所以我用一个例子说明这几种隔离级别。假设数据表T中只有一列,其中一行的值为1,下面是按照时间顺序执行两个事务的行为。

1
2
mysql> create table T(c int) engine=InnoDB;
insert into T(c) values(1);

我们来看看在不同的隔离级别下,事务A会有哪些不同的返回结果,也就是图里面V1、V2、V3的返回值分别是什么。

  • 若隔离级别是”读未提交“,则 V1 的值就是 2。这时候事务 B 虽然还没有提交,但是结果已经被 A 看到了。因此,V2、V3 也都是 2。
  • 若隔离级别是”读提交“,则V1是1,V2 的值是 2。事务 B 的更新在提交后才能被 A 看到。所以, V3 的值也是 2。
  • 若隔离级别是”可重复读“,则V1、V2是1,V3是2、之所以V2还是1,遵循的就是这个要求:事务在执行期间看到的数据前后必须是一致的。
  • 若隔离级别是”串行化“,则在事务B执行”将1改成2“的时候,会被锁住。直到事务A提交后,事务B才可以继续执行。所以从A的角度看,V1、V2值是1,V3的值是2。

在实现上,数据库里面会创建一个视图,访问的时候以视图的逻辑结果为准。在”可重复读“隔离级别下,这个视图是在事务启动时创建的,整个事务存在期间都用这个视图。在”读提交“隔离级别下,这个视图是在每个SQL语句开始执行的时候创建的。这里需要注意的是,”读未提交“隔离级别下直接返回记录上的最新值,没有视图概念;而”串行化“隔离级别下直接用加锁的方式来避免并行访问。

我们可以看到在不同的隔离级别下,数据库行为是有所不同的。Oracle数据库的默认隔离级别其实就是”读提交“,因此对于一些从Oracle迁移到MySQL的应用,为保证数据库隔离级别的一致,一定要记得将MySQL的给级别设置为”读提交“。

配置的方式是,将启动参数transaction-isolation的值设置成READ-COMMITTED。你可以使用show variables

来查看当前的值。

1
2
3
4
5
6
7
8
9
10
11
mysql> show variables like 'transaction_isolation';

+-----------------------+----------------+

| Variable_name | Value |

+-----------------------+----------------+

| transaction_isolation | READ-COMMITTED |

+-----------------------+----------------+

总结来说,存在即合理,每种隔离级别都有自己的使用场景,你要根据自己的业务情况来定。我想你可能会问那什么时候需要”可重复读“的场景呢?我们来看一个数据校对逻辑的案例。

假设你在管理一个个人银行账户表。一个表存了账户余额,一个表存了账单明细。到了月底你要做数据校对,也就是判断上个月的余额和当前余额的差额,是否与本月的账单明细一致。你一定希望在校对过程中,即使有用户发生了一笔新的交易,也不影响你的校对结果。

这时候使用“可重复读”隔离级别就很方便。事务启动时的视图可以认为是静态的,不受其他事务更新的影响。

事务隔离的实现

理解了事务的隔离级别,我们再来看看事务隔离具体是怎么实现的。这里我们展开说明“可重复读”。

在MySQL中,实际上每条记录在更新的时候都会同时记录一条回滚操作(前者记录在redo log,后者记录在undo log)。记录上的最新值,通过回滚操作,都可以得到前一个状态的值。

假设一个值从1被按顺序改成了2、3、4,在回滚日志里面就会有类似下面的记录。

当前值是4,但是在查询这条记录的时候,不同时刻启动的事务会有不同的read-view。如图中看到的,在视图A、B、C里面,这一个记录的值分别是1、2、4,同一条记录在系统中可以存在多个版本,就是数据库的多版本并发控制(MVCC)。对于read-view A,要得到1,就必须将当前值依次执行图中所有的回滚操作得到。

同时你会发现,即使现在有另外一个事务正在将4改成5,这个事务跟read-view A、B、C对应的事务是不会冲突的。

你一定会问,回滚日志总不能一直保留吧,什么时候删除呢?答案是,在不需要的时候才删除。也就是说,系统会判断,当没有事务再需要用到这些回滚日志时,回滚日志会被删除。

什么时候才不需要了呢?就是当系统里没有比这个回滚日志更早的read-view的时候。

基于上面的说明,我们来讨论一下为什么建议你尽量不要使用长事务。

长事务意味着系统里面会存在很老的事务视图。由于这些事务随时可能访问数据库里面的任何数据,所以这个事务提交之前,数据库里面它可能用到的回滚记录都必须保留,这就会导致大量占用存储空间。

在MySQL 5.5及以前的版本,回滚日志是跟数据字典一起放在ibdata文件里的,即使长事务最终提交,回滚段被清理,文件也不会变小。我见过数据只有20GB,而回滚段有200GB的库。最终只好为了清理回滚段,重建整个库。

除了对回滚段的影响,长事务还占用锁资源,也可能拖垮整个库,这个我们会在后面讲锁的时候展开。

事务的启动方式

如上面所述,长事务有这些潜在风险,我当然是建议你尽量避免。其实很多时候业务开发同学并不是有意使用长事务,通常是由于误用所致。MySQL的事务启动方式有以下几种:

  1. 显式启动事务语句,begin或start transaction。配套的提交语句是commit,回滚语句是rollback。
  2. set autocommit=0,这个命令会将这个线程的自动提交关掉。意味着如果你只执行一个select语句,这个事务就启动了,而且不不会自动提交。这个事务持续存在知道你主动执行commit或rollback语句,或者断开连接。

有些客户端连接框架会默认连接成功后先执行一个et autocommit=0的命令。这就导致接下来的查询都在事务中,如果是长连接,就导致了意外的长事务。

因此,我会交易你总是使用set autocommit=1,通过显式语句的方式来启动事务。

但是有的开发同学会纠结“多一次交互”的问题。对于一个需要频繁使用事务的业务,第二中凡是每个事务在开始时都不需要主动执行一次“begin”,减少额语句的交互次数。如果你也有这个顾虑,我建议你使用commit work and chain语法。

在autocommit为1的情况下,用begin显式启动的事务,如果执行commit则提交事务。如果执行commit work and chaini,则是提交事务并自动启动下一个事务,这样也省去了再次执行begin语句的开销。同时带来的好处是从程序开发的角度明确地知道每个语句是否处于事务中。

你可以在information_schema库中的innodb_trx这个表中查询长事务,比如下面这个语句,用于查找持续时间超过60s的事务。

1
select * from information_schema.innodb_trx where TIME_TO_SEC(timediff(now(),trx_started))>60

小结

这篇文章,主要介绍了MySQL的事务隔离级别的现象和实现,根据实现原理分析了长事务存在的风险,以及如何用正确的方式避免长事务,希望举的例子能够帮助你理解事务,并更好的使用MySQL的事务特性。

1.哲学家进餐问题

五个哲学家围着一张圆桌,每个哲学家免签放着食物。哲学家的生活有两种交替活动:吃饭以及思考。当一个哲学家吃法时,需要先拿起自己左右两边的两根筷子,并且一次只能拿起一根筷子。

下面是一种错误的解法,如果所有哲学家同时拿起左手边的筷子,那么所有哲学家都在等到其他哲学家吃完并释放自己手中的筷子,导致死锁。

1
2
3
4
5
6
7
8
9
10
11
12
#define N 5

void philosopher(int i) {
while(TRUE) {
think();
take(i); // 拿起左边的筷子
take((i+1)%N); // 拿起右边的筷子
eat();
put(i);
put((i+1)%N);
}
}

为了防止死锁的发生,可以设置两个条件:

  • 必须同时拿起左右两根筷子;
  • 只有在两个邻居都没有进餐的情况下才允许进餐。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N // 右邻居
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N]; // 跟踪每个哲学家的状态
semaphore mutex = 1; // 临界区的互斥,临界区是 state 数组,对其修改需要互斥
semaphore s[N]; // 每个哲学家一个信号量

void philosopher(int i) {
while(TRUE) {
think(i);
take_two(i);
eat(i);
put_two(i);
}
}

void take_two(int i) {
down(&mutex);
state[i] = HUNGRY;
check(i);
up(&mutex);
down(&s[i]); // 只有收到通知之后才可以开始吃,否则会一直等下去
}

void put_two(i) {
down(&mutex);
state[i] = THINKING;
check(LEFT); // 尝试通知左右邻居,自己吃完了,你们可以开始吃了
check(RIGHT);
up(&mutex);
}

void eat(int i) {
down(&mutex);
state[i] = EATING;
up(&mutex);
}

// 检查两个邻居是否都没有用餐,如果是的话,就 up(&s[i]),使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
state[i] = EATING;
up(&s[i]);
}
}

2.读者-写者问题

允许多个进程同时对数据进行读操作,但是不允许读和写以及写和写操作同时发生。

一个整型变量count记录在对数据进行读操作的进程数量,一个互斥量count_mutex用于对count加锁,一个互斥量data_mutex用于对读写的数据加锁。

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
typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
while(TRUE) {
down(&count_mutex);
count++;
if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁,防止写进程访问
up(&count_mutex);
read();
down(&count_mutex);
count--;
if(count == 0) up(&data_mutex);
up(&count_mutex);
}
}

void writer() {
while(TRUE) {
down(&data_mutex);
write();
up(&data_mutex);
}
}

Travelling Salesman Problem(TSP)旅行商问题:给定一个集合的城市和每一对城市之间的距离,问题是找到最短可能的路径,访问每个城市恰好一次,并且返回出发的城市。

注意汉密尔顿循环问题和TSP问题的区别。汉密尔顿循环问题是要找到是否存在一条完全访问每个城市一次的旅游路线。这里我们知道汉密尔顿循环路线存在(因为图是完整的),事实上很多这样的环存在,问题是找到一个最小权重的汉密尔顿循环。

比如,考虑右图所示的图形。图中一个TSP循环是1-2-4-3-1。旅行的费用是10+25+30+15即80。

这个问题是一个著名的NP问题。这个问题没有多项式时间的已知解。

以下是旅行商问题的不同解法。

朴素的解法:

  1. 将城市1作为起点和终点
  2. 生成所有(n-1)!城市的排列组合
  3. 计算每个排列组合的成本,并跟踪成本最小的排列组合
  4. 返回成本最小的排列组合

时间复杂度:O(n!)

DP 动态递推

让给定的顶点集为{1, 2, 3, 4, ..., n}。让我们把1作为输出的起点和终点。对于每一个其他的顶点i(1除外),我们找到以1为起点,i为终点,且所有顶点只出现一次的最小成本路径。让这条路径的成本为cost(i)。对应CUcle的成本将是cost(i) + dist(i, 1),其中dist(i, 1)是i到1的距离。最后我们返回所有[cost(i) + dist(i, 1)]值的最小值。到目前为止,这看起来很简单。现在的问题是如何得到cost(i)?

为了使用DP计算cost(i),我们需要在子问题方面有一些地推关系。让我们定义一个术语C(S, i)为从1开始,到i结束,精确访问集S中每个顶点一次的最小成本路径的成本。我们从大小为2的所有子集开始,计算S为子集的所有子集的C(S, i),然后我们计算大小为3的所有子集S的C(S, i),以此类推。注意,每个子集中必须有1.

1
2
3
4
If size of S is 2, then S must be {1, i},
C(S, i) = dist(1, i)
Else if size of S is greater than 2.
C(S, i) = min { C(S-{i}, j) + dist(j, i)} where j belongs to S, j != i and j != 1.

对于一个大小为n的集合,我们考虑每个大小为n-1的n-2个子集,使所有子集中没有t(代表集合的排序)。

利用上述递归关系,我们可以写出基于DP的解决方案。最多有O(n*2^n)个子问题,每个子问题的求解都需要线性时间。因此,总的运行时间是O(n^2*2^n)。时间复杂度远小于O(n!),但仍是指数级的。所需空间也是指数级的。所以这种方法即使对于稍高的顶点数量也是不可行的。

我们很快就会讨论旅行推销员问题的近似算法。

参考:

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

软件的开始到后来...

开始:

软件=代码?

软件=算法+数据结构?

软件=算法+数据结构+文档?

软件=算法+数据结构+文档+数据?

后来:

软件=算法+数据结构+文档+数据 + 单元测试 + workflow ?

对自己的要求,至少要做到

软件=算法+数据结构+文档。