1.外部排序
处理数据量过大无法全部载入内存的排序技术。要读取和写入硬盘上的数据,并在内存中间对这些数据进行排序。性能主要取决于 I/O 操作。
外部排序(External Sorting)是一种可以处理数据量过大无法全部载入内存的排序技术。当待排序数据的大小超出计算机内存的容量时,就需要使用外部排序来进行排序。外部排序通常涉及到读取和写入硬盘上的数据,并在内存中对这些数据进行排序。因此,外部排序的主要性能瓶颈在于 I/O 操作,即从磁盘读取数据和将数据写入磁盘的速度。
实现外部排序的核心思想是分治法。把待排序的数据分成若干个大小合适块。每次读入一个块的数据并且在内存中间进行排序,排好序的块写回磁盘。然后把排好序的块写回到磁盘。从已排好序的块中间选取一个作为当前的最小值,不断的将最小的数输出到新的文件。直到块中所有的元素都输出,最后将新文件重新命名为原始文件
外部排序过程
1.数据分块:首先需要将待排序的数据按照一定的大小分成多个块,每个块大小要尽量小于内存的容量。这些块会被逐个读入内存中进行排序。
2.内部排序:对于每个块内的数据,在内存中使用经典的排序算法(如快速排序、归并排序等)进行排序操作。
3.归并排序(Merging sorted chunks)将已经排好序的块合并为一个大的有序文件。最终输出的文件是由所有排序好的数据组成的,但其中的任意两个元素满足有序性。
4.块归并排序的实现:(1)把每个块的第一个元素读入内存,建立最小堆,根据建堆算法,调整堆的结构,使得堆顶部的元素最小。(2)把堆顶元素输出到文件中,并从所属块读取下一个待排序元素放入堆中。如果某块已经没有剩余元素,那么就把堆的大小减去 1(3)直到所有输入文件的元素都被输出到输出文件中。)(4)得到的输出文件就是所有排序的数据组成的。
不断的通过对每个块的最小的元素不断的比较,选取最小的元素作为待输出的下一个元素。因为每个块都是排好顺的可以保证每次输出都是最小的元素。将有序的小块合并为一个大块,多次合并得到完全有序的输出文件。
外部排序复杂度
最坏的情况下 对于多路归并排序算法来说,时间复杂度主要与读写磁盘的次数有关。在最坏情况下,需要进行 $log_B N$ $B$ 为内存可容纳的块大小,$N$ 为待排序数据的总量)每次排序需要读取和写入每个块一遍。因此,总的磁盘 I/O 操作次数为 $2N*log_B N$。
2.缓存
缓存是一种将计算机程序经常需要的数据存储在一个临时存储器或内存中的技术。这样,在后续的请求中,相同的数据可以更快地被检索到。缓存可以减少网络带宽的使用,提高网页加载速度,并降低服务器的负载。通常,浏览器缓存经常访问的文件(如图像和 CSS 文件),以便在下次访问时能够更快地加载页面。在开发中,我们可以使用缓存来优化应用程序的性能。
Redis 是一个开源的数据结构服务器,可用作数据库、高速缓存和消息代理。它支持多种类型的数据结构,包括字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)和有序集合(sorted sets)等。Redis 具有极高的性能,在处理大规模数据时表现优异。它通常被用于处理高频查询和写入操作,并可以通过复制和分片来提供高可用性和横向扩展性。同时,Redis 还支持诸如事务、Lua 脚本和发布/订阅等功能。由于其高速、灵活和可扩展的特点,Redis 已经成为了当今广泛使用的数据解决方案之一,被用于构建实时应用程序、互联网应用程序、游戏应用程序等。
3.缓存和数据库数据不一致的问题
分布式缓存
把缓存数据分散到多个缓存服务器。同时使用缓存协议进行协调。在更新数据的时候先更新缓存,让缓存服务器异步的写入数据库。降低对数据库的读写操作,提高数据库性能的同时还保证了数据一致性。
1.如果只有一个缓存服务器出现问题或者宕机,那么系统就无法使用了,因为所有的请求都需要访问数据库。 2.把缓存的压力分散到多个服务器,避免单一服务器压力过高。 3.当需要增加缓存容量的时候,只需要添加新的缓存服务器即可。 4.可以通过负载均衡选择最合适的服务器来处理请求。提高系统的性能和稳定。
把数据发送给消息队列,让消息队列异步的写入数据库。既可以控制消息队列中消息消费的速度,实现了解耦和异步化。减少了对数据库的压力,还保证了数据的一致性。
具体的过程是:1.(生产者需要更新数据库,并同步更新缓存。)生产者将需要更新的数据写入消息队列,同时等待消费者处理后的确认消息。2.消费者从消息队列中获取到生产者发送的数据更新请求,并且首先更新缓存中的相应数据。3.消费者向消息队列发送“更新成功”的确认消息。 4.一旦生产者收到“更新成功”的确认消息,就开始执行 MySQL 数据库中的数据更新操作。5.当数据更新完成后,生产者向消息队列发送“更新完成”的确认消息。消费者收到“更新完成”的确认消息之后,就可以继续处理下一个数据更新请求了。
4.MySQl 数据不一致的场景
并发更新:
较晚更新覆盖之前的更新。多个用户同时对同一行记录进行更新,最后写入数据库的数据只有最后一个提交的事务所更新的数据.如果两个事务都尝试更新同一时间并将它们保存回 MySQL,则较晚的一个提交将覆盖先前的更改。
解决:使用 MySQL 的事务机制保证数据一致性,使用锁机制避免并发更新问题。
写操作丢失: 在高并发情况下,如果多个并发操作同时试图写入相同的数据记录,可能会导致某些写操作被覆盖,因此不能正常保存到数据库中。
解决方案:让每个写操作单独获得锁,以确保每个写操作都成功,并且它们的顺序正确。
数据库故障:
当 MySQL 崩溃或发生硬件故障时,可能会丢失最近的事务,从而导致数据文件中的数据与缓存数据不一致。 解决方案:
使用 MySQL 的备份机制,定期将数据库备份到另一个位置或使用主从复制机制自动备份。 使用 MySQL 的 redo 日志或 binlog 来恢复丢失的数据。
5.Redis 中数据不一致的场景
1.缓存穿透
当大量请求同时查询缓存中不存在的相同数据时,会导致所有的请求都绕过缓存访问数据库,从而使数据库负载骤增。更糟糕的是,如果有人故意发送这种类型的请求,则可能会使服务器崩溃。
解决方案:使用布隆过滤器或其他缓存穿透技术来防止缓存穿透。
2.缓存击穿
热点数据过期,当某个热点数据在缓存中失效后,大量请求会同时访问数据库,从而使数据库负载骤增。这被称为缓存击穿。
解决方案:互斥锁和分布式锁。在互斥锁或者分布式锁的机制中:当某个请求发现缓存中间不存在所需要的数据,那么该请求就会试图获取一个锁,其他的请求同时到达并尝试更新相同的数据时,它们将会被阻塞,直到第一个请求完成并释放锁。这样就避免了多个请求同时访问数据库的情况。
使用互斥锁或分布式锁来解决缓存击穿问题的过程一般是这样的:
(1)当 A 请求找不到对应的缓存值,先获取一个独占锁:SETNX
命令
(2)如果操作成功(试图加锁),则说明当前请求获得了锁锁,可以开始加载数据,设置缓存值,释放锁。
(3)如果获取锁失败,说明其他请求正在加载数据,那么 A 请求可以选择等待一段时间后重试。或者立即响应一个友好的Response
3.缓存雪崩
缓存雪崩是指缓存中大量的数据在同一时间过期失效,导致请求直接打到数据库上,从而压垮数据库的现象。
大量相同的 key 同时失效:如果应用系统中的大量缓存 key 同时失效,会导致大量请求落到数据库上,导致服务器压力骤增。
热点数据集中过期:在某些场景下,热点数据的访问频率很高,当这些数据过期后,大量请求会直接命中数据库,导致数据库短时间内承受大量流量。
缓存服务器故障:例如网络异常、内存耗尽等,导致缓存服务不可用。
解决方案:热点数据随机过期+热点数据不过期+多级缓存(本地缓存和分布式缓存)+限流+降级+监测。
4.Redis 持久化机制错误配置
如果 Redis 的持久化配置不正确,就会产生数据不一致性的情况,比如 AOF 日志不及时落盘,数据丢失等。
解决方案:在 Redis 中正确配置持久化机制,以确保数据持久化的稳定性和完整性
6.虚拟内存
虚拟内存是操作系统的一个抽象层。 可以访问大于物理内存容量的地址空间。
底层实现:
1 页面分配:虚拟内存把进程的地址空间分为大小相同的页,每一页都有唯一的标识符。进程需要新的内存页的时,操作系统为他分配未使用的物理页,并映射到对应的物理地址。 2 换页:如果物理内存不足,那么操作系统会通过换页机制将不常用的页面换出,如果进程需要访问被换出的页面,就会触发缺页异常,操作系统会重新从磁盘读取出物理内存并更新该页面的映射关系。 3 页面保护:虚拟内存为每个页面设置访问权限和保护权限,只读/可执行。 4 TLB 管理。TLB(Translation Lookaside Buffer)是硬件缓存加速虚拟地址到物理地址的映射。
分页+换页+权限控制+硬件缓存
7.LRU 缓存淘汰算法
LRU 是一种常用的缓存淘汰算法,其全称为 Least Recently Used,即最近最少使用。其核心思想是优先淘汰最近最少使用的缓存块,从而保留经常使用的缓存块,提高访问效率。LRU 算法的底层实现通常有以下几种方式:
1 双向链表
使用一个双向链表表示缓存块的使用顺序,将最新访问的块加入到链表的头部,每次淘汰的时候删除链表尾部的缓存块。
2 哈希表+双向链表
双向链表虽然实现简单,但是在查找特定节点的时候需要遍历整个链表,效率低。这个时候如果维护一个哈希表,那么可以在 O(1)的时间内,快速获取到指定的缓存块,加速淘汰操作。
需要注意的问题有哪些?
多线程并发访问需要加锁。在 golang 中间我如果使用 HashMap + 双向链表 ,golang 的 map 线程不安全。
Map 线程不安全是因为:一个协程正在往 Map 插入(或者)删除元素,另外一个协程正在进行读取操作。就会出现数据不一致的情况。因为在插入元素的时候,Map 内部对 bucket 进行 RESIZE 操作,这会导致某些 bucket 的指针指向发生改变,但是正在读取的 bucket 的协程并不能感知到这种改变,从而读取到错误的结果。
Go1.9 及之后版本中新增了一种线程安全的 Map 类型——sync.Map,它是一种高效的并发安全哈希表,可以安全地被多个协程并发访问,而不需要额外的锁或同步机制。但需要注意的是,在使用 sync.Map 时,需要注意其操作的原子性和数据一致性问题。如果需要对整个 map 进行遍历、复制等操作,还需要通过加锁的方式进行保证。
8.RPC
RPC 远程过程调用协议:允许程序直接调用另外一台机器上的函数或者方法获取结果。
RPC 框架把这个过程封装起来了,使得客户端和服务端不用关心底层细节,像调用本地一样调用远程。
RPC 模型设计两个角色一个客户端一个服务端。 客户端向服务端发起调用请求,通过传递参数来指定需要调用的函数名,需要的参数。服务端收到请求的时候,更具客户端传递的信息,在自己的环境中执行对应的函数,并把结果返回给客户端。客户端解析得到返回值。
RPC 协议有:JSON-RPC XML-RPC SOAP RPC 协议可以使用 JSON-RPC、XML-RPC 和 SOAP 等多种不同的传输协议
JSON-RPC:使用 JSON 格式进行编码和解码,通常用于轻量级的数据交换场景。
XML-RPC:使用 XML 进行编码和解码,通常用于较为复杂的数据交换场景。
SOAP:基于 XML 实现,提供了更为完整的消息传递机制(如安全性、事务管理等),适用于大规模的企业级应用开发。
Golang 中,标准库中已经集成了 RPC 支持,提供了 net/rpc 包和 net/rpc/jsonrpc 包。其中,net/rpc 包使用 Go 语言自带的 gob 进行序列化和反序列化,而 net/rpc/jsonrpc 包则使用 JSON 来进行数据传输。
在 Go 语言中,net/rpc 包使用 gob(Go Binary)进行参数和返回值的序列化和反序列化。gob 是一个 Go 语言自带的二进制编码/解码库,它专门用于将 Go 中的结构体和基本数据类型序列化成二进制流,同时具有高效性和跨平台性能,因此非常适合用于网络传输。由于 gob 只能与 Go 语言交互,因此不支持和其他语言之间的交互操作。
HTPP在分布式和微服务下也可以实现节点之间的请求啊?为什么需要RPC呢?
抽象级别:
HTTP:基于资源的通信,通常采用 RESTful 设计。客户端知道要通过特定的 URL 和 HTTP 方法(如 GET、POST)进行交互。 RPC:基于功能或方法的通信。客户端像调用本地函数一样调用远程服务的函数或方法。
数据格式: HTTP (RESTful):通常使用 JSON 或 XML 作为数据交换格式。 RPC:可以使用各种数据格式,如 Protocol Buffers、Thrift、JSON-RPC 等。 性能:因为 RPC 可以使用如 Protocol Buffers 这样的紧凑的二进制格式,所以它通常比 JSON 或 XML 的 HTTP 通信更快、更高效。
类型安全:使用 Protocol Buffers 或 Thrift 这样的 RPC 框架,可以在编译时捕获类型相关的错误,而 HTTP/REST 通常在运行时处理这些错误。
服务发现和负载均衡:某些 RPC 框架(如 gRPC)内置了服务发现和客户端负载均衡的功能。
跨语言支持:RPC 框架如 gRPC 和 Thrift 支持多种编程语言,允许不同语言的服务间进行无缝通信。
流式传输:某些 RPC 框架(如 gRPC)支持双向流式通信,而标准的 HTTP/REST 通常不支持。
紧密耦合 vs 松散耦合:
HTTP:倾向于更加松散地耦合,使得服务间的交互更为灵活。 RPC:可能导致更紧密的耦合,但也可以实现更高效和严格定义的交互。
在一个动态变化的分布式环境中,服务可能会在不同的机器或容器上启动或关闭。因此,硬编码的服务地址或端口号是不可行的。这就需要一个动态的方式来找到运行的服务实例的当前地址。这就是服务发现的作用。
工作原理:
注册:当一个服务实例启动并准备好接受请求时,它会向服务发现系统(如 Consul、Etcd 或 ZooKeeper)注册自己,包括其 IP 地址、端口和其他可能的元数据。
发现:RPC 客户端在需要调用某个服务时,会查询服务发现系统以获取这个服务的可用实例列表。
健康检查:服务发现系统会定期地对所有注册的服务实例进行健康检查。如果某个实例没有响应,那么它将被标记为不健康,并从可用服务列表中移除。
RPC 的客户端负载均衡:
客户端负载均衡是直接在 RPC 客户端内部进行的请求分发。
工作原理:
服务列表:RPC 客户端首先从服务发现系统获取一个服务的所有可用实例列表。
选择策略:客户端会根据某种策略选择一个服务实例发送请求。常见的策略包括轮询、最少连接、加权轮询等。例如,轮询策略会依次将请求发送到服务列表中的每个实例。
健康检查:客户端可能还会执行其自己的健康检查,确保所选择的实例真的是可达和健康的。
动态更新:如果服务实例列表发生变化(例如,新实例加入或旧实例失败),客户端会动态更新其内部的服务列表,确保始终向健康的实例发送请求。
SOAP
SOAP(Simple Object Access Protocol)是一种基于 XML 和 HTTP(或 SMTP 等其他协议)的消息传递协议,主要用于分布式应用程序之间的通信。
<soap:Envelope xmlns:soap="http://www.w3.org/2003/05/soap-envelope/" xmlns:wsa="http://www.w3.org/2005/08/addressing">
<soap:Header>
<wsa:To>http://example.com/Some/Endpoint</wsa:To>
<wsa:From>
<wsa:Address>http://example.com/Some/OtherEndpoint</wsa:Address>
</wsa:From>
<wsa:MessageID>urn:uuid:12345678-1234-5678-1234-567812345678</wsa:MessageID>
</soap:Header>
<soap:Body>
<greeting>Hello, World!</greeting>
</soap:Body>
</soap:Envelope>
基于 XML 实现:SOAP 的消息体采用 XML 格式编写,便于跨平台和语言进行数据传输
完整的消息传递机制:SOAP 提供了完整的消息传递机制,包括消息头、消息体和消息尾等部分,可以支持各种复杂的消息交互模式,并提供了安全性、事务管理、可靠性等方面的支持。
与 Web Service 相关联:SOAP 是 Web Service 技术中最核心的一部分,通过 SOAP 协议,不同的 Web Service 可以进行互联互通,并实现各种业务功能。
支持多种协议:SOAP 不仅支持 HTTP 协议,还支持 SMTP、FTP 等多种协议,能够满足不同场景下的需要。
RPC-分布式系统中的服务调用场景
分布式系统中的服务调用:在分布式系统中,各个计算机之间可能需要进行函数调用或方法调用,以实现不同节点之间的数据共享和信息交互。RPC 协议可以让这些不同节点使用相同的远程调用方式,使得不同计算机之间提供的服务能够相互配合工作,完成更为复杂的业务需求。
作用: 实现不同节点之间的直接调用RPC 是底层的通信协议。
应用程序在多个计算机上部署,每个计算机的实例可以提供不同的服务-分布式系统
在此类系统中,不同的服务调用可能会发生在不同的计算机上,而且它们通过网络进行交互。
当我们进行 RPC 服务调用的时候,各个实例节点上的服务被我们以远程调用的方式执行并得到执行的结果。让分布式系统的不同计算机之间提供的服务可以协同工作。
跨计算机调用服务的场景。假设我们有一个电商网站,需要在不同的服务器上运行不同的模块,如用户管理、订单管理、库存管理等。这些模块需要通过远程服务进行通信,如下单时需要查询库存情况,这就需要用到跨计算机调用服务的场景,RPC 协议就足以实现这样的远程调用。
当我们使用 RPC 进行服务调用时,各个节点之间会以远程调用的方式来执行函数或方法,并将返回值传递回来。因此,它可以让分布式系统中的不同计算机之间使用相同的函数调用或方法调用方式,从而使得不同计算机之间提供的服务能够协同工作,完成更为复杂的业务需求
RPC-微服务场景
微服务场景下,系统通常是被拆分成多个小型的服务,小型的服务之间需要频繁的调用和通信。RPC 作为一种轻量级、高效、可扩展的通信协议,非常适合在微服务架构中使用。
底层实现
1 序列化和反序列化 因为通过网络传输数据,需要把传输的数据序列化和反序列化。常用的序列化框架有 Protobuf、Thrift 等。
2 服务注册和发现
具体的服务实例地址可能不断的发生变化,需要使用服务注册中心来管理个各个服务实例的状态
3 负载均衡
一个服务有多个实例的,需要使用负载均衡器确保 RPC 请求被均匀的分配到各个实例上。常用的负载均衡器有 Nginx、HAProxy 等
RPC-远程对象场景
远程对象场景通常是指:一个进程或计算机节点访问另外一个进程或计算机节点的对象。
这种情况下,RPC 是作为可靠的通信机制,帮助不同节点指尖进行对象交互和传输,帮助不同节点之间进行对象交互和数据传输。
具体来说,当一个对象需要被远程调用时,在调用方发送 RPC 请求后,RPC 框架会将请求传递给远程节点,由远程节点接受并执行请求。然后,远程节点会将执行结果返回给调用方。
好处: 通过 RPC 可以隐藏系统底层的网络通信细节,使得远程对象调用变得更加简单和透明。 通过 RPC 可以使不同节点之间的远程对象调用具有良好的性能和可靠性,因为 RPC 框架通常会自动处理网络延迟、请求重试、故障转移等问题。 通过 RPC 可以支持跨平台、跨语言的对象调用,因为 RPC 框架通常可以提供相应的协议和序列化方案。
9.RPC 在微服务和分布式场景下的区别
分布式系统中间 RPC 被视为是底层的通信协议。实现不同节点之间的直接调用。
在典型的分布式场景下,多个节点部署在不同的物理机器,这些节点需要通过网络进行通信。在这种情况下,RPC 负责把请求从一个节点传递到另外一个节点,并把响应结果返回给调用方。
微服务架构下,RPC 被视为是高级的通信协议。实现不同服务之间的调用和协作。
具体来说,当一个系统被拆分成多个小型的服务时,这些服务之间需要频繁地进行通信和调用。在这种情况下 RPC 负责把服务之间调用请求传递,返回结果给调用方。但是在微笑服务架构下 RPC 要和服务注册和发现
负载均衡技术
实现更高效的服务调用方式。
10. MYSQL 用 B+树做查询?
多叉树/从根到叶子节点只有一条路径/叶子节点大小是磁盘块大小的整数倍(可以把多个节点读入内存)/基于排序的数据结构,通过遍历算法实现快速定位某个区间的数据/
1.B+树是自平衡的多叉树。支持对数级别查找复杂度。B+树的每次查找操作都是用根节点到叶子节点的一条路径。而且 B+树中的节点大小被设置为磁盘块大小的整数倍。I/O 操作可以把多个节点度入内存。
从根到叶子节点只有一条路径: B+ 树的内部节点存储索引值,不存储数据记录。数据记录存储在叶子节点。在进行查找的时候,每个节点中都会包含一个索引值,用来指导下一步查找的方向。
从根节点开始,获取它的子节点列表以及它们对应的索引值列表。根据要查找的关键字,在子节点列表中选择一个最靠近该关键字的节点,然后跳转到该节点进行下一步查找。重复以上步骤,直到找到一个叶子节点为止。这个叶子节点中将包含需要查找的具体数据记录。
2.B+树是一种基于排序的数据结构,它的每个节点都按照某种顺序存储关键字,并且相邻节点之间也是有序的。这种有序性可以使得范围查询变得更加高效,因为它可以通过 B+树的遍历算法实现快速地定位某个区间的数据。
3.B+树的多叉结构+自平衡机制,使得它可以在高并发的场景下表现良好。叶子节点不存储数据记录,并发写入的时候不存在死锁。B+树的非叶子节点有多个子节点,降低节点分裂的频率和代价,减少写入的开销。
B+树的叶子节点只负责存储数据记录,而不保存任何索引信息。这一特点使得 B+树在高并发读写场景下表现良好。具体来说,当需要进行查找或更新某个数据记录时,可以利用 B+树结构从根节点开始快速定位到相应的叶子节点,然后直接读取或修改该节点中的数据记录。由于 B+树的节点通常被设置为磁盘块大小的整数倍,每次读取一个节点就可以将其全部载入内存,这样可以有效地减少磁盘 I/O 的次数,提高查询效率。
B+树的非叶子节点有多个子节点,能够降低节点分裂的频率和代价的原因如下:1.减少节点分裂的触发条件:B+树的节点分裂是在节点中元素数量达到阈值时触发的,而非叶子节点有多个子节点时,节点分裂需要的元素数量也相应增加了。这样可以减少节点分裂的触发条件,避免不必要的结构调整。2.如果非叶子节点的子节点数目较多,那么每个子节点包含的元素数量就会相对减少。在这种情况下,如果该节点需要进行分裂,那么它只需要将其中的一部分子节点和元素重新分配到一个新的节点中,而另一个子节点则保持不变。由于每个子节点包含的元素数量较少,所以节点分裂的代价也会相应减小。
自平衡机制是指当插入或删除节点时,B+树会自动调整结构以保持树的平衡,从而避免在高并发读写场景下出现性能问题。具体而言,当插入或删除节点后导致某个节点的子树高度不平衡时,B+树会通过节点的分裂或合并等操作来调整该节点及其祖先节点的结构,使得整棵树重新达到平衡状态。
节点分裂是指当某个节点中元素过多而需要拆分成两个节点时,B+树会将该节点中一半的元素移动到新创建的兄弟节点中,并将兄弟节点与原节点之间建立适当的连接关系,从而维持树的平衡。
节点合并是指当某个节点中元素过少而需要与其兄弟节点合并时,B+树会将该节点中的所有元素移动到其兄弟节点中,并且将这两个节点从父节点中删除,同时将它们的父节点也适当地向下移动,从而仍然保持树的平衡。
通过这些自平衡机制,B+树能够在高并发读写场景下保持较高的查询效率和数据一致性,从而被广泛地应用在数据库系统等领域。
4.B+树非叶节点上是不存在存储数据的,只存在存储键值,而 B 树节点中不只存在存储键值,也会存在存储数据。并且 B+树的所有数据记录按顺序存储在叶子节点。使得范围查找,排序查找,分组查找很简单。B+树各页指尖是双向表链接,叶子节点之间单向表链接
MyISAM 中的 B+树查询实现与 innodb 中的略有不同。在 MyISAM 中,B+树查询的叶节点并不存在存储数据,而是存储数据的文件地址。
聚集索引
如果使用聚集索引,在存储数据时会按照索引顺序对数据行进行排序,并且每个叶子节点上存储了整个数据行的信息。这样,当我们通过这个索引查询数据时,数据库可以快速定位到对应的数据行,并直接返回给我们需要的结果。
聚集索引(聚集索引):以 innodb 作为存储引力的表,表中的数据都会有一个主键,即使不创建主键,系统也会帮助创建 db 个隐式是隐式的是误数据存放在 B+树中的,而 B+树的键值就是主键,在 B+树的叶节点中,存贮了表中所有的数据。这种以主键作 B+树引的键值而构造的 B+树,索式我们称之为聚集索引。
非聚集索引
以主键以外的列表值作为按键值构建的 B+树搜索引,我们称之为非聚集搜索引。于非聚集索引的叶子节点不存表中的数据,而且是存储该列表对应的主键,想找数据我们还需要根据主键再去聚集搜索中进行查找,这个再根据表格整理集合过程,我们称之为返回表。
在 B+树中如何进行数据的查询?
https://github.com/lifei6671/interview-go/blob/master/mysql/mysql-index-b-plus.md
一般根据节点都是常驻内存的,也就是说页 1 已经内存了,此时不需要到磁盘中读取数据,直接从内存中读取即可。从内存中读到页 1,要查找这个 id>=18 and id <40 或者其范围值,我们首先需要找到 id=18 的键值。从页 1 中我们可以找到键值 18,此时我们需要根据指针到 p2。
要从页 3 中查找数据,我们就需要拿着 p2 指针去磁盘中进行读取页 3。 从磁盘中读取页 3 后将页 3 放入内存中,然后进行查找,我们可以找到键值 18,然后再拿到页 3 中的指针 p1,定位到页 8。
同样的页 8 页不在内存中,我们需要再去磁盘中将页 8 读取到内存中。 将页 8 读取到内存中后。因为页中的数据是链表进行连接的,而且键值是按照顺序存放的,此时可以根据二分查找法定位到键值 18。 此时因为已经到数据页了,此时我们已经找到一条满足条件的数据了,就是键值 18 对应的数据。 因为是范围查找,而且此时所有的数据又都存在叶子节点,并且是有序排列的,那么我们就可以对页 8 中的键值依次进行遍历查找并匹配满足条件的数据。 我们可以一直找到键值为 22 的数据,然后页 8 中就没有数据了,此时我们需要拿着页 8 中的 p 指针去读取页 9 中的数据。
因为页 9 不在内存中,就又会加载页 9 到内存中,并通过和页 8 中一样的方式进行数据的查找,直到将页 12 加载到内存中,发现 41 大于 40,此时不满足条件。那么查找到此终止。 最终我们找到满足条件的所有数据为:(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt) 总共 12 条记录。
GMP
https://github.com/lifei6671/interview-go/blob/master/base/go-gpm.md
并发模型有七种: 线路与锁 函数式编程 Clojure 之道 演员 通讯顺序进程(CSP) 数据等级并行 Lambda 架构
Goroutine:就是我们经常使用的用 go 键创建的执行体,它对应一个结构体 g,结构体里保存了 goroutine 的堆信息。
type g struct {
stack struct {
lo uintptr
hi uintptr
} // 栈内存:[stack.lo, stack.hi)
stackguard0 uintptr
stackguard1 uintptr
_panic *_panic
_defer *_defer
m *m // 当前的 m
sched gobuf
stktopsp uintptr // 期望 sp 位于栈顶,用于回溯检查
param unsafe.Pointer // wakeup 唤醒时候传递的参数
atomicstatus uint32
goid int64
preempt bool // 抢占信号,stackguard0 = stackpreempt 的副本
timer *timer // 为 time.Sleep 缓存的计时器
...
}
Machine:操作系统的线程。M 等于 CPU 个数的原因是:每个 m 分配到一个 CPU 上,就不会出现线程的上下问的切换。其中有两个比较重要的东西:一个保存当前正在 Machine 上执行的 g ,另外一个深度参与运行时的调度过程,比如 g 的创建,内存分配等等。
type m struct {
g0 *g
curg *g
...
}
Processor:性能追踪、垃圾回收、计时器等相关的字段外,还存储了处理器的待运行队列,队列中存储的是待执行的 Goroutine 列表。负责把 Goroutine 绑定到 M 上执行。
type p struct {
m muintptr
runqhead uint32
runqtail uint32
runq [256]guintptr
runnext guintptr
...
}
过程:
1.默认启动四个线程四个处理器,然后互相绑定 2.一个 G 结构体被创建,在进行函数体地址、参数起始地址、参数长度等信息以及调度相关属性更新之后,它就要进到一个 P 的队列。 3.又创建了一个 G?那就轮流往其他 P 里面放呗 4.假如有很多 G,都塞满了怎么办呢?那就不把 G 塞到处理器的私有队列里了,而是把它塞到全局队列里(候车大厅)。5.M 这边还要疯狂往外取,首先去 P 的私有队列里取 G 执行,如果取完的话就去全局队列取,如果全局队列里也没有的话,就去其他 P 里偷。6.如果哪里都没找到要执行的 G 呢,那 M 就会因为太失望和 P 断开关系,然后去睡觉(idle)7.如果两个 Goroutine 正在通过 channel 阻塞住了怎么办,难道 M 要等他们完事了再继续执行?显然不会,M 会转身去找别的 G 执行。8. 当 G 跟进系统调用 syscall,那么 M 也会跟进系统调用。那么这个时候 P 会寻找其他比较闲的 M 执行其他的 G 。当 G 执行完系统调用,再寻找一个空闲的处理器发车。如果没有处理器就会把 G 放入到全局队列中间等待分配。
数据库的并发模型
乐观锁的机制是:先获取资源的版本信息,在更新的时候比较版本是否一致,如果被修改,那么就回滚或者重试。如果没有被修改,那么就提交。并发量比较高的情况下,乐观锁会导致很多次的无效的版本比对(然后冲突重试)增加了系统开销,降低了吞吐率和响应速度。
1- 乐观锁模型:与悲观锁不同,乐观锁认为多数情况下数据访问不会出现冲突,因此不需要提前上锁,而是在提交修改时检查数据是否被其他用户修改过。如果没有修改,则提交成功;否则需要回滚并重新尝试。
写操作频繁的情况下,悲观锁更适合保证数据的一致性。悲观锁机制下,事务对某个资源进行修改的时候,会先获取到该资源的独占锁。阻塞其他事务对该资源的任何读或者写操作。确保当前事务修改完后对该资源进行读或者写操作的时候可以获取到最新的数据,从而保证数据的一致性。
2- 悲观锁模型:即认为多个用户同时访问同一数据时可能会出现冲突,因此在访问前就对数据进行上锁,只允许一个用户进行访问和修改。悲观锁的实现方式包括排他锁和共享锁。排他锁是指一个事务在对某个数据进行操作时,其他事务无法同时访问该数据;共享锁则是多个事务可以同时读取同一份数据,但不能同时修改。
在读多写少的情况下,可以减少锁的使用并发效能。
3-MVCC(多版本并发控制)模型:MVCC 是一种既支持高并发,又能保证一致性的并发模型,其核心思想是在每次写操作时都创建一个新的版本,读操作可以访问历史版本或当前版本。这样,在并发读写时就不需要加锁,从而提高了数据库的并发性能。
MySQL 默认的并发模型和优化策略
MySQL 默认的并发模型是悲观并发控制(Pessimistic Concurrency Control,PCC)。在 PCC 模型下,MySQL 使用了诸如共享锁和排他锁等机制来保证数据并发读写时的正确性和一致性。其优化策略主要包括:
1- 尽量使用索引:使用合适的索引可以提高查询效率,减少全表扫描的开销。
2- 优化查询语句:避免使用子查询、不必要的联表查询会影响查询性能的语句。同时,尽可能减少查询结果集大小,只查询需要的列。
3- 合理设置缓存:通过调整配置项,合理设置缓存大小,提高缓存命中率
4- 水平拆分:水平拆分是指将同一表的数据拆分到多个数据库或多张表中
假设有一个订单表,其中包含了所有用户的订单信息。如果这个表的数据量很大,那么可能会导致查询变慢,甚至出现性能瓶颈。为了解决这个问题,可以考虑对该订单表进行水平拆分。
一种可能的做法是按照订单的创建时间,将所有订单记录按照月份拆分到不同的数据库节点(或者不同的数据表中),比如将 2019 年 1 月份的订单记录放在一个数据库节点中,将 2019 年 2 月份的订单记录放在另一个数据库节点中,以此类推。这样一来,每个数据库节点只需要处理一部分订单记录,查询和更新的效率就会得到提高。
具体实现时,可以使用一些分库分表的工具或框架来完成数据的划分和迁移。比如 MYSQL 中可以使用 MyCAT,ShardingSphere-JDBC 等框架老实现分库分表。这些底层框架在底层都是利用 MYSQL 的分区特性,把数据按照一定的规则进行划分和路由。
ShardingSphere-JDBC 是一个分布式数据库中间件
在实现数据水平拆分时,ShardingSphere-JDBC 主要通过以下几个步骤来利用 MySQL 的分区表特性,将数据按照一定规则进行划分和路由:1.定义分片键(Sharding Key)。比如订单创建时间。即用于区分不同数据节点的字段或字段组合。例如,可以根据订单创建时间、用户 ID 等字段来定义分片键。2.定义分片算法(Sharding Algorithm):根据分片键的取值,通过分片算法计算出具体的数据节点或数据表 ShardingSphere-JDBC 支持多种分片算法,如基于取模或哈希等方式的分片算法。3. 建立分片键+分片算法+数据节点+数据表的映射关系进行绑定。4.建立分片表(Sharding Table):根据分片规则,在物理数据库中创建对应的分片表。例如,如果按月份拆分订单表,则需要在每个物理数据库上都创建 12 个分片表。5. 当请求到达 ShardingSphere-JDBC 中间件的时候,根据 SQL 语句的分片条件,通过分片算法计算出具体的数据节点或者数据表,将查询请求路由到对应的数据库。例如,按照用户 ID 进行分片,如果有 10 个物理节点,每个节点将会创建 10 张分片表,分别对应其他 9 个节点上的用户数据。
5- 垂直拆分:单个数据库中的不同表或列拆分为不同的数据库。
垂直拆分:假设我们有一个名为“ecommerce”的数据库,其中包含三个表:“products”、“customers”和“orders”。如果我们希望将这些表垂直拆分为不同的数据库,则可以按如下方式进行:
创建一个名为“products”的新数据库,并将“products”表从原始“ecommerce”数据库中移动到“products”数据库中。
创建一个名为“customers”的新数据库,并将“customers”表从原始的“ecommerce”数据库中移动到“customers”数据库中。
创建一个名为“orders”的新数据库,并将“orders”表从原始的“ecommerce”数据库中移动到“orders”数据库中。
过程:1.评估表的结构和数据量:首先需要评估原始表的结构和数据量,确定哪些列需要被拆分出去,这些列是否频繁访问以及它们所占据的空间等。2.创建新表和更新应用逻辑:根据前面的评估结果,可以使用 CREATE TABLE 语句创建新表,并将需要拆分的列插入到新表中。在执行拆分操作之后,需要对应用程序的逻辑进行相应的修改,以确保正确地读取和写入新的表。3.索引维护和数据迁移:在完成新表的创建和插入操作之后,需要对新表进行索引维护,以确保查询性能的优化。此外,如果原始表中有大量数据需要迁移到新表中,还需要进行数据迁移操作。
MYSQL 数据迁移
1- 备份原始数据库:在开始迁移之前,需要先备份原始数据库,以防止数据丢失或损坏。
2- 创建新的 MySQL 数据库:在目标环境中创建一个新的 MySQL 数据库,确保它具有足够的空间和资源来存储和处理迁移后的数据。
3- 将数据导出到文件中:使用 mysqldump 命令将原始数据库中的数据导出到文件中。该命令可用于导出整个数据库或单个表,语法是mysqldump -u [username] -p [password] [database_name] > [filename.sql]
4- 将数据导入到新的 MySQL 数据库中:使用 mysql 命令将先前导出的文件中的数据导入到新的 MySQL 数据库中。该命令的语法是mysql -u [username] -p [password] [database_name] < [filename.sql]
5- 验证数据迁移:在数据迁移完成后,需要对新的 MySQL 数据库进行验证,确保其包含了正确的数据,并且应用程序能够访问和使用它。
其他并发模型
在计算机科学领域中,除了数据库并发控制外还有其他类型的并发模型。以下是一些常见的并发模型:
1- 线程池:将线程预先创建并保存在线程池中,以便随时可以调度执行不同的任务。
一个例子是一个 Web 服务器使用线程池来处理客户端请求。假设这个 Web 服务器需要同时处理很多的客户端请求,而每个客户端请求都需要分配一个线程来进行处理。采用线程池可以将一定数量的线程预先创建并保存在线程池中,以便随时可以调度执行不同的任务,而无需即时创建和销毁线程。当有客户端请求到达时,服务器可以从线程池中获取一个空闲的线程来处理该请求,而不是新建一个线程。当某个线程完成了当前任务后,它会返回到线程池中变为可用状态,等待下一个任务的分配。这样可以显著减少线程的创建和销毁次数,降低系统开销、提高运行效率,并且可以控制同时并发执行的线程数量避免过多开启线程耗尽系统资源导致请求阻塞甚至崩溃。
2-Actor 模型:基于消息通信的并发模型,每个 Actor 都可以接收和发送消息,并且可以独立地运行,从而避免数据共享导致的冲突。
在线游戏中使用 Actor 模型进行并发处理。假设在游戏中有很多玩家同时在线,而每个玩家都需要独立地控制自己的角色和进行游戏交互。采用 Actor 模型可以将每个玩家的角色看作独立的 Actor,它们之间相互独立、互不干扰。这样,每个 Actor 可以接收其他 Actor 发送的消息(例如位置信息、输入指令等),并根据接收到的消息更新自己的状态和执行相应的操作。由于每个 Actor 都是独立的运行实体,并且彼此之间不共享数据,因此可以避免数据共享导致的冲突,确保游戏的并发性和稳定性。
3- 协程:也称为轻量级线程,可以看作是对线程的扩展,它们之间切换的成本更低,因为它们可以共享堆栈和上下文信息。
一个典型的例子是 Web 服务器使用协程来处理客户端请求,每个客户端请求要分配一个线程来处理。采用协程可以把线程拆分成多个协程。实现一个线程内并发执行多个请求,减少了线程的创建和上下文切换的开销。当协程遇到 I/O,会主动的让出 CPU,当协程完成了自己的任务又会进入到协程队列等待执行。
当有客户端请求到达时,服务器可以将该请求包装成一个协程任务,并将该任务提交给一个协程调度器。协程调度器会根据协程任务的优先级和状态选择一个处于空闲状态的协程来执行该任务。当某个协程遇到 I/O 或者等待其他操作时,它会主动让出 CPU 并将自己保存到协程队列中,等待下一次调度执行。当某个协程完成了当前任务后,它会返回到协程队列中变为可用状态,等待下一个任务的分配。
协程之间可以共享线程堆栈和上下文信息。 减少了上下文切换的开销。
4- Futures 与 Promises:一种通过将异步结果封装到对象中来管理并发操作的模型,可以帮助开发人员编写更容易理解的并发代码。
举个例子,假设我们需要向服务器发起一个网络请求并等待响应,但由于网络延迟,我们不能立即获得响应结果。
在这种情况下,我们可以创建一个 Promise 对象来表示未来接收到的结果,并返回一个 Future 对象作为异步任务的句柄,供调用方使用。当异步操作完成时,Promise 对象会将结果存储在内部,并通知与之相关联的 Future 对象,使得调用方可以获取结果。
5-数据流:基于数据流的并发模型,将数据管道化,实现并行处理,以提高大规模数据处理的效率。
读取大规模日志文件时,使用数据流的方式进行并行处理。假设有一个包含数百万条记录的日志文件需要进行分析和处理,单个线程很难胜任这个任务。采用并发模型可以将数据划分为多个数据流,每个数据流由不同的处理线程负责处理。例如,一个线程负责过滤掉无效的记录,另一个线程负责解析有效的记录,而其他线程则负责对数据进行汇总和归档。这种方式可以显著提高数据处理的效率和速度,同时减少处理过程中可能出现的错误。
6- 事件驱动架构(EDA):利用事件通知的方式来实现异步处理,将任务拆分为多个事件组件,以便可以适应高负载的场景
假设我们正在为一个电子商务网站编写系统,该系统需要在每个订单被创建时发送一封确认电子邮件给客户,以及通知仓库准备出货。这里我们可以将整个处理过程分解为多个事件:OrderCreated:当一个新订单被创建时触发。CustomerNotified:当确认电子邮件已成功发送给客户时触发。WarehouseNotified:当仓库准备好出货时触发。为了实现这样的事件驱动架构,我们可以使用 Apache Kafka 来扮演消息代理的角色。先定义三个 Topic:orders、emails 和 warehouse。然后将每个事件组件的输入与输出连接到对应的 Topic 上:
OrderCreated 组件从 orders Topic 中读取订单信息,并向 emails Topic 发送确认电子邮件.CustomerNotified 组件从 emails Topic 中读取确认邮件信息,并向 orders Topic 发送回执.WarehouseNotified 组件从 orders Topic 中读取订单信息,并向 warehouse Topic 发送货物出库指令。
过程:实现这个功能需要在代码中创建 Consumer 和 Producer 。OrderCreated 组件需要做的事情是消费 orders Topic 中的订单信息,然后在电子邮件模板中填入订单详细信息,并将填好信息的邮件发送到 emails Topic 中。
1- 创建一个名为 orders 的 Topic,用于存储订单信息
2- 在 OrderCreated 组件中创建一个 Kafka Consumer,订阅 orders Topic。
consumer = new KafkaConsumer<>(properties);
consumer.subscribe(Collections.singleton("orders"));
3- 从 orders Topic 中读取订单信息。
ConsumerRecords<String, Order> records = consumer.poll(Duration.ofMillis(100));
for (ConsumerRecord<String, Order> record : records) {
Order order = record.value();
// 在订单信息中提取必要的信息,比如订单号、客户姓名、商品信息等
// 将这些信息填入电子邮件模板
}
4- 在邮件正文中填入订单详细信息,利用 JavaMail API 发送确认电子邮件。
String messageBody = "亲爱的" + customerName + ",您的订单#" + orderId + "已经确认,您购买了以下商品:" + itemNames;
Message message = new MimeMessage(session);
message.setFrom(new InternetAddress(from));
message.setRecipients(Message.RecipientType.TO, InternetAddress.parse(to));
message.setSubject("您的订单已确认");
message.setText(messageBody);
Transport.send(message);
5 - 创建一个 Kafka Producer,将填好信息的邮件发送到 emails Topic 中。
// 创建Producer
Producer<String, String> producer = new KafkaProducer<>(properties);
// 创建ProducerRecord,指定目标Topic、键和值
ProducerRecord<String, String> record = new ProducerRecord<>("emails", customerId, messageBody);
// 发送消息
producer.send(record);
总之,OrderCreated 组件通过消费 orders Topic 中的订单信息,并在电子邮件模板中填入必要的信息,然后将填好信息的邮件发送到 emails Topic 中,从而实现了向客户发送确认电子邮件的功能。