CMS

CMS全称 Concurrent Mark Sweep，是一款并发的、使用标记-清除算法的垃圾回收器.

JVM 中,老年代的gc可以使用CMS.

触发点

1 周期性触发

2 条件性触发

• 老年代使用率达到阈值
• 新生代的晋升担保失败

主要是上面两个,还有其他情况暂不考虑.

收集过程

CMS是一种优化的mark-sweep算法,mark-sweep的核心是对象树的遍历, 面临的问题是这个数非常的巨大.但还是基于简单的图的遍历算法:三色标记法.

对象在标记过程中，根据标记情况，分成三类：

1. 白色对象，表示自身未被标记；
2. 灰色对象，表示自身被标记，但内部引用未被处理；
3. 黑色对象，表示自身被标记，内部引用都被处理；

Phase 1: InitialMarking（初始化标记，整个过程STW）

该阶段单线程执行，主要分分为两步：

1. 标记GC Roots可达的老年代对象；
2. 遍历新生代对象，标记可达的老年代对象；

标记结束后,如下图:

Phase 2: Marking（并发标记）

该阶段GC线程和应用线程并发执行，遍历InitialMarking阶段标记出来的存活对象，然后继续递归标记这些对象可达的对象。

因为该阶段并发执行的，在运行期间可能发生

• 新生代的对象晋升到老年代、
• 或者是直接在老年代分配对象、
• 或者更新老年代对象的引用关系等等.

对于这些对象，都是需要进行重新标记的，否则有些对象就会被遗漏，发生漏标的情况。

为了提高重新标记的效率，该阶段会把上述对象所在的Card标识为Dirty，后续只需扫描这些Dirty Card的对象，避免扫描整个老年代。

Phase 3: Concurrent Preclean 预清理

This is again a concurrent phase, running in parallel with the application threads, not stopping them. While the previous phase was running concurrently with the application, some references were changed. Whenever that happens, the JVM marks the area of the heap (called “Card”) that contains the mutated object as “dirty” (this is known as Card Marking).

总的来说, 这个阶段是一个并行的标记过程.

主要目的:减轻Final remark的执行时间.

主要做两件事情：

1. 处理新生代已经发现的引用，比如在并发阶段，在Eden区中分配了一个A对象，A对象引用了一个老年代对象B（这个B之前没有被标记），在这个阶段就会标记对象B为活跃对象。
2. 在并发标记阶段，如果老年代中有对象内部引用发生变化，会把所在的Card标记为Dirty（其实这里并非使用CardTable，而是一个类似的数据结构，叫ModUnionTalble），通过扫描这些Table，重新标记那些在并发标记阶段引用被更新的对象（晋升到老年代的对象、原本就在老年代的对象）. Dirty card 会被清理干净,当这个card中的对象的可达对象都被标记之后.如下面三个图:

#####

Phase 4: Concurrent Abortable Preclean 可中断的预清理

又是一个并行的标记过程.

主要目的: 减轻Final Remark 的执行时间.

该阶段发生的前提是，新生代Eden区的内存使用量大于参数CMSScheduleRemarkEdenSizeThreshold 默认是2M，如果新生代的对象太少，就没有必要执行该阶段，直接执行重新标记阶段。

在该阶段，主要循环的做两件事：

1. 处理 From 和 To 区的对象，标记可达的老年代对象
2. 和上一个阶段一样，扫描处理Dirty Card中的对象

当然了，这个逻辑不会一直循环下去，打断这个循环的条件有三个：

1. 可以设置最多循环的次数 CMSMaxAbortablePrecleanLoops，默认是0，意思没有循环次数的限制。
2. 如果执行这个逻辑的时间达到了阈值CMSMaxAbortablePrecleanTime，默认是5s，会退出循环。
3. 如果新生代Eden区的内存使用率达到了阈值CMSScheduleRemarkEdenPenetration，默认50%，会退出循环。（这个条件能够成立的前提是，在进行Precleaning时，Eden区的使用率小于十分之一）

如果在循环退出之前，发生了一次YGC，对于后面的Remark阶段来说，大大减轻了扫描年轻代的负担，但是发生YGC并非人为控制，所以只能祈祷这5s内可以来一次YGC。

Phase 5: Final Remark (STW)

这是第二个会STW的步骤,也是最后一个.这个步骤的目的是标记Old Generation中的所有存活对象. 因为之前的标记步骤都是和用户线程并发进行的,所以需要一个STW来确保所有的存活对象不会被误回收.

进行如下的处理：

1. 遍历新生代对象，重新标记
2. 根据GC Roots，重新标记
3. 遍历老年代的Dirty Card，重新标记，这里的Dirty Card大部分已经在clean阶段处理过

之所以要在之前进行Phase 3,4,主要原因是为了减少标记的时间,虽然在phase5中还是要从ROOT扫描全部,但是已经标记过的对象就会快速跳过.

