Posts

“redis scan” redis用scan代替keys 众所周知，当redis中key数量越大，keys 命令执行越慢，而且最重要的会阻塞服务器，对单线程的redis来说，简直是灾难，且在生产环境，keys命令一般是被禁止的。scan可用来替换keys请求。 所以说官方的建议是: 生产环境屏蔽掉 keys 命令。 在对键进行增量式迭代的过程中， 键可能会被修改， 所以增量式迭代命令只能对被返回的元素提供有限的保证 。 scan用法 SCAN cursor [MATCH pattern] [COUNT count] scan 0 match *news* count 3 scan是一个增量迭代式的命令，这意味着每次调用这个命令都会返回一个游标cursor，该游标用于下次查询。查询开始时，cursor值为0；当查询结束时，cursor的值也回归到0。 举个例子: 开始查询，scan cursor为0，返回的cursor为17 redis 127.0.0.1:6379> scan 0 “17” “key:12” “key:8” “key:4” “key:14” “key:16” “key:17” “key:15” “key:10” “key:3” “key:7” “key:1” 下一次查询，以上一次查询返回的cursor为起始位置 redis 127.0.0.1:6379> scan 17 查询返回cursor为0，标志查询结束 “0” “key:5” “key:18” “key:0” “key:2” “key:19” “key:13” “key:6” “key:9” “key:11” count count可理解为迭代过程中的步长，指每次调用scan时应执行的工作量，该值默认为10。每次调用count的值可以随意指定，只要下一次传递cursor是上一次调用返回的cursor就行。 match 需要注意的是，match操作时在元素被检出后执行的。假设redis中只有少量元素符合pattern条件，那么很可能在多次调用中scan返回的数据为空，例如: 查找key中包含11的键，因为这里没有指定count，所以默认为10 redis 127.0.0.1:6379> scan 0 MATCH 11 ...

“gcm cbc” 主要区别 AES-GCM可以并行加密解密，AES-CBC的模式决定了它只能串行地进行加密。因为加密是耗时较久的步骤，且加密的方式是相同的，所以并行地实现AES-GCM算法的时候，其效率是高于AES-CBC的； AES-GCM提供了GMAC信息校验码，用以校验密文的完整性。AES-CBC没有，无法有效地校验密文的完整性； AES-GCM是流加密的模式，不需要对明文进行填充。AES-CBC是块加密的模式，需要对明文进行填充。(AES-GCM中进行AES加密的是counter，AES-CBC中进行AES加密的是明文块)； 由于AES-CBC中必须要用到padding，导致最后一个明文块与其他密文块不同，因此可能会受到padding Oracle attacks，从而可以直接通过初始向量IV和密码，即可得到明文。 https://blog.csdn.net/weixin_39680609/article/details/111159600

