Inbox

“Cuckoo filter, 布谷过滤器” 过滤器系列 (二) —— Cuckoo filter 这一篇讲的是布谷过滤器(cuckoo fliter)，这个名字来源于更早发表的布谷散列(cuckoo hash)，尽管我也不知道为什么当初要给这种散列表起个鸟名=_= 由于布谷过滤器本身的思想就源自于布谷散列，那么我们就从布谷散列开始说它的设计思想。产生布谷散列表的一个重要背景是人们对于球盒问题的分析: 给定N个球，随机的放在N个盒子里，在装球最多的盒子里，球的个数的期望是多少？答案是Θ(logN/loglogN)，这个问题其实就是散列表装填因子为1时的情况分析。后来有一天，人们发现: 每次放球的时候，如果随机选择两个盒子，将球放到当时较空的那个盒子里，那么这个期望就变成了Θ(loglogN)，这个界小于之前的界，这给了布谷散列表作者启发。 一个布谷散列表通常有两张 (一般来说) 表，分别有一个对应的Hash函数，当有新的项插入的时候，它会计算出这个项在两张表中对应的两个位置，这个项一定会被存在这两个位置之一，而具体是哪一个却不确定。 下图是一个布谷散列表的初始化示意图: image 现在我们假设有一些项要存入散列表，其每个项都有其对应的两个位置，先插入第一项A image 由于插入A的时候其两个候选位置 (0,2) 都没有占用，所以选择第一张表或者是第二张表都可以，我们在这里默认先选择第一张表，然后插入第二项B image 我们看到原来的A的位置被B占用，而A被“踢”到它的备选位置表二的2号位置上了，这就是当发生位置冲突时，布谷散列表的处理逻辑，后来的数据项将会把之前占用的项踢到另一个位置上。我们接下来插入第三项C image 没有冲突，顺利搞定，接着插入D image D成功的把C踢走了，其实看到这里读者应该在猜想，会不会有一种情况，即被踢走的数据的另一个备选位置也被占用了，这样怎么办？答案是继续踢，一个踢一个，直到大家都找到自己合适的归宿为止。那么如果发现出现了循环怎么办？答案是GG，这代表布谷散列表走到了极限 image 插入E image 这里就发生了多次替换的情况，F代替了E，E代替了A，A代替了B，B找到了空余的位子 读者可以考虑一下，如果这个时候要想插入一个“G”，其备选位置是1,2，这样的话会出现什么情况？ 好了，布谷散列表大概介绍完了，现在该布谷过滤器了。布谷过滤器的主要也是通过布谷散列来实现的，其主要变化是: 1.我们不将原来的数据完整的存进来，作为过滤器，当然要省点空间，选用的办法设计一个指纹，将比较大的原数据变成了一个个指纹串，这样就大大节省了空间。 2.由于第一点所说，存储的不是原数据，那么在替换位置的时候，我们需要再次计算原来的数据的备选位置，这样一来布谷散列表的方法就失效了。在这里，作者设计了一个方法，他将两个Hash函数变成了一个Hash函数，第一张表的备选位置是Hash(x),第二张表的备选位置是Hash(x)⊕hash(fingerprint(x))，即第一张表的位置与存储的指纹的Hash值做异或运算。这样做的优点就是不用再另外存储元素的备选位置，在替换时，可以直接用异或来计算出其另一个备选位置。 (读者可以想想如何通过表二的位置计算出元素在表一中的位置) 3.插入时，优先选择空位置，而不是尽可能的踢走其他元素。 插入伪代码如下: Copy Algorithm 1: Insert(x) f = fingerprint(x) i1 = hash(x) i2 = i1 xor hash(f) if bucket[i1] or bucket[i2] has an empty entry then //只要有空位就先插入空位里 add f to that bucket return Done i = randomly pick i1 or i2 for n=0;n<MaxNumKicks;++n randomly select an entry e from bucket[i]; swap f and the fingerprint stored in entry e; i = i xor hash(f) if bucket[i] has an empty entry then add f to bucket[i] return Done return Failure // 已经出现循环情况了 查找伪代码如下: ...

“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

“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) */ } ...

编译器指令重排, 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…] ...

“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) ，特点是高效地插入和查询， 可以用来告诉你 “某样东西一定不存在或者可能存在”。 ...