Phase 6: Concurrent Sweep

清理垃圾对象，这个阶段GC线程和用户线程并发执行。

Phase 7: Concurrent Reset

重置CMS收集器的数据结构，做好下一次执行GC任务的准备工作。

参考

Garbage Collection

Copying Garbage Collection

简单来说,内存分为2个区域,使用其中一个区域分配内存,直到剩余内存不足,则触发GC:遍历所有的ROOT,将可达的对象copy到另外一块内存区域中.

好处: 内存分配相当的快,只是指针的移动.

坏处: 浪费内存.

#Mark and Sweep Garbage Collection

sweep: 扫除; 打扫，清理;

标记，清理垃圾回收

伪代码：

1
2
3
4
5
6
7
8
9
10
11

void GC()
{
    HaltAllProcessing();
    // 枚举root
    ObjectCollection roots = GetRoots();
    for(int i = 0; i < roots.Count(); ++i)
        //标记
        Mark(roots[i]);
    //清理
    Sweep();
}

##枚举root

遍历这些地方的所有reference : registers, global or static fields, local variables on the stack, function arguments on stack。

标记

利用每个对象的header中的marked flag，进行标记

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

void Mark(Object* pObj)
{
    if (!Marked(pObj)) // Marked returns the marked flag from object header
    {
        MarkBit(pObj); // Marks the flag in obj header

        // Get list of references that the current object has
        // and recursively mark them as well
        ObjectCollection children = pObj->GetChildren();
        for(int i = 0; i < children.Count(); ++i)
        {
            Mark(children[i]); // recursively call mark
        }	
    }
}

利用递归的方法进行标记。

清理

通过遍历整个内存并释放未标记的内存块来开始扫描。它还会清除标记位，以便后续GC通过可以正确标记/取消标记它们。

1
2
3
4
5
6
7
8
9
10
11
12
13

void Sweep()
{
	//遍历整个内存
    Object *pHeap = pHeapStart;
    while(pHeap < pHeapEnd)
    {
        if (!Marked(pHeap))
            Free(pHeap); // put it to the free object list
        else
            UnMarkBit(pHeap);
        pHeap = GetNext(pHeap);
    }
}

压缩

长期的进行GC，可能会导致内存碎片。回收后的压缩能减少碎片，但是，当内存被压缩时，对象会移动，因此必须更新对它们的所有引用以指向新位置。

溢出处理

垃圾回收面对的是一个非常巨大的对象树，之前的Mark-sweep伪代码中，使用递归的方法，容易引起stack overflow。

我们可以用一个MarkStack来代替递归，然后使用广度优先来遍历，来尽量避免overflow。但是如果溢出还是不能完全避免，如果发生了溢出，可以采取一些fallbakc 方法：

• Overflow stack

  我们会有另外一个stack，叫overflow stack。如果mark steack 满了，object会被塞入overflow stack，并且暂时不去遍历它的孩子节点。

• Overflow-arena

  对于overflow stack 都overflow的情况，使用一个链表保存溢出的对象。

优点和缺点

优点：可以处理循环引用，而且对平时的处理没有额外的开销（相对引用计数而言）

缺点：1 stw

2 需要遍历整个内存

对这两个缺点，Mark-sweep算法也有很多优化的版本，如JVM的 CMS。

Generational Garbage Collection

分代垃圾收集的思想是基于基本的垃圾回收算法之上的.

上面提到的一个mark-sweep的一个重要缺点就是会导致系统暂停。用于解决该问题的主要优化方法之一是采用分代垃圾收集。分代垃圾收集基于以下几个特点:

• 大部分对象在很年轻的时候就死了
• GC中回收的对象有90%是在上次GC之后创建的
• 如果一个对象在一次GC中存活, 它在短期内变成垃圾的概率很低

一种常见的方法是将新创建的对象视为在第0代（Gen0）中，然后如果它没有被垃圾收集循环收集，则将其提升到下一个更高代的Gen1. 更频繁地收集较低代. 这可确保降低系统暂停时间. 触发较高代的集合的次数较少. 使用了多少代，因系统而异. 在.NET中使用了3代。为简单起见，我们将考虑使用2代系统，但概念很容易扩展到2代以上.

高代到低代的引用

分代垃圾回收器(Generational garbage collectors)需要跟踪 老年代->年轻代的引用, 以便在对年轻代回收时, 不用去遍历老年代的所有对象.

为什么只用考虑老年代中指向了年轻代的引用?

因为年轻代的内存次数远大于老年代, 且老年代的内存空间一般会更大.并且经过统计信息显示，老年代持有新生代对象引用的情况不足1%.其实在对老年代GC的时候,也是需要考虑年轻代中的对老年代中对象的引用.

Write Barrier定义

