中等规模海量数据处理实例分析.ppt

中等规模海量数据处理实例分析 王斌 BI 组 2009-12-04 内容 项目简介 流程 演化过程 遇到的若干问题 支撑技术 总结 项目简介 本项目通过分析用户访问标题的log日志文件，提取出用户的喜好，进而为广告投放提供精准支持 此项目属于web使用挖掘的一个应用 项目简介 log数据 单日压缩文件约为10G，压缩比约为8 需要整合一个月的数据 总共约2T~3T数据 用户数量 约1.5亿 目前一个月活跃标题数量 约1400万，支持3000万标题数量 项目简介 硬件环境 4 CPU 4G内存 编程环境 c++ vim+ctags+cscope g++ gdb 流程 演化过程—项目开始前（2008.04） 动手做程序前，有过类似的经验，但所处理的数据量不大。 当时具备的知识如下： 诊断性能瓶颈 多线程技术 定长技术 二进制技术 抽取公共信息 缓存技术 双备份技术 有一定的数据结构和算法基础 演化过程—项目初期（2008.05） 目标：简单流程开发完毕，优化以后再做 遇到的主要问题： 计算所的开源词库错误百出 有道的词库软件因为版权问题不能用 演化过程—项目进展中（2008.06） 目标：做一些优化工作 遇到的问题： 计算所的开源词库性能非常差，百万标题需要一千秒 分词本身带来不少误差问题 内存碎片问题 探索： 利用kmp算法+trie树来解决关键词的提取 演化过程—项目进展中（2008.07～08） 通过不断地探索，关键词提取已经有了方案，不过偶然发现前人已经解决了关键词提取的问题，而且解决地更好，就采用了前人的算法 -----多模式串匹配算法 演化过程—项目进展中（2008.09～10） 遇到的问题： 运行时间越来越长，甚至到了不可用的地步 存储量也越来越大 解决方案： 原来文本文件方式改造成二进制文件方式 采用缩短用户id长度和标题id长度的策略减少计算时间和存储量 信息采用定长方式 演化过程—项目进展中（2008.11～12） 遇到的问题： 二进制文件越来越大 标题越来越多，导致性能恶化 耗用的内存也越来越大，接近3G限制 解决方案： 分割大文件 淘汰很久没有访问过的标题 查询大数据量时用hash，小数据量用红黑树 及时释放不再需要的内存 遇到的若干问题 如何快速处理如此多的数据？ 如何快速提取关键词？ 海量信息如何保存？ 如何解决大内存问题？ 标题如何淘汰？ 如何解决高容错？ 如何快速发现问题？ 支撑技术 诊断性能瓶颈 数据结构和算法 多线程技术 磁盘IO技术 定长技术 位技术 二进制技术 数学概率 抽取公共信息 缓存技术 裁剪技术 内存池技术 双备份技术 调试技术 诊断性能瓶颈 主要内容 利用gprof来查找性能瓶颈（最好是单线程的程序） 80%的执行时间花在20%的代码上 举例：能够找到性能比较差的函数 主要用来解决如下问题 快速处理海量数据 数据结构和算法 思想 不同规模的数据量，用不同的数据结构和算法 减少不必要的操作 主要用到的数据结构和算法 多模式串匹配算法 (log处理过程中非常有用) nth element算法 Hash （数据量大时） 红黑树（中小规模用） 各类排序算法 倒排索引 外部排序 主要用来解决如下问题： 快速处理海量数据 快速提取关键词 多线程技术 主要技术点 并发执行，充分利用4 CPU 流水线技术 主要用来解决如下问题 快速处理海量数据 磁盘IO技术 主要技术点 磁盘读要顺序读，顺序写（性能比随机读快10倍左右） 磁盘读写磁盘要分开，一个读磁盘，一个写磁盘 分割大文件（大文件性能一般比小文件差） 压缩技术（log文件都是压缩文件） 缓存（上一页，有缓存，不是逐个记录读取的） 主要用来解决如下问题 快速处理海量数据 高容错 定长技术 主要内容 每个标题长度是不一样的，每个url长度也是不一样的 不定长需要转变为定长 主要采用md5技术（md5转换程序每秒处理能力在百万级别左右） 主要用来解决如下问题 快速处理海量数据 海量信息保存 解决大内存问题 位技术 主要思想 充分分析数据的特性，以位为单位，而不是字节为单位来存储信息。 主要用来解决如下问题 快速处理海量数据 海量信息保存 解决大内存问题 位技术举例 假如用户访问17个站点信息，每个站点的信息值在0～7之间 常规做法： 用1个字节来保存每个站点的信息，因此需要17个字节(17×8bits=136bits) 来保存用户访问站点的信息 新系统做法： 由于每个站点的信息值在0～7之间，所以可以用3个位信息即可保存。 需要的空间为17×3=51bits ，用7字节(56bits)即可保留用户访问站点的信息。 本系统采用了这种方式后仅仅对于原用户细分系统的2千万用户数据，只需600M的内存（原系统1.7G