Reactor / Dispatcher 模式 了解 Reactor 模式，就要先从事件驱动的开发方式说起。 我们知道，服务器开发，CPU 的处理速度远高于 IO 速度，为了避免 CPU 因为 IO 而阻塞，好一点的方法是多进程或线程处理，但这会带来一些进程切换的开销。 这时先驱者找到了事件驱动，或者叫回调的方法。这种方式就是，应用向一个中间人注册一个回调 (Event handler)，当 IO 就绪后，这个中间人产生一个事件，并通知此 handler 进行处理。这种回调的方式，也实现了"好莱坞原则" - “Don’t call us, we’ll call you.” 那在 IO 就绪这个事件后，谁来充当这个中间人？Reactor 模式的答案是: 有一个不断等待和循环的单独进程 (线程) 来做这件事，它接受所有 handler 的注册，并负责向操作系统查询 IO 是否就绪，在就绪后用指定的 handler 进行处理，这个角色的名称就叫做 Reactor。 事件驱动, 回调函数, reactor, 响应式编程 事件驱动是概念，回调函数是实现方式。不用回调函数，也可以实现事件驱动。例如：把事件消息发送到队列，另外一个进程取队列处理即可 (没有回调函数）。事件驱动的本质特征：中心轮询机制。event loop的loop是轮询。轮询的目的是什么？感知！对象发生变化，如何感知这种变化？不断的循环查询，loop探测！系统n个对象，每个对象一个for循环 探测彼此的变化？nonono……建立一个轮询中心，这个轮询中心去轮询每个对象，这就是事件驱动。发生了变化，通知感兴趣的对象，怎么处理？就是定义一个回调函数。事件驱动，属于“感知层”的概念；轮询中心，往往就是操作系统本身；对于浏览器而言，就是浏览器本身。也就是系统是轮询中心，你定义 函数，系统调用你定义的函数。对比：系统定义api，你调用api。谁定义函数，谁调用，角色颠倒了！api：系统定义的函数，你去调用； 事件驱动：你定义的回调函数，被系统调用。还是没有懂？事件驱动，就是“哨兵模式”！哨兵轮询环境信息，你就安心睡大觉好了，不用每个人都轮询环境。发生了事件，哨兵 (操作系统/浏览器/轮询中心）负责通知你！怎么处理这个消息，是你的责任！ 作者：fdego 链接：https://www.zhihu.com/question/30396023/answer/447966119 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 事件驱动, reactor The reactor design pattern is an event handling pattern for handling service requests delivered concurrently to a service handler by one or more inputs. https://en.wikipedia.org/wiki/Reactor_pattern ...

“MESI” CPU 在执行指令的时候需要从 memory 中获取指令和需要的数据，但是 CPU 的速度要比 memory 快很多，这就导致了 CPU 大部分时间都不是在做运算上而是用在了和 memory 进行数据的 I/O 过程中，这样性能是很低的。这就导致了 CPU cache 的产生，CPU 将数据从 memory 读取到 cache 中，在 cache 中对数据进行读写的速度是很快的，这样就提高了性能。CPU 执行运算时不可能需要某一个数据就去读取一次，这样就增加了 I/O 的频率，导致性能低下。所以会一次性读取一块内存的数据存放到 cache 中， 这个块称为 “cache line” ， cache line 的大小是固定的， 通常是 2 的 N 次方，在 16 ~ 256 byte 不等。当某个数据首次被 CPU 访问时， cache 中不存在，这称为 “cache miss” (或 “startup” 或 “warmup” cache miss)。这意味着 CPU 必须要去 memory 中读取该数据，这时候 CPU 必须等待 (stalled)。当 cache 装满后，后续的 cache miss 需要置换 cache 中现有的数据，这样的 cache miss 被称为 “capacity miss” 。如果随后又访问了被替换的 cache line ，这时的 cache miss 被称为 “associativity miss” 。 ...

“Store Buffer” 就像spinlock的进化史，软件工程师会对自己的代码做足够的优化以提高性能。同样，硬件工程也不甘示弱，尽最大的努力设计硬件以获取更好的性能。我们引入高速缓存的目的就是为了降低内存访问的延迟，谁知硬件工程师依然不满足于高速缓存带来的延迟，当然软件工程师或许也不满足。为了进一步加快内存访问速度，硬件引入了新的缓存 - store buffer。随着store buffer的引入，彻底刷新了软件工程师对代码执行流的认知。store buffer又是怎么刷新我们的认知呢？ 文章测试代码已经开源，可以点击这里查看。 store buffer是什么 在之前的文章介绍中，我们了解到每个CPU都会有自己私有L1 Cache。从我了解的资料来说，L1 Cache命中的情况下，访问数据一般需要2个指令周期。而且当CPU遭遇写数据cache未命中时，内存访问延迟增加很多。硬件工程师为了追求极致的性能，在CPU和L1 Cache之间又加入一级缓存，我们称之为store buffer。store buffer和L1 Cache还有点区别，store buffer只缓存CPU的写操作。store buffer访问一般只需要1个指令周期，这在一定程度上降低了内存写延迟。不管cache是否命中，CPU都是将数据写入store buffer。store buffer负责后续以FIFO次序写入L1 Cache。store buffer大小一般只有几十个字节。大小和L1 Cache相比，确实是小巫见大巫了。 store buffer对程序的影响 我们现在知道，当存在store buffer的情况下。针对写操作，CPU直接把数据扔给store buffer。后续store buffer负责以FIFO次序写回L1 Cache。这会对我们的程序产生什么影响呢？我们来看个例子。 static int x = 0, y = 0; static int r1, r2; static void int thread_cpu0(void) { x = 1; /* 1) / r1 = y; / 2) */ } static void int thread_cpu1(void) { y = 1; /* 3) / r2 = x; / 4) */ } ...

“Memory Barrior, 内存屏障” 屏障技术 内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作6。 https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/ 内存屏障 Memory Barrior 内存屏障 (Memory barrier) 为什么会有内存屏障 每个CPU都会有自己的缓存 (有的甚至L1,L2,L3) ，缓存的目的就是为了提高性能，避免每次都要向内存取。但是这样的弊端也很明显: 不能实时的和内存发生信息交换，分在不同CPU执行的不同线程对同一个变量的缓存值不同。 用volatile关键字修饰变量可以解决上述问题，那么volatile是如何做到这一点的呢？那就是内存屏障，内存屏障是硬件层的概念，不同的硬件平台实现内存屏障的手段并java通过屏蔽这些差异，统一由jvm来生成内存屏障的指令。 内存屏障是什么 硬件层的内存屏障分为两种: Load Barrier 和 Store Barrier即读屏障和写屏障。 内存屏障有两个作用: 阻止屏障两侧的指令重排序； 强制把写缓冲区/高速缓存中的脏数据等写回主内存，让缓存中相应的数据失效。 对于Load Barrier来说，在指令前插入Load Barrier，可以让高速缓存中的数据失效，强制从新从主内存加载数据； 对于Store Barrier来说，在指令后插入Store Barrier，能让写入缓存中的最新数据更新写入主内存，让其他线程可见。 java内存屏障 java的内存屏障通常所谓的四种即LoadLoad,StoreStore,LoadStore,StoreLoad实际上也是上述两种的组合，完成一系列的屏障和数据同步功能。 LoadLoad屏障: 对于这样的语句Load1; LoadLoad; Load2，在Load2及后续读取操作要读取的数据被访问前，保证Load1要读取的数据被读取完毕。 StoreStore屏障: 对于这样的语句Store1; StoreStore; Store2，在Store2及后续写入操作执行前，保证Store1的写入操作对其它处理器可见。 LoadStore屏障: 对于这样的语句Load1; LoadStore; Store2，在Store2及后续写入操作被刷出前，保证Load1要读取的数据被读取完毕。 StoreLoad屏障: 对于这样的语句Store1; StoreLoad; Load2，在Load2及后续所有读取操作执行前，保证Store1的写入对所有处理器可见。它的开销是四种屏障中最大的。 volatile语义中的内存屏障 volatile的内存屏障策略非常严格保守，非常悲观且毫无安全感的心态: 在每个volatile写操作前插入StoreStore屏障，在写操作后插入StoreLoad屏障； 在每个volatile读操作前插入LoadLoad屏障，在读操作后插入LoadStore屏障； 由于内存屏障的作用，避免了volatile变量和其它指令重排序、线程之间实现了通信，使得volatile表现出了锁的特性。 final语义中的内存屏障 对于final域，编译器和CPU会遵循两个排序规则: 新建对象过程中，构造体中对final域的初始化写入和这个对象赋值给其他引用变量，这两个操作不能重排序； (废话嘛) 初次读包含final域的对象引用和读取这个final域，这两个操作不能重排序； (晦涩，意思就是先赋值引用，再调用final值) 总之上面规则的意思可以这样理解，必需保证一个对象的所有final域被写入完毕后才能引用和读取。这也是内存屏障的起的作用: 写final域: 在编译器写final域完毕，构造体结束之前，会插入一个StoreStore屏障，保证前面的对final写入对其他线程/CPU可见，并阻止重排序。 读final域: 在上述规则2中，两步操作不能重排序的机理就是在读final域前插入了LoadLoad屏障。 X86处理器中，由于CPU不会对写-写操作进行重排序，所以StoreStore屏障会被省略；而X86也不会对逻辑上有先后依赖关系的操作进行重排序，所以LoadLoad也会变省略。 ...

编译器指令重排, Compiler Instruction Reordering compiler的主要工作就是将对人们可读的源码转化成机器语言，机器语言就是对CPU可读的代码。因此，compiler可以在背后做些不为人知的事情。我们考虑下面的C语言代码: int a, b; void foo(void) { a = b + 1; b = 0; } 使用 aarch64-linux-gnu-gcc 在不优化代码的情况下编译上述代码，使用 objdump 工具查看 foo() 反汇编结果 : … ldr w0, [x0] // load b to w0 add w1, w0, #0x1 … str w1, [x0] // a = b + 1 … str wzr, [x0] // b = 0 我们应该知道 Linux 默认编译优化选项是-O2，因此我们采用-O2 优化选项编译上述代码，并反汇编得到如下汇编结果: : ldr w2, [x0] // load b to w2 str wzr, [x0] // b = 0 add w0, w2, #0x1 str w0, [x1] // a = b + 1 比较优化和不优化的结果，我们可以发现。在不优化的情况下，a 和 b 的写入内存顺序符合代码顺序 (program order)。但是-O2 优化后，a 和 b 的写入顺序和 program order 是相反的。-O2优化后的代码转换成C语言可以看作如下形式: ...

“文件锁” 文件锁也被称为记录锁，文件锁如果深讲的话，内容不少 (比如文件锁最起码分为了建议锁和强制性锁) 这里不准备深纠，深纠没有任何意义 主要是为了对比学习各种的加锁机制，比如进程有进程信号量加锁机制，线程有线程互斥锁、线程信号量等 加锁机制，学习文件锁有助于我们对比理解，对于我们后续理解驱动课程中的内核锁，c++、java等库所提供的 资源保护的锁机制，都是很有意义的。 当然还有另一个目的，那就是练习fcntl函数的使用，因为文件锁也需要用到fcntl函数。 由于文件锁的知识点是刚才所讲的这样一种存在，所以对于文件锁内容的学习，理解>实际使用。 4.1 文件锁的作用 顾名思义，就是用来保护文件数据的。 当多个进程共享读写同一个文件时，为了不让进程们各自读写数据时相互干扰，我们可以使用进程信号量来 互斥实现，除了可以使用进程信号量以外，还可以使用我们这里的的“文件锁”来实现，而且功能更丰富， 使用起来相对还更容易些。 4.2 多进程读写文件 file_lock.png 多进程共享读写同一个文件时，如果数据很重要的话，为了防止数据相互修改，应该满足如下读写条件: (1) 写与写应该互斥 当某个进程正在写文件，而且在数据没有写完时，其它进程不能写，否者会相互打乱对方写的数据 (2) 读与写也应该是互斥的 分两种情况: 某个进程正在写数据，而且在数据没有写完时，其它进程不能读数据因为别人在没有写完之前，读到的数据是不完整的，所以读和写时互斥的 某个进程正在读数据，在数据没有读完之前，其它进程不能写数据因为可能会扰乱别人读到的数据 (3) 读与读共享 某个进程在读数时，就算数据没有读完，其它进程也可以共享读数据，并不需要互斥等别人读完后才能读。 因为读文件是不会修改文件的内容，所以不用担心数据相互干扰的问题 总结起来就是，多进程读写文件时，如果你想进行资源保护的话，完美的资源保护应该满足如下这样的。 写与写之间互斥 读与写之间互斥 读与读之间共享 如何实现以上读写要求？ 如果使用信号量来实现保护的话，只能是一律互斥，包括读与读都是互斥的，不能够向上面描述的，能互斥又能共享，但是文件锁可以做到 4.3 文件锁 4.3.1 文件锁的读锁与写锁 对文件加锁时可以加两种锁，分别是“读文件锁”和“写文件锁”，我们这里简称为读锁和写锁。 读锁、写锁之间关系 (1) 读锁和读锁共享: 可以重复加读锁，别人加了读锁在没有解锁之前，我依然可以加读锁，这就是共享。 (2) 读锁与写锁互斥: 别人加了读锁没有解锁前，加写锁会失败，反过来也是如此。 加锁失败后两种处理方式， 阻塞，直到别人解锁然后加锁成功为止 出错返回，不阻塞 (3) 写锁与写锁互斥: 别人加了写锁在没有解锁前，不能加写锁，加写锁会失败。 加锁失败后两种处理方式， 阻塞，直到别人解锁然后加锁成功为止 出错返回，不阻塞 常用的是阻塞加锁，至于如何实现阻塞和非阻塞，后面详细讲 4.3.2 使用文件锁对文件进行保护 读文件时加读锁，写文件时就加写锁，然后就可以很容易的实现符合如下要求的资源保护。 写与写之间互斥 读与写之间互斥 读与读之间共享 4.4 文件锁的加锁方式 (1) 对整个文件内容加锁 对整个文件加锁是最常用的文件锁的加锁方式。 当你对整个文件加锁时，如果文件的长度因为写入新数据或者截短而发生了变化，加锁内容的长度会 自动变化，保证对内容变化着的整个文件加锁。 (2) 对文件某部分内容加锁 不过一般来说是，对多少内容加锁，就对多少内容解锁，如果你是对整个文件加锁，就将整个文件解锁。 但是实际上加锁和实际解锁的长度可以不相同，比如我对1000个字节的内容加了锁，但是可以只对其中的 100字节解锁，不过这种情况用的少，知道有这么回事即可 4.5 文件锁的实现 实现文件锁时，我们还是需要使用fcntl函数 4.5.1 再看看fcntl的函数原型 ...

“拜占庭将军问题” 接触区块链的同学，多少都听说过拜占庭将军问题，经常看到或听到某某区块链使用某某算法解决了拜占庭将军问题，那么究竟什么是拜占庭将军问题呢? 什么是拜占庭将军问题 也被称为“拜占庭容错”、“拜占庭将军问题”。 拜占庭将军问题是 Leslie Lamport (2013年的图灵讲得主) 用来为描述分布式系统一致性问题 (Distributed Consensus) 在论文中抽象出来一个著名的例子。 这个例子大意是这样的: 拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队 (一半以上) 同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？ 拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题的. 问题分析 单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下: 先看在没有叛徒情况下，假如一个将军A提一个进攻提议 (如: 明日下午1点进攻，你愿意加入吗？) 由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议 (如: 明日下午2点、3点进攻，你愿意加入吗？) ，由于时间上的差异，不同的将军收到 (并认可) 的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。 再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议 (通知A明日下午1点进攻， 通知B明日下午2点进攻等等) ，一个叛徒也会可能同意多个进攻提议 (即同意下午1点进攻又同意下午2点进攻) 。 叛徒发送前后不一致的进攻提议，被称为“拜占庭错误”，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。 相信大家已经可以明白这个问题的复杂性了。 https://learnblockchain.cn/2018/02/05/bitcoin-byzantine/

“Gossip” Gossip是什么 Gossip协议是一个通信协议，一种传播消息的方式，灵感来自于: 瘟疫、社交网络等。使用Gossip协议的有: Redis Cluster、Consul、Apache Cassandra等。 六度分隔理论 说到社交网络，就不得不提著名的六度分隔理论。1967年，哈佛大学的心理学教授Stanley Milgram想要描绘一个连结人与社区的人际连系网。做过一次连锁信实验，结果发现了“六度分隔”现象。简单地说: “你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。 数学解释该理论: 若每个人平均认识260人，其六度就是260↑6 =1,188,137,600,000。消除一些节点重复，那也几乎覆盖了整个地球人口若干多多倍，这也是Gossip协议的雏形。 原理 Gossip协议基本思想就是: 一个节点想要分享一些信息给网络中的其他的一些节点。于是，它周期性的随机选择一些节点，并把信息传递给这些节点。这些收到信息的节点接下来会做同样的事情，即把这些信息传递给其他一些随机选择的节点。一般而言，信息会周期性的传递给N个目标节点，而不只是一个。这个N被称为fanout (这个单词的本意是扇出) 。 用途 Gossip协议的主要用途就是信息传播和扩散: 即把一些发生的事件传播到全世界。它们也被用于数据库复制，信息扩散，集群成员身份确认，故障探测等。 基于Gossip协议的一些有名的系统: Apache Cassandra，Redis (Cluster模式) ，Consul等。 图解 接下来通过多张图片剖析Gossip协议是如何运行的。如下图所示，Gossip协议是周期循环执行的。图中的公式表示Gossip协议把信息传播到每一个节点需要多少次循环动作，需要说明的是，公式中的20表示整个集群有20个节点，4表示某个节点会向4个目标节点传播消息: Gossip Protocol 如下图所示，红色的节点表示其已经“受到感染”，即接下来要传播信息的源头，连线表示这个初始化感染的节点能正常连接的节点 (其不能连接的节点只能靠接下来感染的节点向其传播消息) 。并且N等于4，我们假设4根较粗的线路，就是它第一次传播消息的线路: first infected node 第一次消息完成传播后，新增了4个节点会被“感染”，即这4个节点也收到了消息。这时候，总计有5个节点变成红色: infected nodes 那么在下一次传播周期时，总计有5个节点，且这5个节点每个节点都会向4个节点传播消息。最后，经过3次循环，20个节点全部被感染 (都变成红色节点) ，即说明需要传播的消息已经传播给了所有节点: infected all nodes 需要说明的是，20个节点且设置fanout=4，公式结果是2.16，这只是个近似值。真实传递时，可能需要3次甚至4次循环才能让所有节点收到消息。这是因为每个节点在传播消息的时候，是随机选择N个节点的，这样的话，就有可能某个节点会被选中2次甚至更多次。 发送消息 由前面对Gossip协议图解分析可知，节点传播消息是周期性的，并且每个节点有它自己的周期。另外，节点发送消息时的目标节点数由参数fanout决定。至于往哪些目标节点发送，则是随机的。 一旦消息被发送到目标节点，那么目标节点也会被感染。一旦某个节点被感染，那么它也会向其他节点传播消息，试图感染更多的节点。最终，每一个节点都会被感染，即消息被同步给了所有节点: infected 可扩展性 Gossip协议是可扩展的，因为它只需要O(logN) 个周期就能把消息传播给所有节点。某个节点在往固定数量节点传播消息过程中，并不需要等待确认 (ack) ，并且，即使某条消息传播过程中丢失，它也不需要做任何补偿措施。大哥比方，某个节点本来需要将消息传播给4个节点，但是由于网络或者其他原因，只有3个消息接收到消息，即使这样，这对最终所有节点接收到消息是没有任何影响的。 如下表格所示，假定fanout=4，那么在节点数分别是20、40、80、160时，消息传播到所有节点需要的循环次数对比，在节点成倍扩大的情况下，循环次数并没有增加很多。所以，Gossip协议具备可扩展性: 可扩展性 失败容错 Gossip也具备失败容错的能力，即使网络故障等一些问题，Gossip协议依然能很好的运行。因为一个节点会多次分享某个需要传播的信息，即使不能连通某个节点，其他被感染的节点也会尝试向这个节点传播信息。 健壮性 Gossip协议下，没有任何扮演特殊角色的节点 (比如leader等) 。任何一个节点无论什么时候下线或者加入，并不会破坏整个系统的服务质量。 然而，Gossip协议也有不完美的地方，例如，拜占庭问题 (Byzantine) 。即，如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出问题。 作者: 阿飞的博客 链接: https://www.jianshu.com/p/54eab117e6ae 来源: 简书 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 ...

“failover, failfast, failback, failsafe” failover: 失效转移/故障转移 故障转移（fail-over） Fail-Over 的含义为“失效转移”，是一种备份操作模式，当主要组件异常时，其功能转移到备份组件。其要点在于有主有备，且主故障时备可启用，并设置为主。如MySQL的双Master模式，当正在使用的Master出现故障时，可以拿备Master做主使用 通俗地说，即当A无法为客户服务时，系统能够自动地切换，使B能够及时地顶上继续为客户提供服务，且客户感觉不到这个为他提供服务的对象已经更换。 这里的A和B可以存在于各种领域，但一般fail-over特指计算机领域的数据库、应用服务、硬件设备等的失效转移。 failfast: 快速失败 从字面含义看就是“快速失败”，尽可能的发现系统中的错误，使系统能够按照事先设定好的错误的流程执行，对应的方式是“fault-tolerant (错误容忍) ”。以JAVA集合 (Collection) 的快速失败为例，当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如: 当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常 (发现错误执行设定好的错误的流程) ，产生fail-fast事件。 failback: 失效自动恢复 Fail-over 之后的自动恢复，在簇网络系统 (有两台或多台服务器互联的网络) 中，由于要某台服务器进行维修，需要网络资源和服务暂时重定向到备用系统。在此之后将网络资源和服务器恢复为由原始主机提供的过程，称为自动恢复 failsafe: 失效安全 Fail-Safe的含义为“失效安全”，即使在故障的情况下也不会造成伤害或者尽量减少伤害。维基百科上一个形象的例子是红绿灯的“冲突监测模块”当监测到错误或者冲突的信号时会将十字路口的红绿灯变为闪烁错误模式，而不是全部显示为绿灯。 ———————————————— 版权声明: 本文为CSDN博主「青鱼入云」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接: https://blog.csdn.net/u011305680/article/details/79730646 https://blog.csdn.net/u013699827/article/details/73251649

“taskset” 一、在Linux上修改进程的“CPU亲和力” 在Linux上，可以通过 taskset 命令进行修改。以Ubuntu为例，运行如下命令可以安装taskset工具。 apt-get install schedutils 对运行中的进程，文档上说可以用下面的命令，把CPU#1 #2 #3分配给PID为2345的进程: taskset -cp 1,2,3 2345 但我尝试没奏效，于是我关掉了MySQL，并用taskset将它启动: taskset -c 1,2,3 /etc/init.d/MySQL start 对于其他进程，也可如此处理 (nginx除外，详见下文) 。之后用top查看CPU的使用情况，原来空闲的#1 #2 #3，已经在辛勤工作了。 二、配置nginx绑定CPU 刚才说nginx除外，是因为nginx提供了更精确的控制。 在conf/nginx.conf中，有如下一行: worker_processes 1; 这是用来配置nginx启动几个工作进程的，默认为1。而nginx还支持一个名为worker_cpu_affinity的配置项，也就是说，nginx可以为每个工作进程绑定CPU。我做了如下配置: worker_processes 3; worker_cpu_affinity 0010 0100 1000; 这里0010 0100 1000是掩码，分别代表第2、3、4颗cpu核心。 重启nginx后，3个工作进程就可以各自用各自的CPU了。 三、刨根问底 如果自己写代码，要把进程绑定到CPU，该怎么做？可以用sched_setaffinity函数。在Linux上，这会触发一次系统调用。 如果父进程设置了affinity，之后其创建的子进程是否会有同样的属性？我发现子进程确实继承了父进程的affinity属性。 四、Windows？ 在Windows上修改“CPU亲和力”，可以通过任务管理器搞定。 个人感觉，Windows系统中翻译的“处理器关系”比“CPU亲和力”容易理解点儿 —————– 进行了这样的修改后，即使系统负载达到3以上，不带缓存打开blogkid.net首页 (有40多次查询) 依然顺畅；以前一旦负载超过了1.5，响应就很慢了。效果很明显。 linux taskset命令详解 SYNOPSIS taskset [options] [mask | list ] [pid | command [arg]…] OPTIONS -p, –pid operate on an existing PID and not launch a new task -c, –cpu-list specifiy a numerical list of processors instead of a bitmask. The list may contain multiple items, separated by comma, and ranges. For example, 0,5,7,9-11. -h, –help display usage information and exit -V, –version output version information and exit

“HyperLogLog” HyperLogLog HyperLogLog，下面简称为HLL，它是 LogLog 算法的升级版，作用是能够提供不精确的去重计数。 127.0.0.1:6379> PFADD language "PHP" "Python" "Perl" "Ruby" (integer) 1 127.0.0.1:6379> PFCOUNT language (integer) 4 127.0.0.1:6379> PFADD language "PHP" # Redis 已经存在，不必对估计数量进行更新 (integer) 0 127.0.0.1:6379> PFCOUNT language # 元素估计数量没有变化 (integer) 4 127.0.0.1:6379> PFADD language "JAVA" # 添加一个不存在的元素 (integer) 1 127.0.0.1:6379> PFCOUNT language # 估计数量增一 5 https://juejin.cn/post/6844903785744056333 https://www.cnblogs.com/wmyskxz/p/12396393.html http://content.research.neustar.biz/blog/hll.html 存在以下的特点: 代码实现较难。 能够使用极少的内存来统计巨量的数据，在 Redis 中实现的 HyperLogLog，只需要12K内存就能统计2^64个数据。 计数存在一定的误差，误差率整体较低。标准误差为 0.81% 。 误差可以被设置辅助计算因子进行降低。 稍微对编程中的基础数据类型内存占用有了解的同学，应该会对其只需要12K内存就能统计2^64个数据而感到惊讶。为什么这样说呢，下面我们举下例子: 取 Java 语言来说，一般long占用8字节，而一字节有8位，即: 1 byte = 8 bit，即long数据类型最大可以表示的数是: 2^63-1。对应上面的2^64个数，假设此时有2^63-1这么多个数，从 0 ~ 2^63-1，按照long以及1k = 1024字节的规则来计算内存总数，就是: ((2^63-1) * 8/1024)K，这是很庞大的一个数，存储空间远远超过12K。而 HyperLogLog 却可以用 12K 就能统计完。 伯努利试验 在认识为什么HyperLogLog能够使用极少的内存来统计巨量的数据之前，要先认识下伯努利试验。 ...

“redis bitmap” BitMap https://www.cnblogs.com/54chensongxia/p/13794391.html BitMap# BitMap 原本的含义是用一个比特位来映射某个元素的状态。由于一个比特位只能表示 0 和 1 两种状态，所以 BitMap 能映射的状态有限，但是使用比特位的优势是能大量的节省内存空间。 在 Redis 中，可以把 Bitmaps 想象成一个以比特位为单位的数组，数组的每个单元只能存储0和1，数组的下标在 Bitmaps 中叫做偏移量。 需要注意的是: BitMap 在 Redis 中并不是一个新的数据类型，其底层是 Redis 实现。 BitMap 相关命令# 设置值，其中value只能是 0 和 1 setbit key offset value 获取值 getbit key offset 获取指定范围内值为 1 的个数 start 和 end 以字节为单位 bitcount key start end BitMap间的运算 operations 位移操作符，枚举值 AND 与运算 & OR 或运算 | XOR 异或 ^ NOT 取反 ~ result 计算的结果，会存储在该key中 key1 … keyn 参与运算的key，可以有多个，空格分割，not运算只能一个key 当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0。返回值是保存到 destkey 的字符串的长度 (以字节byte为单位) ，和输入 key 中最长的字符串长度相等。 bitop [operations] [result] [key1] [keyn…] ...

“28” 0%的汽车狂人，制造了80%以上的交通事故；世界上不足20%的富人拥有80%以上的财富；企业中80%的销售额是由20%的产品或客户贡献的。 这些现象暗合帕累托法则，即在任何一组事物中，最重要的只占其中一小部分，约20%，其余80%尽管是多数，却是次要的，这一法则又被称为二八定律或20/80定律。 二八定律可以解决企业管理方面的许多问题: 如资源分配，核心产品，关键人才，核心利润，财富分配等。若公司80%的销售额由20%产品贡献，那么就应该将更多的资源投入到这少数的20%产品上。 二八定律不仅在经济学、企业管理领域广泛应用，它对我们的自身发展也具有重要的现实意义: 要避免将时间和精力花费在琐事上，学会抓主要矛盾。 一个人的时间和精力都是非常有限的，要想真正“做好每一件事情”几乎是不可能的，应该学会合理分配时间和精力。想面面俱到还不如重点突破，把80%的资源花在能出关键效益的20%的方面，这20%的方面又能带动其余80%的发展。 https://zhuanlan.zhihu.com/p/28480261

“热数据, 温数据, 冷数据” 热数据 热数据是需要被计算节点频繁访问的在线类数据，比如可以是半年以内的数据，用户经常会查询它们，适合放在数据库中存储，比如MySQL、MongoDB和HBase。 温数据 温数据是非即时的状态和行为数据，也可以简单理解为把热数据和冷数据混在一起就成了温数据。如果整体数据量不大，也可以不区分温数据和热数据。 冷数据 冷数据是指离线类不经常访问的数据，用于灾难恢复的备份或者因为要遵守法律规定必须保留一段时间，比如企业备份数据、业务与操作日志数据、话单与统计数据。通常会存储在性能较低、价格较便宜的文件系统里，适用于离线分析，比如机器学习中的模型训练或者大数据分析。

“redis list” linkedlist 每个node包含了三个部分，指向前一个节点和后一个节点的指针，以及一个数据值。而一个list包含了指向首尾的指针、整个list的长度，以及三个函数指针，用来复制节点的值、释放节点的值，以及比较节点内容。 ziplist 压缩列表 ziplist是一种特殊编码的节省内存空间的双链表，能以O(1)的时间复杂度在两端push和pop数据 ziplist是redis中实现的一个地址连续的链表。 每次操作都需要重新分配内存 先看下官方对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 ...

“bloom filter, 布隆过滤器” Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one. 大意是不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。 在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、 大集合中重复元素的判断和缓存穿透等问题。 布隆过滤器 (Bloom Filter) 是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定地误识别率和删除困难。 什么是布隆过滤器 本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构 (probabilistic data structure) ，特点是高效地插入和查询， 可以用来告诉你 “某样东西一定不存在或者可能存在”。 ...

“IO多路复用, IO Multiplexing” 什么是IO多路复用 I/O 多路复用技术会用一个系统调用函数来监听我们所有关心的连接，也就说可以在一个监控线程里面监控很多的连接。 一个用机场管理来解释的例子，以及对select、poll、epoll的讲解 IO 多路复用是什么意思？ - 罗志宇的回答 - 知乎 有趣的比喻 这些名词比较绕口，理解涵义就好。一个epoll场景: 一个酒吧服务员 (一个线程) ，前面趴了一群醉汉，突然一个吼一声“倒酒” (事件) ，你小跑过去给他倒一杯，然后随他去吧，突然又一个要倒酒，你又过去倒上，就这样一个服务员服务好多人，有时没人喝酒，服务员处于空闲状态，可以干点别的玩玩手机。至于epoll与select，poll的区别在于后两者的场景中醉汉不说话，你要挨个问要不要酒，没时间玩手机了。io多路复用大概就是指这几个醉汉共用一个服务员。 作者: 匿名用户 链接: https://www.zhihu.com/question/32163005/answer/55687802 为什么要有IO多路复用 一个从本质上讲的清晰描述 要弄清问题 先要知道问题的出现原因 原因: 由于进程的执行过程是线性的(也就是顺序执行),当我们调用低速系统I/O(read,write,accept等等),进程可能阻塞,此时进程就阻塞 在这个调用上,不能执行其他操作.阻塞很正常. 接下来考虑这么一个问题: 一个服务器进程和一个客户端进程通信,服务器端read(sockfd1,bud,bufsize),此时客户端进程没有发送数据,那么read(阻塞调用)将 阻塞直到客户端调用write(sockfd,but,size)发来数据. 在一个客户和服务器通信时这没什么问题,当多个客户与服务器通信时,若服 务器阻塞于其中一个客户sockfd1,当另一个客户的数据到达 socket sockfd2时,服务器不 能处理,仍然阻塞在read(sockfd1,…)上;此时问题就出现了,不能及时处理另一个客户的服务,咋么办?I/O多路复用来解决! I/O多路复用:继续上面的问题,有多个客户连接,sockfd1,sockfd2,sockfd3..sockfdn 同时监听这n个客户,当其中有一个发来消息时就从select的阻塞中返回,然后就调用read 读取收到消息的sockfd,然后又循环回select阻塞;这样就不会因为阻塞在其中一个上而不能处 理另一个客户的消息 Q: 那这样子，在读取socket1的数据时，如果其它socket有数据来，那么也要等到socket1读取完了才能继续读取其它socket的数据吧。那不是也阻塞住了吗？而且读取到的数据也要开启线程处理吧，那这和多线程IO有什么区别呢？ A: CPU本来就是线性的，不论什么都需要顺序处理，并行只能是多核CPU io多路复用本来就是用来解决对多个I/O监听时,一个I/O阻塞影响其他I/O的问题,跟多线程没关系. 跟多线程相比较,线程切换需要切换到内核进行线程切换,需要消耗时间和资源. 而I/O多路复用不需要切换线/进程,效率相对较高,特别是对高并发的应用nginx就是用I/O多路复用,故而性能极佳.但多线程编程逻辑和处理上比I/O多路复用简单.而I/O多路复用处理起来较为复杂. 作者总结 用自己的话解释清楚新的知识，这就是内化的过程。 【IO多路复用】和【多线程】是两种解决单个服务器应对多客户端同时IO请求阻塞问题的方案，问题出现的根源在于原始情况下，服务器收到客户端的进程的连接请求后都会调用阻塞的read()方法尝试从客户端读取数据，若读取不到则一直保持阻塞，但是这种处理方式显然会造成问题，譬如如果正在等待读取的这个客户端不传数据了，而其它有正在等待处理的客户端数据传输请求，那么显然就会造成服务器资源的浪费 (不能及时处理真正紧急的客户端请求，而浪费时间在暂时没有处理需求的客户端请求上) 。 解决这个问题有个简单的思路: 【多线程】: 即针对每一个客户端进程都新建一个新的服务器端线程，即一对一地应付客户端的通信需求。 不过这个解决方案有个问题就是: 如果通信的客户端很多，那么服务器就需要开很多线程来处理IO，服务器这边的压力就会比较大，除开开启线程与维持线程本身需要的资源以外，服务器CPU在线程之间切换也要耗时，导致效率低下。 因此，【IO多路复用】搞定了多线程解决方案的痛点，只用一个线程来解决阻塞问题，具体做法就是: 依然调用一个阻塞方法，这个阻塞方法会监听跟踪每一个IO流的状态，当有一个新的数据传输请求到来，就会通知服务器，然后服务器找到对应有需求的客户端，并读取它要传输的数据。这样，就不用开一大堆线程去一对一的监听IO状态变化了。 而select、poll、epoll三个东西都是上述思路的不同实现方式，并且是按照它们被列出的顺序被先后发明出来的，每个更新发明出来的方法都是在之前方法上做了一些改进。 poll在select的基础上，去掉了select给定的只能最多处理1024个客户端连接的限制，并不会再修改传入该方法的参数数组。epoll是在poll的基础上，使其变成了线程安全的 (不会因为通信过程中其它线程关掉了已经加入到select或者poll中的IO流而产生未知的后果) ，同时会告知服务端具体是哪个IO流来了数据，不需要靠服务器自己去找。 ———————————————— 版权声明: 本文为CSDN博主「蓝色枫魂」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接: https://blog.csdn.net/qq_32690999/article/details/80157034 ...

race condition 数据争用 (data race) 和竞态条件 (race condition) 在有关多线程编程的话题中，数据争用 (data race) 和竞态条件 (race condition) 是两个经常被提及的名词，它们两个有着相似的名字，也是我们在并行编程中极力避免出现的。但在处理实际问题时，我们应该能明确区分它们两个。 数据争用 (data race) 定义: 多个线程对于同一个变量、同时地、进行读/写操作的现象并且至少有一个线程进行写操作。 (也就是说，如果所有线程都是只进行读操作，那么将不构成数据争用) 后果: 如果发生了数据争用，读取该变量时得到的值将变得不可知，使得该多线程程序的运行结果将完全不可预测，可能直接崩溃。 如何防止: 对于有可能被多个线程同时访问的变量使用排他访问控制，具体方法包括使用mutex (互斥量) 和monitor (监视器) ，或者使用atomic变量。 竞态条件 (race condition) 竞态条件(race conditions)，多个线程以非一致性的顺序同时访问数据资源 相对于数据争用，竞态条件(race condition) 指的是更加高层次的更加复杂的现象，一般需要在设计并行程序时进行细致入微的分析，才能确定。 (也就是隐藏得更深) 定义: 受各线程上代码执行的顺序和时机的影响，程序的运行结果产生 (预料之外) 的变化。 后果: 如果存在竞态条件(race condition)，多次运行程序对于同一个输入将会有不同的结果，但结果并非完全不可预测，它将由输入数据和各线程的执行顺序共同决定。 如何预防: 竞态条件产生的原因很多是对于同一个资源的一系列连续操作并不是原子性的，也就是说有可能在执行的中途被其他线程抢占，同时这个“其他线程”刚好也要访问这个资源。解决方法通常是: 将这一系列操作作为一个 critical section (临界区) 。 代码示例 下面以C++实现的一个银行存款转账操作为例，说明数据争用(data race) 和竞态条件(race condition)的区别。 该系统的不変性条件: 存款余额≥0，不允许借款。 3.1.数据争用的例子 int my_account = 0; //我的账户余额 int your_account = 100; //你的账户余额 // 转账操作: 存在数据争用(data race)！ bool racy_transfer(int& src, int& dst, int m) { if (m <= src) { //操作结果不可预测 src -= m; //操作结果不可预测 dst += m; //操作结果不可预测 return true; } else { return false; } } // 将下面两个函数在两个线程分别运行 racy_transfer(your_account, my_account, 50); racy_transfer(your_account, my_account, 80); 运行上面的的代码后，不光我们双方账号的余额不可预测，甚至整个系统会发生什么事情都无法保证。 ...