图解一致性哈希

起源

比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；

hash(object) % N

一切都运行正常，再考虑如下的两种情况；

1. 一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 …

蛤？什么是 raft 协议？

Raft 协议是一个分布式的一致性协议，主要通过 Leader Election 和 Log Replication 两个步骤来实现高可用的一致性状态存储。

这篇文章并不是 Raft 协议的一个完整介绍，只是其中核心概念的一个总结概括，要完全理解所有细节还是得看论文。

Leader 选举

1. 每个节点有三种状态：follower、candidate、leader。
2. 作为 leader 有任期(term)的概念，根据基本法必须选举上台。Term 是一个自增的数字。
3. 作为 leader 要不断发送心跳给 follower，告诉他们一律不得经商。
4. 所有节点都有一个随机的定时器（150ms~300ms），当 follower 没有收到日志后就会升级为 candidate，term + 1，给自己投一票，并且发送 Request Vote RPC 给所有节点，也就是 apply …

LSM 和 sstable

核心要点

lsm 是 bigtable、leveldb、rocksdb 等数据库采用的算法。

硬盘，尤其是机械硬盘，顺序写入性能远大于随机写入性能，所以 lsm 把大量的随机写入抓换成了顺序写入，从而极大地又花了写入能力。同时查找效率收到了损伤。

适用于顺序写入多，随机读取少的场景。

之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

操作

1. 插入

写入 WAL，然后操作 memtable。WAL 是顺序读写，而memtable 是跳表，操作都很迅速

1. 更新

和插入其实是一样的操作

1. 删除

插入一条特殊的删除日志，在 memtable 中标记删除

1. compaction（压缩）

当 memtable 达到设定的阈值的时候，会写入到 immutable memtable，然后写入到硬盘上的 …

红黑树

红黑树的要求：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

两篇不错的教程：

1. 漫画：什么是红黑树
2. 维基上的红黑树

动态规划（LeetCode 413. Arithmetic Slices）

LeetCode 413. Arithmetic Slice

是一道可以用动态规划解的问题

题目

给定一个数组，找出其中等差数列的个数。等差数列的定义：3各元素以上，每个元素之间差相等。

比如：

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

下面的就不是：

1, 1, 2, 5, 7

例子：

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3 …

大规模字符串的匹配

问题：假设我们有一组比较长的文本，每一个文本都有几十k左右，还有一些敏感关键词需要删除，大概有几千，然后需要在这些文本中把关键词找出来。

方法1：暴力搜索

import re

compiled_words = [re.compile(r'\b' + word + r'\b') for word in my20000words]

for sentence in sentences:
  for word in compiled_words:
    print(re.sub(word, "***", sentence))

改进1：把正则组合起来

pattern = "\b(word1|word2|word3)\b"

for sentence in sentences:
  print(re.sub …

跳表（skiplist）

平衡二叉树可以实现 O(logn) 的查找复杂度。跳表可以实现相当于平衡二叉树的复杂度查询数据，而代码实现比较简单。在 Redis 中，zset 就用到了 skiplist。

跳表是用并连的链表来实现的查询结构

• 每个节点包含的指针的层数是由一个随机数决定的。
• 跳表的时间复杂度和平衡二叉树相同，但是在实现上要简单很多。
• 跳表是有序的，跳跃表的特点就是有序的，所以对于一些有序类型的数据，比如整数，日期这种，用跳跃表可以进行范围查找。
• 在构建跳跃表和查询跳跃的复杂度一致，所以也比较适合于在线的实时索引查询，可以来一个文档，一边查找就一边知道要如何进行插入操作了。
• 保存到磁盘和从磁盘载入也比较简单，因为本质上是几个链表，所以保存的时候可以按照数组的方式分别保存几个数组就可以了。

一些优化

空间优化，把底层的表放到硬盘里，影响增加删除节点的效率

时间优化，用数组代替链表，可以使用二分查找而非遍历

对于类似时间这种数据，比如24小时对应1440分钟对应86400秒钟

甚至可以固定直接用索引随机访问

实现

https://github.com/begeekmyfriend/skiplist/blob/master/skiplist …

simhash

shingling

n-shingling 就是把一个句子或者文章分成 n 个连续单词的组合，然后去重。

比如： the cat sat on the cat

第一步，分组： the cat, cat sat, sat on, on the, the cat 第二步，去重： the cat, cat sat, sat on, on the

simhash 计算过程

生成 shingle

Reference

[1] http://matpalm.com/resemblance/jaccard_coeff/

[2] http://blog.csdn …

Jaccard coefficient(杰拉德距离)

the jaccard index is a simple measure of how similiar two sets are. it's simply the ratio of the size of the intersection of the sets and the size of the union of the sets.

eg.

if J(A,B) is jaccard index between sets A and B
and A …

Graph Theory

四个基础算法

http://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html