Zhu.Yang

朱阳的个人博客(公众号:think123)

0%

当我们运行Java程序main方法的时候,我们都知道当前线程是main线程

1
Thread.currentThread().getName()

那么这个main线程是被谁启动,又是在什么时候被启动的呢?我们通过源码一探究竟。

阅读全文 »

最近在看synchronized 锁优化方面的内容,有些地方看起来不是很方便,干脆就编译个源码来看看。

在windows上编译

由于自己常用的电脑操作系统是win10,所以最开始是想要在win10上编译的,但是一来网上文章太少,二来在windows上编译确实麻烦太多了(windows可以参考深入理解JVM虚拟机这本书),故放弃了。

阅读全文 »

在之前的文章中我们讲到过引起多线程bug的三大源头问题(可见性,原子性,有序性问题),java的内存模型(Java Memory Model)可以解决可见性和有序性问题,但是原子性问题如何解决呢?

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
public class Counter {

volatile int count;

public void add10K() {
for(int i = 0; i < 10000; i++) {
count++;
}
}

public int get() {
return count;
}

public static void main(String[] args) throws InterruptedException {

Counter counter = new Counter();

Thread t1 = new Thread(() -> counter.add10K());

Thread t2 = new Thread(() -> counter.add10K());

t1.start();
t2.start();

t1.join();
t2.join();

System.out.println(counter.count);
}

}
阅读全文 »

编写正确的程序难,编写正确的并发程序则是难上加难。既然这么难为什么还要并发,单线程执行不好吗?为了快呀,点个链接你愿意等1分钟吗?,别说等一分钟了,要是有个网页让我等超过10秒钟,我就马上要关掉了。

我们编写的代码在计算机中运行,那么它肯定会用到计算机中的资源,一般都逃不过cpu、内存以及I/O(文件I/O或者网络I/O等)。但是这三者速度上有极大的差异。

CPU的速度远远快于内存,而内存的速度又远远远快于I/O。

比喻: CPU速度相当于 火箭,内存速度相当于 高铁,I/O速度相当于 步行。

而我们的程序运行的快慢实际上是取决于最慢的那个操作–I/O操作,仿佛在这个时候CPU再快都没啥作用。

我们一般都说尽可能少的查询数据库(batch的方式更好),就是为了较少I/O操作

阅读全文 »

nginx应该是我们常用到的一个软件了,它的用法和语法也很简单,本文主要介绍nginx语法以及各个模块作用。

Nginx配置目录

当我们安装好nginx之后,我们主要关注两个文件夹

  1. /etc/nginx/conf.d/ 文件夹,是我们进行子配置的配置项存放处,/etc/nginx/nginx.conf 主配置文件会默认把这个文件夹中所有子配置项都引入

    windows下,是对应的安装目录下的conf目录。

  2. /usr/share/nginx/html/ 文件夹,通常静态文件都放在这个文件夹,你也可以放到其他地方

    windows下,对应的目录是在安装目录下的html目录。

阅读全文 »

traefik2 DaemonSet

云原生微服务中我们使用了traefik2来作为我们的网关,当然我们也是通过DaemonSet(也可以使用deployment)的方式来部署到Kubernetes集群中。
DaemonSet部署之后的pod有如下特征

Kubernetes集群中的每个work node上都有这个pod(traefik2实例)
每个work node上只有一个这样的pod实例
当有新的work node加入Kubernetes集群后,该pod会自动在新加入的work node上被创建出来,而当旧的work node被删除后,它上面的pod也会被相应的删除掉。

阅读全文 »

web开发中,经常会获取请求端IP地址,熟悉的同学可能第一时间就想到了

1
String ip = httpServletRequest.getRemoteAddr();
阅读全文 »

查看执行计划

索引优化是一个永远都绕不过的话题,作为NoSQL的MongoDB也不例外。Mysql中通过explain命令来查看对应的索引信息,MongoDB亦如此。

1
2
3
4
5
6
1. db.collection.explain().<method(...)>
db.products.explain().remove( { category: "apparel" }, { justOne: true })

