Java中的锁是用于管理多线程并发访问共享资源的关键机制。锁可以确保在任意给定时间内只有一个线程可以访问特定的资源,从而避免数据竞争和不一致性。Java提供了多种锁机制,可以分为以下几类:
synchronized
关键字是内置锁机制的基础,可以用于方法或代码块。当一个线程进入synchronized
代码块或方法时,它会获取关联对象的锁;当线程离开该代码块或方法时,锁会被释放。如果其他线程尝试获取同一个对象的锁,它们将被阻塞,直到锁被释放。其中,syncronized加锁时有无锁、偏向锁、轻量级锁和重量级锁几个级别。偏向锁用于当一个线程进入同步块时,如果没有任何其他线程竞争,就会使用偏向锁,以减少锁的开销。轻量级锁使用线程栈上的数据结构,避免了操作系统级别的锁。重量级锁则涉及操作系统级的互斥锁。java.util.concurrent.locks.ReentrantLock
是一个显式的锁类,提供了比synchronized
更高级的功能,如可中断的锁等待、定时锁等待、公平锁选项等。ReentrantLock
使用lock()
和unlock()
方法来获取和释放锁。其中,公平锁按照线程请求锁的顺序来分配锁,保证了锁分配的公平性,但可能增加锁的等待时间。非公平锁不保证锁分配的顺序,可以减少锁的竞争,提高性能,但可能造成某些线程的饥饿。java.util.concurrent.locks.ReadWriteLock
接口定义了一种锁,允许多个读取者同时访问共享资源,但只允许一个写入者。读写锁通常用于读取远多于写入的情况,以提高并发性。synchronized
和ReentrantLock
都是悲观锁的例子。乐观锁(Optimistic Locking)通常不锁定资源,而是在更新数据时检查数据是否已被其他线程修改。乐观锁常使用版本号或时间戳来实现。synchronized
是一个很好的选择。它使用起来简单,不需要额外的资源管理,因为锁会在方法退出或代码块执行完毕后自动释放。synchronized
代码块。这可以让你更精细地控制同步的范围,从而减少锁的持有时间,提高并发性能。synchronized
关键字使用对象的内置锁(也称为监视器锁),这在需要使用对象作为锁对象的情况下很有用,尤其是在对象状态与锁保护的代码紧密相关时。ReentrantLock 的底层实现主要依赖于 AbstractQueuedSynchronizer(AQS)这个抽象类。AQS 是一个提供了基本同步机制的框架,其中包括了队列、状态值等。ReentrantLock 在 AQS 的基础上通过内部类 Sync 来实现具体的锁操作。不同的 Sync 子类实现了公平锁和非公平锁的不同逻辑。
ReentrantLock fairLock = new ReentrantLock(true);
ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newCondition();
// 使用下面方法进行等待和唤醒
condition.await();
condition.signal();
索引概念
当你想查阅书中某个知识的内容,你会选择一页一页的找呢?还是在书的目录去找呢?
傻瓜都知道时间是宝贵的,当然是选择在书的目录去找,找到后再翻到对应的页。书中的目录,就是充当索引的角色,方便我们快速查找书中的内容,所以索引是以空间换时间的设计思想。
那换到数据库中,索引的定义就是帮助存储引擎快速获取数据的一种数据结构,形象的说就是索引是数据的目录。
所谓的存储引擎,说白了就是如何存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。MySQL 存储引擎有 MyISAM 、InnoDB、Memory,其中 InnoDB 是在 MySQL 5.5 之后成为默认的存储引擎。
下图是 MySQL 的结构图,索引和数据就是位于存储引擎中:
底层数据结构
MySQL 是会将数据持久化在硬盘,而存储功能是由 MySQL 存储引擎实现的,所以讨论 MySQL 使用哪种数据结构作为索引,实际上是在讨论存储引使用哪种数据结构作为索引,InnoDB 是 MySQL 默认的存储引擎,它就是采用了 B+ 树作为索引的数据结构。
要设计一个 MySQL 的索引数据结构,不仅仅考虑数据结构增删改的时间复杂度,更重要的是要考虑磁盘 I/0 的操作次数。因为索引和记录都是存放在硬盘,硬盘是一个非常慢的存储设备,我们在查询数据的时候,最好能在尽可能少的磁盘 I/0 的操作次数内完成。
二分查找树虽然是一个天然的二分结构,能很好的利用二分查找快速定位数据,但是它存在一种极端的情况,每当插入的元素都是树内最大的元素,就会导致二分查找树退化成一个链表,此时查询复杂度就会从 O(logn)降低为 O(n)。
为了解决二分查找树退化成链表的问题,就出现了自平衡二叉树,保证了查询操作的时间复杂度就会一直维持在 O(logn) 。但是它本质上还是一个二叉树,每个节点只能有 2 个子节点,随着元素的增多,树的高度会越来越高。
而树的高度决定于磁盘 I/O 操作的次数,因为树是存储在磁盘中的,访问每个节点,都对应一次磁盘 I/O 操作,也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数,所以树的高度越高,就会影响查询性能。
B 树和 B+ 都是通过多叉树的方式,会将树的高度变矮,所以这两个数据结构非常适合检索存于磁盘中的数据。
选择 B+ 数据结构的原因
1、B+Tree vs B Tree
B+Tree 只在叶子节点存储数据,而 B 树 的非叶子节点也要存储数据,所以 B+Tree 的单个节点的数据量更小,在相同的磁盘 I/O 次数下,就能查询更多的节点。
另外,B+Tree 叶子节点采用的是双链表连接,适合 MySQL 中常见的基于范围的顺序查找,而 B 树无法做到这一点。
2、B+Tree vs 二叉树
对于有 N 个叶子节点的 B+Tree,其搜索复杂度为O(logdN),其中 d 表示节点允许的最大子节点个数为 d 个。
在实际的应用当中, d 值是大于100的,这样就保证了,即使数据达到千万级别时,B+Tree 的高度依然维持在 3~4 层左右,也就是说一次数据查询操作只需要做 3~4 次的磁盘 I/O 操作就能查询到目标数据。
而二叉树的每个父节点的儿子节点个数只能是 2 个,意味着其搜索复杂度为 O(logN),这已经比 B+Tree 高出不少,因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。
3、B+Tree vs Hash
Hash 在做等值查询的时候效率贼快,搜索复杂度为 O(1)。
但是 Hash 表不适合做范围查询,它更适合做等值的查询,这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因
SQL 标准提出了四种隔离级别来规避这些现象,隔离级别越高,性能效率就越低,这四个隔离级别如下:
按隔离水平高低排序如下:
针对不同的隔离级别,并发事务时可能发生的现象也会不同。
也就是说:
MVCC允许多个事务同时读取同一行数据,而不会彼此阻塞,每个事务看到的数据版本是该事务开始时的数据版本。这意味着,如果其他事务在此期间修改了数据,正在运行的事务仍然看到的是它开始时的数据状态,从而实现了非阻塞读操作。
对于「读提交」和「可重复读」隔离级别的事务来说,它们是通过 Read View 来实现的,它们的区别在于创建 Read View 的时机不同,大家可以把 Read View 理解成一个数据快照,就像相机拍照那样,定格某一时刻的风景。
Read View 有四个重要的字段:
对于使用 InnoDB 存储引擎的数据库表,它的聚簇索引记录中都包含下面两个隐藏列:
在创建 Read View 后,我们可以将记录中的 trx_id 划分这三种情况:
一个事务去访问记录的时候,除了自己的更新记录总是可见之外,还有这几种情况:
这种通过「版本链」来控制并发事务访问同一个记录时的行为就叫 MVCC(多版本并发控制)。
头部压缩
HTTP/2 没使用常见的 gzip 压缩方式来压缩头部,而是开发了 HPACK 算法,HPACK 算法主要包含三个组成部分:
客户端和服务器两端都会建立和维护「字典」,用长度较小的索引号表示重复的字符串,再用 Huffman 编码压缩数据,可达到 50%~90% 的高压缩率。
二进制帧
HTTP/2 厉害的地方在于将 HTTP/1 的文本格式改成二进制格式传输数据,极大提高了 HTTP 传输效率,而且二进制数据使用位运算能高效解析。
你可以从下图看到,HTTP/1.1 的响应和 HTTP/2 的区别:
HTTP/2 把响应报文划分成了两类帧(Frame),图中的 HEADERS(首部)和 DATA(消息负载) 是帧的类型,也就是说一条 HTTP 响应,划分成了两类帧来传输,并且采用二进制来编码。
HTTP/2 二进制帧的结构如下图:
帧头(Frame Header)很小,只有 9 个字节,帧开头的前 3 个字节表示帧数据(Frame Playload)的长度。
帧长度后面的一个字节是表示帧的类型,HTTP/2 总共定义了 10 种类型的帧,一般分为数据帧和控制帧两类,如下表格:
帧类型后面的一个字节是标志位,可以保存 8 个标志位,用于携带简单的控制信息,比如:
帧头的最后 4 个字节是流标识符(Stream ID),但最高位被保留不用,只有 31 位可以使用,因此流标识符的最大值是 2^31,大约是 21 亿,它的作用是用来标识该 Frame 属于哪个 Stream,接收方可以根据这个信息从乱序的帧里找到相同 Stream ID 的帧,从而有序组装信息。
最后面就是帧数据了,它存放的是通过 HPACK 算法压缩过的 HTTP 头部和包体。
并发传输
我们都知道 HTTP/1.1 的实现是基于请求-响应模型的。同一个连接中,HTTP 完成一个事务(请求与响应),才能处理下一个事务,也就是说在发出请求等待响应的过程中,是没办法做其他事情的,如果响应迟迟不来,那么后续的请求是无法发送的,也造成了队头阻塞的问题。
而 HTTP/2 就很牛逼了,通过 Stream 这个设计,多个 Stream 复用一条 TCP 连接,达到并发的效果,解决了 HTTP/1.1 队头阻塞的问题,提高了 HTTP 传输的吞吐量。
为了理解 HTTP/2 的并发是怎样实现的,我们先来理解 HTTP/2 中的 Stream、Message、Frame 这 3 个概念。
你可以从上图中看到:
因此,我们可以得出个结论:多个 Stream 跑在一条 TCP 连接,同一个 HTTP 请求与响应是跑在同一个 Stream 中,HTTP 消息可以由多个 Frame 构成, 一个 Frame 可以由多个 TCP 报文构成。
在 HTTP/2 连接上,不同 Stream 的帧是可以乱序发送的(因此可以并发不同的 Stream ),因为每个帧的头部会携带 Stream ID 信息,所以接收端可以通过 Stream ID 有序组装成 HTTP 消息,而同一 Stream 内部的帧必须是严格有序的。
客户端和服务器双方都可以建立 Stream,因为服务端可以主动推送资源给客户端, 客户端建立的 Stream 必须是奇数号,而服务器建立的 Stream 必须是偶数号。
服务器主动推送资源
HTTP/1.1 不支持服务器主动推送资源给客户端,都是由客户端向服务器发起请求后,才能获取到服务器响应的资源。
比如,客户端通过 HTTP/1.1 请求从服务器那获取到了 HTML 文件,而 HTML 可能还需要依赖 CSS 来渲染页面,这时客户端还要再发起获取 CSS 文件的请求,需要两次消息往返,如下图左边部分:
如上图右边部分,在 HTTP/2 中,客户端在访问 HTML 时,服务器可以直接主动推送 CSS 文件,减少了消息传递的次数。
在 Nginx 中,如果你希望客户端访问 /test.html 时,服务器直接推送 /test.css,那么可以这么配置:
location /test.html {
http2_push /test.css;
}
那 HTTP/2 的推送是怎么实现的?
客户端发起的请求,必须使用的是奇数号 Stream,服务器主动的推送,使用的是偶数号 Stream。服务器在推送资源时,会通过 PUSH_PROMISE 帧传输 HTTP 头部,并通过帧中的 Promised Stream ID 字段告知客户端,接下来会在哪个偶数号 Stream 中发送包体。
如上图,在 Stream 1 中通知客户端 CSS 资源即将到来,然后在 Stream 2 中发送 CSS 资源,注意 Stream 1 和 2 是可以并发的。
Redis 提供了丰富的数据类型,常见的有五种数据类型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合)。
随着 Redis 版本的更新,后面又支持了四种数据类型:BitMap(2.2 版新增)、HyperLogLog(2.8 版新增)、GEO(3.2 版新增)、Stream(5.0 版新增)。Redis 五种数据类型的应用场景:
Redis 后续版本又支持四种数据类型,它们的应用场景如下:
当你修改一个字符串类型的value时,Redis的底层处理取决于修改的类型和规模:
Redis 的读写操作都是在内存中,所以 Redis 性能才会高,但是当 Redis 重启后,内存中的数据就会丢失,那为了保证内存中的数据不会丢失,Redis 实现了数据持久化的机制,这个机制会把数据存储到磁盘,这样在 Redis 重启就能够从磁盘中恢复原有的数据。
Redis 共有三种数据持久化的方式:
AOF 日志是如何实现的?
Redis 在执行完一条写操作命令后,就会把该命令以追加的方式写入到一个文件里,然后 Redis 重启时,会读取该文件记录的命令,然后逐一执行命令的方式来进行数据恢复。
我这里以「set name xiaolin」命令作为例子,Redis 执行了这条命令后,记录在 AOF 日志里的内容如下图:
Redis 提供了 3 种写回硬盘的策略, 在 Redis.conf 配置文件中的 appendfsync 配置项可以有以下 3 种参数可填:
我也把这 3 个写回策略的优缺点总结成了一张表格:
RDB 快照是如何实现的呢?
因为 AOF 日志记录的是操作命令,不是实际的数据,所以用 AOF 方法做故障恢复时,需要全量把日志都执行一遍,一旦 AOF 日志非常多,势必会造成 Redis 的恢复操作缓慢。
为了解决这个问题,Redis 增加了 RDB 快照。所谓的快照,就是记录某一个瞬间东西,比如当我们给风景拍照时,那一个瞬间的画面和信息就记录到了一张照片。
所以,RDB 快照就是记录某一个瞬间的内存数据,记录的是实际数据,而 AOF 文件记录的是命令操作的日志,而不是实际的数据。
因此在 Redis 恢复数据时, RDB 恢复数据的效率会比 AOF 高些,因为直接将 RDB 文件读入内存就可以,不需要像 AOF 那样还需要额外执行操作命令的步骤才能恢复数据。
Redis 提供了两个命令来生成 RDB 文件,分别是 save 和 bgsave,他们的区别就在于是否在「主线程」里执行:
混合持久化
在 Redis 4.0 提出了混合持久化。如果想要开启混合持久化功能,可以在 Redis 配置文件将下面这个配置项设置成 yes:
aof-use-rdb-preamble yes
混合持久化是工作在 AOF 日志重写过程。当开启了混合持久化时,在 AOF 重写日志时,fork 出来的重写子进程会先将与主线程共享的内存数据以 RDB 方式写入到 AOF 文件,然后主线程处理的操作命令会被记录在重写缓冲区里,重写缓冲区里的增量命令会以 AOF 方式写入到 AOF 文件,写入完成后通知主进程将新的含有 RDB 格式和 AOF 格式的 AOF 文件替换旧的的 AOF 文件。
也就是说,使用了混合持久化,AOF 文件的前半部分是 RDB 格式的全量数据,后半部分是 AOF 格式的增量数据。!
这样的好处在于,重启 Redis 加载数据的时候,由于前半部分是 RDB 内容,这样加载的时候速度会很快。
加载完 RDB 的内容后,才会加载后半部分的 AOF 内容,这里的内容是 Redis 后台子进程重写 AOF 期间,主线程处理的操作命令,可以使得数据更少的丢失。
完全同步
完全同步发生在以下几种情况:
主从服务器间的第一次同步的过程可分为三个阶段:
image.png
实现过程:
SYNC
命令,请求开始同步。SYNC
命令后,主服务器会保存当前数据集的状态到一个临时文件,这个过程称为RDB(Redis Database)快照。replication backlog buffer
。replication backlog buffer
中的命令发送给从服务器,从服务器会执行这些命令,以保证数据的一致性。增量同步
增量同步允许从服务器从断点处继续同步,而不是每次都进行完全同步。它基于PSYNC
命令,使用了运行ID(run ID)和复制偏移量(offset)的概念。
主要有三个步骤:
那么关键的问题来了,主服务器怎么知道要将哪些增量数据发送给从服务器呢?答案藏在这两个东西里:
那 repl_backlog_buffer 缓冲区是什么时候写入的呢?
在主服务器进行命令传播时,不仅会将写命令发送给从服务器,还会将写命令写入到 repl_backlog_buffer 缓冲区里,因此 这个缓冲区里会保存着最近传播的写命令。
网络断开后,当从服务器重新连上主服务器时,从服务器会通过 psync 命令将自己的复制偏移量 slave_repl_offset 发送给主服务器,主服务器根据自己的 master_repl_offset 和 slave_repl_offset 之间的差距,然后来决定对从服务器执行哪种同步操作:
当主服务器在 repl_backlog_buffer 中找到主从服务器差异(增量)的数据后,就会将增量的数据写入到 replication buffer 缓冲区,这个缓冲区我们前面也提到过,它是缓存将要传播给从服务器的命令。
repl_backlog_buffer 缓行缓冲区的默认大小是 1M,并且由于它是一个环形缓冲区,所以当缓冲区写满后,主服务器继续写入的话,就会覆盖之前的数据。因此,当主服务器的写入速度远超于从服务器的读取速度,缓冲区的数据一下就会被覆盖。
那么在网络恢复时,如果从服务器想读的数据已经被覆盖了,主服务器就会采用全量同步,这个方式比增量同步的性能损耗要大很多。
因此,为了避免在网络恢复时,主服务器频繁地使用全量同步的方式,我们应该调整下 repl_backlog_buffer 缓冲区大小,尽可能的大一些,减少出现从服务器要读取的数据被覆盖的概率,从而使得主服务器采用增量同步的方式。
在 Redis 的主从架构中,由于主从模式是读写分离的,如果主节点(master)挂了,那么将没有主节点来服务客户端的写操作请求,也没有主节点给从节点(slave)进行数据同步了。
这时如果要恢复服务的话,需要人工介入,选择一个「从节点」切换为「主节点」,然后让其他从节点指向新的主节点,同时还需要通知上游那些连接 Redis 主节点的客户端,将其配置中的主节点 IP 地址更新为「新主节点」的 IP 地址。
这样也不太“智能”了,要是有一个节点能监控「主节点」的状态,当发现主节点挂了,它自动将一个「从节点」切换为「主节点」的话,那么可以节省我们很多事情啊!
Redis 在 2.8 版本以后提供的哨兵(_Sentinel_)机制,它的作用是实现主从节点故障转移。它会监测主节点是否存活,如果发现主节点挂了,它就会选举一个从节点切换为主节点,并且把新主节点的相关信息通知给从节点和客户端。
哨兵其实是一个运行在特殊模式下的 Redis 进程,所以它也是一个节点。从“哨兵”这个名字也可以看得出来,它相当于是“观察者节点”,观察的对象是主从节点。
当然,它不仅仅是观察那么简单,在它观察到有异常的状况下,会做出一些“动作”,来修复异常状态。
哨兵节点主要负责三件事情:监控、选主、通知。
当redis集群的主节点故障时,Sentinel集群将从剩余的从节点中选举一个新的主节点,有以下步骤:
Sentinel集群的每一个Sentinel节点会定时对redis集群的所有节点发心跳包检测节点是否正常。如果一个节点在down-after-milliseconds时间内没有回复Sentinel节点的心跳包,则该redis节点被该Sentinel节点主观下线。
当节点被一个Sentinel节点记为主观下线时,并不意味着该节点肯定故障了,还需要Sentinel集群的其他Sentinel节点共同判断为主观下线才行。
该Sentinel节点会询问其他Sentinel节点,如果Sentinel集群中超过quorum数量的Sentinel节点认为该redis节点主观下线,则该redis客观下线。
如果客观下线的redis节点是从节点或者是Sentinel节点,则操作到此为止,没有后续的操作了;如果客观下线的redis节点为主节点,则开始故障转移,从从节点中选举一个节点升级为主节点。
如果需要从redis集群选举一个节点为主节点,首先需要从Sentinel集群中选举一个Sentinel节点作为Leader。
每一个Sentinel节点都可以成为Leader,当一个Sentinel节点确认redis集群的主节点主观下线后,会请求其他Sentinel节点要求将自己选举为Leader。被请求的Sentinel节点如果没有同意过其他Sentinel节点的选举请求,则同意该请求(选举票数+1),否则不同意。
如果一个Sentinel节点获得的选举票数达到Leader最低票数(quorum和Sentinel节点数/2+1的最大值),则该Sentinel节点选举为Leader;否则重新进行选举。
举个例子,假设哨兵节点有 3 个,quorum 设置为 2,那么任何一个想成为 Leader 的哨兵只要拿到 2 张赞成票,就可以选举成功了。如果没有满足条件,就需要重新进行选举。
当Sentinel集群选举出Sentinel Leader后,由Sentinel Leader从redis从节点中选择一个redis节点作为主节点:
快速排序
快速排序是一种不稳定排序,它的时间复杂度为O(nlgn),最坏情况为O(n2),空间复杂度为O(nlgn)
快排使用了分治策略的思想,所谓分治,顾名思义,就是分而治之,将一个复杂的问题,分成两个或多个相似的子问题,在把子问题分成更小的子问题,直到更小的子问题可以简单求解,求解子问题,则原问题的解则为子问题解的合并。快排的过程简单的说只有三步:
具体按以下步骤实现:
注意这里的基准该如何选择?最简单的一种做法是每次都是选择最左边的元素作为基准,但这对几乎已经有序的序列来说,并不是最好的选择,它将会导致算法的最坏表现。还有一种做法,就是选择中间的数或通过 Math.random() 来随机选取一个数作为基准。
public class QuickSort {
// 快速排序算法
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
// 递归排序左半部分
quickSort(arr, low, pi - 1);
// 递归排序右半部分
quickSort(arr, pi + 1, high);
}
}
// 划分函数,用于找到基准元素的正确位置
int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 初始化较小元素的索引
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素放到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 返回基准元素的位置
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
for (int value : arr) {
System.out.print(value + " ");
}
}
}
冒泡排序算法
冒泡排序:通过相邻元素的比较和交换,每次将最大(或最小)的元素逐步“冒泡”到最后(或最前)
public class BubbleSort {
// 冒泡排序算法
public void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制比较轮数
for (int i = 0; i < n - 1; i++) {
// 内层循环进行两两比较并交换
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换两个元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.bubbleSort(arr);
System.out.println("Sorted array:");
for (int value : arr) {
System.out.print(value + " ");
}
}
}