“c, file, open, fopen” "" fopen 是 C 标准库函数,用于处理作为流对象的文件的打开。与本质上是系统调用的 open 函数不同,fopen 将 FILE 指针对象与给定的文件相关联。它需要两个参数；第一个参数代表要打开的文件的路径名,第二个参数是打开文件的模式。 open 函数本质上是一个低级的系统服务,即使使用 fopen 也会被调用。需要注意的是,系统调用通常是用 C 库的封装函数提供给最终用户的,但其特点和性能用例与 C stio 库中的函数不同。如: open 在创建新文件时,第二个参数取类型为 int,第三个参数可选,指定文件模式位。 https://www.delftstack.com/zh/howto/c/open-vs-fopen-in-c/

pve + openwrt 局域网网段: 192.168.50.0/24 pve 宿主机 ip: 192.168.50.6 软路由 ip: 192.168.50.1 download openwrt image 下载 “ext4-combined-efi” curl -O https://downloads.openwrt.org/releases/19.07.7/targets/x86/64/openwrt-19.07.7-x86-64-combined-ext4.img.gz curl -O https://downloads.openwrt.org/releases/21.02.3/targets/x86/64/openwrt-21.02.3-x86-64-generic-ext4-combined-efi.img.gz curl -O https://downloads.openwrt.org/releases/24.10.0/targets/x86/64/openwrt-24.10.0-x86-64-generic-ext4-combined-efi.img.gz upload image to pve # 解压出 .img 文件 gunzip openwrt-19.07.7-x86-64-combined-ext4.img.gz 把 openwrt-24.10.0-x86-64-generic-ext4-combined-efi.img 上传到 pve local pve>local(xxx)>ISO Images>upload 创建虚拟机 点击 “创建虚拟机(Create VM)”, 填写虚拟机名称 (例如 openwrt-24-10), 选"高级"，勾选"开机自启动" (软路由必须开机启动) ，点击"下一步"。 OS: CD/DVD 选择 “Do not use any media”(不要去选择刚才上传的镜像)，点击"下一步"。 System: 系统选项卡全部默认，点击"下一步"。 Disk: 硬盘不用改，之后会删除，会用上一步下载的 .img 镜像创建虚拟磁盘。 CPU 核心数量按需添加，一般双核足够了 内存 256MB 以上都是够的，系统有富余就多加一点，一般不用超过 2GB，点击"下一步" Network: PVE 虚拟机可选网卡模型 (虚拟网卡) 有 Intel E1000、VirtIO (半虚拟化) 、Realtek RTL8139和VMware vmxnet3四种。建议选用默认的 VirtIO (半虚拟化) ，其性能和效率最高。 分离不用的硬盘: 选择刚刚创建的虚拟机 > 硬件(Hardware) > Hard Disk(scsi0) > 点击"分离(Detach)", 然后它会变成 unused disk。 删除不用的硬盘和光驱: 选中"Unused disk 0"，点击"删除"；再用同样的方法删除不用的光驱。 添加启动盘 上传 Openwrt 镜像: 选择"pve"节点 > local存储空间 > 内容 > 点击上传 > 选择"openwrt-24.10.0-x86-64-generic-ext4-combined-efi.img"镜像 > 点击"上传"。 ...

