Yixin Luo
Yixin Luo
在mypaxos定义特殊提案，用于变更成员。当需要变更成员时，可触发propose。
编写测试用例，用于正确性验证
## Why I'm doing: ## What I'm doing: Add UT test for pk size tiered compaction policy, it can verify the rowset order in one level. ## What type of...
## Why I'm doing: A faster compaction apply strategy for local pk table. More detail : #43934 ## What I'm doing: The compaction processing in the new scheme consists of...
### 背景 在分布式系统中，由于每台机器产生的时间戳无法达成共识，导致每台机器从自身读取的时间戳变得毫无意义。在不想引入中心时间戳产生器的场景下，我们可以通过ntp服务，不断地校准每台机器的时间，但是这种方式得到的时间戳依然无法从理论上证明其正确性。在Google Spanner论文中，提出来了一个很有趣的关于时间的想法，就是假设每台机器产生的时间戳是有误差的，但是误差的增长速率是有上界的。在这个已知前提下，我们可以在分布式系统中达成关于时间戳误差范围的共识，这就是我们后面要讨论的true time。 根据spanner论文中关于true time描述部分提到的两篇论文，《Time synchronization in DCNET hosts》[1] 和《Maintaining the time in a distributed system》[2]，这里重新梳理了下truetime的实现，并证明truetime的正确性。 ### 算法 以下总结了《Maintaining the time in a distributed system》[2] 中提到的算法。 1. 假设:...
原子操作对于我们来说，是非常熟悉的概念。在某些场景下，可以用原子操作来替换重量级的锁同步，从而提高程序性能。原子操作可以保障多个线程或进程在更新某块共享内存区时，可以避免同步原语。 对于原子操作的实现来说，需要分开考虑单处理器单核系统，和多处理器系统，多核系统。 对于单处理器单核系统来说，只要保证操作指令序列不被打断即可实现原子操作。对于简单的原子操作，cpu实现上会提供单条指令，比如INC和XCHG。对于复杂的原子操作，需要包含多条指令。执行过程中，出现上下文切换行为，比如任务切换，中断处理等。这里的行为会影响原子操作的原子性。因此需要自旋锁spinlock[[1]](https://en.wikipedia.org/wiki/Spinlock)来保证操作指令序列不会在执行的中途受干扰。 但是如果对于多处理器或者多核的系统，原子操作的实现除了需要spinlock来保证外，还需要保证不会受到同处理器上其他核，或者其他处理器的影响。当其他核上执行的指令访问的内存空间，与当前原子操作需要访问的内存空间存在冲突时，就会破坏原子操作的正确性。 在x86架构中，提供了指令前缀LOCK。LOCK保证了指令不会受其他处理器或cpu核的影响。在PentiumPro之前，LOCK的实现，是通过锁住bus（总线），从而阻止其他cpu核的内存访问。可想而知，这种实现是非常低效的。从PentiumPro开始，LOCK只会阻塞其他cpu核对相关内存的缓存块的访问。 现在，大多数的x86处理器都支持了CAS[[2]](https://en.wikipedia.org/wiki/Compare-and-swap)的硬件实现，保证了多处理器多核系统下的原子操作的正确性。CAS的实现同样无需锁住总线，只会阻塞其他cpu核对相关内存的缓存块的访问。同样的，在MIPS和ARM架构下，还支持了LL/SC的实现[[3]](https://en.wikipedia.org/wiki/Load-link/store-conditional)。LL/SC不会出现CAS中的ABA问题。 在继续深入以前，需要了解MESI缓存协议[[4]](https://en.wikipedia.org/wiki/MESI_protocol)。当然，还存在其他的MESI变种，不过这里只会简单解释下MESI。每个cache line存在四种状态，Modified代表该cache line为该cpu核独有，且尚未写回（write back）到内存（对缓存一致性不了解的看这里[[5]](https://en.wikipedia.org/wiki/Cache_coherence)）。Exclusive代表该cache line为该cpu核独有，且与内存一致。Shared代表该cache line为多核共享，且与内存一致。Invalid代表缓存失效。系统中多个核之间通过快速通道直接通信，比如intel家的QPI，amd家的Hypertransport。cpu核之间通信的消息包括读消息，以及读消息的响应消息。使无效消息，以及使无效消息的响应消息。当运行在某个cpu核的线程准备读取某个cache line的内容时，如果状态处于M,E,S，直接读取即可。如果状态处于I，则需要向其他cpu核广播读消息，在接受到其他cpu核的读响应后，更新cache line，并将状态设置为S。而当线程准备写入某个cache line时，如果处于M状态，直接写入。如果处于E状态，写入并将cache line状态改为M。如果处于S，则需要向其他cpu核广播使无效消息，并进入E状态，写入修改，后进入M状态。如果处于I，则需要向其他cpu核广播读消息核使无效消息，在收集到读响应后，更新cache line。在收集到使无效响应后，进入E状态，写入修改，后进入M状态。 从上面的说明可知，LOCK的实现，只需要保持cache line的M状态即可，此时就可以阻止其他cpu核对该块内存的修改，而不用去锁住整个总线。 同理，CAS和LL/SC的实现，您应该可以猜出来了吧？ 在下一篇文章中，我打算讲讲内存屏障。。
常见的cpu架构中，都有对内存屏障指令[[1]](https://en.wikipedia.org/wiki/Memory_ordering)的支持，比如x86的mfence/sfence/lfence指令，mips的sync指令等，各种用法这里就不多写了。这篇文章，主要想漫谈下内存屏障[[2]](https://en.wikipedia.org/wiki/Memory_barrier)的实现和内存一致性模型[[3]](https://en.wikipedia.org/wiki/Consistency_model)相关的东西。 在上一篇文章[[4]](https://github.com/luohaha/MyBlog/issues/3)中，我写到了原子操作的实现。在文章中，我简单介绍了MESI这个cache一致性协议。MESI能够保障在cpu1上能够读取到在cpu2上已写入cache，但未换入内存的修改。看似此时的内存模型的一致性（后续会详细介绍一致性模型）保障已足够严格，但并如此。让我们来看看wiki上给出的自旋锁spinlock[[5]](https://en.wikipedia.org/wiki/Spinlock)的实现： ``` ; Intel syntax locked: ; The lock variable. 1 = locked, 0 = unlocked. dd 0 spin_lock: mov eax, 1 ; Set the EAX register to 1....
## 说明 我曾经在研究生期间负责开发过一个对可用性有要求的服务。为了保障该服务的可用性，我基于zookeeper设计了一个副本复制的解决方法，以确保当单个服务节点出现故障后，其他的备用服务节点能够被选为主用服务节点，并对外提供服务，以保障整个系统不受单点故障的影响。与此同时，还能保障系统的数据一致性。本文介绍的内容就是这种解决方案的总结和抽象。 ## 背景 在一个分布式系统中，多个有状态的服务节点协同工作，完成某项系统功能。对于服务节点来说，保障其无故障运行，或者当其出现故障时，能够快速恢复，是一件很有挑战的事情。同时，带有状态的服务节点在快速恢复时，还需要恢复到故障出现前的服务状态，更加地加大了系统设计的难度。 #### 1. CAP定理 由Eric Brewer在2000年提出的CAP定理[1]，提出了在一个服务中，无法同时满足数据一致性，服务可用性和分区容错性。分区容错性不仅仅包含网络分区，还应该包括宕机等异常情形。由于在分布式系统中，分区容错性是必须被满足的，因此分布式系统只能在数据一致性和服务可用性中做出选择。 可用性指的是在足够长的时间内，一个服务可用的时间。因此为了提高可用性，需要提高系统的可靠性，也就是系统连续无故障运行的时间，和需要减少系统在出现故障后的恢复时间。系统的可靠性与系统本身的实现与部署有关，不在本文讨论的范围。本文的设计，主要关注的是系统故障后的恢复时间。 对于数据一致性，保障的是后续操作对于先前操作的可见性。如果后续的读取，无法读到先前写入的数据，会使得基于此系统的开发变得困难。 #### 2. 多副本容灾 为了能够达成故障恢复的目标，传统的做法是基于主用服务器与备用服务器之间做同步或者异步数据复制，也就是primary-secondary协议[2]。当主用服务故障后，可以快速切换到备用服务。如果使用同步的数据复制，可以保障数据一致性，但是没办法保障系统可用性。因为无论主用服务还是备用服务出现了故障，都会导致服务不可用。因为必须将宕机服务重新启动后才能恢复服务，从而导致系统故障恢复时间变长。如果使用异步的数据复制，如果主用服务节点出现故障，可以很快切换到备用正常工作，从而缩短了故障恢复时间，因而提高了系统的可用性。但是有可能会出现数据不一致的情况，例如，用户在之前写入的数据，在后续的读取中无法被读到。 基于paxos[3]协议和raft[4]协议的系统是多副本容灾中最常用的解决方案。因为paxos协议或者raft协议能够保障数据一致性，并同时最大限度地保障系统可用性，只有当副本节点出现一半或以上的宕机情况时，才会影响可用性。否则，系统都能够在短时间内恢复回来，并拥有一致性的数据副本。但是由于在系统中嵌入地正确实现无论是paxos协议，还是简化的raft协议，都是相当有挑战的事情。为了简化上述系统的实现，我们可以借助像zookeeper[5]等高可用的分布式协调服务，来帮助我们完成选主，和节点状态监听等工作。从而在此基础上，完成日志复制等工作，进而大大地简化这个系统的实现。因此在这个系统设计中，我会使用zookeeper来完成选主和节点监听等工作。 #### 3. 设计考虑 无论是在paxos还是raft中，系统保障的是CAP中的数据一致性和分区容错性，也就是CP。因为只要出现一半或者以上数量的副本节点宕机的情况，就会影响系统的可用性，因此paxos协议或者raft协议都不能保障完美可用性。本文设计的系统依然是保证了CAP中的数据一致性和分区容错性，但是为了简化实现，并没有采用paxos或者raft的方案。而是借鉴了了primary-secondary协议的做法，在主用节点和备用节点之间做同步日志复制。但同时引入了zookeeper来监听节点的存活状态，从而缩短了系统恢复可用的时间，提高了可用性。 因为本文设计的系统保障了数据一致性，牺牲了系统的部分性能和可用性。但是这种选择是值得的，保障了数据一致性的系统，可以屏蔽数据不一致给业务层带来的烦恼，从而降低业务开发的工作难度。 ## 相关工作 #### 1. 复制状态机 在本文介绍的系统中，需要把服务节点抽象成一个状态机[6]。每个节点包含一组状态，一个转换函数和一个输出函数。客户发往服务节点的请求都可以抽象为一个操作日志，作为转换函数和输出函数的输入。多个相同初始状态的状态机，输入相同的操作日志序列，最终能够得到相同的状态，并且输出相同的结果。因此，系统只需要在多个副本节点中同步复制操作日志流，即可实现系统的状态复制。 ####...
## Why I'm doing: In column mode partial update, we need to read from `.upt` files and generate partial column files for each segment files. When handle large partial update...
## Why I'm doing: In current implementation, if one ingest in tablet has multi segment files, and SR will load all segment file state at once, which will cost lots...