2. db.collection.<method(...)>.explain({})
db.products.remove( { category: "apparel" }, { justOne: true }).explain()

阅读全文 »

除了 B+ 树,你可能还听说过 B 树、 B- 树,实际上, B- 树就是 B 树,英文翻译都是 B-Tree ,这里的 “-” 并不是相对 B+ 树中的 “+” ,而只是一个连接符。而 B 树实际上是低级版的B+ 树,或者说 B+ 树是 B 树的改进版。

B+ tree

B+ tree 实际上是一颗m叉平衡查找树(不是二叉树)

平衡查找树定义:树中任意一个节点的左右子树的高度相差不能大于 1

B+ tree

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
/**
* 这是B+树非叶子节点的定义。
*
* 假设keywords=[3, 5, 8, 10]
* 4个键值将数据分为5个区间:(-INF,3), [3,5), [5,8), [8,10), [10,INF)
* 5个区间分别对应:children[0]...children[4]
*
* m值是事先计算得到的,计算的依据是让所有信息的大小正好等于页的大小:
* PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
*/
public class BPlusTreeNode {
// 5叉树
public static int m = 5;

// 键值,用来划分数据区间
public int[] keywords = new int[m-1];

// 保存子节点指针
public BPlusTreeNode[] children = new BPlusTreeNode[m];
}
/**
* 这是B+树中叶子节点的定义。
*
* B+树中的叶子节点跟内部结点是不一样的,
* 叶子节点存储的是值,而非区间。
* 这个定义里,每个叶子节点存储3个数据行的键值及地址信息。
*
* k值是事先计算得到的,计算的依据是让所有信息的大小正好等于页的大小:
* PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
*/
public class BPlusTreeLeafNode {
public static int k = 3;

// 数据的键值
public int[] keywords = new int[k];

// 数据地址
public long[] dataAddress = new long[k];

// 这个结点在链表中的前驱结点
public BPlusTreeLeafNode prev;

// 这个结点在链表中的后继结点
public BPlusTreeLeafNode next;
}

在B+ 树中,树中的节点并不存储数据本身,而是只是作为索引。除此之外,所有记录的节点按大小顺序存储在同一层的叶节点中,并且每个叶节点通过指针连接。

总结下,B+树有以下特点

  1. B +树的每个节点可以包含更多节点,其原因有两个,其一是降低树的高度(索引不会全部存储在内存中,内存中可能撑不住,所以一般都是将索引树存储在磁盘中,只是将根节点放到内存中,这样对每个节点的访问,实际上就是访问磁盘,树的高度就等于每次查询数据时磁盘 IO 操作的次数),另一种是将数据范围更改为多个间隔。间隔越大,数据检索越快(可以想象跳表)

  2. 每个节点不在是存储一个key,而是存储多个key

  3. 叶节点来存储数据,而其他节点用于索引

  4. 叶子节点通过两个指针相互链接,顺序查询性能更高。

这样设计还有以下优点:

  1. B +树的非叶子节点仅存储键,占用很小的空间,因此节点的每一层可以索引的数据范围要宽得多。换句话说,可以为每个IO操作搜索更多数据

  2. 叶子节点成对连接,符合磁盘的预读特性。例如,叶节点存储50和55,它们具有指向叶节点60和62的指针。当我们从磁盘读取对应于50和55的数据时,由于磁盘的预读特性,我们将顺便提一下60和62。读出相应的数据。这次是顺序读取,而不是磁盘搜索,加快了速度。

  3. 支持范围查询,局部范围查询非常高效,每个节点都可以索引更大,更准确的范围,这意味着B +树单磁盘IO信息大于B树,并且I / O效率更高

  4. 由于数据存储在叶节点层中,并且有指向其他叶节点的指针,因此范围查询仅需要遍历叶节点层,而无需遍历整个树。

由于磁盘访问速度和内存之间存在差距,为了提高效率,应将磁盘I / O最小化。磁盘通常不是严格按需读取的,而是每次都被预读。磁盘读取所需的数据后,它将向后读取内存中的一定长度的数据。这样做的理论基础是计算机科学中众所周知的本地原理:

