Top100summit-海量实时记录的索引方法——从兴技术钱善海

揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！海量实时记录的索引方法钱善海技术主管从兴技术有限公司揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！摘要•案例简介•需求分析•快速索引算法•系统实现要点•案例ROI分析海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！案例简介BOSS计费系统快速索引系统交换机打电话发短信上网流量营业厅网站自助终端移动终端生成记录处理记录查询记录海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！案例简介上线前上线后CPU:95%以上内存:100%文件IO:50~100M/s存储:30T查询:6秒以上到十几分钟使用Oracle存放部分索引CPU:5%以下内存:100%文件IO:2~5M/s存储:不变查询:小于1秒不使用Oracle海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！需求分析•总用户数1亿,每天活跃用户5000万•每天记录数40亿,高峰期达100万条/秒•每天数据量达600G•用户基本按月或天进行查询•用户可查10个月的历史数据•用户一天之内就有千万条记录•每天的查询量超过1000万人次海量实时记录的索引方法•大量的延迟记录,不仅是今天有昨天的,今天还有前几个月的揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！使用快速合并算法每一条记录只需进行下面的操作,即能完成最终的索引:•读1次•压缩2次(gzip算法)•解压缩1次•写1次读取120G数据写到内存,同时进行压缩文件系统解压输出海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！把一天的数据放到内存中•使用多块内存•每个内存有多个页(page)•每个page有多个溢出页•记录(key,value)放到第crc32(key)%mem_total个内存中的第reverse_crc32(key)%page_total个块中•使用30个内存•每个内存4G,•每个page约64Kpage1page2pageH内存溢出页海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！使用分块压缩每一个page的结构:[C1][C2][C3]…[Cn]R1R1R2R1R2…RqC1R1C1R1R2R3…RkC1C2R1page1page2pageH内存溢出页海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！快速索引算法内存1内存2内存n文件1文件2文件n……file_datafile_index偏移量海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！快速索引算法……file_datafile_indexr1r2rH偏移量Key:整数0~H-1Value:偏移量,长度•使用30个内存•每个内存4G,•每个page约64Kpage1page2pageH内存溢出页海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！快速索引算法page1page2pageH内存溢出页d1d2d3difile_datapageiS1S2S3Sk1.若记录数超过1/k,则该Key单独占用一个Si2.其它的记录按照该key均匀分到剩下的Si中海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！快速索引算法file_datafile_indexr1r2rHKey:整数0~H-1Value:structfile_index_value{charindex[5];len[k];/*每个len[i]占3byte*/charflag;intcrc32[k];};sizeof=55byte或约60byteH=60000,K=7每个file_index大小:H*30(内存个数)*60=103M所有file_index大小:103M*31=3G每天每个号码只占索引:103M/5000万(活跃用户)=2byte海量实时记录的索引方法……揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！效率•读1次•压缩2次(Gzip算法)•解压缩1次•写1次海量实时记录的索引方法从内存解压输出到文件只需30分钟,使用读取内存：最多遍历10个page读取文件：只需读取一个文件中的约31个=10K块CPU:5%文件IO:2~5M/s查询1000条记录:=0.05秒查询5000条记录:=0.5秒查询10000条记录:=0.5秒步骤1步骤2结果建立索引的效率查询效率处理每天输出系统资源揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！系统实现要点•只有两个模块：索引模块和查询模块•不能也无需使用排序•使用快速的合并算法•系统崩溃如何快速恢复内存•注意延迟单的处理海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！案例ROI分析开发人力40人月开发成本:50万利润:150万海量实时记录的索引方法揭示研发管理白金定律，分享那些激动人心的创新与变革，使得团队获得过多源动力与更大的推动力！