在上一篇文章中,通过阅读 《In Search of an Understandable Consensus Algorithm》 前三节的内容,对论文的大致内容做了简介,简单说明了一下 Replicated state machines 的用途以及 Paxos 本身存在的问题。
4. Designing for understandability several goals in designing Raft:
it must providea complete and practical foundation for system building;
it must be safe under all conditions and available under typical operating conditions;
it must be efficient for common operations.
Our most important goal — and most difficult challenge — was understandability.
从这里可以看出,Raft 设计的初衷就是为了易于理解和便于构建。
There were numerous points in the design of Raft where we had to choose among alternative approaches. In these situations we evaluated the alternatives based on understandability.
前一段时间,在一次开组会的时候,给小组成员简单介绍了一下 Raft 协议。大概四年前读过 Raft 的论文,这次分享的时候,好多好多细节都忘了。所以,再次把 《In Search of an Understandable Consensus Algorithm》 这篇论文找出来,重读一遍,做个笔记和摘要,方便后续学习和复习。
Abstract Raft is a consensus algorithm for managing a replicated log. 开篇摘要就点出了 Raft 的特点: Raft 是一种管理复制日志的共识算法。
In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number of states that must be considered. 为了增强可理解性,Raft 将共识分解成几个关键元素,例如 Leader 选举,日志复制,以及安全性等;同时,为了降低需要考虑的状态的数量,还强制实施了更强的一致性。
1. Introduction Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members.
Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现,Redis 的实现表现出很多独到之处,很多地方设计得别具匠心。下面就来简要介绍一下。
linkedlist Redis 底层也有很多地方使用到 linkedlist,并且也是双向链表。
adlist.h typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; Redis 的 linkedlist 实现特点是:
双向:节点带有前后指针;
无环:首尾没有相连,所以没有构成环状;
链表保存了首尾指针;
多态:可以保存不同类型的值,这里成为泛型也许更符合 Java 中的语义。
Redis 在 2014 年实现了 quicklist,并使用 quicklist 代替了 linkedlist。所以,现在 linkedlist 几乎已经是废弃状态。
ziplist Redis 官方在 ziplist.c 文件的注释中对 ziplist 进行了定义:
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.