Neo's Blog

ELK方案

• elastic search

对日志进行分词，并建立倒排索引

• log stash

日志采集

• Kibana

设计DNS服务器中cache的数据结构。

要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）

回答：

DNS服务器实现域名到IP地址的转换。

每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。

总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）

可以考虑的数据结构包括hash_map，字典树，红黑树等等。

核心思想：估算、哈希

问题：
求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。
回答：

可能需要想到的思路：哈希、bloomfilter

问题：
某海量用户网站，用户拥有积分，积分可能会在使用过程中随时更新。现在要为该网站设计一种算法，在每次用户登录时显示其当前积分排名。用户最大规模为2亿；积分为非负整数，且小于100万。

回答：

存储结构
首先，我们用一张用户积分表user_score来保存用户的积分信息。表结构：

下面的算法会基于这个基本的表结构来进行。

实时输出最近一个小时内访问频率最高的10个IP，要求：
（1）实时输出
（2）从当前时间向前数的1个小时
（3）QPS可能会达到10W/s

Feed系统的本质就是一个相对更加简单的IM系统。

推模式

• 写入延迟问题：并行写入，对存储到写入压力大，更牛B的写入存储引擎：LevelDB、TokuDb等
• 存储量特别大：压缩率更高的存储引擎 + 定期清理数据
• 微博分组，更是扩大了写入量
• 取消关注、删除微博等操作对该模式影响也很大（可以通过读时过滤来解决）

问题重重，feed推模式，更适合粉丝有限的场景，例如朋友圈

拉模式

用户发件箱，来缓存UP最近5天发布的微博

缓存节点的带宽成本比较高，可以通过多缓存副本来解决。

推拉结合

1. 按照用户是否活跃在线与不在线
2. 按照UP的粉丝数来划分
3. 区分关注的普通人与大V

• 基于名单库

hash、布隆过滤器等

• 基于规则

人为找出规则-包含哪些词的是垃圾｜需要有样本数据，然后进行机器学习-基于出现频次

• 基于概率统计（朴素贝叶斯）

如果一条短信包含了A，B，C等N个词，那么这条短信是垃圾短信的概率是多少呢

问题：

从300万字符串中找到最热门的10条搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前10条，我们每次输入的一个字符串为不超过255byte，内存使用只有1G。请描述思想，写出算法（c语言），空间和时间复杂度。

答案：

300万个字符串最多（假设没有重复，都是最大长度）占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。

可以使用key为字符串（事实上是字符串的hash值），值为字符串出现次数的hash来统计每个字符串出现的次数。

并用一个长度为K的堆来的数组/链表存储目前出现次数最多的10个字符串。

设计要点：

长链接接入网关

• 接入层：如何做负载均衡（基于IP 还是 基于7层的用户唯一标识）
• 就近接入
• 接入层如何升级：尽量减少升级（否则断开连接），拆分为负责连接的进程与负责处理业务的进程，两者之间通过共享内存通信