如果store操作把一个老年代的引用指向了一个新的object(一般在年轻代中),系统必须保证这个位置被记录到remember set中, 这种机制,通常被叫做 write barrier 或者 store check

在非函数式语言中, store操作是很频繁的,所以一个高效的write barrier实现是很必要的.

card marking 是write barrier的一种实现.

card marking实现

堆被划分为固定大小的card,每个card都关联到一个bit vector中的一个bit. store操作如果改变了这个card中内容,对应的bit会被设置.在垃圾收集时，收集器扫描bit vector，每当找到标记位时，检查对应的堆中相应card中的所有指针。

HotSpot中的Write barrier

• dirty card

  card marking方式

• SATB

  snapshot-at-the-beginning, 被G1收集器采用.

###write barrier + card-table

首先创建一个称为卡表(card-table)的表。这本质上是一个位数组。每个位指示给定范围的内存是否脏（包含对较低生成对象的写入）。例如。我们可以使用单个位来标记4KB块。

第一次标记仅针对Gen0对象。一旦结束，它会检查卡表以找到Gen1中的脏块。然后，它将该脏块中的每个对象视为新根，并使用它标记对象。

##参考链接

#JVM synchronizer

SafePoint

避免程序长时间运行而不进入safepoint

markword

markword是java对象数据结构中的一部分。

markword数据的长度在32位和64位的虚拟机（未开启压缩指针）中分别为32bit和64bit，它的最后2bit是锁状态标志位，用来标记当前对象的状态

CAS的问题

CAS为什么会引入本地延迟？这要从SMP（对称多处理器）架构说起。下图大概表明了SMP的结构：

其意思是所有的CPU会共享一条系统总线（BUS），靠此总线连接主存。每个核都有自己的一级缓存，各核相对于BUS对称分布，因此这种结构称为“对称多处理器”。

CAS的全称为Compare-And-Swap，是一条CPU的原子指令。Core1和Core2可能会同时把主存中某个位置的值Load到自己的L1 Cache中，当Core1在自己的L1 Cache中修改这个位置的值时，会通过总线，使Core2中L1 Cache对应的值“失效”，而Core2一旦发现自己L1 Cache中的值失效（称为Cache命中缺失）则会通过总线从内存中加载该地址最新的值，大家通过总线的来回通信称为“Cache一致性流量”，因为总线被设计为固定的“通信能力”，如果Cache一致性流量过大，总线将成为瓶颈。

全局安全点

偏向锁(Biased Locking)

偏向锁就是为了消除CAS，消除无竞争情况下的同步原语，即轻量锁的CAS。

它会偏向于第一个访问锁的线程，如果在运行过程中，同步锁只有一个线程访问，不存在多线程争用的情况，则线程是不需要触发同步的，减少加锁／解锁的一些CAS操作（比如等待队列的一些CAS操作），这种情况下，就会给线程加一个偏向锁。 如果在运行过程中，遇到了其他线程抢占锁，则持有偏向锁的线程会被挂起，JVM会消除它身上的偏向锁，将锁恢复到标准的轻量级锁。

就是说如果同一时间只有一个线程来获取锁的话，是满足偏向锁的条件的

问题1 ：偏向锁什么时候升级为轻量锁，怎么升级

btree的go实现：https://github.com/sutoo/btree/blob/master/btree.go

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

// Item represents a single object in the tree.
type Item interface {
	// Less tests whether the current item is less than the given argument.
	//
	// This must provide a strict weak ordering.
	// If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only
	// hold one of either a or b in the tree).
	Less(than Item) bool
}

type items []Item
// children stores child nodes in a node.
type children []*node

// node is an internal node in a tree.
//
// It must at all times maintain the invariant that either
//   * len(children) == 0, len(items) unconstrained
//   * len(children) == len(items) + 1
type node struct {
	items    items
	children children
	cow      *copyOnWriteContext
}
// BTree is an implementation of a B-Tree.
//
// BTree stores Item instances in an ordered structure, allowing easy insertion,
// removal, and iteration.
//
// Write operations are not safe for concurrent mutation by multiple
// goroutines, but Read operations are.
type BTree struct {
	degree int
	length int
	root   *node
	cow    *copyOnWriteContext
}

node是Btree中的一个节点。

items 表示key的列表， items中的gap对应一个children node。

###BTree Struct

方法介绍：

maxItems degree * 2 -1 ，每个node中，items的最大值。

minItemsdegree - 1，node中，items的最小值。

###Btree and B+tree

Btree:

B+tree:

###transaction locks

维护在不同的Isolation level下数据库的Atomicity和Consistency两大基本特性。

• table locks

  对整个表加锁，影响所有记录。通常用在DDL语句中，如DELETE TABLE,ALTER TABLE等。

• row locks

  对一行记录加锁，只影响一条记录。通常用在DML语句中，如INSERT, UPDATE, DELETE等。

