进程是我们开发同学非常熟悉的概念，我们可能也听说过进程上下文切换开销。那么今天让我们来思考一个问题，究竟一次进程上下文切换会吃掉多少CPU时间呢？线程据说比进程轻量，它的上下文切换会比进程切换节约很多CPU时间吗？带着这些疑问，让我们进入正题。 1 进程以及进程切换 进程是操作系统的伟大发明之一，对应用程序屏蔽了CPU调度、内存管理等硬件细节，而抽象出一个进程的概念，让应用程序专心于实现自己的业务逻辑既可，而且在有限的CPU上可以“同时”进行许多个任务。但是它为用户带来方便的同时，也引入了一些额外的开销。如下图，在进程运行中间的时间里，虽然CPU也在忙于干活，但是却没有完成任何的用户工作，这就是进程机制带来的额外开销。 在进程A切换到进程B的过程中，先保存A进程的上下文，以便于等A恢复运行的时候，能够知道A进程的下一条指令是啥。然后将要运行的B进程的上下文恢复到寄存器中。这个过程被称为上下文切换。上下文切换开销在进程不多、切换不频繁的应用场景下问题不大。但是现在Linux操作系统被用到了高并发的网络程序后端服务器。在单机支持成千上万个用户请求的时候，这个开销就得拿出来说道说道了。因为用户进程在请求Redis、Mysql数据等网络IO阻塞掉的时候，或者在进程时间片到了，都会引发上下文切换。 2 一次简单的进程切换开销测试 废话不多说，我们先用个实验测试一下，到底一次上下文切换需要多长的CPU时间！实验方法是创建两个进程并在它们之间传送一个令牌。其中一个进程在读取令牌时就会引起阻塞。另一个进程发送令牌后等待其返回时也处于阻塞状态。如此往返传送一定的次数，然后统计他们的平均单次切换时间开销。编译、运行 # gcc main.c -o main # ./main./main Before Context Switch Time1565352257 s, 774767 us After Context SWitch Time1565352257 s, 842852 us 每次执行的时间会有差异，多次运行后平均每次上下文切换耗时3.5us左右。当然了这个数字因机器而异，而且建议在实机上测试。 前文我们测试系统调用的时候，最低值是200ns。可见，上下文切换开销要比系统调用的开销要大。系统调用只是在进程内将用户态切换到内核态，然后再切回来，而上下文切换可是直接从进程A切换到了进程B。显然这个上下文切换需要完成的工作量更大。 3 进程切换开销分析 那么上下文切换的时候，CPU的开销都具体有哪些呢？开销分成两种，一种是直接开销、一种是间接开销。 直接开销就是在切换时，cpu必须做的事情，包括： 1、切换页表全局目录 2、切换内核态堆栈 3、切换硬件上下文（进程恢复前，必须装入寄存器的数据统称为硬件上下文） ip(instruction pointer)：指向当前执行指令的下一条指令 bp(base pointer): 用于存放执行中的函数对应的栈帧的栈底地址 sp(stack poinger): 用于存放执行中的函数对应的栈帧的栈顶地址 cr3:页目录基址寄存器，保存页目录表的物理地址 …… 4、刷新TLB 5、系统调度器的代码执行 间接开销主要指的是虽然切换到一个新进程后，由于各种缓存并不热，速度运行会慢一些。如果进程始终都在一个CPU上调度还好一些，如果跨CPU的话，之前热起来的TLB、L1、L2、L3因为运行的进程已经变了，所以以局部性原理cache起来的代码、数据也都没有用了，导致新进程穿透到内存的IO会变多。其实我们上面的实验并没有很好地测量到这种情况，所以实际的上下文切换开销可能比3.5us要大。 想了解更详细操作过程的同学请参考《深入理解Linux内核》中的第三章和第九章。 4 一个更为专业的测试工具-lmbench… Continue reading 进程/线程切换究竟需要多少开销？
Author: admin
图解Linux网络包接收过程
因为要对百万、千万、甚至是过亿的用户提供各种网络服务，所以在一线互联网企业里面试和晋升后端开发同学的其中一个重点要求就是要能支撑高并发，要理解性能开销，会进行性能优化。而很多时候，如果你对Linux底层的理解不深的话，遇到很多线上性能瓶颈你会觉得狗拿刺猬，无从下手。 我们今天用图解的方式，来深度理解一下在Linux下网络包的接收过程。还是按照惯例来借用一段最简单的代码开始思考。为了简单起见，我们用udp来举例，如下： int main(){ int serverSocketFd = socket(AF_INET, SOCK_DGRAM, 0); bind(serverSocketFd, …); char buff[BUFFSIZE]; int readCount = recvfrom(serverSocketFd, buff, BUFFSIZE, 0, …); buff[readCount] = ‘\0’; printf(“Receive from client:%s\n”, buff); } 上面代码是一段udp server接收收据的逻辑。当在开发视角看的时候，只要客户端有对应的数据发送过来，服务器端执行recv_from后就能收到它，并把它打印出来。我们现在想知道的是，当网络包达到网卡，直到我们的recvfrom收到数据，这中间，究竟都发生过什么？ 通过本文，你将深入理解Linux网络系统内部是如何实现的，以及各个部分之间如何交互。相信这对你的工作将会有非常大的帮助。本文基于Linux 3.10，源代码参见https://mirrors.edge.kernel.org/pub/linux/kernel/v3.x/，网卡驱动采用Intel的igb网卡举例。 友情提示，本文略长，可以先Mark后看！ 一 Linux网络收包总览 在TCP/IP网络分层模型里，整个协议栈被分成了物理层、链路层、网络层，传输层和应用层。物理层对应的是网卡和网线，应用层对应的是我们常见的Nginx，FTP等等各种应用。Linux实现的是链路层、网络层和传输层这三层。 在Linux内核实现中，链路层协议靠网卡驱动来实现，内核协议栈来实现网络层和传输层。内核对更上层的应用层提供socket接口来供用户进程访问。我们用Linux的视角来看到的TCP/IP网络分层模型应该是下面这个样子的。 图1 Linux视角的网络协议栈 在Linux的源代码中，网络设备驱动对应的逻辑位于driver/net/ethernet, 其中intel系列网卡的驱动在driver/net/ethernet/intel目录下。协议栈模块代码位于kernel和net目录。 内核和网络设备驱动是通过中断的方式来处理的。当设备上有数据到达的时候，会给CPU的相关引脚上触发一个电压变化，以通知CPU来处理数据。对于网络模块来说，由于处理过程比较复杂和耗时，如果在中断函数中完成所有的处理，将会导致中断处理函数（优先级过高）将过度占据CPU，将导致CPU无法响应其它设备，例如鼠标和键盘的消息。因此Linux中断处理函数是分上半部和下半部的。上半部是只进行最简单的工作，快速处理然后释放CPU，接着CPU就可以允许其它中断进来。剩下将绝大部分的工作都放到下半部中，可以慢慢从容处理。2.4以后的内核版本采用的下半部实现方式是软中断，由ksoftirqd内核线程全权处理。和硬中断不同的是，硬中断是通过给CPU物理引脚施加电压变化，而软中断是通过给内存中的一个变量的二进制值以通知软中断处理程序。 好了，大概了解了网卡驱动、硬中断、软中断和ksoftirqd线程之后，我们在这几个概念的基础上给出一个内核收包的路径示意: 图2 Linux内核网络收包总览 当网卡上收到数据以后，Linux中第一个工作的模块是网络驱动。网络驱动会以DMA的方式把网卡上收到的帧写到内存里。再向CPU发起一个中断，以通知CPU有数据到达。第二，当CPU收到中断请求后，会去调用网络驱动注册的中断处理函数。网卡的中断处理函数并不做过多工作，发出软中断请求，然后尽快释放CPU。ksoftirqd检测到有软中断请求到达，调用poll开始轮询收包，收到后交由各级协议栈处理。对于UDP包来说，会被放到用户socket的接收队列中。 我们从上面这张图中已经从整体上把握到了Linux对数据包的处理过程。但是要想了解更多网络模块工作的细节，我们还得往下看。… Continue reading 图解Linux网络包接收过程
TCP快速打开 fast_open
TCP快速打开（英语：TCP Fast Open，简称TFO）是对计算机网络中传输控制协议（TCP）连接的一种简化握手手续的拓展，用于提高两端点间连接的打开速度。 它通过握手开始时的SYN包中的TFO cookie（一个TCP选项）来验证一个之前连接过的客户端。如果验证成功，它可以在三次握手最终的ACK包收到之前就开始发送数据，这样便跳过了一个绕路的行为，更在传输开始时就降低了延迟。这个加密的Cookie被存储在客户端，在一开始的连接时被设定好。然后每当客户端连接时，这个Cookie被重复返回。 此Cookie通常采用一种分组密码，私钥由服务器根据客户端的IP地址保存，生成一个第三方难以仿冒的消息认证码标签，即便第三方可以伪造源IP地址或从其他IP地址制造到同一个服务器的连接。尽管使用了加密技术来生成cookie，但TFO并不着眼于提供比它所替换的三次握手有更多的安全性，并且不对所产生的TCP连接提供任何形式的加密保护或端点身份认证。它的目的不是为了抵挡中间人攻击。 这个协议最早提出于2011年 并在2012年2月时已为一个IETF互联网草案， 这项规范最终在2014年12月作为RFC 7413发布。 过程 请求Fast Open Cookie 客户端发送SYN数据包，该数据包包含Fast Open选项，且该选项的Cookie为空，这表明客户端请求Fast Open Cookie； 支持TCP Fast Open的服务器生成Cookie，并将其置于SYN-ACK数据包中的Fast Open选项以发回客户端； 客户端收到SYN-ACK后，缓存Fast Open选项中的Cookie。 第一次连接抓包数据 captures 实施TCP Fast Open 以下描述假定客户端在此前的TCP连接中已完成请求Fast Open Cookie的过程并存有有效的Fast Open Cookie。 客户端发送SYN数据包，该数据包包含数据（对于非TFO的普通TCP握手过程，SYN数据包中不包含数据）以及此前记录的Cookie，也可以带上请求数据； 支持TCP Fast Open的服务器会对收到Cookie进行校验：如果Cookie有效，服务器将在SYN-ACK数据包中对SYN和数据进行确认（Acknowledgement），服务器随后将数据递送至相应的应用程序；否则，服务器将丢弃SYN数据包中包含的数据，且其随后发出的SYN-ACK数据包将仅确认（Acknowledgement）SYN的对应序列号； 如果服务器接受了SYN数据包中的数据，服务器可在握手完成之前发送数据； 客户端将发送ACK确认服务器发回的SYN以及数据，但如果客户端在初始的SYN数据包中发送的数据未被确认，则客户端将重新发送数据； 此后的TCP连接和非TFO的正常情况一致。 注：客户端在请求并存储了Fast Open Cookie之后，可以不断重复TCP Fast Open直至服务器认为Cookie无效（通常为过期）。 获取fast_open的cookies的快速打开包 captures 实现 TFO的实现包括： TFO的IPv4支持在3.6（客户端）和3.7（服务端）版本中被合并进Linux内核主线。IPv6服务器的TFO支持被合并进入3.16版本。 FreeBSD自10.3版本（支持服务端）和12.0版本（支持客户端）开始支持TFO。 Mozilla Firefox 56支持TFO。… Continue reading TCP快速打开 fast_open
图解Raft：最简单易懂的分布式一致性算法
关注与点赞是我最大的动力！ 分布式一致性 想象一下，我们有一个单节点系统，且作为数据库服务器，然后存储了一个值（假设为X）。然后，有一个客户端往服务器发送了一个值（假设为8）。只要服务器接受到这个值即可，这个值在单节点上的一致性非常容易保证： 单击环境 但是，如果数据库服务器有多个节点呢？比如，如下图所示，有三个节点：a，b，c。这时候客户端对这个由3个节点组成的数据库集群进行操作时的值一致性如何保证，这就是分布式一致性问题。而Raft就是一种实现了分布式一致性的协议（还有其他一些一致性算法，例如：ZAB、PAXOS等）： 分布式环境 一些概念 讲解Raft算法之前，先普及一些Raft协议涉及到的概念： term：任期，比如新的选举任期，即整个集群初始化时，或者新的Leader选举就会开始一个新的选举任期。 大多数：假设一个集群由N个节点组成，那么大多数就是至少N/2+1。例如：3个节点的集群，大多数就是至少2；5个节点的集群，大多数就是至少3。 状态：每个节点有三种状态，且某一时刻只能是三种状态中的一种：Follower（图左），Candidate（图中），Leader（图右）。假设三种状态不同图案如下所示： 节点状态图 初始化状态时，三个节点都是Follower状态，并且term为0，如下图所示： 初始化 Leader选举 Leader选举需要某个节点发起投票，在确定哪个节点向其他节点发起投票之前，每个节点会分配一个随机的选举超时时间（election timeout）。在这个时间内，节点必须等待，不能成为Candidate状态。现在假设节点a等待168ms , 节点b等待210ms , 节点c等待200ms 。由于a的等待时间最短，所以它会最先成为Candidate，并向另外两个节点发起投票请求，希望它们能选举自己为Leader： 发起投票请求 另外两个节点收到请求后，假设将它们的投票返回给Candidate状态节点a，节点a由于得到了大多数节点的投票，就会从Candidate变为Leader，如下图所示，这个过程就叫做Leader选举（Leader Election）。接下来，这个分布式系统所有的改变都要先经过节点a，即Leader节点： 如果某个时刻，Follower不再收到Leader的消息，它就会变成Candidate。然后请求其他节点给他投票（类似拉票一样）。其他节点就会回复它投票结果，如果它能得到大多数节点的投票，它就能成为新的Leader。 日志复制 假设接下来客户端发起一个SET 5的请求，这个请求会首先由leader即节点a接收到，并且节点a写入一条日志。由于这条日志还没被其他任何节点接收，所以它的状态是uncommitted。 为了提交这条日志，Leader会将这条日志通过心跳消息复制给其他的Follower节点： 日志复制 一旦有大多数节点成功写入这条日志，那么Leader节点的这条日志状态就会更新为committed状态，并且值更新为5： Leader节点然后通知其他Follower节点，其他节点也会将值更新为5。如下图所示，这个时候集群的状态是完全一致的，这个过程就叫做日志复制（Log Replication）： 两个超时 接下来介绍Raft中两个很重要的超时设置：选举超时和心跳超时。 选举超时 为了防止3个节点（假设集群由3个节点组成）同时发起投票，会给每个节点分配一个随机的选举超时时间（Election Timeout），即从Follower状态成为Candidate状态需要等待的时间。在这个时间内，节点必须等待，不能成为Candidate状态。如下图所示，节点C优先成为Candidate，而节点A和B还在等待中： 选举超时 心跳超时 如下图所示，节点A和C投票给了B，所以节点B是leader节点。节点B会固定间隔时间向两个Follower节点A和C发送心跳消息，这个固定间隔时间被称为heartbeat timeout。Follower节点收到每一条日志信息都需要向Leader节点响应这条日志复制的结果： 心跳超时 重新选举 选举过程中，如果Leader节点出现故障，就会触发重新选举。如下图所示，Leader节点B故障（灰色），这时候节点A和C就会等待一个随机时间（选举超时），谁等待的时候更短，谁就先成为Candidate，然后向其他节点发送投票请求： re-election 如果节点A能得得到节点C的投票，加上自己的投票，就有大多数选票。那么节点A将成为新的Leader节点，并且Term即任期的值加1更新到2： 新Leader节点… Continue reading 图解Raft：最简单易懂的分布式一致性算法
分布式一致性算法：Raft
分布式系统的一致性算法就是指一组机器协同工作，即便其中有某些机器宕机了，系统还能正常对外提供服务。以前通常都喜欢用Paxos来讲解一致性算法，但是Paxos本身很复杂，代码实现也很难，于是催生了Raft这个更加简单易懂的一致性算法，难得的是，它的效果跟Paxos差不多。 为了易于理解，Raft采用了算法分解(分为leader选举，日志复制以及安全性)和减少状态的方式。与以往一致性算法不同的是，Raft有一些特别的地方： 强Leader。Raft使用了一个强Leader特性，日志复制只能从Leader节点复制到其他节点。 Leader选举。Raft使用了一个随机超时来选举Leader，以确保选举不会失败。 成员变化。Raft使用了联合一致性方法来实现成员配置变化时保证服务不受影响。 1. Raft 节点状态 在分布式系统上，每台服务器相当于一个分布式网络节点，每个节点有三种状态：Follower，Candidate，Leader，状态之间是互相转换的，可以参考下图，具体的后面说。 每个节点上都有一个倒计时器 (Election Timeout)，时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout： 收到选举的请求 收到 Leader 的 Heartbeat (后面会讲到) 在 Raft 运行过程中，最主要进行两个活动： 选主 Leader Election 复制日志 Log Replication 2. 选主 Leader Election 2.1 正常情况下选主 假设现在有如图5个节点，5个节点一开始的状态都是 Follower。 在一个节点倒计时结束 (Timeout) 后，这个节点的状态变成 Candidate 开始选举，它给其他几个节点发送选举请求 (RequestVote) 其他四个节点都返回成功，这个节点的状态由 Candidate 变成了 Leader，并在每个一小段时间后，就给所有的 Follower 发送一个 Heartbeat 以保持所有节点的状态，Follower 收到… Continue reading 分布式一致性算法：Raft
分布式事务，这一篇就够了
[作者简介] 李文华，小米信息技术部海外商城组随着互联网技术的不断发展，系统越来越复杂，几乎所有 IT 公司的系统都已经完成从单体架构到分布式架构的转变，分布式系统几乎无处不在。谈到分布式系统，特别是微服务架构，我们不得不谈分布式事务。今天就跟大家一起聊聊分布式事务以及常用解决方案。 基础理论 在讲解具体方案之前，我们有必要了解一些分布式事务所涉及到的基础理论知识。 事务 事务是应用程序中一系列严密的操作，所有操作必须成功完成，否则在每个操作中所作的所有更改都会被撤消。也就是事务具有原子性，一个事务中的一系列的操作要么全部成功，要么一个都不做。事务应该具有 4 个属性：原子性、一致性、隔离性、持久性。这四个属性通常称为 ACID 特性。 分布式事务 分布式事务是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。例如在大型电商系统中，下单接口通常会扣减库存、减去优惠、生成订单 id, 而订单服务与库存、优惠、订单 id 都是不同的服务，下单接口的成功与否，不仅取决于本地的 db 操作，而且依赖第三方系统的结果，这时候分布式事务就保证这些操作要么全部成功，要么全部失败。本质上来说，分布式事务就是为了保证不同数据库的数据一致性。 强一致性、弱一致性、最终一致性 强一致性 任何一次读都能读到某个数据的最近一次写的数据。系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。简言之，在任意时刻，所有节点中的数据是一样的。 弱一致性 数据更新后，如果能容忍后续的访问只能访问到部分或者全部访问不到，则是弱一致性。 最终一致性 不保证在任意时刻任意节点上的同一份数据都是相同的，但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。简单说，就是在一段时间后，节点间的数据会最终达到一致状态。 CAP 原则 CAP 原则又称 CAP 定理，指的是在一个分布式系统中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼。 一致性（C）： 在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本） 可用性（A）： 在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性） 分区容错性（P）： 以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在 C 和 A 之间做出选择。 CAP 原则的精髓就是要么 AP，要么 CP，要么 AC，但是不存在 CAP。如果在某个分布式系统中数据无副本， 那么系统必然满足强一致性条件， 因为只有独一数据，不会出现数据不一致的情况，此时 C… Continue reading 分布式事务，这一篇就够了
分布式事务最经典的七种解决方案
随着业务的快速发展、业务复杂度越来越高，几乎每个公司的系统都会从单体走向分布式，特别是转向微服务架构。随之而来就必然遇到分布式事务这个难题，这篇文章总结了分布式事务最经典的解决方案，分享给大家。 基础理论 在讲解具体方案之前，我们先了解一下分布式事务所涉及到的基础理论知识。 我们拿转账作为例子，A需要转100元给B，那么需要给A的余额-100元，给B的余额+100元，整个转账要保证，A-100和B+100同时成功，或者同时失败。看看在各种场景下，是如何解决这个问题的。 事务 把多条语句作为一个整体进行操作的功能，被称为数据库事务。数据库事务可以确保该事务范围内的所有操作都可以全部成功或者全部失败。 事务具有 4 个属性：原子性、一致性、隔离性、持久性。这四个属性通常称为 ACID 特性。 Atomicity（原子性）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被恢复到事务开始前的状态，就像这个事务从来没有执行过一样。 Consistency（一致性）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。完整性包括外键约束、应用定义的等约束不会被破坏。 Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。 Durability（持久性）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。 分布式事务 银行跨行转账业务是一个典型分布式事务场景，假设A需要跨行转账给B，那么就涉及两个银行的数据，无法通过一个数据库的本地事务保证转账的ACID，只能够通过分布式事务来解决。 分布式事务就是指事务的发起者、资源及资源管理器和事务协调者分别位于分布式系统的不同节点之上。在上述转账的业务中，用户A-100操作和用户B+100操作不是位于同一个节点上。本质上来说，分布式事务就是为了保证在分布式场景下，数据操作的正确执行。 分布式事务在分布式环境下，为了满足可用性、性能与降级服务的需要，降低一致性与隔离性的要求，一方面遵循 BASE 理论（BASE相关理论，涉及内容非常多，感兴趣的同学，可以参考BASE理论）： 基本业务可用性（Basic Availability） 柔性状态（Soft state） 最终一致性（Eventual consistency） 同样的，分布式事务也部分遵循 ACID 规范： 原子性：严格遵循 一致性：事务完成后的一致性严格遵循；事务中的一致性可适当放宽 隔离性：并行事务间不可影响；事务中间结果可见性允许安全放宽 持久性：严格遵循 分布式事务的解决方案 两阶段提交/XA XA是由X/Open组织提出的分布式事务的规范，XA规范主要定义了(全局)事务管理器(TM)和(局部)资源管理器(RM)之间的接口。本地的数据库如mysql在XA中扮演的是RM角色 XA一共分为两阶段： 第一阶段（prepare）：即所有的参与者RM准备执行事务并锁住需要的资源。参与者ready时，向TM报告已准备就绪。 第二阶段 (commit/rollback)：当事务管理者(TM)确认所有参与者(RM)都ready后，向所有参与者发送commit命令。 目前主流的数据库基本都支持XA事务，包括mysql、oracle、sqlserver、postgre XA 事务由一个或多个资源管理器（RM）、一个事务管理器（TM）和一个应用程序（ApplicationProgram）组成。 把上面的转账作为例子，一个成功完成的XA事务时序图如下： 如果有任何一个参与者prepare失败，那么TM会通知所有完成prepare的参与者进行回滚。 XA事务的特点是： 简单易理解，开发较容易 对资源进行了长时间的锁定，并发度低 如果读者想要进一步研究XA，go语言可参考DTM，java语言可参考seata SAGA Saga是这一篇数据库论文saga提到的一个方案。其核心思想是将长事务拆分为多个本地短事务，由Saga事务协调器协调，如果正常结束那就正常完成，如果某个步骤失败，则根据相反顺序一次调用补偿操作。 把上面的转账作为例子，一个成功完成的SAGA事务时序图如下： SAGA事务的特点： 并发度高，不用像XA事务那样长期锁定资源… Continue reading 分布式事务最经典的七种解决方案
单机SQL Join的原理分析
Join在SQL是给两个或以上表建立连接的基本操作，本文以TenDB （开源MySQL分支) 为例，介绍Join算法的底层原理。 更多TenDB Cluster相关技术交流，欢迎加入 QQ群: 584695931 官方网址: https://tendbcluster.com TSpider: https://github.com/Tencent/TenDBCluster-TSpider TenDB: https://github.com/Tencent/TenDBCluster-TenDB Tdbctl: https://github.com/Tencent/TenDBCluster-Tdbctl 单机Join — 以TenDB为例 以下面的表结构和数据为例： CREATE TABLE t2 ( id INT PRIMARY KEY AUTO_INCREMENT, a INT, b INT, # b是一个普通列 KEY ka(a) # a上有个索引, id是主键 )ENGINE=INNODB; # 插入数据 (1,1,1)到(1k,1k,1k)共1000条 INSERT INTO t2 VALUES(1,1,1),(2,2,2),…,(1000,1000,1000); # t1与t2表结构相同,是t2的前100条数据 CREATE TABLE t1 LIKE t2;INSERT INTO t1 (SELECT * FROM t2 WHERE id<=100); Nested Loop Join 对于基于索引a的两表Join语句: SELECT * FROM… Continue reading 单机SQL Join的原理分析
分布式理论(六) – 一致性协议Raft
前言 Raft 也是一个 一致性算法，和 Paxos 目标相同。但它还有另一个名字 – 易于理解的一致性算法。Paxos 和 Raft 都是为了实现 一致性 产生的。这个过程如同选举一样，参选者 需要说服 大多数选民 (服务器) 投票给他，一旦选定后就跟随其操作。Paxos 和 Raft 的区别在于选举的 具体过程 不同。 正文 小试牛刀 在进入正题前，给大家分享一个《数学发散思维》中的一个故事，站在不同思维角度上，了解对一个问题理解的差异性。 问题: 甲乙两人轮流在一张圆桌上平放黑白围棋子，每次放一子，棋子不许重叠，谁先没有地方放就输。请问怎样放才能赢？ 这个问题有两层意思，第一，有没有一种放法保证必赢？第二，如果有怎么证明？ 上图回答了这个问题，那就是先行者必胜，这里使用了三种不同的思维方式来阐述: 假如桌子只有一个围棋子那么大。 假如桌子无限大，先行者先占住圆心。由于圆是对称图形，所以只要对手还能找到位置放，你总能在对称的另一面找到位置放。 一个圆中可画单数个直径相等且互切的小圆。 三种不同的思维方式在可理解性难度上逐渐加深。 第一种是 极简化思维，但数学上是 不严谨 的。 第二种是 极限思维，和第一种结合起来就是 数学归纳法，在数学上是 严谨 的。 第三种是 形象思维，使用了 几何学概念，但对于没有几何学基础知识的人就很难理解了。 什么是Raft协议 Raft 协议将 Server 进程分成三类，分别是 Leader，Candidate，Follower。一个 Server 进程在某一时刻，只能是其中… Continue reading 分布式理论(六) – 一致性协议Raft
分布式理论(五) – 一致性算法Paxos
前言 世界上只有一种一致性算法，就是 Paxos。出自一位 Google 大神之口。Paxos 也是出名的 晦涩难懂，推理过程极其复杂。 Paxos 有点类似之前说的 2PC，3PC，但是解决了这两种算法各种硬伤。该算法在很多大厂都得到了工程实践，比如阿里的 OceanBase 的 分布式数据库，底层就是使用的 Paxos 算法。再比如 Google 的 chubby 分布式锁 也是用的这个算法。可见该算法在分布式系统中的地位，甚至于，Paxos 就是 分布式一致性 的代名词。 正文 1. Paxos算法是什么 Paxos 算法是 基于消息传递 且具有 高效容错特性 的一致性算法，目前公认的解决 分布式一致性问题 最有效的算法之一. 2. Paxos算法产生背景 2.1. 拜占庭将军问题 拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于信使中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。 2.2. Paxos算法由来 故事背景是古希腊 Paxos 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。 2.3 产生背景 在常见的 分布式系统 中，总会发生 节点宕机 或 网络异常 (包括消息的 重复、丢失、延迟、乱序、网络分区) 等情况。… Continue reading 分布式理论(五) – 一致性算法Paxos