海量数据去重的hash

1 背景使用word文档时word如何判断某个单词是否拼写正确网络爬虫程序怎么让它不去爬相同的url页面垃圾邮件过滤算法如何设计公安办案时如何判断某嫌疑人是否在网逃名单中缓存穿透问题如何解决平衡二叉树增删改查时间复杂度为 O(logn)平衡的目的是增删改后保证下次搜索能稳定排除一半的数据O(logn)的直观理解100万个节点最多比较20次10亿个节点最多比较 30次因此平衡二叉树的有序性是通过比较保证的通过每次排除一半的元素达到快速索引的目的2 散列表hash表而散列表则是通过key进行一定的处理哈希函数处理对数组长度取余后在对应的数组的索引位置存储。根据 key 计算 key 在表中的位置的数据结构是 key 和其所在存储地址的映射关系注意散列表的节点中 kv 是存储在一起的struct node { void *key; void *val; struct node *next; };2.1 hash函数映射函数 Hash(key)addrhash 函数可能会把两个或两个以上的不同 key 映射到同一地址这种情况称之为冲突或者hash 碰撞hash函数的选择计算速度快强随机分布等概率、均匀地分布在整个地址空间murmurhash1murmurhash2使用最多murmurhash3siphash redis6.0 当中使用rust 等大多数语言选用的 hash 算法来实现 hashmapcityhash 都具备强随机分布性测试地址如下https://github.com/aappleby/smhashersiphash 主要解决字符串接近的强随机分布性负载因子数组存储元素的个数 / 数组1长度用来形容散列表的存储密度负载因子越小冲突概率越小负载因子越大冲突概率越大2.2 冲突处理链表法引用链表来处理哈希冲突也就是将冲突元素用链表链接起来这也是常用的处理冲突的方式但是可能出现一种极端情况冲突元素比较多该冲突链表过长这个时候可以将这个链表转换为红黑树、最小堆由原来链表时间复杂度O(n)转 换为红黑树O(logn)时间复杂度那么判断该链表过长的依据是多少可以采用超过 256经验值个节点的时候将链表结构转换为红黑树或堆结构java hashmap开放寻址法将所有的元素都存放在哈希表的数组中不使用额外的数据结构一般使用线性探查的思路解决当插入新元素的时使用哈希函数在哈希表中定位元素位置检查数组中该槽位索引是否存在元素。如果该槽位为空则插入否则3在 2 检测的槽位索引上加一定步长接着检查2 加一定步长 分为以下几种i1,i2,i3,i4, ... ,ini-1^2 ,i2^2 ,i-3^2 ,14^2, ... 这两种都会导致同类 hash 聚集也就是近似值它的hash值也近似那么它的数组槽位也靠近形成 hash 聚集第一种同类聚集冲突在前第二种只是将聚集冲突延后另外还可以使用双重哈希来解决上面出现的hash聚集现象下面要讲的布隆过滤器也是使用双重哈希的方式解决hash聚集的现象在.net HashTable类的hash函数Hk定义如下 Hk(key) [GetHash(key) k * (1 (((GetHash(key) 5) 1) %(hashsize – 1)))] % hashsize 在此 (1 (((GetHash(key) 5) 1) %(hashsize – 1))) 与 hashsize互为素数两数互为素数表示两者没有共同的质因⼦ 执⾏了 hashsize 次探查后哈希表中的每⼀个位置都有且只有⼀次被访问到也就是说对于给定的 key对哈希表中的同⼀位置不会同时使⽤Hi 和 Hj2.3 stl中实现的散列表结构在 STL 中 unordered_map、unordered_set、 unordered_multimap、unordered_multiset 四兄弟底层实现都是散列表stl实现的散列表对原始的散列表进行了优化如上图所示。原因是stl需要对迭代器进行封装即需要方便寻找某个节点所在的位置。所以有一个_M_before_begin的节点作为头节点将所有节点串成一个链表的结构。而数值中的索引指向的不是所在所以位置的第一个节点而是指向上一个节点所存储索引位置的最后一个节点。插入节点时类似一种头插法的感觉。3 布隆过滤器3.1 背景上面所讲的数据结构如红黑树、散列表、B树和B树都是采用的存储k和v数据。但是实际上有时候我们并不需要知道key具体对应的value的值我们只需要知道对应的key是否在某个容器中。那么这时候就可以使用布隆过滤器布隆过滤器是一种概率型数据结构它的特点是高效地插入和查询能确定某个字符串一定不存在或者可能存在布隆过滤器不存储具体数据所以占用空间小查询结果存在误差但是误差可控同时不支持删除操作例如我们需要在mysql数据库中插叙某个key对应的值直接查询需要经过网络交互和查找过程我们可以先在服务器部署一个布隆过滤器先判断是否存在于mysql中再进行查询。3.2 构成如上图所示我们可以采用byte buf[8]数据来表示64bit的位图1byte 8bit然后通过对key进行hash计算出一个值映射到位图中在对应索引位置中置为1。3.3 原理当一个元素加入位图时通过 k 个 hash 函数将这个元素映射到位图的 k 个点并把它们置为 1当检索时再通过 k 个 hash 函数运算检测位图的 k 个点是否都为 1如果有不为 1 的点那么认为该 key 不存在如果全部为 1则可能存在 为什么不支持删除操作在位图中每个槽位只有两种状态0 或者 1一个槽位被设置为 1 状态但不确定它被设置了多少次也就是不知道 被多少个 key 哈希映射而来以及是被具体哪个 hash 函数映射而来只要一个索引位为0就一定不存在如果都为1是否一定存在不一定可控的假阳率3.4 应用分析在实际应用中该选择多少个 hash 函数要分配多少空间的位图预期存储多少元素如何控制误差n -- 预期布隆过滤器中元素的个数如上图 只有str1和str2 两个元素 那么 n2 p -- 假阳率在0-1之间 m -- 位图所占空间 k -- hash函数的个数 公式如下 n ceil(m / (-k / log(1 - exp(log(p) / k)))) p pow(1 - exp(-k / (m / n)), k) m ceil((n * log(p)) / log(1 / pow(2, log(2)))); k round((m / n) * log(2));Bloom filter calculator可以使用这个网址通过n和p计算对应的m和k的值上图引申出一个面试题在很多的hash函数中经常出现‘31’这个数字为什么原因可以通过上面这个图看出来其实时一个经验值当khash函数个数为31时假阳率或者冲突概率最低。那k个hash函数如何做到几十个hash函数呢选择一个 hash 函数通过给 hash 传递不同的种子偏移值采用线性探寻的方式构造多个 hash 函数#define MIX_UINT64(v) ((uint32_t)((v32)^(v))) uint64_t hash1 MurmurHash2_x64(key, len, Seed); uint64_t hash2 MurmurHash2_x64(key, len,MIX_UINT64(hash1)); for (i 0; i k; i) // k 是hash函数的个数 { Pos[i] (hash1 i*hash2) % m; // m 是位图的⼤⼩ }3.5 应用场景布隆过滤器通常用于判断某个 key 一定不存在的场景同时允许判断存在时有误差的情况常见处理场景① 缓存穿透的解决② 热 key 限流描述缓存场景为了减轻数据库mysql的访问压力在server 端与数据库mysql之间加入缓存redis用来存储热点数据描述缓存穿透server端请求数据时缓存和数据库都不包含该数据最终请求压力全部涌向数据库数据请求步骤如图中 2 所示发生原因黑客利用漏洞伪造数据攻击或者内部业务 bug 造成大量重复请求不存在的数据解决方案如图中 3 所示拓展知识缓存击穿 vs 缓存穿透 vs 缓存雪崩缓存穿透查询不存在的数据缓存和数据库均无记录恶意攻击。缓存雪崩大量缓存同时失效导致请求批量击穿到数据库。缓存击穿单个热点数据失效引发集中式高并发请求。某个热点数据在缓存过期或失效的瞬间大量并发请求直接穿透缓存层直接访问数据库对应解决方案缓存穿透可以使用布隆过滤器或者缓存空对象的方式解决。缓存雪崩缓存数据过期时间分散在设置缓存过期时间时增加随机值如base_time random_delta避免同时失效。多级缓存架构使用本地缓存如 Guava Cache作为一级缓存Redis 作为二级缓存分散压力。热点数据永不过期对极热点数据设置永不过期通过异步线程主动更新。限流与降级使用熔断器如 Hystrix限制并发请求量或直接返回默认值缓存击穿使用互斥锁在缓存失效时只允许一个线程去重建缓存其他线程等待实现过程请求发现缓存未命中时尝试获取分布式锁如 Redis 的SETNX。获取锁成功的线程查询数据库并重建缓存。其他线程等待锁释放后直接从缓存读取数据。Q在2GB 内存限制下从20 亿个整数中找到出现次数最多的数4 分布式一致性hash4.1 背景分布式一致性hash解决的是多个节点分布式缓存扩容的场景比如之前所学的redis的cluster集群一样。数据库的数据不会存储在一个节点中而是采用主从节点进行存储。如上图所示一个server端和三个redis端的节点三个节点对应着不同的机器。首先在server端对key进行运算确定存储到哪个节点中进行分布式的存储。但是当增加一个节点后就会有一个问题那么我们hash算法就会发生改变。原来对3取余就会变成对4取余。那么就会出现缓存失效的问题即扩容后算法改变后原来存储的某些索引再次查询时就找不到了。于是就引出了分布式一致性hash的解决方法先固定算法。分布式一致性 hash 算法将哈希空间组织成一个虚拟的圆环圆环的大小是2^32算法为hash(ip) %2^32最终会得到一个 [0,2^32-1 ] 之间的一个无符号整型这个整数代表服务器的编号多个服务器都通过这种方式在 hash 环上映射一个点来标识该服务器的位置当用户操作某个 key通过同样的算法生成一个值沿环顺时针定位某个服务器那么该 key 就在该服务器中;但是此时如果进行扩容仍然会出现缓存失效的问题如下图所示即原来用户2的数据时存储在服务器2中的扩容后我们查询时会在服务器3进行查询很明显是不可能查询到数据的因此出现缓存失效。但是这个缓存失效时小部分的缓存失效只是在用户2和服务器3之间的数据失效只需要将这一部分的数据进行迁移即可。4.2 hash偏移我们知道hash算法的强随机分布性的当样本数过少的时候就有可能出现一个问题如下图所示服务器的节点可能聚集在某个位置不能保证服务器节点均匀分布在哈希环上分布不均匀造成请求访问不均匀服务器承受的压力不均匀hash偏移问题本质就是样本数过少的问题为了解决哈希偏移的问题增加了虚拟节点的概念理论上哈希环上节点数越多数据分布越均衡为每个服务节点计算多个哈希节点虚拟节点通常做法是hash(IP:PORT:seqno) %2^32即可以在每个ip和端口之后再添加一个序列号的方式从而增加节点而存储的时候只需要截取前面的ip和端口即可确定对应存储的节点而且这种密集存储可以减少hash迁移的数据量。