参考资料

https://tech.meituan.com/innodb-lock.html

摘要

快照读(读): select语句
当前读(写): 增删改语句;特殊读(select * from table where ? lock in share mode).

快照读: 使用乐观锁(MVCC);
当前读: 使用间隙锁(其实是行锁+间隙锁=>nextKey锁)。

规范中的可重复读: 有幻读问题;
Mysql中的可重复读: 快照读没有幻读问题.

RC: update只有行锁
RR(Mysql默认隔离级别): update where有间隙锁。（可能锁住不需要锁的范围）

之前一直对mysql中间隙锁有点迷糊, 不知道为什么有了MVCC这么好的东西,还需要间隙锁。
今天看了美团的技术博客才恍然大悟。

MVCC其实就是乐观锁:
优点: 并发性能好;
缺点: 实效性差,本质上读到的是快照(历史数据).

对于实效性要求比较高的写操作,MVCC是不可用的,比如:

1

update class_teacher set class_name='xxx' where teacherid=30;

这种操作如果要达到没有幻读,就要使用间隙锁.
间隙锁顾名思义,就是把teacherid=30的左边的间隙和右边的间隙都锁上,不能插入新的teacherid=30的。

如果现有teacherid总共有10,30,50三种，会对(10,50)都上锁,其中30的是行锁,[10,30),(30,50]的是间隙锁.
这个时候,不但30的插入不了,20的也插入不了了,因为正好在区间内。

特殊情况: 如果teacherid没有索引,那么也没什么间隙可以锁了,于是mysql就只好锁全表了.

以上说的间隙锁，只在RR(可重复读,mysql默认隔离级别下会有);
如果是RC，那只有行锁了，会出现幻读。

不符合规范的优化:
mysql加了范围锁以后,会把不符合条件的行锁提前释放.而这种操作是不符合两段锁规范的,两段锁协议要求流程要是一旦开始解锁就不能再加锁了。(所有解锁操作都在加锁后面.)

ConcurrentLinkedQueue

目标: 线程安全的队列，并发性能好。
实现: 基于链表的队列,ConcurrentLinkedQueue,使用volatile,CAS和HOPS变量（LockFree）,性能较好,而且可以通过HOPS变量调节性能.

初始时:

1
2
3
4
5
6

private transient volatile Node<E>tail = head;
private transient volatile Node<E> tail;
public ConcurrentLinkedQueue() {
        head = tail = new Node<E>(null);
        // 数据为null. 相当于一个dump头节点.
}

simple解法(假想方案)

一种simple的实现方案是这样的:

• tail定义:

  1	将tail定义成永远是队列最后一个节点:

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

public <E> boolean offer(E e) {
    if (e == null) {
        throw new NullPointerException();
    }
    Node<E> n = new Node(e);
    for (; ; ) {
        Node<E> t = tail;
        if (t.casNext(null, n) && casTail(t, n)) {
        // 1. casNext: 把t的next从null换成n;
        // 2. casTail: 把tail从t换成n。
            return true;
        }
    }
}

回想我们的目标:

1. 安全: 由于tail是volatile的,因此可以通过CAS操作保证并发写的安全;
2. 性能: 每次入列至少需要:

   1 2 3 4

   1次 volatile读;(tail) 2次 CAS操作; 2次 volatie写.(tail.next和tail) // tail.next实际上也是volatile变量。

jdk注释

直接阅读源码有可能误解了作者的意思,而且源码确实比较trick,看不太懂,注释里声明的几个基本点:

1
2
3
4
5
6
7
8
9
10

1. 仅有一个节点的next为null,它是队列的最后一个节点. 想访问最后一个节点的话,可以通过tail节点往后找,可以通过O(1)时间找到(最多4次); 
// 注意tail不一定指向最后一个节点

2. 队列没有null的实际数据(item = null),也就是容器不接受空元素。
// dumpHead头节点的item为null; 移除节点的时候把item置为null,所以null是一个很重要的标志量,所以不允许实际数据有null造成冲突;

3. 为了满足上一条,更为了gc,过期的节点的next指向自己;
//  所以很多节点遇到p==p.next的时候,会跳转到head重新进入有效节点范围,或者进行过期逻辑处理;

4. 把item置为null相当于移除了该数据,迭代器iterator会跳过item为null的节点.

实际解法

这个思路最重要的有两点:
一点就是updateHead函数,离群节点的next置为自己;
另一点就是tail不一定是最后一个节点.
由于volatile写的开销远远高于volatile读,jdk中的解法是:

1
2
3

1. 假设队列中最后一个节点为:realTail;
2. tail 不一定等于 realTail;
3. 仅当tail与realTail距离大于等于HOPS时,才更新tail=realTail.

这样设计以后,可以通过增加volatile读减少volatile写。

具体实现:

updateHead方法

1
2
3
4
5
6
7

// 如果当前的head是h,把它换成p
final void updateHead(Node<E> h, Node<E> p) {
        if (h != p && casHead(h, p))
        // 这个是最重要的一个地方
        // 将离群h节点的next置为自己
            h.lazySetNext(h); // 不急,但是迟早进行离群标记
    }

offer方法

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

public boolean offer(E e) {
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);

    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {// 如果p是尾节点
            if (p.casNext(null, newNode)) {// 把item加入队列,让newNode变成活节点
                if (p != t) // hop two nodes at a time
                    casTail(t, newNode);  
                    // 更新tail失败也没关系,因为tail仅仅用于优化性能,并不影响正确性
                return true;
            }
        }
        else if (p == q) // p==q意味着p已经是一个离群节点
            p = (t != (t = tail)) ? t : head;
            // 首先我们一定过时了:
            // 如果t过时了,尝试从tail重连;
            // 如果t没过时,说明tail也过时了,从head重连。
        else // Check for tail updates after two hops.
            p = (p != t && t != (t = tail)) ? t : q;
            // 写竞争失败了而已,把p往后挪就好了. 
    }
}

其中有一种trick：

1
2
3
4
5
6
7
8
9

t != (t = tail)
// 可以展开成:
if(t!=tail){
t= tail;
// return true;
}
else{
// return false;
}

因此p = (t != (t = tail)) ? t : head;的实际含义就是:

1
2
3
4
5
6
7
8
9
10
11

if(t!=tail){
    t=tail;
    p=t;
}
else{
    p=head;
}
// 这段代码实际意思就是,已知p节点过时(离群,已经被删除)了,我们需要重新连接到queue中可用的节点,然后重新定位到尾节点.
1. 如果t!=tail,说明t过时了,tail可能还可用,因此尝试从tail重连;(t=tail,p=t);

2. 如果t==tail,说明t和tail都过时了,尝试从head重连。(p=head)

使用这个trick的目的不得而知,个人猜测是因为效率更高,代码更精炼。毕竟非阻塞并发存在的意义就是性能,而不是可读性,如果想要可读性,就去用阻塞队列了。
可读性下降了.但如果用得熟练的话,肉眼parse功力上涨,也可能对于大牛来说比if else阅读起来更快。

节点定义

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

private static class Node<E> {
        volatile E item;
        volatile Node<E> next;

        Node(E item) {
            UNSAFE.putObject(this, itemOffset, item);
        }

        boolean casItem(E cmp, E val) {
            return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
        }

        void lazySetNext(Node<E> val) {
            UNSAFE.putOrderedObject(this, nextOffset, val);
        }

        boolean casNext(Node<E> cmp, Node<E> val) {
            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
        }

        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE;
        private static final long itemOffset;
        private static final long nextOffset;