关于MySQL数据索引是如何实现的,可以参考这篇文章:https://time.geekbang.org/column/article/77830

B-Tree

B-Tree实际上也是一颗m叉平衡查找树

B-Tree

  1. 所有的key值分布在整个树中
  2. 所有的key值出现在一个节点中
  3. 搜索可以在非叶子节点处结束
  4. 在完整的关键字搜索过程中,性能接近二分搜索。

B树和B+树之间的区别

  1. B +树中的非叶子节点不存储数据,并且存储在叶节点中的所有数据使得查询时间复杂度固定为log n。

  2. B树查询时间的复杂度不是固定的,它与键在树中的位置有关,最好是O(1)。

  3. 由于B+树的叶子节点是通过双向链表链接的,所以支持范围查询,且效率比B树高

  4. B树每个节点的键和数据是一起的

为什么MongoDB使用B-Tree,Mysql使用B+Tree ?

B +树中的非叶子节点不存储数据,并且存储在叶节点中的所有数据使得查询时间复杂度固定为log n。B树查询时间复杂度不是固定的,它与键在树中的位置有关,最好是O(1)。

我们已经说过,尽可能少的磁盘IO是提高性能的有效方法。MongoDB是一个聚合数据库,而B树恰好是键域和数据域的集群。

至于为什么MongoDB使用B树而不是B +树,可以从其设计的角度考虑它。
MongoDB不是传统的关系数据库,而是以BSON格式(可以认为是JSON)存储的nosql。目的是高性能,高可用性和易于扩展。

Mysql是关系型数据库,最常用的是数据遍历操作(join),而MongoDB它的数据更多的是聚合过的数据,不像Mysql那样表之间的关系那么强烈,因此MongoDB更多的是单个查询。

由于Mysql使用B+树,数据在叶节点上,叶子节点之间又通过双向链表连接,更加有利于数据遍历,而MongoDB使用B树,所有节点都有一个数据字段。只要找到指定的索引,就可以对其进行访问。毫无疑问,单个查询MongoDB平均查询速度比Mysql快。

Hash索引

简而言之,哈希索引使用某种哈希算法将键值转换为新的哈希值。不需要像B +树那样从根节点到叶节点逐步搜索。只需要一种哈希算法,就可以立即找到对应的位置,速度非常快。(此处可以想想Java中的HashMap)。

B+树索引和Hash索引的区别

  1. 如果是等价查询,则哈希索引显然具有绝对优势,因为只需一种算法即可找到相应的键值;当然,前提是键值是唯一的,如果存在hash冲突就必须链表遍历了。

  2. 哈希索引不支持范围查询(不过改造之后可以,Java中的LinkedHashMap通过链表保存了节点的插入顺序,那么也可以使用链表将数据的大小顺序保存起来)

    这样做虽然支持了范围查询但是时间复杂度是O(n),效率比跳表和B+Tree差

  3. 哈希索引无法使用索引排序以及模糊匹配

  4. 哈希索引也不支持多列联合索引的最左边匹配规则。

  5. 键值大量冲突的情况下,Hash索引效率极低

以前刚入行当CRUD boy的时候,我常去刷leetcode,每次遇到排列问题以及它的变种我就抓瞎了,然后搜索别人的实现方式我发现我都无法理解,甚至我还背过这类题的解法,可惜没啥用,过几天又忘记了,想不到时隔多年,我还是找到了一种适合我理解的实现方式。

我们初高中的时候,都学过排列,它的概念是这么说的:从 n 个不同的元素中取出m(1≤m≤n)个不同的元素,按照一定的顺序排成一列,这个过程就叫排列。当 m=n 这种特殊情况出现的时候,就是全排列(All Permutation)。如果选择出的这 m 个元素可以有重复的,这样的排列就是为重复排列(否则就是不重复排列。

如果有这样一道题:求 1,2,3,4,5五个数字的全排列,那么该如何实现呢?我们都知道答案是有120种(54321=120)。

很明显这这里我们会想到用递归来做,以下是我的心路历程:

阅读全文 »