面试--- 关于海量数据问题的处理具体解释

 

问题：

微博有11亿的用户，当中大约50万是蓝V用户，用户用uid标示，试设计一套架构，推断一个用户是否是蓝V，画出架构图，并给出关键算法。要求消耗的内存最小。效率最高。同一时候可以适应蓝V用户的动态增减。

 

海量数据问题的处理

个人感觉：这个题不仅考察了基础，同一时候又有project上的引申

 

思路：

（1）发现这是个类似redis的架构，KV（key-value）的结构：key是uid，（uid应是内部系统中用来表示用户的user id，是一个字符  串）；value用一个位表示就可以。0或1，1表示是蓝V用户

（2）索引与hash，在涉及到查找的时候。能够使用一些数据结构中的知识，如红黑树。字典树。跳表，hash之类的，在这里。我考虑了一下，hash的效率是最高的，尽管它有大量的key是无法命中的，也会浪费一些存指针的空间，可是在瞬间性推断是否是该key的性能上是高的

（3）多机的可扩展性，因为数据量太大，单机的话内存可能无法hold住，这时候能够利用多机的可扩展性来解决，貌似涉及到分布式中的一致性哈希问题，这个不太熟悉，查阅后发现能够进行数据的动态处理的。

 

算法：

1、内存消耗最小

（1） 能够将全部的蓝V的uid通过hash变成一个key来表示，其余的非蓝V数据不存。这种话在查找的时候直接就来推断是否命中   key。命中了那么就是蓝V；

（2） 对于key，能够採用Bit-map和Bloom Filter来优化内存空间的消耗。因为採用了Bit为单位来存储数据。因此在存储空间方面。   能够大大节省。

2、效率最高

（1）    涉及到效率，就非常easy想到hash和查找树，所以这个key非常关键。在这里我採用了hash，尽管它有大量的key是无法命中的。  也会浪费一些存指针的空间。可是在瞬间性推断是否是该key的性能上是高的

（2） 关于uid。这是内部系统中用来表示用户的user id，是一个字符串，应该存在分级或者分布式存储的规律，比方省市级的数据分布区域划分，这种话就能够降低查找的范围，优化效率

3、适应性增减

（1）这里因为数据量太大，单机下内存无法hold住。所以涉及到了多机的可扩展性，这里关于添加，能够採用一致性哈希来进行机器的平缓的加入，降低的话貌似须要依据数据量来先分配内存。详细的细节待思考。

涉及知识点：

一、Bloom Filter

基础操作

  位数组+k个独立hash函数。

将hash函数相应的值的位数组置1，查找时假设发现全部hash函数相应位都是1说明存在，非常明显这个过程并不保证查找的结果是100%正确的。同一时候也不支持删除一个已经插入的keyword，由于该keyword相应的位会牵动到其它的keyword。

所以一个简单的改进就是 counting Bloom filter，用一个counter数组取代位数组。就能够支持删除了。 

扩展性问题

    Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。

Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF採用counter中的最小值来近似表示元素的出现频率

 

二、hash索引

  哈希查找是通过计算数据元素的存储地址进行查找的一种方法。哈希查找的操作步骤：

  ⑴用给定的哈希函数构造哈希表；⑵依据选择的冲突处理方法解决地址冲突;⑶在哈希表的基础上运行哈希查找。

   哈希查找步骤为：

设哈希表为HST[0~M-1]，哈希函数取H（key）。解决冲突的方法为R（x）；

Step1 对给定k值，计算哈希地址 Di=H（k）；若HST为空，则查找失败。

若HST=k，则查找成功；否则。运行step2（处理冲突）。

Step2 反复计算处理冲突的下一个存储地址 Dk=R（Dk-1）。直到HST[Dk]为

空，或HST[Dk]=k为止。

若HST[Dk]=K，则查找成功，否则查找失败。

三、redis

基于redis分布式缓存兑现