        static {
            try {
                UNSAFE = sun.misc.Unsafe.getUnsafe();
                Class<?> k = Node.class;
                itemOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("item"));
                nextOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("next"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }

poll方法

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

public E poll() {
    restartFromHead:
    for (;;) {
        for (Node<E> h = head, p = h, q;;) {
            E item = p.item;
            if (item != null && p.casItem(item, null)) {
                // 成功找到第一个数据节点(item!=null)并移除item
                if (p != h) 
                // p!=h说明p往后找过,说明队首有至少2个非数据节点,更新head
                    updateHead(h, ((q = p.next) != null) ? q : p);
                return item;
            }
            else if ((q = p.next) == null) {// 往后找数据节点
                updateHead(h, p); // 已经是空队列
                return null;
            }
            else if (p == q) // 离群了,重连
                continue restartFromHead;
            else
                p = q;
        }
    }
}

succ方法

1
2
3
4
5

/*找next.如果next与自身相等,说明离群了,返回head以便重连*/
final Node<E> succ(Node<E> p) {
    Node<E> next = p.next;
    return (p == next) ? head : next;
}

remove方法

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

public boolean remove(Object o) {
        if (o != null) {
            Node<E> next, pred = null;
            for (Node<E> p = first(); p != null; pred = p, p = next) {
                boolean removed = false;
                E item = p.item;
                if (item != null) {
                    if (!o.equals(item)) {
                        next = succ(p);
                        continue;
                    }
                    removed = p.casItem(item, null);
                }

                next = succ(p);
                if (pred != null && next != null) // unlink
                    pred.casNext(p, next);
                if (removed)
                    return true;
            }
        }
        return false;
    }

2-3树与红黑树

参考资料：
2-3树：
http://blog.jobbole.com/79307/
红黑树：
http://blog.jobbole.com/79309/

背景

2-3树和红黑树都是一种平衡查找树。其中红黑树是在2-3树的基础上，对于实现进行了简化，代价是逻辑上（表现图）增加了直接理解的难度。换句话说就是:

• 2-3树理解起来简单，实现起来代码比较麻烦(其实也可以实现);
• 红黑树理解起来稍微曲折，实现起来代码非常简单/简洁,如果用递归实现还非常优雅。

因此我们应该先学2-3树，理解以后，带着简单理解去学红黑树的实现。上述参考资料里的两个链接对于两者的介绍非常值得一看。

2-3树

定义

2-3树意思就是树里有两种节点:
2-node: 保存1个key,左右2个子节点;
3-node: 保存2个key,左中右3个子节点。

和二叉查找树类似,如果中序遍历一个2-3树,可以得到一个排好序的序列。
在一个完全平衡的2-3树中,根节点到每一个叶节点距离相同.

平衡性:

直观上理解: 由于2-3树的3-node具有缓冲作用,而且它的分裂逻辑可以将不平衡因子传递到父节点(还可以继续),最终消除;
严谨证明: 还没找到相关论文,理论上它与AA树等价,所以可以按left-leaning red-black tree/LLRB的证明来完成。

查找

和B树类似,按key跳转子节点查找就好了.

插入

往2-node节点插入

插入K,把2-node变成3-node。

往3-node节点插入

1. 只有一个3-node节点

插入S,把3-node变成4-node,把4-node分裂成3个2-node,中间key拉升做根节点.（无法向上传导,根分裂,高度+1）

2. 父节点是2-node,节点是3-node

插入Z:

1. 把3-node变成4-node;
2. 把中间key往上扔,传递给父节点;
3. 父节点从2-node=>3-node。

3. 父节点是3-node,节点是3-node

思路和之前相似,把中间元素往上传导,直到遇到父节点是2-node的。
如果连根节点也是3-node，就进行根节点分裂，高度+1。

性能

最坏情况,所有节点都是2-node,因此最坏时间复杂度为O(logN).
最好情况,所有节点都是3-node,因此最好时间复杂度为O(log3N)=0.631logN.

红黑树

(这里其实是left-leaning red-black tree/LLRB)
2-3树中有3-node，红黑树则是将其全部转化成二叉树来实现。
参考资料2中同时出现红色节点与红色连线,容易引起混淆. 这里统一定义一下, 红色本质上是指节点,红黑信息实现上存放在红子节点中. 之所以有红色连线,主要是为了在图里画,可以更清晰得看出有两个红子节点的父节点.

下文中:

1. 图中: 以红色连线表示子节点是红节点;️
2. 实现中: 红色信息存放在子节点中. （并不会存指向父节点的指针）

具体实现:

1
2
3
4
5
6
7
8
9
10
11

class Node
{
    public Node Left { get; set; } // 左子
    public Node Right { get; set; } // 右子
    public TKey Key { get; set; } // key
    public TValue Value { get; set; } // 数据
    public int Number { get; set; } // 当前子树的size,总共有多少节点 
    
    // 当前节点是红还是黑
    public bool Color { get; set; }  
}

定义:

1
2
3

1. 所有节点分为红节点和黑节点;
2. 表现图中一个红节点的画法: 把它和父节点之间的连线画成红色。
(看图的时候,一条红线:子节点是红节点)

规则:

1
2
3
4

1. 所有节点,只有左子节点可以是红节点, 右子节点只能是黑;(通过旋转保证)
2. 红色节点不能相连; // 父节点红色,子节点不能也红色
3. 不能左右都是红节点. // 左右子节点不能都是红色
(2，3两个规则,图上看就是一个节点不能有两个红色连线)

如上图所示，红黑树其实是2-3树的另一种表现形式。将红黑树的红色连线水平绘制，就可以把水平的两个节点整体看作一个3-node.
从实现上看，也就是把节点和它的红子节点看作一个3-node。
从这个思路来看,也就能理解上述的3条规则了, 如果违反了任意一条,都会导致节点与其红子节点合并成一个整体来看待的时候, 变成4-node甚至5-node更多.
只有满足所有规则, 才能保证合并来看的时候最多是一个3-node。

查找

由于本质上还是二叉查找树,查找的代码与普通二叉查找树一样.
只不过由于比较平衡,性能有保障。
(如果把红黑树看作2-3树的话,查找过程的差别就在于遇到3-node的时候,先找的是最左的key,然后通过红子节点查找了中间key。)

平衡化

为了维持上文中的规则，也为了红黑树保持平衡,保障性能,需要进行一些平衡操作。

旋转

左旋: 输入父节点;
右旋: 输入父节点.

左旋

左旋实现:

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

//左旋转
private Node RotateLeft(Node h)// 输入父节点
{
    Node x = h.Right;
    //将x的左节点复制给h右节点
    h.Right = x.Left;
    //将h复制给x右节点
    x.Left = h;
    x.Color = h.Color;
    h.Color = RED;
    return x;
}

注意: 子节点继承父节点的颜色.
父节点变为红色。

右旋

右旋实现:

1
2
3
4
5
6
7
8
9
10
11

//右旋转
private Node RotateRight(Node h)// 输入父节点
{
    Node x = h.Left;
    h.Left = x.Right;
    x.Right = h;

    x.Color = h.Color;
    h.Color = RED;
    return x;
}

注意: 子节点继承父节点的颜色.
父节点变为红色。

颜色反转

如果违反规则2，也就是两个子节点都是红色节点,也需要调整/平衡化.如下图所示的话,其实就是把父节点变成红色，两个子节点变成黑色. 很简单。

插入

往2-node底部插入

规则:

1

新插入的节点标记为红色.

左图不需要额外操作;
右图需要一次左旋.

往3-node底部插入

1. 往只有两个节点的树中插入: （注意形状一定是左偏的）
   规则:

   1	新插入的节点标记为红色.

   左图需要1次颜色反转;
   中图需要1次右旋,1次颜色反转;
   右图需要1次左旋,1次右旋,1次颜色反转.

简单总结一下平衡化的技巧如下:(按顺序检查,每次调整后回到1从头重复检查)

1. 如果左右都是红,用颜色反转;
2. 如果右子是红,左旋;
3. 如果连续两个左子是红,(父子都是红节点),右旋,然后颜色反转.

更多案例:

注意图14中到红色传递到根节点M后,由于根节点没有父节点,它的红黑属性不再重要,为了维持不打破上述的规则,定义根节点始终为黑. 如果通过颜色反转或者其他平衡化操作,把根节点变红以后,可以视作根节点还是黑.(强制根节点黑)

Put实现代码

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

public override void Put(TKey key, TValue value)
{
    root = Put(root, key, value);
    root.Color = BLACK; // 强制根节点黑
}

private Node Put(Node h, TKey key, TValue value)
{
    if (h == null) return new Node(key, value, 1, RED);
    
    // 1. 进行二叉树插入: 
    int cmp = key.CompareTo(h.Key);
    if (cmp < 0) h.Left = Put(h.Left, key, value);
    else if (cmp > 0) h.Right = Put(h.Right, key, value);
    else h.Value = value;

    // 2. 进行平衡化:
    if (IsRed(h.Right) && !IsRed(h.Left)) h = RotateLeft(h); // 右边红节点
    if (IsRed(h.left) && IsRed(h.Left.Left)) h = RotateRight(h); // 我个人理解的写法,连续红节点
    // if (IsRed(h.Right) && IsRed(h.Left.Left)) h = RotateRight(h); //  原文写法,我感觉不对	
    if (IsRed(h.Left) && IsRed(h.Right)) h = FlipColor(h);// 颜色反转

    h.Number = Size(h.Left) + Size(h.Right) + 1; // 更新子树size信息
    return h;
}

private int Size(Node node)
{
    if (node == null) return 0;
    return node.Number;
}

注意到插入操作是自顶向下(dfs递归调用)进行的,由于dfs深度优先,可以先从子节点检查平衡/调整.因此不平衡从子节点传递到父节点,可以逐步调整传递到根节点,平衡操作也贯穿这个层层返回的过程,从平衡树的底层一直进行到根节点为止.

性能

满足上述规则后, 红黑树能保障所有操作最坏复杂度为O(logN)。

• 最坏情况:
  除了最左侧路径,其他全部是3-node组成. 红黑相间的路径长度是全黑路径的两倍.

特性:
红黑树从根节点到叶子节点的路径中,全黑路径是平衡的.

应用

主要是各种map/符号表:

1
2
3
4

Java: TreeMap,TreeSet,HashMap,ConcurrentHashMap
C++: STL: map,multimap,multiset
.Net: SortedDictionary,SortedSet
Linux: epoll,防火墙规则表

核心规则

1. 不能两个左右子节点都是红节点; (颜色反转)
2. 父子节点不能都是红节点;(右旋)
3. 右节点不能是红节点;(左旋)
4. 新插入的节点是红节点;(新红)
5. 根节点强制是黑节点.(根黑)

/etc/resolv.conf配置文件的4个关键字:

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

// 1. 定义dns服务器的地址,按序查找
nameserver 8.8.8.8
nameserver 114.114.114.114

// 2. 本地域名.  
domain google.com

// 3. 搜索域名.
search google.com cn.bing.com

// 4. 返回域名的排序
sortlist

主要用到的其实是nameserver和search.

其中search的用例如下:

1

ping new

由于new这个域名找不到ip;
尝试搜索new.google.com,(search域的第一项)
如果还是搜不到,就尝试搜索new.cn.bing.com.
也就说search会尝试补齐域名。

至于domain,相当于配置search的默认值。

第六章 java并发容器和框架

主要内容是concurrent包中并发性能较好的几个容器，逻辑上是：

1. map： concurrentHashMap;
2. 队列: concurrentLinkedQueue;
3. 阻塞队列.
   此外还有Fork/Join工作窃取框架（java8 stream api的底层）。

6.1 ConcurrentHashMap

6.1.1 背景

HashTable缺点：并发性能低，直接锁整个table。
HashMap缺点：非线程安全，并发时产生死循环。
多线程put操作可能导致环形链表。

• ConcurrentHashMap：
  分段加锁，并发效率高。

6.1.2 具体实现

concurrentHashMap在不同jdk版本中实现不同：

jdk1.6中的实现

• 基本思路
  将哈希表分成几个段，然后分段加锁。
  把原来的一维数组，变成二维数组。（类似于二级索引，先寻址到第一级，获得锁以后再访问第二级具体数据）

如类图所示：
ConcurrentHashMap->Segment->HashEntry

第一维是Segment数组，每个Segment里存一个HashEntry数组，最后拉链表。
HashEntry源码：

1
2
3
4
5

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

特点
1.实际并发度为2的n次方。（离散取值，而不是连续）
=>原因：
Segment数组的长度需要为2的n次方
=>原因：
寻址的时候使用移位来提高性能，需要数组长度为2的n次方：
hash值的高位确定落在哪个Segment里，低位确定落在Segment中的位置。

1
2
3

hash >>> segmentShift) & segmentMask//定位Segment所使用的hash算法
int index = hash & (tab.length - 1);// 定位HashEntry所使用的hash算法
// 当tab.length为2的n次方时，index的计算等价于= hash % tab.length

并发度(Concurrency Level)实际就是由多少锁，也就是Segment数组的长度。
如果设定并发度为14，实际上会创建长度为16的Segment数组，也就是实际并发度为16.

2.弱一致性
写入的数据并不一定能马上读到，或者不一定能读到最新数据。
// get,containsKey,clear方法和迭代器都是弱一致性的
原因：
并发的时候使用了volatile代替锁提高性能，牺牲了一致性换取性能。

1
2
3
4
5

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

由于遍历期间其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据。如在get执行UNSAFE.getObjectVolatile(segments, u)之后，其他线程若执行了clear操作，则get将读到失效的数据。

由于clear没有使用全局的锁，当清除完一个segment之后，开始清理下一个segment的时候，已经清理segments可能又被加入了数据，因此clear返回的时候，ConcurrentHashMap中是可能存在数据的。因此，clear方法是弱一致的。

如果加锁的话，就能保证强一致性了。

jdk1.8中的实现

• 基本思路
  //把链表改成红黑树，提高效率。
  第一维：数组
  第二维：链表(<8)/红黑树
  用CAS操作代替大范围加锁。
  锁的粒度缩小到Node级别。（linux中很多并发相关的数据结构都是红黑树，在如epoll，防火墙中应用）

• 具体实现

1. 最小粒度是Node,成员变量如下:

   1 2 3 4 5

   static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next;

   可以看出与原来的HashEntry基本一致，多了一个继承。

其他的容器成员：

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

/**
 * The array of bins. Lazily initialized upon first insertion.
 * Size is always a power of two. Accessed directly by iterators.
 */
transient volatile Node<K,V>[] table;

/**
 * 平时为null。扩容时,为下一个表。
 */
private transient volatile Node<K,V>[] nextTable;

/**
 * Base counter value, used mainly when there is no contention,
 * but also as a fallback during table initialization
 * races. Updated via CAS.
 */
private transient volatile long baseCount;
private transient volatile int sizeCtl;

/**
 * The next table index (plus one) to split while resizing.
 */
private transient volatile int transferIndex;

/**
 * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
 */
private transient volatile int cellsBusy;

/**
 * Table of counter cells. When non-null, size is a power of 2.
 */
private transient volatile CounterCell[] counterCells;

// views
private transient KeySetView<K,V> keySet;
private transient ValuesView<K,V> values;
private transient EntrySetView<K,V> entrySet;

修饰符复习：
transient: 序列化的时候忽略。（一般会自定义相关的序列化操作）一般用于一些运行时的状态变量。

sizeCtl
表初始化和扩容时的控制状态量。

• 负数时:

  • -1: 正在初始化;
  • -2: 正在扩容,有1个活跃的扩容线程数;
  • -3: 正在扩容,有2个活跃的扩容线程数;
  • -N: 正在扩容,有N-1个活跃的扩容线程数;
    以此类推…

• 0: 还没初始化,未指定容量。

• 正数时:

  • table=null: 还没初始化,目标初始化容量。
  • table!=null: sizeCtrl=0.75*n(扩容阈值,抵达这个值就要进行扩容了)

2. Node节点会从链表节点转化为红黑树节点TreeNode:

   1 2 3 4 5 6 7 8 9

   /** * Nodes for use in TreeBins */ static final class TreeNode<K,V> extends Node<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red;

3. TreeBin作为红黑树的根节点，封装相关的操作，并且有读写锁:

   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

   static final class TreeBin<K,V> extends Node<K,V> { TreeNode<K,V> root; volatile TreeNode<K,V> first; volatile Thread waiter; volatile int lockState; // values for lockState static final int WRITER = 1; // set while holding write lock static final int WAITER = 2; // set when waiting for write lock static final int READER = 4; // increment value for setting read lock /** * Acquires write lock for tree restructuring. 进行平衡梳理的时候,也会lockRoot */ private final void lockRoot() { if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) contendedLock(); // offload to separate method } /** * Releases write lock for tree restructuring. */ private final void unlockRoot() { lockState = 0; } /** * Finds or adds a node. * @return null if added */ final TreeNode<K,V> putTreeVal(int h, K k, V v) {

4. tabAt方法,获取i位置上的Node:

   1 2 3

   static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); }

5. casTabAt方法,CAS设定i位置上的Node:

   1 2 3 4

   static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }

6. setTabAt方法,直接设定i位置上的Node(已经占据锁的时候使用),
   利用volatile:

   1 2 3

   static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); }

简单总结:
get方法: 利用volatile,不加锁,并发访问;(弱一致性)
put方法: 利用CAS方法,轮询,大部分时候不加锁.如果是红黑树，调用它的putTreeVal方法。

前情提要:

1
2

(1)中写的主要是Lock接口,Condition接口的api；
然后是自定义Lock时，需要使用的AQS的api以及大致实现、示例、基础数据结构。

这部分主要介绍案例：jdk库中提供的重入锁、读写锁以及LockSupport。

java并发编程的艺术-第五章(2)

5.3 重入锁

重入锁： 一个线程能否重复获得同一个锁。
该特性需要解决两个问题：

1. 线程再次获取锁。识别获取锁的线程是否为当前占据锁的线程。
2. 锁的最终释放。重复获取n次，则也需要释放n次。

重入锁示例：

1. synchronized临界区,同一个线程能够重复进入;
2. ReentrantLock锁，能够重复使用lock.lock().

不可重入锁示例:
前文(1)部分中自定义的锁Mutex。

公平锁与非公平锁
公平锁： FIFO，竞争锁时需要判断先来后到；
非公平锁： 效率优先，可能有饥饿。同一个线程可能连续获得锁。

• 实现上：
  ReentrantLock的公平锁的tryAcquire方法判断条件比非公平的多了一个hasQueuedPredecessors方法，以确保FIFO。

回顾之前同步队列的节点数据结构，是一个双向链表，因此可以判断前驱节点是否存在，即使是因为中断被唤醒节点也可以正确判断自己的位置。 而等待队列是一个单向链表，因此如果节点需要进入到等待队列时，本质上都是非公平的。

5.4 读写锁ReentrantReadWriteLock

前文提到的所有Lock的实现，依赖于一个状态变量volatile int state。本质上都是排他锁。只不过有些实现上通过设定state的合法状态范围(TwinsLock)，设定了资源的最大数量，让同一个时间能有多个线程同时获取到锁。(需要考虑与可重入特性是否冲突)

