GeekBand C++ Week14 Notes

海量数据问题的处理方法：

1.hash map

就是把任意长度的输入通过散列算法编程固定长度的输出。这种转换时一种压缩映射

哈希表，用来快速查找删除，通常要求总的数据量可以放入内存，散列值空间通常要小于输入空间，哪些问题可以用到hash表呢。

2.bit map用一个bit位来表示某个元素对应的value，而key是该元素。由于采用了bit为单位来存储数据，因此在存储空间方面可以大大节省。

3.bloom filter

4.heap堆是一种特殊的二叉树，每个节点的值都大于其子节点的值，树是完全平衡的，而且最后一层的树叶都在最左边，海量数据前n大，并且n比较小，堆可以放入内存、

5.双层桶，算法设计思想，无法处理的时候分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。第k大，中位数，不重复或重复的数字。因为元素范围很大，不能利用直接寻址表。所以通过多次划分逐步确定范围，然后最后在一个可以接受的范围内进行，可以通过多次缩小。双层只是一个例子，分治才是其根本。

6.数据库索引好比是一本书前面的目录，能加快数据库的查询速度，select * from table1 where id = 44如果没有索引必须遍历整个表，知道id等于44这一行被找到为止，有了索引以后必须是在id这一列上建立的所以，直接在索引里找44，也就是在id这一列找，就可以得知这一行的为止，也就是找到了这一行，由此可见索引是用来定位的。它还可以建立表和表之间的连接索引有这么多优点，那是不是可以给所有类建立一个索引呢。索引的缺点有创建维护索引的时候肯定要消耗时间的，比如插入或删除的时候，索引还要占据物理空间。

7.倒排索引是一种缩影方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。单词指向包含的文档，查询包含的单词

8.外排序外排序的归并方法，置换选择败者树，最优归并树

9.B+树，其构建过程中引入了有序数组，从而有效降低了树的高度，一次性取出一个连续的数组，这个操作在磁盘上比取出与数组相同数量的离散数据要便宜的多，所以磁盘上基本都是B+树的结构。比较次数比较少，存储系统一次性要读大块的数据，比一次性读小块数据要快，这里面可以做很多事情，可以查找一个区间。可以查找一个数，增加一个节点很容易，复杂度可控，hash表的话性能就要下降。

10.Trie tree又称字典树，字典查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。适用范围是数据量大，重复多，但是数据种类小可以放入内存的时候。利用字符串的公共前缀来节省空间。

11.分布式mapreduce，适用范围、：数据量大，数据种类小可以放入内存、

海量数据案例1.

上千万，或者亿数据，里面有重复，统计其中出现次数最多的前N个数据，分两种情况，可一次读入内存，不可一次读入。

能否一次性读入内存是去除重复数据量，建立一个字典，hash map来进行一个统计。当你在更新每条数据的时候，可以用堆来维护。这样会导致你维护的次数增多，如果你是无法放入内存的，可以考虑能不能加以改进。出现次数最多的前100个。你归并了以后不能保证找到的是真正最多的一百个。外排序会消耗大量的IO。效率不高。可以考虑近似统计，把实际中出现最多的放入内存。

设计一个可控制规模的社交网络系统，可以查找两个用户之间的关系。

在数据量不大的情况下，所有数据可以存放在同一台机器上，那查找两个用户的关系是单纯的搜索。

当数据量大的情况下，可以用相似的思路，用hash，用户的前几位数字决定存储在哪个机器上，获得用户的好友列表，ID机器名，再去访问机器ID的节点。访问另一台机器的成本可能比较高。所以相关的数据要一次读取完毕。节点有没有被访问过，防止重复的访问，可以建立hashmap，如果用户三层关系才可以联系上，可以判断两个用户是陌生的。

一个服务器有一个访问，设计数据结构可以判断上一秒，上一分和上一小时的访问量。

对每一个请求分配当前的一个时间戳，对时间戳进行排序，那就是有序序列。用二分查找通过快速的定位。一分钟之内访问到哪里。找到了对应的request,如何知道request已经进行了多少次请求，request可以计数，第几个。可以知道一共发生了多少次。复杂度。二分搜索某个特定时间request是log n

电商网站，单个机器MVC，在初期一台机器能承受的时候，CS和BS两种模型，browser的协议更加标准一些。MVC是一个分层的框架。简单的认为client提一个请求到web server上面，用一个控制器去请求数据库和文件资源再返还给用户。典型的网站结构，开源的技术。技术的选型

login: session和cookie

web server: apache/php/nginx

mvc: templates, spring

db: mysql

登陆的时候有session表。Cookie是在浏览器端的设置，通过cookie传递给server看看session是不是存在，可以认为cookie是明码，session是设立在服务器端的。

Nginx在异步和大规模并发的时候有很好的性能。

Mvc模板类

电商网站2.0版本。SOA

服务指向结构。

Cache APP server，DB server，fileserver.

遇到性能问题，第一反应就是加cache

SOA的一些特点，

Scaling

规模，graceful degradatron平稳地降级。

如果一个模块比方说评论或者广告宕机了，不能影响到整个网站的访问。要保证基本的核心能保证稳定的。

Reuse复用性。当我们搭建一些小的服务可以搭积木可以变成更强大的服务。

Ownership有责任。从设计到代码的完成，到监控和alert，

Simplification通过接口的方式。REST

电商网站3.0版本，多了一些组件，前面加了router反向代理。不同的请求放到app server上去。

海量数据案例2

聊天系统

facebook message wechat

工作流

Q2get new message

Pull和push，pull每隔三秒

Online status上次在线的时间。

Heart beat

每隔一分钟，自动去update

conversation list

数据抽样，长度为N的链表，不知道n有多大，遍历一次平均概率取出k个元素。

蓄水池抽样，保存k个元素，k+1开始

一次扫描每个元素，top k的算法。

Ab两个文件各存放50亿个url,每个占64字节，内存限制4G，找到ab文件共同的URL，存储到1000个小文件里，每个小文件

Bloom filter

有十个文件，每个文件1G，每一行是用户的query,每隔query都可能重复，按照query的频度排序