InnoDB定义了如下的lock mode:

1
2
3
4
5
6
7
8

/* Basic lock modes */
enum lock_mode {
LOCK_IS = 0,     /* intention shared */
LOCK_IX,     /* intention exclusive */
LOCK_S,          /* shared */
LOCK_X,          /* exclusive */
LOCK_AUTO_INC,     /* locks the auto-inc counter of a table
......

• shared lock （S) 容许获得锁的事务去 读一行

• exclusive lock （X) 容许获得锁的事务去更新或者删除一行

• Intention shared （IS） 获取IS表示事务希望获取S锁（或更高）。在获取这一行的S锁之前，需要先获取表的IS

• Intention exclusive （IX） 获取IX表示事务希望获取X锁。在获取这一行的X锁之前，需要先获取表的IX。

####lock type compatibility：

####解释：

S，X锁，就像是读写锁，S是读锁，X是写锁。（注：S锁只有IN SHARE MODE才会加。一般的select是consistent read）。在给一行记录加锁前，首先要给该表加意向锁。

####意向锁的作用：

1

The main purpose of intention locks is to show that someone is locking a row, or going to lock a row in the table.

为方便检测table lock 和 row lock之间的冲突，引入了意向锁。

当再向一个表添加表级X锁的时候

• 如果没有意向锁的话，则需要遍历所有整个表判断是否有行锁的存在，以免发生冲突
• 如果有了意向锁，只需要判断该意向锁与即将添加的表级锁是否兼容即可。因为意向锁的存在代表了，有行级锁的存在或者即将有行级锁的存在。因而无需遍历整个表，即可获取结果

###内存锁

为了维护内存结构的一致性，比如Dictionary cache、sync array、trx system等结构。 InnoDB并没有直接使用glibc提供的库，而是自己封装了两类：

1. 一类是mutex，实现内存结构的串行化访问
2. 一类是rw lock，实现读写阻塞，读读并发的访问的读写锁

###Row Level Lock 细分

####Record Locks

在index records上的锁。比方说：

1

SELECT c1 FROM t WHERE c1 = 10 FOR UPDATE;

这个就为c1 = 10的这个索引加了锁，防止其他事物对所有c1=10的行做inserting, updating,deleting操作。

Gap Locks

是一种在index records之间的一种锁。

1

SELECT c1 FROM t WHERE c1 BETWEEN 10 and 20 FOR UPDATE;

阻止其他事物向c1 的10～20区间内，插入数据。（只有插入）

在gap lock锁定的范围内，可以有0～n个index records。

gap lock 是在性能和一致性上的一个折衷，只在某些事物隔离级别下生效。

特点：

1 使用unique index来查单条的语句不会用到gap lock

2 gap lock之间不会有冲突，X-gap lock 和S-gap lock没什么区别。

3 gap lock只是为了防止向一个区间内插入

Next-Key Locks

是record lock 和gap lock的组合：当前index record 的 record lock + 当前index record之前的区域的 gap lock。

举例：index record为10，11，13，20，则next-key lock可以有以下几种可能：

1
2
3
4
5

(negative infinity, 10]
(10, 11]
(11, 13]
(13, 20]
(20, positive infinity)

作用：

1

By default, InnoDB operates in REPEATABLE READ transaction isolation level. In this case, InnoDB uses next-key locks for searches and index scans, which prevents phantom rows

InnoDB使用next-key locks 来防止幻读。

幻读，就是在一个事物内，两次select，第二次得到了一个新的row。

所以在锁住当前记录的同事，要把他到前一个记录的‘gap’也锁住。才能保证。不会出现新的纪录。

Insert Intention Locks

//TODO

AUTO-INC Locks

是一个table level的锁，当传入有AUTO_INCREMENT列的字段的时候。如果一个事物在插入几条记录，其他事物也想插入时，必须等待。否则第一个事物就无法获取到连续的自增值。当然，自增序列的顺序的可预见性和插入的并发性能，也是一个权衡的点，可以通过innodb_autoinc_lock_mode来设置。

具体参考：https://dev.mysql.com/doc/refman/8.0/en/innodb-auto-increment-handling.html

###

###Transaction Isolation Levels

事物隔离级别，是ACID中的I。

前置知识：

Consistent Reads： 无锁的select，（plain select）,MVCC

1

A consistent read means that InnoDB uses multi-versioning to present to a query a snapshot of the database at a point in time.

Locking Reads：SELECT with FOR UPDATE or FOR SHARE, UPDATE, and DELETE statements

Repeatalbe Read

innoDB默认隔离级别。

• Consistent Reads，即无锁的select，读的都是事物中第一个select得到的snapshot。
• Locking Reads
  • 使用了唯一索引：只有record lock
  • 没使用惟一索引：使用next-key lock 锁住区间。

Read Commited

• Consistent Reads：每一个select（即使在同一个事物内）都是一个新的snapshot。

• Locking Reads：只上Record lock，无gap lock或next-lock

所以，幻读出现。

####READ UNCOMMITTED

SERIALIZABLE

Locks Set by Different SQL Statements in InnoDB

• Select ... from...是consistent read,读一个snapshot。除非是SERIALIZABLE隔离级别，这个时候，设置shared next-key lock。
• select ... for update 和 select ... for share会加X next-key lock。如果是唯一索引，会加record lock。
• Update...where..会加 X next-key lock。如果是唯一索引，会加record lock。
• delete from ... where加X next-key lock。如果是唯一索引，会加record lock。
• insert会给当前插入的行加record lock。

参考：https://dev.mysql.com/doc/refman/8.0/en/innodb-locks-set.html

Consistent Reads

consistent reads的含义是InnodB使用multi-versioning去给查询提供一个数据库的snapshot。查询只能看到这个点之前提交的事物的改动，而对之后的一无所知。

Consistent read is the default mode in which InnoDB processes SELECT statements in READ COMMITTEDand REPEATABLE READ isolation levels.

A consistent read does not set any locks on the tables it accesses,

If you want to see the “freshest” state of the database, use either the READ COMMITTED isolation level or a locking read:

1

SELECT * FROM t FOR SHARE;

参考：https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html

Undo

Undo Log是为了实现事务的原子性，在MySQL数据库InnoDB存储引擎中，还用UndoLog来实现多版本并发控制(简称：MVCC)。 -事务的原子性(Atomicity) 事务中的所有操作，要么全部完成，要么不做任何操作，不能只做部分操作。如果在执行的过程中发了错误，要回滚(Rollback)到事务开始前的状态，就像这个事务从来没有执行过。

参考：https://www.cnblogs.com/kongzhongqijing/articles/7905051.html

Redo

记录的是新数据的备份。在事务提交前，只要将Redo Log持久化即可，不需要将数据持久化。当系统崩溃时，虽然数据没有持久化，
但是RedoLog已经持久化。系统可以根据RedoLog的内容，将所有数据恢复到最新的状态。

InnoDB有buffer pool（简称bp）。bp是数据库页面的缓存，对InnoDB的任何修改操作都会首先在bp的page上进行，然后这样的页面将被标记为dirty并被放到专门的flush list上，后续将由master thread或专门的刷脏线程阶段性的将这些页面写入磁盘（disk or ssd）。这样的好处是避免每次写操作都操作磁盘导致大量的随机IO，阶段性的刷脏可以将多次对页面的修改merge成一次IO操作，同时异步写入也降低了访问的时延。然而，如果在dirty page还未刷入磁盘时，server非正常关闭，这些修改操作将会丢失，如果写入操作正在进行，甚至会由于损坏数据文件导致数据库不可用。为了避免上述问题的发生，Innodb将所有对页面的修改操作写入一个专门的文件，并在数据库启动时从此文件进行恢复操作，这个文件就是redo log file。这样的技术推迟了bp页面的刷新，从而提升了数据库的吞吐，有效的降低了访问时延。带来的问题是额外的写redo log操作的开销（顺序IO，当然很快），以及数据库启动时恢复操作所需的时间。

redo log包括两部分：

• 一是内存中的日志缓冲(redo log buffer)，该部分日志是易失性的；
• 二是磁盘上的重做日志文件(redo log file)，该部分日志是持久的。

在概念上，innodb通过force log at commit机制实现事务的持久性，即在事务提交的时候，必须先将该事务的所有事务日志写入到磁盘上的redo log file和undo log file中进行持久化。

为了确保每次日志都能写入到事务日志文件中，在每次将log buffer中的日志写入日志文件的过程中都会调用一次操作系统的fsync操作(即fsync()系统调用)。因为MariaDB/MySQL是工作在用户空间的，MariaDB/MySQL的log buffer处于用户空间的内存中。要写入到磁盘上的log file中(redo:ib_logfileN文件,undo:share tablespace或.ibd文件)，中间还要经过操作系统内核空间的os buffer，调用fsync()的作用就是将OS buffer中的日志刷到磁盘上的log file中。

也就是说，从redo log buffer写日志到磁盘的redo log file中，过程如下：

MySQL支持用户自定义在commit时如何将log buffer中的日志刷log file中。这种控制通过变量 innodb_flush_log_at_trx_commit 的值来决定。该变量有3种值：0、1、2，默认为1。但注意，这个变量只是控制commit动作是否刷新log buffer到磁盘。

• 当设置为1的时候，事务每次提交都会将log buffer中的日志写入os buffer并调用fsync()刷到log file on disk中。这种方式即使系统崩溃也不会丢失任何数据，但是因为每次提交都写入磁盘，IO的性能较差。
• 当设置为0的时候，事务提交时不会将log buffer中日志写入到os buffer，而是每秒写入os buffer并调用fsync()写入到log file on disk中。也就是说设置为0时是(大约)每秒刷新写入到磁盘中的，当系统崩溃，会丢失1秒钟的数据。
• 当设置为2的时候，每次提交都仅写入到os buffer，然后是每秒调用fsync()将os buffer中的日志写入到log file on disk。

参考：

https://www.cnblogs.com/f-ck-need-u/archive/2018/05/08/9010872.html

https://www.cnblogs.com/kongzhongqijing/articles/7905051.html

MVCC

上述更新前建立undo log，根据各种策略读取时非阻塞就是MVCC，undo log中的行就是MVCC中的多版本，这个可能与我们所理解的MVCC有较大的出入，一般我们认为MVCC有下面几个特点：

• 每行数据都存在一个版本，每次数据更新时都更新该版本
• 修改时Copy出当前版本随意修改，各个事务之间无干扰
• 保存时比较版本号，如果成功（commit），则覆盖原记录；失败则放弃copy（rollback）

就是每行都有版本号，保存时根据版本号决定是否成功，听起来含有乐观锁的味道，而Innodb的实现方式是：

• 事务以排他锁的形式修改原始数据
• 把修改前的数据存放于undo log，通过回滚指针与主数据关联
• 修改成功（commit）啥都不做，失败则恢复undo log中的数据（rollback）

二者最本质的区别是，当修改数据时是否要排他锁定，如果锁定了还算不算是MVCC？

Innodb的实现真算不上MVCC，因为并没有实现核心的多版本共存，undo log中的内容只是串行化的结果，记录了多个事务的过程，不属于多版本共存。但理想的MVCC是难以实现的，当事务仅修改一行记录使用理想的MVCC模式是没有问题的，可以通过比较版本号进行回滚；但当事务影响到多行数据时，理想的MVCC据无能为力了。

比如，如果Transaciton1执行理想的MVCC，修改Row1成功，而修改Row2失败，此时需要回滚Row1，但因为Row1没有被锁定，其数据可能又被Transaction2所修改，如果此时回滚Row1的内容，则会破坏Transaction2的修改结果，导致Transaction2违反ACID。

理想MVCC难以实现的根本原因在于企图通过乐观锁代替二段提交。修改两行数据，但为了保证其一致性，与修改两个分布式系统中的数据并无区别，而二提交是目前这种场景保证一致性的唯一手段。二段提交的本质是锁定，乐观锁的本质是消除锁定，二者矛盾，故理想的MVCC难以真正在实际中被应用，Innodb只是借了MVCC这个名字，提供了读的非阻塞而已。

Consul

整体架构

10,000 foot view

• Agent

Agent是在consul集群上一直运行的后台进程，通过 “consul agent” 启动，可以以两种方式运行：客户端，服务器。上图的每个长方形就是一个Agent。

• Client

表示Agentl的客户端模式（紫色方块）。是consul节点的一种模式，这种模式下，所有注册到当前节点的服务会被转发到SERVER，本身是不持久化这些信息。

• Server

SERVER表示consul的服务器模式（红色方块）。表明这个consul是个server，这种模式下，功能和CLIENT都一样，唯一不同的是，它会把所有的信息持久化的本地，这样遇到故障，信息是可以被保留的。

• Server-Leader

它和其它SERVER不一样的一点是（红色方块，带LEADER字样的），它需要负责同步注册的信息给其它的SERVER，同时也要负责各个节点的健康监测。

• DateCenter

  在consul中，datacenter被定义为：私有，低延迟，高带宽。所以不会跨公网的情况。

server 和client

还是看下上面的图， 图中有2个数据中心。consul是支持

**多数据中心**

的。每个DataCenter 包含多个 server 和client， 但是server 可能只有 3到5个，多了的话可能会变慢。因为server间要保持一致性。client没有这样的限制，他们可以成千上万。

LAN Gossip Pool

数据中心中所有的节点，都在一个 gossip protocol中，有2个目的：

1 新增的节点可以被自动发现。

2 失效节点的检测是分布式的。（这里可以看下gossip的实现）

server-leader 的特殊职责

leader负责处理所有请求和事务。非leader的sercer收到rpc请求的时候，会把它转给leader。

WAN gossip pool

所有DataCenter的server同时也是WAN gossip pool的一部分。与LAN Gossip Pool不同的是： 对公网的高延迟做了优化。

带来的好处：DataCenter之间可以互相发现，新增一个DateCenter会很简单，join进来就可以。

同时支持了跨DC的RPC调用，在 failure detection，connection cache，multiplexing等技术的应用，跨DC的调用也不是很慢。

问题： 跨DC调用是可以的，但是数据可能是按DC分片的，怎么解决？

答： There are some special situations where a limited subset of data can be replicated, such as with Consul’s built-in ACL replication capability, or external tools like consul-replicate.

一致性

Raft in Consul

只有server节点参与Raft。

Raft 主要被分成了领导人选举，日志复制和安全三个模块

• 领导选举：一个新的领导人需要被选举出来，当现存的领导人宕机的时候
• 日志复制：领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同。
• 安全性：在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。

任期在 Raft 算法中充当逻辑时钟的作用

两种类型的 RPCs。

• 请求投票（RequestVote） RPCs 由候选人在选举期间发起 ，
• 然后附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制

领导者周期性的向所有跟随者发送心跳包来维持自己的权威

###复制状态机

复制状态机通常都是基于复制日志实现的，如图 1。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。

保证复制日志相同就是一致性算法的工作了。

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

#CMS

全称 Concurrent Mark Sweep

本质是标记-清除算法，针对老年代的GC。进行了改进，缩短了STW的时间。

阶段：

• 初始标记 Initial Mark（STW）

  标记GC ROOT和年轻代对象能直接关联到的对象。

  

• 并发标记

  由前阶段标记过的对象出发，所有可到达的对象都在本阶段中标记。 GC线程和用户线程并发执行。Old代不是所有存活对象会被标记

• 并发预清理 Concurrent Preclean

  JVM将包含变异对象的堆区域（称为“Card”）标记为“脏”

  

• Concurrent Abortable Preclean

  ？？

• Final Remark （STW）

  最终标记所有的老年代的存活对象。

• Concurrent Sweep

  删除未标记的对象并回收它们占用的空间。

###安全点（safepoint）

程序只有在运行到安全点的时候，才可以暂停下来。HotSpot采用主动中断的方式，让执行线程在运行期轮询是否需要暂停的标志，若需要则中断挂起。

可达性

1.本身是根对象。根（root）是指由堆以外空间访问的对象。JVM会将以下对象标记为根：

a.虚拟机栈（栈帧中的本地变量表）中引用的对象；

b.方法区中的类静态属性引用的对象；

c.方法区中的常量引用的对象；

d.本地方法栈中JNI的引用对象。

2.被一个可达的对象引用。

参考：https://plumbr.io/handbook/garbage-collection-algorithms-implementations/concurrent-mark-and-sweep

Hystrix

##

Command模式解决什么问题

What solution does the Command design pattern describe?

• Define separate (command) objects that encapsulate a request.
• A class delegates a request to a command object instead of implementing a particular request directly.

What problems can the Command design pattern solve?

• Coupling the invoker of a request to a particular request should be avoided. That is, hard-wired requests should be avoided.
• It should be possible to configure an object (that invokes a request) with a request.

Implementing (hard-wiring) a request directly into a class is inflexible because it couples the class to a particular request at compile-time, which makes it impossible to specify a request at run-time.

总结：Hystrix的command模式带来的好处是在运行时，可以动态切换对某个client的方法的实现。（fallback）

Hystrix的设计原则

• 防止任何单个依赖项用尽所有容器（例如Tomcat）用户线程。
• 甩负荷（Shedding load）并快速失败而不是排队。
• 在可行的地方提供fallback以保护用户免于失败。
• 使用隔离技术来限制任何一个依赖项的影响。
• 通过近实时指标，监控和警报优化问题发现时间。

执行流程

有4种方式可以执行一个command：

• 同步执行

  execute()— 阻塞式调用，返回一个单个的response。当调用execute()实际上会调用queue().get()

• 异步执行

  queue() — 返回一个Future，用这个Future可以获取一个单个的response。实际会调用toObservable().toBlocking().toFuture()

• 响应式执行（hot）

  observe()— 返回一个Observable，并且立刻订阅。 实际会调用 toObservable().subscribe(subject)

• 响应式执行 （cold）

  toObservable()— 返回一个Observable，当被订阅的时候，才开始执行指令。

1
2
3
4

K             value   = command.execute();
Future<K>     fValue  = command.queue();
Observable<K> ohValue = command.observe();         //hot observable
Observable<K> ocValue = command.toObservable();    //cold observable

注解方式

• 同步执行

1
2
3

@HystrixCommand //execute()
public User getUserById(String id) {
}

• 异步执行

1
2
3

@HystrixCommand //queue()
public Future<User> getUserByIdAsync(final String id) {
}

• 响应式执行

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

@HystrixCommand（observableExecutionMode = EAGER）//observable()
//or
@HystrixCommand（observableExecutionMode = LAZY）//toObservable()
public Observable<User> getUserById(final String id) {
     return Observable.create(new Observable.OnSubscribe<User>() {
                @Override
                public void call(Subscriber<? super User> observer) {
                    try {
                        if (!observer.isUnsubscribed()) {
                            observer.onNext(new User(id, name + id));
                            observer.onCompleted();
                        }
                    } catch (Exception e) {
                        observer.onError(e);
                    }
                }
      });
}

隔离

Thread pool

好处：安全，能够将client看作黑盒。

坏处：耗时增加，每一个command的执行都要经历queueing, scheduling和线程切换。

Semaphores

好处：没有额外的消耗

坏处：因为无法主动中断，必须完全相信client能够快速失败。

Sequence Diagram

@adrianb11 has kindly provided a sequence diagram demonstrating the above flows

Hystrix 参数调整

Timeout

• 用接近99.5线的值来设置Thread Timeout。

• 如果容许重试的话，Thread Timeout和NetworkTimeout要配合起来，留够一次retry的时间：

  ThreadTimeout >（NetworkTimeOut + retry的预估用时）
  

• NetworkTimeout的一般被设置为在网络层可以拦截最耗时的1%的请求。

ThreadPool

• 线程池大小 = 每秒请求数*99线的响应时间（以秒为单位）

queued + poolSize = 并发数

队列过长，会导致响应时间增加。

Hystrxi的treahdpool的配置和java的线程池一样。

Metrix

Metric

Metric

参考：

https://blog.csdn.net/xiaojia1100/article/details/65631778

https://en.wikipedia.org/wiki/Command_pattern

https://github.com/Netflix/Hystrix/wiki

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ThreadPoolExecutor.html

#Observable基础：

基本的类：

1
2
3
4
5
6
7
8
9
10

public class Observable<T> {
    final OnSubscribe<T> onSubscribe;
    public interface OnSubscribe<T> extends Action1<Subscriber<? super T>> {
           // cover for generics insanity
    }
}

public interface Action1<T> extends Action {
    void call(T t);
}

例子：

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

//给Observable的onSubscribe赋值了我们定义的OnSubscribe对象
Observable.create(new Observable.OnSubscribe<String>() {
    @Override
    public void call(Subscriber<? super String> subscriber) {
        subscriber.onNext("hello");
    }
})
    //subscribe这个函数做了什么事?
    //调用Observable中的OnSubscribe对象的call方法，以下面的Subscriber对象作为参数。
    .subscribe(new Subscriber<String>() {
    @Override
    public void onCompleted() {

    }

    @Override
    public void onError(Throwable e) {

    }

    @Override
    public void onNext(String s) {
        Log.d("rx", s);
    }
});

A Histogram measures the distribution of values in a stream of data

直方图描述数据流中的数据分布情况。

直方图不仅仅能提供最大，最小，平均值，而且可以提供median（中位线）或者99th线。

计算直方图的基本方法：排序。但是对吞吐量大，低延迟要求的系统，不适用。下面介绍下常用的方法。

dropwizard

一个开源的Metrics库，https://metrics.dropwizard.io/3.2.3/manual/core.html#exponentially-decaying-reservoirs。采用了下面的方法来统计Histogram。

reservoir sampling （蓄水池采样）

在一个给定长度的数组中随机等概率抽取一个数据很容易，但如果面对的是长度未知的海量数据流呢？蓄水池采样(Reservoir Sampling)算法就是来解决这个问题的, 它在分析一些大数据集的时候非常有用。

先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n，证明如下

第m个对象被选中的概率=选择m的概率 x（其后元素不被选择的概率+其后元素被选择的概率 x 不替换第m个对象的概率），即

• Uniform Reservoirs

  统计全量数据，通过 Vitter’s R算法，来随机选取数据。用于长时间的测量。

• Exponentially Decaying Reservoirs

  只看最后5分钟的数据，通过使用 forward-decaying priority reservoir来对新数据进行指数加权。不像Uniform Reservoirs，它只展示最近的数据，可以让你尽早的发现数据的变化

• Sliding Window Reservoirs

  只关注最后N个

• Sliding Time Window Reservoirs

  只关注最后N秒内

SlidingTimeWindowReservoirs 因为它是无界的，如果被用在一个大吞吐量的系统，会造成大量的内存浪费，因为它记录每一个measurement，所以也是最慢的。

但是看到了这篇文章：https://medium.com/hotels-com-technology/your-latency-metrics-could-be-misleading-you-how-hdrhistogram-can-help-9d545b598374

Dropwizard内部默认使用Exponentially decaying Reservoirs （EDR）

但是有以下缺点：

• EDR设计有损;它们不存储每个样本（它们具有统计学上的代表性）。
• 默认情况下，EDR存储静态1028个样本，并且样本在过去5分钟内被加权。
• EDR中样本衰减的速率受直方图更新频率的影响。

这些缺点加起来意味着您报告的指标可能会产生误导，要么是由于丢弃的样本导致的不准确，要么是通过包含可能更旧的样本来计算的。虽然提供代替方案，但都不适合实时报告。

HdrHistogram（高动态范围直方图）是一种无损直方图实现，具有可配置的值精度，可解决EDR的缺点。

HdrHistogram

//TODO