读写锁通过对state状态变量进行前16位和后16位分割，当作两个状态变量来使用（需要考虑数据类型溢出），从而同时保存了读写状态。

• 读写锁：

1. 同一时刻可以允许多个读线程访问;
2. 写线程访问时：其他读写线程都不能访问；
3. 读线程访问时：读线程可以访问，写线程不能访问。

回顾(1)部分中的独占式和共享式api的区别，可以明白读写锁的实现需要同时实现tryAcquire(独占式)和tryAcquireShared(共享式)。

读写锁能提供比简单写锁更好的性能。（并发性和吞吐量）

• 读写锁ReentrantReadWriteLock的特性：

1. 支持公平或非公平锁；
2. 支持重进入；
3. 支持锁降级。

• 锁降级
  锁降级指的是从写锁降级为读锁。
  具体流程：

1. 获取写锁;
2. 写数据+do something;
3. 获取读锁;
4. 释放写锁;
5. 读数据+do something;
6. 释放读锁。

那么为什么需要锁降级这个特性呢？
因为需要提高性能。
锁降级的基本思想就尽量减少写锁的持续时间，同时保持这个线程操作的语义不变。

例如：
假如一个线程A需要做的事：

1. 写a=1;
2. 读a,然后计算b=a+1(结果b=2)。

上述过程中其实只有步骤1需要写锁，从步骤2开始只需要读锁就好了。
但如果直接在步骤1后释放写锁，从1到2的时间间隙中，可能被别的线程获取到写锁，然后修改了a的值。这样就改变了线程A操作的原子性。

为了保证线程A操作的原子性，有两种方案：

1. 步骤1和2整个过程都占据写锁；
2. 步骤1结束后，进行锁降级。由于线程A占据读锁后，所有线程无法获取写锁，达到了性能与语义兼顾。

使用锁降级的话，整个过程中所有别的线程都无法获取写锁，但别的线程在后半程能够获取读锁。因此提高了读性能。

5.4.1 读写锁的接口与示例

接口： ReadWriteLock
jdk实现： ReentrantReadWriteLock

ReadWriteLock的api:

1. readLock()

2. writeLock()

   ReentrantReadWriteLock的api:

案例之Cache
ReentrantReadWriteLock的使用示例，实现一个cache:

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

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class Cache {
    static Map<String, Object> map = new HashMap<>();
    static ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
    static Lock r = rwl.readLock();
    static Lock w = rwl.writeLock();

    public static final Object get(String key) {
        r.lock();
        try {
            return map.get(key);
        } finally {
            r.unlock();
        }
    }

    public static final Object put(String key, Object value) {
        w.lock();
        try {

            return map.put(key, value);
        } finally {
            w.unlock();
        }
    }

    public static final void clear() {
        w.lock();
        try {
            map.clear();
        } finally {
            w.unlock();
        }
    }
}

通过ReentrantReadWriteLock生成的readLock和writeLock，把非线程安全的HashMap操作包装成线程安全的，并且尽量保持了并发性能。使用上还是比较简单的，只需要每次加上finally unlock即可。

5.4.2 读写锁的实现分析

1. 读写状态的设计
   由于需要使用AQS来实现读写锁，而AQS成员变量里状态变量只有一个，因此将state变量复用为两个变量。state本来是一个int，把高16位作为读的状态量,低16位作为写的状态量。
   由此可以看出读线程最大并发数是2^16-1，写线程重入的嵌套深度是2^16-1。

读状态: S>>>16 (无符号右移)
写状态：S & 0x0000FFFF

