羽洵
TA的个人档案
个人介绍
做最好的云数据库！
擅长的技术
- Java
- Linux
- 数据库
- 高分内容
- 最新动态
- 文章
- 问答
-
发表了文章 2020-06-15
libcuckoo论文概述
本文简要阐述libcuckoo项目的两篇论文基础。如有错漏之处，欢迎指出一起讨论交流。 论文1 《MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing》这篇论文主要讲了在多线程模式下如何提升cuckoo hash table的吞吐。 问题 传统hash表在并发效率上并不高，使用链表解决哈希冲突效率低，使用分shard的模式并不能提升热点负载。 改进一：Tag-based Lookup/Insert kv不存储在hash表中，hash表的每个slot只存储 对这个key的 tag 和真实存储这个key的指针。如此一次可读取单个bucket内的所有slot信息，对cache line也十分友好。 查找过程优先比较tag，tag命中后再全比较key。同时提供了 主bucket id和备 bucket id的函数公式计算，可通过tag加其中一个主bucket id推算出备bucket id。方便查找移动合适的bucket。 改进二：Concurrent Cuckoo Hashing 通过DFS算法找到key 迁移bucket的路线图，查找过程非互斥，找到之后再尝试从最后的key开始往前挪动，挪动的过程才是互斥的行为。可以查找多条路径，找到最优的路径移动bucket。每个bucket有对应的一个原子版本号，对应这个bucket下的所有slot，本质上是lock striping。虽然粒度粗了，但是和每个slot都有版本号相比，减少了内存消耗。在此基础上实现了乐观锁，每个insert之前先对版本号+1，完成之后再对版本号+1。每个读操作之前先读取版本号，如果是奇数，说明有insert正在进行，放弃重试。如果是偶数，再读取之后再重新获取一下版本号，如果版本号已经发生了改变，放弃重新获取。 改进三：Clock LRU 传统的LRU算法会使用双向链表来实现，通过移动链表来计算出最近访问的key。这种方法空间利用率低。使用一个环形的bit数据结构来替换双向链表。每个bit代表了slot的位置，当有insert/update发生时，这个slot的bit被置为1。有个独立的evict扫描器，从环形bit开始扫描，遇到为1的置为0，继续向前扫描，遇到0的则将对应的slot的数据设置为需要淘汰。淘汰的过程中也使用上述的乐观锁，与insert/update一致，避免脏读。 论文2 《Algorithmic Improvements for Fast Concurrent Cuckoo Hashing》这篇论文是基于上一篇论文提出的进一步优化提高吞吐量。其中关于HTM部分的优化本文略过。 改进一：BFS 将DFS 路径查找改成BFS，尽量找到最短的路径。论文测试出最适合的单个bucket最适合的slot个数是8，论文在读和写吞吐的平衡中找到最合适的桶深度为8，8个slot会超过一个cache line，论文认为可一次读取两个cache line，经实践是最优配置。 改进二：Fine-grained Locking 论文1中当需要挪动bucket时，对路径图中key的bucket都提前加上了锁，锁的力度太大。同时读的时候如果发生更改，每次都需要重试，很容易发生了活锁。由此论文2提出更细粒度的锁，使用spinlock替换版本号实现lock-striped。对于cuckoo hash来说，无论如何移动bucket，最终数据的操作粒度在主备bucket之中操作，所以在lookup/insert过程中，都细粒度到只是对两个bucket的操作，每次都是获取两个bucket的锁。 结束语 云数据库Redis版（ApsaraDB for Redis）是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全SSD盘高性能存储，支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用：阿里云redis
-
发表了文章 2019-06-12
走进KeyDB
KeyDB项目是从redis fork出来的分支。众所周知redis是一个单线程的kv内存存储系统，而KeyDB在100%兼容redis API的情况下将redis改造成多线程。项目git地址：https://github.com/JohnSully/KeyDB网上公开的技术细节比较少，本文基本是通过阅读源码总结出来的，如有错漏之处欢迎指正。 多线程架构 线程模型 KeyDB将redis原来的主线程拆分成了主线程和worker线程。每个worker线程都是io线程，负责监听端口，accept请求，读取数据和解析协议。如图所示： KeyDB使用了SO_REUSEPORT特性，多个线程可以绑定监听同个端口。每个worker线程做了cpu绑核，读取数据也使用了SO_INCOMING_CPU特性，指定cpu接收数据。解析协议之后每个线程都会去操作内存中的数据，由一把全局锁来控制多线程访问内存数据。主线程其实也是一个worker线程，包括了worker线程的工作内容，同时也包括只有主线程才可以完成的工作内容。在worker线程数组中下标为0的就是主线程。主线程的主要工作在实现serverCron，包括： 处理统计 客户端链接管理 db数据的resize和reshard 处理aof replication主备同步 cluster模式下的任务 链接管理 在redis中所有链接管理都是在一个线程中完成的。在KeyDB的设计中，每个worker线程负责一组链接，所有的链接插入到本线程的链接列表中维护。链接的产生、工作、销毁必须在同个线程中。每个链接新增一个字段int iel; /* the event loop index we're registered with */用来表示链接属于哪个线程接管。KeyDB维护了三个关键的数据结构做链接管理： clients_pending_write：线程专属的链表，维护同步给客户链接发送数据的队列 clients_pending_asyncwrite：线程专属的链表，维护异步给客户链接发送数据的队列 clients_to_close：全局链表，维护需要异步关闭的客户链接 分成同步和异步两个队列，是因为redis有些联动api，比如pub/sub，pub之后需要给sub的客户端发送消息，pub执行的线程和sub的客户端所在线程不是同一个线程，为了处理这种情况，KeyDB将需要给非本线程的客户端发送数据维护在异步队列中。同步发送的逻辑比较简单，都是在本线程中完成，以下图来说明如何同步给客户端发送数据： 如上文所提到的，一个链接的创建、接收数据、发送数据、释放链接都必须在同个线程执行。异步发送涉及到两个线程之间的交互。KeyDB通过管道在两个线程中传递消息： int fdCmdWrite; //写管道 int fdCmdRead; //读管道 本地线程需要异步发送数据时，先检查client是否属于本地线程，非本地线程获取到client专属的线程ID，之后给专属的线程管到发送AE_ASYNC_OP::CreateFileEvent的操作，要求添加写socket事件。专属线程在处理管道消息时将对应的请求添加到写事件中，如图所示： redis有些关闭客户端的请求并非完全是在链接所在的线程执行关闭，所以在这里维护了一个全局的异步关闭链表。 锁机制 KeyDB实现了一套类似spinlock的锁机制，称之为fastlock。fastlock的主要数据结构有： struct ticket { uint16_t m_active; //解锁+1 uint16_t m_avail; //加锁+1 }; struct fastlock { volatile struct ticket m_ticket; volatile int m_pidOwner; //当前解锁的线程id volatile int m_depth; //当前线程重复加锁的次数 }; 使用原子操作__atomic_load_2，__atomic_fetch_add，__atomic_compare_exchange来通过比较m_active=m_avail判断是否可以获取锁。fastlock提供了两种获取锁的方式： try_lock：一次获取失败，直接返回 lock：忙等，每1024 * 1024次忙等后使用sched_yield 主动交出cpu，挪到cpu的任务末尾等待执行。 在KeyDB中将try_lock和事件结合起来，来避免忙等的情况发生。每个客户端有一个专属的lock，在读取客户端数据之前会先尝试加锁，如果失败，则退出，因为数据还未读取，所以在下个epoll_wait处理事件循环中可以再次处理。 Active-Replica KeyDB实现了多活的机制，每个replica可设置成可写非只读，replica之间互相同步数据。主要特性有： 每个replica有个uuid标志，用来去除环形复制 新增加rreplay API，将增量命令打包成rreplay命令，带上本地的uuid key，value加上时间戳版本号，作为冲突校验，如果本地有相同的key且时间戳版本号大于同步过来的数据，新写入失败。采用当前时间戳向左移20位，再加上后44位自增的方式来获取key的时间戳版本号。 结束语 云数据库Redis版（ApsaraDB for Redis）是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全SSD盘高性能存储，支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用:云数据库 Redis 版
-
发表了文章 2019-04-29
Redis radix tree源码解析
Redis实现了不定长压缩前缀的radix tree，用在集群模式下存储slot对应的的所有key信息。本文将详述在Redis中如何实现radix tree。 核心数据结构 raxNode是radix tree的核心数据结构，其结构体如下代码所示： typedef struct raxNode { uint32_t iskey:1; uint32_t isnull:1; uint32_t iscompr:1; uint32_t size:29; unsigned char data[]; } raxNode; iskey：表示这个节点是否包含key 0：没有key 1：表示从头部到其父节点的路径完整的存储了key，查找的时候按子节点iskey=1来判断key是否存在 isnull：是否有存储value值，比如存储元数据就只有key，没有value值。value值也是存储在data中 iscompr：是否有前缀压缩，决定了data存储的数据结构 size：该节点存储的字符个数 data：存储子节点的信息 iscompr=0：非压缩模式下，数据格式是：[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)，有size个字符，紧跟着是size个指针，指向每个字符对应的下一个节点。size个字符之间互相没有路径联系。 iscompr=1：压缩模式下，数据格式是：[header strlen=3][xyz][z-ptr](value-ptr?)，只有一个指针，指向下一个节点。size个字符是压缩字符片段 Rax Insert 以下用几个示例来详解rax tree插入的流程。假设j是遍历已有节点的游标，i是遍历新增节点的游标。 场景一：只插入abcd z-ptr指向的叶子节点iskey=1，使用了压缩前缀。 场景二：在abcd之后插入abcdef 从abcd父节点的每个压缩前缀字符比较，遍历完所有abcd节点后指向了其空子节点，j = 0， i < len(abcded)。查找到abcd的空子节点，直接将ef赋值到子节点上，成为abcd的子节点。ef节点被标记为iskey=1，用来标识abcd这个key。ef节点下再创建一个空子节点，iskey=1来表示abcdef这个key。 场景三：在abcd之后插入ab ab在abcd能找到前两位的前缀，也就是i=len(ab)，j < len(abcd)。将abcd分割成ab和cd两个子节点，cd也是一个压缩前缀节点，cd同时被标记为iskey=1，来表示ab这个key。cd下挂着一个空子节点，来标记abcd这个key。 场景四：在abcd之后插入abABC abcABC在abcd中只找到了ab这个前缀，即i < len(abcABC)，j < len(abcd)。这个步骤有点复杂，分解一下： step 1：将abcd从ab之后拆分，拆分成ab、c、d 三个节点。 step 2：c节点是一个非压缩的节点，c挂在ab子节点上。 step 3：d节点只有一个字符，所以也是一个非压缩节点，挂在c子节点上。 step 4：将ABC 拆分成了A和BC， A挂在ab子节点上，和c节点属于同一个节点，这样A就和c同属于父节点ab。 step 5：将BC作为一个压缩前缀的节点，挂在A子节点下。 step 6：d节点和BC节点都挂一个空子节点分别标识abcd和abcABC这两个key。 场景五：在abcd之后插入Aabc abcd和Aabc没有前缀匹配，i = 0，j = 0。将abcd拆分成a、bcd两个节点，a节点是一个非压缩前缀节点。将Aabc拆分成A、abc两个节点，A节点也是一个非压缩前缀节点。将A节点挂在和a相同的父节点上。同上，在bcd和abc这两个节点下挂空子节点来分别表示两个key。 Rax Remove 删除 删除一个key的流程比较简单，找到iskey的节点后，向上遍历父节点删除非iskey的节点。如果是非压缩的父节点并且size > 1，表示还有其他非相关的路径存在，则需要按删除子节点的模式去处理这个父节点，主要是做memove和realloc。 合并 删除一个key之后需要尝试做一些合并，以收敛树的高度。合并的条件是： iskey=1的节点不能合并 子节点只有一个字符 父节点只有一个子节点（如果父节点是压缩前缀的节点，那么只有一个子节点，满足条件。如果父节点是非压缩前缀的节点，那么只能有一个字符路径才能满足条件） 结束语 云数据库Redis版（ApsaraDB for Redis）是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全SSD盘高性能存储，支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用:云数据库 Redis 版
-
发表了文章 2018-12-18
深入解析redis cluster gossip机制
社区版redis cluster是一个P2P无中心节点的集群架构，依靠gossip协议传播协同自动化修复集群的状态。本文将深入redis cluster gossip协议的细节，剖析redis cluster gossip协议机制如何运转。 协议解析 cluster gossip协议定义在在ClusterMsg这个结构中，源码如下： typedef struct { char sig[4]; /* Signature "RCmb" (Redis Cluster message bus). */ uint32_t totlen; /* Total length of this message */ uint16_t ver; /* Protocol version, currently set to 1. */ uint16_t port; /* TCP base port number. */ uint16_t type; /* Message type */ uint16_t count; /* Only used for some kind of messages. */ uint64_t currentEpoch; /* The epoch accordingly to the sending node. */ uint64_t configEpoch; /* The config epoch if it's a master, or the last epoch advertised by its master if it is a slave. */ uint64_t offset; /* Master replication offset if node is a master or processed replication offset if node is a slave. */ char sender[CLUSTER_NAMELEN]; /* Name of the sender node */ unsigned char myslots[CLUSTER_SLOTS/8]; char slaveof[CLUSTER_NAMELEN]; char myip[NET_IP_STR_LEN]; /* Sender IP, if not all zeroed. */ char notused1[34]; /* 34 bytes reserved for future usage. */ uint16_t cport; /* Sender TCP cluster bus port */ uint16_t flags; /* Sender node flags */ unsigned char state; /* Cluster state from the POV of the sender */ unsigned char mflags[3]; /* Message flags: CLUSTERMSG_FLAG[012]_... */ union clusterMsgData data; } clusterMsg; 可以对此结构将消息分为三部分： 1、sender的基本信息： sender： node name configEpoch：每个master节点都有一个唯一的configEpoch做标志，如果和其他master节点冲突，会强制自增使本节点在集群中唯一 slaveof：master信息，假如本节点是slave节点的话，协议带有master信息 offset：主从复制的偏移 flags：本节点当前的状态，比如 CLUSTER_NODE_HANDSHAKE、CLUSTER_NODE_MEET mflags：本条消息的类型，目前只有两类：CLUSTERMSG_FLAG0_PAUSED、CLUSTERMSG_FLAG0_FORCEACK myslots：本节点负责的slots信息 port: cport: ip: 2、集群视图的基本信息: currentEpoch：表示本节点当前记录的整个集群的统一的epoch，用来决策选举投票等，与configEpoch不同的是：configEpoch表示的是master节点的唯一标志，currentEpoch是集群的唯一标志。 3、具体的消息，对应clsuterMsgData结构中的数据： ping、pong、meet：clusterMsgDataGossip，这个协议将sender节点中保存的集群所有节点的信息都发送给对端，节点个数在clusterMsg的字段count中定义，这个协议包含其他节点的信息的字段有： nodename： ping_sent：最近一次sender节点给该节点发送ping的时间点。收到pong回复后ping_sent会被赋值为0 这里作者用了一个技巧去减少gossip通信带宽。 如果receiver节点上关于该节点的ping_sent=0 并且没有任何节点正在failover&该节点没有fail&receiver节点上关于该节点的pong_received<sender上的pong_received并且sender的pong_received大于receiver节点内核时间的500ms内，则将receiver节点关于该节点的pong_received时间设置为和sender节点一致，复用sender节点的pong_received。那么received节点则会减少对该节点发送ping。参考issue:https://github.com/antirez/redis/issues/3929 pong_received：最近一次sender节点收到该节点发送pong的时间点 ip： port： cport： flags：对应clusterMsg的flags，只不过存储的其他节点的 fail：clusterMsgDataFail，只有一个表示fail节点的nodename字段, 统计超过一半以上节点任务node pfail后发送fail msg publish：clusterMsgDataPublish，集群间同步publish信息，以支持客户端在任一节点发送pub/sub update：clusterMsgDataUpdate，当receiver节点发现sender节点的configepoch低于本节点的时候，会给sender节点发送一个update消息通知sender节点更新状态，包含： configEpoch：receiver节点中保存的sender节点的configepoch nodename：receiver节点中保存的sender节点的nodename slots：receiver节点中保存的sender节点的slots列表 运转机制 通过gossip协议，cluster可以提供集群间状态同步更新、选举自助failover等重要的集群功能。 握手联结 客户端给节点X发送cluster meet 节点Y的请求后，节点X之后就会尝试主从和节点Y建立连接。此时在节点X中保存节点Y的状态是： CLUSTER_NODE_HANDSHAKE：表示节点Y正处于握手状态，只有收到来自节点Y的ping、pong、meet其中一种消息后该状态才会被清除 CLUSTER_NODE_MEET：表示还未给节点Y发送meet消息，一旦发送该状态清除，不管是否成功 以下是meet过程： （0）节点X通过getRandomHexChars这个函数给节点Y随机生成nodename （1）节点X 在clusterCron运转时会从cluster->nodes列表中获取未建立tcp连接，如未发送过meet，发送CLUSTERMSG_TYPE_MEET，节点Y收到meet消息后： （2）查看节点X还未建立握手成功，比较sender发送过来的消息，更新本地关于节点X的信息 （3）查看节点X在nodes不存在，添加X进nodes，随机给X取nodename。状态设置为CLUSTER_NODE_HANDSHAKE （4）进入gossip处理这个gossip消息携带的集群其他节点的信息，给集群其他节点建立握手。 （5）给节点X发送CLUSTERMSG_TYPE_PONG，节点Y处理结束（注意此时节点Y的clusterReadHandler函数link->node为NULL）。 （6）节点X收到pong后，发现和节点Y正处在握手阶段，更新节点Y的地址和nodename，清除CLUSTER_NODE_HANDSHAKE状态。 （7）节点X在cron()函数中将给未建立连接的节点Y发送ping （8）节点Y收到ping后给节点X发送pong （9）节点X将保存的节点Y的状态CLUSTER_NODE_HANDSHAKE清除，更新一下nodename和地址，至此握手完成，两个节点都保存相同的nodename和信息。 看完整个握手过程后，我们尝试思考两个问题： 1、如果发送meet失败后，节点X的状态CLUSTER_NODE_MEET状态又被清除了，cluster会如何处理呢？ 这时候节点Y在下一个clusterCron()函数中会直接给节点Y发送ping，但是不会将节点X存入cluster->nodes，导致节点X认为已经建立连接，然而节点Y并没有承认。在后面节点传播中，如果有其他节点持有节点X的信息并给节点Y发送ping，也会触发节点Y主动再去给节点X发送meet建立连接。 2、如果节点Y已经有存储节点X，但还是收到了节点X的meet请求，如何处理？ nodename相同： （1）节点Y发送pong给节点X （2）如果正处于握手节点，会直接删除节点，这里会导致节点Y丢失了节点X的消息。相当于问题1。 （3）非握手阶段往下走正常的ping流程 nodename不同： （1）节点Y重新创建一个随机nodename放入nodes中并设置为握手阶段，此时有两个nodename存在。 （2）节点Y发送pong给节点X （3）节点Y如果已经创建过和节点X的连接，节点Y会在本地更新节点X的nodename，删除第一个nodename存储的node，更新握手状态，此时只剩下第二个正确的nodename。 （4）节点Y如果没创建过和节点X的链接，会在clustercron(）中再次给节点X发送ping请求，两个nodename会先后各发送一次。 （5）第一个nodename发送ping后，在收到节点X回复的pong中，更新节点X的nodename （6）第二个nodename发送ping后，在收到节点X回复的pong中，发送节点X的nodename已经存在，第二个nodename处于握手状态，这时候直接删除了第二个nodename。 结论：只有nodename相同并且两个节点都在握手阶段，会导致其中一个节点丢掉另外一个节点。 健康检测及failover 详情见文章：https://yq.aliyun.com/articles/638627?utm_content=m_1000016044 状态更新及冲突解决 假如出现两个master的时候gossip协议是如何处理冲突的呢？ 首先要理解两个重要的变量： configEpoch： 每个分片有唯一的epoch值，主备epoch应该一致 currentEpoch：集群当前的epoch，=集群中最大分片的epoch 在ping包中会自带sender节点的slots信息和currentEpoch, configEpoch。 master节点收到来自slave节点后的处理流程： （1）receiver比较sender的角色， 如果sender认为自己是master，但是在receiver被标记为slave，则receiver节点在集群视图中将sender标记为master。 如果sender认为自己是slave，但是在receiver被标记为master, 则在receiver的集群视图中将sender标记为slave, 加入到sender标记的master中，并且删除sender在reciver集群视图中的slots信息。 （2）比较sender自带的slot信息和receiver集群视图中的slots是否冲突，有冲突则进行下一步比较 （3）比较sender的configEpoch 是否 > receiver集群视图中的slots拥有者的configepoch，如是在clusterUpdateSlotsConfigWith函数中重新设置slots拥有者为sender，并且将旧slots拥有者设置为sender的slave，再比较本节点是有脏slot, 有则清除掉。 （4）比较sender自身的slots信息 < receiver集群视图中的slots拥有者的configepoch，发送update信息，通知sender更新，sender节点也会执行clusterUpdateSlotsConfigWith函数。 如果两个节点的configEpoch, currentEpoch，角色都是master， 这时候如何处理呢？ receiver的currentEpoch自增并且赋值给configEpoch，也就是强制自增来解决冲突。这时候因为configEpoch大，又可以走回上文的流程。 所以可能存在双master同时存在的情况，但是最终会挑选出新的master。 结束语 云数据库Redis版（ApsaraDB for Redis）是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全SSD盘高性能存储，支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用:云数据库 Redis 版
-
发表了文章 2018-10-10
阿里云Redis集群兼容cluster语法
阿里云Redis集群兼容社区cluster相关语法，允许JedisCluster等客户端访问cluster nodes等命令，用户在开通兼容功能后，可以将自建的cluster集群无缝迁移到阿里云上的Redis集群，无须修改业务代码。开通流程见下文。 开通操作 登录阿里云控制台，选择要操作的Redis集群实例，点开左侧栏上的“参数配置”。找到“cluster_compat_enable”这个参数，点击“修改”，设置为1。0表示关闭此功能，1表示打开，默认为关闭。 限制 该功能只支持VPC网络的Redis集群实例，经典网络的实例需先变更到VPC网络。说明详情见：https://help.aliyun.com/document_detail/43885.html?spm=5176.11065259.1996646101.searchclickresult.70fe3840rs3gcy
滑动查看更多
-
发表了文章
2020-06-15
libcuckoo论文概述
-
发表了文章
2019-06-12
走进KeyDB
-
发表了文章
2019-04-29
Redis radix tree源码解析
-
发表了文章
2018-12-18
深入解析redis cluster gossip机制
-
发表了文章
2018-10-10
阿里云Redis集群兼容cluster语法
-
发表了文章
2018-09-12
深入理解redis cluster的failover机制
-
发表了文章
2017-10-17
etcd源码解析之V2 server和raft核心运转
-
发表了文章
2017-01-11
redis4.0、codis、阿里云redis 3种redis集群对比分析
-
发表了文章
2016-11-24
如何让redis 迁移大key的restore性能提升6倍
-
发表了文章
2016-04-08
如何让glog性能提高10倍
滑动查看更多
暂无更多信息