“用户栈和内核栈” 进程是程序的一次执行过程。用剧本和演出来类比，程序相当于剧本，而进程则相当于剧本的一次演出，舞台、灯光则相当于进程的运行环境。 进程的堆栈 每个进程都有自己的堆栈，内核在创建一个新的进程时，在创建进程控制块 task_struct 的同时，也为进程创建自己堆栈。一个进程有2个堆栈，用户堆栈和内核堆栈；用户堆栈的空间指向用户地址空间，内核堆栈的空间指向内核地址空间。当进程在用户态运行时，CPU 堆栈指针寄存器指向用户堆栈地址，使用用户堆栈，当进程运行在内核态时，CPU 堆栈指针寄存器指向的是内核栈空间地址，使用的是内核栈； 进程用户栈和内核栈之间的切换 当进程由于中断或系统调用从用户态转换到内核态时，进程所使用的栈也要从用户栈切换到内核栈。系统调用实质就是通过指令产生中断，称为软中断。进程因为中断 (软中断或硬件产生中断) ，使得CPU切换到特权工作模式，此时进程陷入内核态，进程进入内核态后，首先把用户态的堆栈地址保存在内核堆栈中，然后设置堆栈指针寄存器的地址为内核栈地址，这样就完成了用户栈向内核栈的切换。 当进程从内核态切换到用户态时，最后把保存在内核栈中的用户栈地址恢复到CPU栈指针寄存器即可，这样就完成了内核栈向用户栈的切换。 这里要理解一下内核堆栈。前面我们讲到，进程从用户态进入内核态时，需要在内核栈中保存用户栈的地址。那么进入内核态时，从哪里获得内核栈的栈指针呢？ 要解决这个问题，先要理解从用户态刚切换到内核态以后，进程的内核栈总是空的。这点很好理解，当进程在用户空间运行时，使用的是用户栈；当进程在内核态运行时，内核栈中保存进程在内核态运行的相关信息，但是当进程完成了内核态的运行，重新回到用户态时，此时内核栈中保存的信息全部恢复，也就是说，进程在内核态中的代码执行完成回到用户态时，内核栈是空的。 理解了从用户态刚切换到内核态以后，进程的内核栈总是空的，那刚才这个问题就很好理解了，因为内核栈是空的，那当进程从用户态切换到内核态后，把内核栈的栈顶地址设置给CPU的栈指针寄存器就可以了。 X86 Linux内核栈定义如下 (可能现在的版本有所改变，但不妨碍我们对内核栈的理解) : 在/include/linux/sched.h中定义了如下一个联合结构: union task_union { struct task_struct task; unsigned long stack[2408]; }; 从这个结构可以看出，内核栈占8kb的内存区。实际上，进程的task_struct结构所占的内存是由内核动态分配的，更确切地说，内核根本不给task_struct分配内存，而仅仅给内核栈分配8K的内存，并把其中的一部分给task_struct使用。 这样内核栈的起始地址就是union task_union变量的地址+8K 字节的长度。例如: 我们动态分配一个union task_union类型的变量如下: unsigned char *gtaskkernelstack gtaskkernelstack = kmalloc(sizeof(union task_union)); 那么该进程每次进入内核态时，内核栈的起始地址均为: (unsigned char *) gtaskkernelstack + 8096 进程上下文 进程切换现场称为进程上下文(context)，包含了一个进程所具有的全部信息，一般包括: 进程控制块 (Process Control Block，PCB) 、有关程序段和相应的数据集。 进程控制块PCB (任务控制块) 进程控制块是进程在内存中的静态存在方式，Linux内核中用task_struct表示一个进程 (相当于进程的人事档案) 。进程的静态描述必须保证一个进程在获得CPU并重新进入运行态时，能够精确的接着上次运行的位置继续进行，相关的程序段，数据以及CPU现场信息必须保存。处理机 现场信息主要包括处理机内部寄存器和堆栈等基本数据。 进程控制块一般可以分为进程描述信息、进程控制信息，进程相关的资源信息和CPU现场保护机构。 进程的切换 当一个进程的时间片到时，进程需要让出CPU给其他进程运行，内核需要进行进程切换。 Linux 的进程切换是通过调用函数进程切换函数schedule来实现的。进程切换主要分为2个步骤: ...

redis basic commands redis-cli -h 127.0.0.1 -p 6379 # -a 使用认证密码登录 redis-cli -h 127.0.0.1 -p 6379 -a password0 # -n 指定 db redis-cli -h 127.0.0.1 -p 6379 -a password0 -n 10 # OBJECT ENCODING 命令可以查看一个数据库键的值对象的编码 OBJECT ENCODING key0 # 分析 redis key 大小 debug object key0 # Value at:0x7f6bffc22a00 refcount:1 encoding:raw serializedlength:7164 lru:12841785 lru_seconds_idle:95 # 查看各个库的 key 数量 info keyspace # 不进入交互模式, 直接执行命令 redis-cli -h 127.0.0.1 -p 6379 hget key0 field0 延迟时间 redis-cli --latency -h 192.168.50.100 -p 6379 sort https://segmentfault.com/a/1190000002806846 ...