2. 写锁的获取与释放：
   写锁获取： S=0(c=0)，没有人获取写锁，也没人获取读锁。
   由exclusiveCount函数获取写状态。

   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

   @ReservedStackAccess protected final boolean tryAcquire(int acquires) { Thread current = Thread.currentThread(); int c = getState(); int w = exclusiveCount(c); if (c != 0) { // (Note: if c != 0 and w == 0 then shared count != 0) if (w == 0 || current != getExclusiveOwnerThread()) return false; if (w + exclusiveCount(acquires) > MAX_COUNT) throw new Error("Maximum lock count exceeded"); // Reentrant acquire setState(c + acquires); return true; } if (writerShouldBlock() || !compareAndSetState(c, c + acquires)) return false; setExclusiveOwnerThread(current); return true; } @ReservedStackAccess protected final boolean tryRelease(int releases) { if (!isHeldExclusively()) throw new IllegalMonitorStateException(); int nextc = getState() - releases; boolean free = exclusiveCount(nextc) == 0; if (free) setExclusiveOwnerThread(null); setState(nextc); return free; }

3. 读锁的获取与释放
   读锁获取： 没有人占据写锁。

   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 60 61 62

   @ReservedStackAccess protected final int tryAcquireShared(int unused) { Thread current = Thread.currentThread(); int c = getState(); if (exclusiveCount(c) != 0 && getExclusiveOwnerThread() != current) return -1; int r = sharedCount(c); if (!readerShouldBlock() && r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) { if (r == 0) { firstReader = current; firstReaderHoldCount = 1; } else if (firstReader == current) { firstReaderHoldCount++; } else { HoldCounter rh = cachedHoldCounter; if (rh == null || rh.tid != LockSupport.getThreadId(current)) cachedHoldCounter = rh = readHolds.get(); else if (rh.count == 0) readHolds.set(rh); rh.count++; } return 1; } return fullTryAcquireShared(current); } @ReservedStackAccess protected final boolean tryReleaseShared(int unused) { Thread current = Thread.currentThread(); if (firstReader == current) { // assert firstReaderHoldCount > 0; if (firstReaderHoldCount == 1) firstReader = null; else firstReaderHoldCount--; } else { HoldCounter rh = cachedHoldCounter; if (rh == null || rh.tid != LockSupport.getThreadId(current)) rh = readHolds.get(); int count = rh.count; if (count <= 1) { readHolds.remove(); if (count <= 0) throw unmatchedUnlockException(); } --rh.count; } for (;;) { int c = getState(); int nextc = c - SHARED_UNIT; if (compareAndSetState(c, nextc)) // Releasing the read lock has no effect on readers, // but it may allow waiting writers to proceed if // both read and write locks are now free. return nextc == 0; } }

4. 案例之锁降级
锁降级指的是从写锁降级为读锁。
具体流程：

1. 获取写锁;
2. 写数据+do something;
3. 获取读锁;
4. 释放写锁;
5. 读数据+do something;
6. 释放读锁。

   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

   // 锁降级案例 public void processData() { r.lock(); if (!update) { r.unlock(); // 1. 获取写锁 w.lock(); try { if (!update) { // 双检,update状态可能又变化了 // do something // 2. 写数据 update = true; } r.lock(); // 3. 获取读锁 } finally { w.unlock(); // 4. 释放写锁（锁降级完成,写锁变成了读锁） } } try { // do something // 5. 读数据 } finally { r.unlock(); // 6. 读锁最终释放 } }

   值得注意的是，案例中使用了双检，因此update变量应该是volatile。

5.5 LockSupport工具

回顾前文中的实现层次，自顶向下：

1
2
3

1. Lock/Condition接口
2. AQS
3. volatile/CAS/LockSupport

其中AQS中除了使用volatile变量与CAS操作以外，还调用了LockSupport以完成等待操作。
例如线程在同步队列中进行自旋等待时，调用的方法：

1
2
3
4

private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
}

唤醒下一个节点时调用的方法：

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

private void unparkSuccessor(Node node) {
        int ws = node.waitStatus;
        if (ws < 0)
            node.compareAndSetWaitStatus(ws, 0);
        Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node p = tail; p != node && p != null; p = p.prev)
                if (p.waitStatus <= 0)
                    s = p;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }

LockSupport提供的api:

上述api也可以不带blocker参数。blocker参数仅仅是用于调试和系统监控。

LockSupport提供的park/unpark类似于wait/notify，都是等待/通知的模式。主要存在以下几点不同：

1. park还可能在没有被唤醒的时候返回,因此必须在循环中重新检查返回条件。这种设计是一种忙碌等待的优化，效率介于快速自旋与wait之间,灵敏度介于快速自旋与wait之间。
   示例用法（检查返回条件）:

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

   public final void await() throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); Node node = addConditionWaiter(); int savedState = fullyRelease(node); int interruptMode = 0; while (!isOnSyncQueue(node)) { LockSupport.park(this); if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break; } if (acquireQueued(node, savedState) && interruptMode != THROW_IE) interruptMode = REINTERRUPT; if (node.nextWaiter != null) // clean up if cancelled unlinkCancelledWaiters(); if (interruptMode != 0) reportInterruptAfterWait(interruptMode); }

2. unpark可以先于park调用，而notify不能先于wait。unpark相当于赋予线程一个许可，最多缓存一个，等待下一次park时可以直接通过。

3. unpark可以精确唤醒某个线程,而notify只能随机唤醒一个，或者唤醒全部。

LockSupport实现浅析

总结：

1
2

park对象用于实现；
blocker对象用于调试。

park与unpark的实现都是委托给了一个Unsafe对象U实现的：

1
2
3
4
5

// Hotspot implementation via intrinsics API
private static final Unsafe U = Unsafe.getUnsafe();
public static void park() {
        U.park(false, 0L);
    }

park方法面向的主体是Thread，每个线程内有一个Parker对象以承载相应的阻塞操作；
wait方法则依赖的是每个对象的内置锁实现。
因此两者是正交的。

可以查阅hotpot的源代码进一步深入其Parker的实现。

Blocker参数
带Blocker参数的park方法:

1
2
3
4
5
6
7
8
9
10

public static void park(Object blocker) {
        Thread t = Thread.currentThread();
        setBlocker(t, blocker);
        U.park(false, 0L);
        setBlocker(t, null);
    }
private static void setBlocker(Thread t, Object arg) {
        // Even though volatile, hotspot doesn't need a write barrier here.
        U.putObject(t, PARKBLOCKER, arg);
}

可以看出区别是多了setBlocker函数的调用，而且Blocker参数在阻塞结束后会被清空。
此外，Blocker与Parker类似，都是每个线程有一个。设定的逻辑是在该线程t的PARKBLOCKER偏移量中填入对象blocker的引用。

使用blocker的话，在线程阻塞时进行线程dump，可以获得blocker的信息，方便调试和监控。
类比，如果线程因为synchronized(this)而阻塞，线程dump的时候是可以获得this的信息的。

实验Blocker：

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

public class ParkWithBlockerTest {
    public static class UnparkerAndReciever extends Thread {
        Thread main;

        UnparkerAndReciever(Thread main) {
            this.main = main;
        }
        private void sleep(int secends){
            try {
                TimeUnit.SECONDS.sleep(secends);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        @Override
        public void run() {
            sleep(1);
            LockSupport.unpark(main);
            sleep(1); // 注释此行则出现结果1

            Object blocker = LockSupport.getBlocker(main);
            if (blocker != null && blocker instanceof String) {
                System.out.println(blocker); // 结果1
            }
            else{
                System.out.println("blocker=null or not a String"); // 结果2
            }


        }
    }

    public static void main(String[] args) {
        Thread mainThread = Thread.currentThread();

        UnparkerAndReciever unparkerAndReciever = new UnparkerAndReciever(mainThread);
        unparkerAndReciever.start();
        LockSupport.park("string in park");
    }
}

第五章 java中的锁

这章主要写java并发包中与锁相关的api.
先是使用，然后是实现。

5.1 Lock接口

Lock接口由Java SE 5新增，对飙的是旧java中的synchronized内置锁。
主要新增了三个api:

1. 非阻塞获取锁（tryLock）;
2. 能被中断地获取锁(lockInterruptbly);
3. 超时获取锁(tryLock(long time,TimeUnit unit)).
   此外还增加了Condition接口，增加了等待队列的数量及相关特性。
   （Condition使用await()，对飙的是原来的obj.wait()）

示例代码：

1
2
3
4
5
6
7
8
9
10

Lock lock=new ReentrantLock();
lock.lock();// 没获取到锁的话抛异常
try{
    // do something
}
finally{
    lock.unlock();
    // 如果lock.lock()放try里，这里就可能会出错。
    // 因为没获取到锁时，不能unlock。
}

回顾之前的线程状态,lock方法会让线程进入Blocked状态。
线程状态与可中断的关系：

1. new: ???
2. Runnable: 不可中断（除非主动检查）
3. Terminated: 不可中断;
4. Blocked: 不可中断; (在synchronized时阻塞住不会响应中断)
5. Waiting: 可中断；(sleep方法，wait方法都会抛异常)
6. Time_waiting： 可中断；

简单得说，就只有Waiting和Time_waiting状态可以中断，或者自己在代码里手动检查中断状态。

本章的内容有点乱，不太通顺，下面的内容按照个人理解重排。

5.6 Condition接口

Condition接口对飙的是原来的wait/notify机制，新推出的是await/signal机制。
wait/notify依赖synchronized获得锁，而Condition依赖Lock获得锁。
原来的wait/notify:

1
2
3
4
5
6
7
8

// A:
synchronize(obj){
    obj.wait();
}
// B:
synchronize(obj){
    obj.notify();
}

使用Condition的await/signal:

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

Lock lock=new ReentrantLock();
Condition condition=lock.newCondition();

// A:
lock.lock();
try{
    condition.await();
}
finally{
    lock.unlock();
}
// B:
lock.lock();
try{
    condition.signal();
}
finally{
    lock.unlock();
}

• 功能上：
  两种实现都是使用一个对象进行同步操作（加锁解锁）。消费者在获得锁后，在该对象上进行等待（释放锁等待）；生产者获得锁后，通知在该对象上等待的其他线程。
  区别在于synchronized不需要关心锁的释放，而Lock接口需要在finally中手动确保锁的释放。
  wait只有一个等待队列，而由于一个Lock可以生成多个Condition，因此await可以有多个等待队列。

案例之有界队列

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

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BoundedQueue<T> {
    private Object[] items;
    private int addIndex, removeIndex, count;
    private Lock lock = new ReentrantLock();
    private Condition notEmpty = lock.newCondition();
    private Condition notFull = lock.newCondition();

    public BoundedQueue(int size) {
        items = new Object[size];
    }

    public void add(T t) throws InterruptedException {
        lock.lock();
        try {
            while (count == items.length) {
                notFull.await();
            }
            items[addIndex] = t;
            if (++addIndex == items.length) { // 循环数组
                addIndex = 0;
            }
            ++count;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    public T remove() throws InterruptedException {
        lock.lock();
        try {
            while (count == 0) {
                notEmpty.await();
            }
            Object x = items[removeIndex];
            if (++removeIndex == items.length) {// 循环数组
                removeIndex = 0;
            }
            --count;
            notFull.signal();
            return (T) x;
        } finally {
            lock.unlock();
        }
    }

}

上述案例中使用一个锁（Lock对象），而有两个等待队列，分别等待notEmpty和notFull条件。

• 实现逻辑上：（逻辑上的工作流程）

1. 线程尝试获取锁，如果成功则占据锁，失败则进入同步队列；
2. 如果成功获取锁，且进行等待（wait或await），则进入等待队列，释放锁，通知同步队列中的后继节点；
3. 如果成功获取锁，且进行通知（notify或signal），则等待队列的首节点挪入同步队列，释放同步锁，通知同步队列中的后继节点。

两个后面会反复用到的概念：

• 同步队列： 获取同步锁失败后的线程进入同步队列；
• 等待队列： 获取同步锁成功后，主动等待的线程进入等待队列。

5.2 队列同步器

前文中锁的实现中，一个很重要的组件是：
队列同步器：AQS(AbstractQueuedSynchronizer)。
此外，其他同步组件的基础框架也是使用AQS。（如ReentrantLock,CountDownLatch）
回顾55页3.5.4节中的架构层次：

1
2
3
4

// 自顶向下：
1.  Lock,同步器,阻塞队列,Executor,并发容器
2.  AQS,非阻塞数据结构,原子变量类
3.  volatile读写,CAS操作

AQS是一个抽象类。
AQS中自底向上的3类方法：

1. 基础方法。(固定)
2. 可重写的方法（调用1的方法）；
3. 模版方法；（固定，调用1，2的方法）

AQS在设计上是基于模版方法模式的抽象类。也就是说，我们需要新增一个子类继承AQS，然后重写上述第2类方法。而第1类和第3类方法，要么是private的无法继承，要么是final的无法重写。而第二类方法，如果没有重写，默认实现只有一行throw new UnsupportedOperationException();,调用的时候就会直接抛异常了。

基础方法

1. getState(): 获取当前同步状态；
2. setState(): 设置当前同步状态；
3. compareAndSetState(int expect,int update): 使用CAS设置当前状态,该方法保证设置的原子性。

可重写的方法

模版方法

案例之-独占锁
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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

public class Mutex implements Lock {
    private static class Sync extends AbstractQueuedSynchronizer {
        @Override
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }

        @Override
        public boolean tryAcquire(int acquireds) {
            if (compareAndSetState(0, 1)) {
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }

        @Override
        protected boolean tryRelease(int releases) {
            if (getState() == 0) {
                throw new IllegalMonitorStateException();
            }
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }

        Condition newCondition() {
            return new ConditionObject();
        }
    }

    // 将操作委托给sync实现即可。
    private final Sync sync = new Sync(); // (代理)

    @Override
    public void lock() {
        sync.acquire(1);
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }

    @Override
    public boolean tryLock() {
        return sync.tryAcquire(1);
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return sync.tryAcquireNanos(1, unit.toNanos(time));
    }

    @Override
    public void unlock() {
        sync.release(1);
    }

    @Override
    public Condition newCondition() {
        return sync.newCondition();
    }

    // 不在Lock接口中，但是有用的方法：
    public boolean isLocked() {
        return sync.isHeldExclusively();
    }

    public boolean hasQueuedThread() {
        return sync.hasQueuedThreads();
    }
}

上述sync只实现了独占操作，因此调用共享操作会抛异常。
因此mutex中只调用了sync的独占模版方法。
因此mutex最多是一个独占锁。

案例之-TwinsLock
用AQS实现一个最多能被两个线程同时占据的锁。
TwinsLock实现：

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
60
61
62
63
64
65
66
67
68
69
70
71
72

public class TwinsLock implements Lock {

    private static final class Sync extends AbstractQueuedSynchronizer {
        Sync(int count) {
            if (count <= 0) {
                throw new IllegalArgumentException("count must larger than 0");
            }
            setState(count);
        }

        @Override
        public int tryAcquireShared(int reduceCount) {
            for (; ; ) {
                int current = getState();
                int newCount = current - reduceCount;
                if (newCount < 0 || compareAndSetState(current, newCount)) {
                    return newCount;
                }
            }
        }

        @Override
        public boolean tryReleaseShared(int returnCount) {
            for (; ; ) {
                int current = getState();
                int newCount = current + returnCount;
                if (compareAndSetState(current, newCount)) {
                    return true;
                }
            }
        }

        // 额外的:
        Condition newCondition() {
            return new ConditionObject();
        }
    }

    private final Sync sync = new Sync(2);// 最多俩人共享

    @Override
    public void lock() {
        sync.acquireShared(1);
    }

    @Override
    public void unlock() {
        sync.releaseShared(1);
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }

    @Override
    public boolean tryLock() {
        return sync.tryAcquireShared(1) >= 0;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return sync.tryAcquireSharedNanos(1, unit.toNanos(time));
    }


    @Override
    public Condition newCondition() {
        return sync.newCondition();
    }

}

与Mutex不同的是，TwinsLock中的同步器主要重写了AQS的共享方法，Lock接口中也调用的是共享方法。也就是按照共享式访问编写，然后用count控制同步资源数。

5.2.2 AQS的实现分析

上面讲了Lock,Condition的使用，AQS的使用（用来自定义Lock），下面讲AQS的实现。

同步队列

• 同步队列与等待队列
  AQS即队列同步器，很重要的一个概念就是同步，要控制多个线程对于一个锁的访问获取释放。
  获取锁失败的线程都会进入同步队列，而一个lock上可以有多个condition,获取锁成功后还需要等待某个condition的线程进入等待队列，然后释放锁。

同步队列是一个FIFO队列，实现上使用一个双向链表。
等待队列也是一个FIFO队列，实现上使用一个单向链表。

同步队列的基本结构：

加上等待队列后的结构：

因为节点可以在同步队列和等待队列之间转化。（同步队列中节点获得锁后，可能发现需要等待condition，进入等待队列尾部；等待队列中节点唤醒后进入同步队列尾部）
JDK中将两个链表的节点的数据结构杂糅在了一起，大致如下：

其中的waitStatus取值包括：
Cancelled：1. 同步队列中等待超时或被中断;
Signal：-1. 当前节点释放了同步状态或者被取消。
Condition: -2. 当前节点等待某个Condition，进入等待队列。
Propagate: -3. 下一次共享式同步状态获取将会无条件地被传播下去。(没看懂.TODO)
Initial: 0. 初始状态。

同步队列遵循FIFO，AQS中保存了head和tail。
每次唤醒时，唤醒head；（由于每次由已经获取锁的线程完成，只有一个线程，没有并发，因此不需要CAS）
每次新增线程时，用CAS新增更改tail。(各种链表指针操作)

• 自旋：
  同步队列中的线程被唤醒的两种可能：

1. 被中断；
2. 被离开队列的首节点唤醒。
   每次被唤醒都会进行一次自旋。
   自旋说白了就是一个死循环，首先检查前驱是否是首节点（判断是否是第二种情况），如果是就试图获取锁，获取失败就接着睡等待下次唤醒（等待下次自旋）。
   因此并不是只有第二个节点会自旋， 同步队列的所有节点都会自旋，毕竟存在被中断唤醒的可能。

同步状态的获取与释放
同步状态获取释放相关的方法主要有两类：独占式和共享式。

• 独占式:

1. 模版方法：(AQS中写好的,可以翻看源码研读)

   1 2 3 4 5

   public final void acquire public final boolean release private Node addWaiter private Node enq final boolean acquiredQueued`

2. 需要自己重写的：

   1 2	protected boolean tryAcquire protected boolean tryRelease

独占式的特点就是：
tyrAcquire,tryRelease的返回值是boolean。
因为同一时刻只能有一个线程占据，因此用boolean就能表达了。
相当于资源数只有1，状态只有0,1两种。

• 共享式

共享式的代码逻辑会复杂一些，如上图所示：

1. 临界区里有共享锁时，只有共享请求能进入；
2. 临界区里有独占锁时，谁都不能进。

共享式的方法：

1. 模版方法：

   1 2 3

   public final void acquiredShared private void doAcquiredShared public final boolean releaseShared

2. 自己重写的方法：

   1 2	protected int tryAcquireShared protected int tryReleaseShared

共享式的特点就是:
tryAcquireShared,tryReleaseShared返回值是int。
因为共享式的资源数可能不为1，状态较多。
doAcquireShared方法中判断是否还有资源，用tryAcquireShared(arg)>=0来判断，可知自己实现的时候，要注意让tryAcquireShared方法返回剩下的资源数。

考虑优化的层面

1. 服务器层(优化器,缓存)
2. 存储引擎
3. schema设计(索引/表)
4. 查询优化

服务器层

1. 待续…

存储引擎 （详见第二章笔记）

1. 尽量使用innodb，以便使用它的行级锁；Myisam是表级锁，锁竞争更频繁。
2. 根据场景选择：
   场景:
   全文索引: InnoDB + Sphinx
   在线热备份: InnoDB
   记录日志: MyISAM,Archive
   10TB以下: InnoDB
   10TB以上: InfoBright.
   大部分情况优先考虑: Innodb
3. 待续…

schema设计

表设计(详见第四章笔记)

1. 数据类型：

   1 2 3 4

   (1) 更小的通常更好, int 好于 char (如可以用int存储ip); date/time/datetime 好于 char. (2) 尽量Not Null; // 因为NULL导致索引需要额外字节.// 不过这个影响不大

2. 考虑使用缓存表，汇总表，计数器表；
3. 表设计原则:

   1 2 3

   1. 避免太多的列; 服务器层需要缓冲存储引擎层的行,变长的行会引入转换开销. 2. 避免太多关联; 3. 恰当使用NULL. 大多数时候避免NULL列,有时候可以使用.(当异常值不好定义时)

4. 适当程度使用范式,不迷信三范式.
   特定需求可以单独定制相应的缓存表和汇总表,而不改变原有的设计结构.
5. 待续…

索引设计（详见第五章笔记）

1. 不同类型索引适用场景：

   1 2 3 4

   1. 哈希索引：（全键值查询，Memory引擎） 数据仓库的查找表。（精确匹配O(1)复杂度，星形,多表连接） 2. B-Tree索引： 大部分场景。

三星系统
索引与查询匹配程度的评价：三星系统：

1. 一星： 将查询相关记录放在了一起；（顺序IO,范围查询能利用到索引）
2. 二星： 数据顺序与查找顺序一致；（避免排序,让排序也能利用到索引）
3. 三星： 索引列包含查询的所有列。(避免二次访问磁盘)

上述评价的对象是(索引,某种查询). 因此并没有一个索引能够完美适应所有查询.只能说尽量适应当前场景下的高频查询.

索引适用场景：

1. 小表： 直接扫全表即可；
2. 中表： 索引；
3. 大表： 分区。索引开销太大。

作为过滤条件的列需要考察的3个属性，按重要性如下：

1. 查询频率；
2. 相关查询是否是范围查询，或者列的取值是否可枚举。
3. 选择性。

设计索引的原则：

1. 查询频率高，则应该加入索引；
2. 如果是范围查询，则如果作为联合索引的一列，应该放在后面；（因为最左前缀无法利用范围查询后的列）
   如果是可枚举列，则查询语句中可以使用In (‘male’,’female’)绕过列顺序限制，让Mysql始终能够应用相关索引；
3. 满足前两个条件后，应该把选择性高的列放在联合索引的前面。

查询优化(详见第六章)

优化思路

1. 尽量减少数据量(提前使用limit);
2. 检查响应时间组成;
3. 索引相关优化;
4. 重写分解复杂查询;
5. 如果是日志系统，开启异步写入数据的参数；
6. 检查关联表的顺序;

• 相关命令

  1 2 3

  explain extended <sql>; show warnings; -- 可以得到重构出的查询。

7. 检查是内排还是外排(max_length_for_sort_data控制);

8. 排序优化:
   关联查询排序时候，尽量把Order by的列提到第一张表中。
   ( 如果Order by的所有列都来自关联的第1个表，Mysql在关联处理第一个表的时候就会进行排序。)

9. 网络传输;
   （1）缓冲区大小(SQL_BUFFER_RESULT);
   （2）先释放表锁，再发送结果：SQL_BUFFER_RESULT。

10. 待续…

索引相关

1. 范围查询转化成枚举，充分利用索引；
   如索引为(dt,city)，查询为：

   1 2 3 4 5 6 7

   select dt,city from t where dt>='2018-01-01' and dt<='2018-01-02' and city='beijing' -- 转化为=> select dt,city from t where dt in ('2018-01-01','2018-01-02'） and city='beijing'

2. 延迟关联+覆盖索引；

3. 检查explain的type:

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

   const(system): 根据PRI或Unique key,只取出确定的(一行)数据,常量优化. eq_ref: JOIN条件包括了所有索引,并且索引是Unique key. ref: JOIN条件包括部分索引或不是Unique key. ref_or_null: WHERE col=exp or col is null index_merge: Where id=xx or userid=xxx. 索引合并优化. unique_subquery: where col in( select id from xxx). 这里id唯一. index_subquery: 同上,只是id不唯一. range: 索引在某个范围内. all: 扫全表

4. 检查索引字段是否正确转换了类型:

   1	dt = date_format(date_sub(current_date, interval 1 day), '%Y-%m-%d')

5. 待续…

查询中锁的使用

1. 尽量使用读锁，避免使用写锁；
2. 降低写锁使用时间（先抢注后处理+定时清理占用标志），消除select ... for update的使用；(避免显式加锁,优先考虑隐式加锁)
3. Innodb不同索引对应的锁：
   (1) 主键索引： 排他锁（写锁）；
   (2) 二级索引： 共享锁（读锁）。
4. 待续…

• 前情提要:
  前面讲了一些场景下针对性的优化。

6.7.5 优化Limit分页

• 场景
  偏移量非常大，数据量非常的时候。

例如Limit 10000,20.

• 工作原理：
  Mysql查询10020条记录，然后返回最后20条。前面1W条都被丢弃。

• 解决方案：

1. 限制分页的数量；(不让查这么大偏移量)
2. 使用覆盖索引优化性能。(延迟关联)
3. 记录上次分页的id。(利用索引)

• 方案2（延迟关联）
  其中方案2，使用覆盖索引优化的原理：

1. 使用覆盖索引，返回目标行的id；
2. 再使用关联查询，返回目标行的所有列。

方案2在偏移量很大的时候，性能优化明显。

• 方案3（记录上次分页id）
  这个方案在多次顺序分页的时候性能很好。
  比如上次分页查询到了id为10240的地方，记录这个值（可以在应用层），然后下次的查询就可以是:

  1 2 3

  select * from t where id>10240 limit 20

6.7.6 SQL_CALC_FOUND_ROWS相关

使用limit的时候，如果加上hint:

1

SQL_CALC_FOUND_ROWS

就可以获得limit之前结果集的行数。

• 工作原理：
  Mysql扫描整个结果集，获得行数。
  如果不用这个hint，则Mysql只扫描limit的行数返回即可，因此这个hint的代价可能非常大。

使用这个hint的可能原因及相关优化：

1. 想知道是否应该显示“下一页”的按钮；
   解决方案：如果原来是limit 20,则改成limit 21即可，这样就知道需不需要“下一页”了。
2. 应用层进行缓存；
3. 使用Explain结果的行数估算。

6.7.7 优化UNION查询

• UNION
  去重后合并

• UNION ALL
  不去重，直接合并

• Mysql执行UNION的原理：
  创建临时表，UNION的过程逐步填充行。

优化方法：
将WHERE,limit,ORDER BY子句置入内部UNION的子句，以提前过滤。

6.7.9 用户自定义变量

• 示例:

  1 2 3 4 5 6 7 8

  -- 定义： set @one :=1; set @min_actor := (select min(id) from actor); -- 赋值运算优先级很低，所以右边一般都要括号。 set @last_week := current_date-interval 1 week; -- 使用： select * from t where col <= @last_week;

缺点：

1. 使用自定义变量后，无法使用查询缓存；
2. 表名，列名，Limit中无法使用；
3. 仅在当前连接中有用；（如果持久化连接、连接池，则会发生数据竞态，出BUG）
4. 不能定义变量的类型；
5. 优化器可能将变量优化掉，导致结果不可预期；
6. 赋值的顺序和时机不固定，导致结果不可预期；
7. 使用未定义的变量不会产生任何语法错误。（编译期无法判断错误）出错几率很大。

• 优点：

优化排名语句

实现行号功能:

1
2
3
4
5
6
7

set @rownum:=0;
select id,@rownum := @rownum+1 as rownum
from actor limit 3;

-- 结果：
id： id1 id2 id3
rownum: 1 2 3

查询并且更新数据

原查询：（2条语句）

1
2
3

update t set lastUpdated=now() 
where id=1;
select lastUpdated from t where id=1;

改写后：(2条语句)

1
2
3
4

update t set lastUpdated=now() 
where id=1 and @now:= now();

select @now; -- 无需访问数据表

统计更新和插入的数量

• 示例：

  1 2 3 4 5 6 7 8 9

  insert into t (c1,c2) values (4,4) ,(2,1) ,(3,1) on duplicate key update c1=values(c1) +( 0* (@x:= @x+1)); select @x;

  第一句的返回值能知道更改了n1行；
  第二句通过@x统计到更新了n2行；
  因此：
  更新的行数=n2;
  插入的行数=n1-n2。

6.8 案例学习

6.8.1 使用MYSQL构建一个队列表

• tips:
  无论什么时候，避免Select .. For Update这种用法。
  原因：会造成事务阻塞。总是有更好的方法替代这个用法。
  此外，对于索引列，它产生排他行锁；
  对于非索引列，它产生排他表锁。

相关函数：

1
2

select connection_id();
-- 返回当前连接的id

案例：
表unsent_emails:

• id
• status (未发送，已发送，正在发送)
• owner （正在处理的连接id，默认是0）
• ts

错误示例：

1
2
3
4
5
6
7
8
9
10
11

Begin;
select id from unsent emails
where owner=0 and status='未发送'
limit 10 
For Update;
-- 结果是1,2,3
update unset_emails
set status='正在发送'
,owner=Connection_id()
where id in (1,2,3);
Commit;

select和update之间的间隙时间内，所有相同的查询会阻塞。（所有线程全都在竞争1个排他锁）

改进后：

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

set autocommit=1;
commit;
update unset_emails
set status='正在发送'
,owner=connection_id()
where owner=0 and status='unsent'
limit 10;

set autocommit=0;
-- 找出自己抢注的部分，进行处理：
select id from unsent_emails
where owner=connect_id() 
and status='正在发送';
-- 处理....

改进后，不必使用select ... for update，避免了事务阻塞。
唯一需要注意的时，需要定期检查是否有线程挂了，需要把它原来抢注的任务重置为无人拥有。

此外，消息队列还是别用Mysql实现了，用MQ,redis之类的吧。XD

6.8.2 计算两点之间的距离

• Tip:
  复杂地理信息计算建议使用PostgreSql.

案例：
某个点附近所有可以出租的房子。
（一定半径内的所有点）
（或社交网站中匹配附近的用户）

表Locations:

• id
• name
• lat: 经度
• lon：纬度

A点和B点之间的距离计算公式CAL:

1
2
3
4

Acos(
    cos(latA)*cos(latB)*cos(lonA-lonB)
  +sin(latA)*sin(latB)
)* 地球的半径

原查询：

1
2

select * from locations
where 地球的半径* CAL <= 100;

上述查询无法使用索引，且非常消耗CPU。

优化方法：降低精度；修改上述的椭圆计算公式，近似成立方体公式。

- 优化后：

1
2
3

select * from locations
where lat between 38.03-degrees(0.0253) and 38.03 + degree(0.0253)
and lon between -78.48 - degrees(0.0253) and -78.48 + degrees(0.0253);

上述查询可以利用索引(lat)或(lon)，但由于都是范围查询，无法利用联合索引。

为了进一步优化范围查询，可以使用枚举优化（使用IN列表）。
由于lat和lon列其实不是离散值，可以手动创建离散列：
新增两列存储坐标的近似值Floor()，然后在查询中使用IN将所有点的整数值放在列表中：

• Lat_floor: floor(lat)
• Lon_floor: floor(lon)
• Key(Lon_floor,Lat_floor)

- 进一步优化：

1
2
3
4
5
6

select * from locations
where lat between 38.03-degrees(0.0253) and 38.03 + degree(0.0253)
and lon between -78.48 - degrees(0.0253) and -78.48 + degrees(0.0253)
-- 增加对于索引的利用：
and lat_floor in (36,37,38,39,40)
and lon_floor in (-80,-79,-78,-77);

上述优化可以利用索引(lat_floor,lon_floor)，因此比前面更快。

• 精度恢复：
  上述优化只是滤掉不适合的点，可以进一步使用原来的公式进行过滤。由于此时剩下的点不多，因此即使原来的公式很复杂，性能也能够接受。

6.8.3 用户自定义函数(UDF)

书里说的比较含糊，总之是写一个C/C++程序作为后台程序，接受某种网络通信协议。
(TODO,进一步搜索别人的实际案例。)

6.9 总结

查询优化的思路：

1. 检查执行的时间消耗；
2. 检查Schema设计；
3. 检查索引设计；(三星系统)
4. 检查Explain计划（是否利用到索引，范围索引转化为枚举）
5. 其他的各种优化：
   (1) limit优化；
   (2) 覆盖索引+延迟关联；
   (3) 复杂查询分解；
   (4) 执行计划搜索提前终止；
   (5) 排序优化（1次传输，2次传输），Order By的列提取到第一张表；
   (6) UNION优化：手动下推谓词；
   (7) Count优化：反向过滤， 利用MyISam的统计信息；
   (8) Delayed优化：日志系统异步写入；
   (9) 排他锁优化：避免使用Select ... for update，尽早释放锁（先抢注，释放锁，后处理）。

• 前情提要：
  SQL
• hash(SQL)查询缓存

• SQL

• 语法解析器-

• 解析树

• 预处理-

• 解析树(合法,有权限)

• 优化器-

• 最优执行计划

• 接下来就要查询执行引擎了：

6.4.4 查询执行引擎

• 工作原理
  查询执行引擎根据执行计划，访问存储引擎的相关API。(Handler Api)
  查询中每张表由一个Handler实例表示，抽象了底层存储引擎的具体实现。

6.4.5 返回结果给客户端

采用TCP传输结果给客户端，为了避免服务器存储太多的结果，每生成一部分结果，就可以向客户端逐步返回结果集。
相关参数：

1
2

SQL_BUFFER_RESULT
-- 结果集的缓冲区

此外，查询的结果如果可以缓存，也会缓存下来。

6.5 优化器的局限性

6.5.1 关联子查询

• 案例

  1 2 3 4 5 6

  Select * from film where id in ( select film_id from film_actor where actor_id=1 );

优化器改写后：

1
2
3
4
5
6

select * from film
where exists(
    select * from film_actor
    where actor_id=1
    and film_id=film.id
);

通过explain命令，可以看到
执行流程是：

1. 对film进行全表扫描，得到所有id；
2. 使用id逐个排查film_actor表。

• 缺点
  对于film表很大的时候，性能很差。

• 解决方案1

  1 2 3 4 5

  select film.* from film join film_actor on id=film_id where actor_id=1;

  这个查询优化后，会使用较小的表作为驱动表，因此可以回避上述缺点。

• 解决方案2

  1 2 3 4 5 6

  select * from film where id in ( select group_concat(film_id) from film_actor where actor_id=1 );

  这个查询优化后，会先对film_actor进行处理，生成IN列表后，会先排序，然后二分查找。仅当film很大，而film_actor表很小的时候效率比原来的方案高。（换言之，不一定更高）

6.5.2 UNION的限制

外层的limit20无法提前传入内层，因此可以自己手动在内层先Limit一下，减少数据量。

1
2
3
4
5
6
7
8

(select * from t1
limit 20
)
UNION ALL
(select * from t2
limit 20
)
limit 20

以下是几个不支持的特性：

6.5.5 Mysql无法并行执行

Mysql无法利用多核。

6.5.6 哈希关联

Mysql的关联都是嵌套关联，不支持哈希关联。
不过可以通过建立哈希索引来曲线实现哈希关联。
Memory存储的索引都是哈希索引。

6.5.7 松散索引扫描

例如当索引为(a,b)，而查询条件中只有b的时候，由于不是最左前缀索引，因此无法利用索引，Mysql只能进行全表扫描。

如果有松散索引扫描：
先扫描a列第一个值对应的b列的范围；
再扫描a列第二个值对应的b列的范围；
以此类推，就能少扫描很多数据行。
（类似一个对a列值进行枚举的过程）

可惜Mysql还不支持松散索引扫描。

6.5.8 最大值和最小值优化

• 案例

  1 2	select min(id) from actor where first_name='PENELOPE'

其中first_name列没有索引，而id是主键列。

因此Mysql的处理方法是：

1. 进行全表扫描获取符合where的数据行；
2. 将上述数据中的id取min.

• 优化方案
  由于数据是按主键顺序排列的，因此全表扫描的时候，顺序IO，顺序扫描，遇到的主键也是递增的。因此扫描时遇到的第一个符合条件的数据行，它的主键值一定是最小的。

• 优化后的SQL

  1 2 3

  select id from actor use index(primary) where first_name='PENELOPE' limit 1;

• 优点：
  快。

• 缺点：
  可读性差。依赖于底层数据的物理组织。
  没人能看懂这里是要取最小值。

6.5.9 同一张表同时查询和更新

Mysql无法运行的SQL：

1
2
3
4
5

update t AS out_t
set cnt= (
    select count(1) from t as in_t
    where in_t.type=out_t.type
);

上述SQL的语意是将表中相似行（type相同）的数量，记录到所有行的cnt列中。

• 改写后可以运行：

  1 2 3 4 5 6 7

  update t join (select type,count(1) as cnt from t group by type ) AS tmp using (type) set t.cnt=tmp.cnt

  上述SQL使用生成表（临时表）的形式绕过了同时进行查询和更新的限制，查询的是临时表，更改的是原表。

上述是Mysql不支持的特性。

6.6 查询优化器的提示(hint)

这些提示随版本可能会变化。
目前可以使用的一些提示如下：

• High_priority/Low_priority
  （作用不大，只对使用表锁的引擎有效）
  多个语句同时访问某一个表时，哪些语句的优先级高。
  原理：
  等待某个表锁的语句组成等待队列。
  这个提示可以控制等待队列中的排列顺序。

• Delayed
  （有用）
  对于Insert和Replace有效。
  相应处理流程：

1. 立即回复客户端；
2. 将插入的行数据放入缓冲区；
3. 表空闲时将数据批量写入。

适用场景： 日志系统；
缺点：

1. 并不是所有存储引擎都支持；
2. 导致Last_insert_id()无法正常工作；
3. 不知道什么时候数据才真正落地。(有效性不好保证)

• Straight_join
  手动指定表的关联顺序。

• SQL_SMALL_RESULT/SQL_BIG_RESULT
  告诉优化器对于Group by或Distinct查询如何使用临时表及排序。

SQL_SMALL_RESULT：
结果集会很小，将结果集放在内存中的索引临时表，以避免排序操作。

SQL_BIG_RESULT：
结果集会很大，建议使用磁盘临时表进行排序。（外排）

• SQL_BUFFER_RESULT
  使用这个hint:
  将查询结果放入一个临时表中，然后尽可能快地释放表锁。

不使用这个hint:
查询结果全部发送给客户端后，才释放表锁。

• SQL_Cache/Sql_no_cache
  是否缓存SQL结果。(详见第七章)

• SQL_CALC_FOUND_ROWS
  (不该使用)
  返回结果中加上结果集的大小。（Limit之前）

• For update/Lock in share mode
  (尽可能避免使用)
  只对实现了行锁的存储引擎有效。

• Use index/ignore index/force index
  (有用)
  指定优化器使用或不使用哪些索引。

• optimizer_search_depth
  (有用)
  优化器穷举执行计划的限度。
  如果查询长时间处于statistics状态，可以考虑调低此参数。

• optimizer_prune_level
  默认开启。
  是否根据扫描的行数决定跳过某些执行计划。

上述hint即使有用，也不应滥用，不应假设自己比优化器的选择更优，可以实验验证。
应注意到随着版本升级，有些hint可能过时。（优化器变得更聪明）

6.7 优化特定类型的查询

6.7.1 count查询优化

count(1)等效于count(*)。

1. 利用Myisam特性优化

• MyIsam特性：
  统计信息中记录数据行数量，因此全表count极快。

案例：

1
2
3

select count(1)
from t
where id>5;

其中id上有索引。

优化后：

1
2
3
4

select  (select count(1) from t ) 
     - count(1)
FROM t
where id<=5；

优化前扫描的为>5的所有行；(可能很多)
优化后扫描的为<=5的所有行（最多5行）。

应当注意到上述优化只对MyISam引擎有用。

2. 使用近似值
   使用explain中预估的行数。
3. 缓存、汇总表

6.7.2 优化关联查询

1. 关联键上有索引；
2. Group by,order by只涉及一张表的列；

6.7.4 优化Group by和Distinct

Group by和Distinct会互相转化。

无法使用索引时，Groupby的两种策略：

1. 用临时表进行分组；(内存排序)
2. 用排序进行分组。(外排)

可以通过hint干预优化器的选择。

关联查询+GroupBy

• 案例

  1 2 3 4

  select first_name,last_name,count(1) from film_actor join actor using (actor_id) group by first_name,last_name

优化后：

1
2
3
4