challenge response, 挑战应答 挑战应答方式”：challenge-response，是零知识证明的方式。 Challenge/Response认证的过程如下: 客户端向服务器发出认证请求； 认证服务器从用户数据库中查询用户是否是合法的用户，若不是，则不做进一步的处理； 认证服务器内部产生一个随机数，作为 “提问” / Challenge，发送给用户； 客户将口令和随机数合并，使用单向 Hash 函数 ( 例如MD5算法 ) 生成一个字节串作为Response； 认证服务器将 Response 与自己的计算结果比较，如两者相同，则通过一次认证，反之认证失败； 认证服务器通知客户端认证成功或失败。 以后的认证由客户不定时发起，过程中没有了客户认证请求一步。两次认证的时间间隔不能太短，否则就给网络、客户和认证服务器带来太大的开销；但也不能太长，否则不能保证用户不被他人盗用IP地址，一般定为1-2分钟。 密钥的分配和管理 密钥的分配由维护模块负责，当用户进行注册时，自行设定自己的口令。用户的密钥由口令生成。 一个口令必须经过两次口令检查。第一次由注册程序检查，强制口令必须有足够的长度。口令被加密后送入数据库，这个口令标记为“未检查的”。第二次，由离线的口令检查工具进行检查，将弱口令进行标记，当下次用户认证时，认证服务器将强制用户修改口令。 密钥的在线修改由认证服务器完成，其过程与认证过程基本类似。 Challenge/Response认证的安全性分析: 下面就常见的对认证服务器攻击方法来分析其安全性。 网络侦听 ( sniffer ) 认证过程中，密钥和口令不是明文不在网络上传输，所以sniffer很难从听到的报文中得到用户的口令。在密钥在线修改过程中，新口令使用旧密钥加密传送，sniffer 攻击仍然无效。 replay attack, 重放攻击 每次 challenge 不同，所以 replay attack 无效。 password guessing 在知道了认证算法后，侦听者可以对用户的口令进行猜测。这种攻击方法直接有效，特别是当用户的口令有缺陷时。解决方法是使用合适的口令。 跟踪地址攻击 攻击者在看到用户认证后，设法将自己的机器地址改为用户的IP地址，从而冒充用户。但由于攻击者无法完成后续的认证，在1-2分钟内，攻击失效。 https://blog.csdn.net/zy531/article/details/6205306 https://en.wikipedia.org/wiki/Challenge%E2%80%93response_authentication

“fork” 一个进程,包括代码、数据和分配给进程的资源。fork() 函数通过系统调用创建一个与原来进程几乎完全相同的进程,也就是两个进程可以做完全相同的事,但如果初始参数或者传入的变量不同,两个进程也可以做不同的事。 一个进程调用fork() 函数后,系统先给新的进程分配资源,例如存储数据和代码的空间。然后把原来的进程的所有值都复制到新的新进程中,只有少数值与原来的进程的值不同。相当于克隆了一个自己。 我们来看一个例子: /* * fork_test.c * version 1 * Created on: 2010-5-29 * Author: wangth */ #include <unistd.h> #include <stdio.h> int main () { pid_t fpid; //fpid表示fork函数返回的值 int count=0; fpid=fork(); if (fpid < 0) printf("error in fork!"); else if (fpid == 0) { printf("i am the child process, my process id is %d/n",getpid()); printf("我是爹的儿子/n");//对某些人来说中文看着更直白。 count++; } else { printf("i am the parent process, my process id is %d/n",getpid()); printf("我是孩子他爹/n"); count++; } printf("统计结果是: %d/n",count); return 0; } 运行结果是: i am the child process, my process id is 5574 我是爹的儿子 统计结果是: 1 i am the parent process, my process id is 5573 我是孩子他爹 统计结果是: 1 在语句fpid=fork()之前,只有一个进程在执行这段代码,但在这条语句之后,就变成两个进程在执行了,这两个进程的几乎完全相同,将要执行的下一条语句都是if(fpid<0)…… 为什么两个进程的fpid不同呢,这与fork函数的特性有关。fork调用的一个奇妙之处就是它仅仅被调用一次,却能够返回两次,它可能有三种不同的返回值: 1) 在父进程中,fork返回新创建子进程的进程ID； 2) 在子进程中,fork返回0； 3) 如果出现错误,fork返回一个负值； ...