有趣的算法(十) ——归并排序思想解决大量用户数据清洗

有趣的算法(十)——归并排序思想解决用户数据清洗

(原创内容,转载请注明来源,谢谢)

一、问题阐述

近期工作中接触到一个很有趣的算法,在此进行分享。

当前有一个千万条级别的用户数据,其中包含用户openid、用户是否有效状态。其中,这些用户是关注微信公众号的用户,openid是可以从微信拿到的接口中,确定的用户信息。

每个用户关注或者取消关注,系统可以从微信接口中获取信息,并且每个新关注的用户,系统会搜索现有库,如果用户openid已经在数据库中存在,则将其状态置为有效;如果用户不存在,则新增一条记录,并将状态置为有效;每个取消关注,系统会将相应的状态置成无效。

由于关注量巨大,每次发送文章的时候,不能采用一键发送给全部人的方式,这样运算量太大,会导致系统数据库资源耗尽,无法提供其他的服务。由于消息没有要求实时性,采取的做法是调用脚本,每隔若干秒给某一批用户发送文件,保证瞬时请求量不会太大。

现在由于某些历史原因,导致部分关注的用户没有记录到数据库中(或状态没有置有效),部分取消关注的用户状态没有相应的置无效,导致发送文件的时候,会存在部分关注的用户收不到文件,而又存在部分无效的发送(没有关注的用户无法对其发送文件)。这两者的差量在百万级别。

为了解决此问题,需要对用户数据进行清洗,将当前没有关注的用户状态置无效;将关注的用户新增或置有效。另外,由于该表中还存在其他字段数据,因此不能直接抛弃该表重新建一个新表。

二、解法分析

微信提供了接口,可以获取当前关注公众号的所有用户的openid。通过比对微信提供的openid数组,与当前系统的用户数组,即可找出系统中不再关注的用户将其状态置无效;找出微信中关注的用户不在系统中的或状态不是有效的,添加或置成有效状态。

对大数据量的问题的解决方案,通常在消耗时间节约空间和消耗空间节约时间两方面来解决。

假设当前数据库字段openid、status。其中status是1表示用户关注,0表示用户取关。

1、暴力解法一——逐一比对法

最简单粗暴的方式,可以给数据库新增一个字段(假设名称为newstatus,默认值设置为0),然后遍历微信接口提供的openid,在系统的数据库中查找数据:如果存在,则将newstatus置成1;如果不存在,则插入一条数据,并将newstatus置1。

遍历完成后,所有微信公众号当前的关注用户的newstatus都是1,其余都是默认值0。再删除status字段即可。

此方式主要问题在于数据库的长连接,而且速度会极其缓慢,解决方式不够优雅。

2、暴力解法二——hash法

hash法会占用较大的内存,但是hash是键值对的存储方式,其速度相对来说足够快。

具体做法是,首先将数据库中的用户数据,以openid-status的方式,进行key-value的存储,其中取出的openid的status全部初始化为0,假设数组名称为system。接着,遍历从微信获取到的全部openid(假设数组名称为weixin),如果某个openid不在system数组中,则在hash中新增一条记录,并将status置为1;如果hash中存在,则直接将状态置1。

接着遍历hash,将status为0的,把数据库中的状态置成0;status为1的,如果不存在则新增,如果存在则置成1。

3、归并排序解法重要内容介绍

上述做法的一大问题在于,一次性要将千万级的数据存在内存中,将会占用好几个g的内存。虽然几个g现在的情况是可以满足的,但是如果数据量增长到过亿,甚至更多的时候,则无法解决此问题。

由于相对于内存来说,硬盘的容量远大于内存。下面采取一个消耗硬盘节约内存的方式的解决方案,相对来说优雅可行。

1)归并排序

由于解决方案依赖于归并排序,则先简要介绍归并排序的思想。

假设数组为[4,1,2,7,5,3,8]。归并排序采用的是并归法的解决方案。首先将整个数组拆成每个独立的元素,上述数字拆成[4]、[1]、[2]…[8]。

接着,两两进行合并,合并的同时进行排序。例如[4]、[1]合并成[1,4]。整个数组会合并成[1,4]、[2,7]、[3,5]、[8]。

接着,将新的数组再两两进行合并,现拿[1,4]、[2,7]合并进行举例。每个数组有一个指针,指向第一个元素。将1和2比较,1比较小,则1进入新数组[1]。接着指针指向4,再和2比,此时2比较小,则2进入新数组[1,2],接着指针指向7。最终数组是[1,2,4,7],另外一边则是[3,5,8]。

最终将整个数组合并成一个数组,则排序完成。

2)外部排序

由于一次性读入大量文件,占用太多的内存,故可以采用分批读取的方式,节约内存。具体做法是,可以根据当前内存可以承载的数量,现假设每次从数据库中读取100万条记录(约100MB),并写入一个文件。这样会将1000万条记录写入10个文件中。从微信读出来的记录(假设也是1000万条)写入到另外10个文件中。这样没有一次性读取全部内容,则不会使用那么多的内存。

3)状态机(核心)

两两比较微信数据和数据库的openid,存在三种情况:微信的openid大于、等于、小于数据库的openid。

现假设状态A是微信openid大于数据库的openid。定义如果数据库的该openid状态是1,则置成0;如果是0,则不进行操作。(即确保数据库的此数据置无效)

假设状态B是微信openid等于数据库的openid。定义如果数据库的该openid状态是0,则置成1;如果是1则不操作。(即确保数据库的此数据置有序)

假设状态C是微信openid小于数据库的openid。定义此情况下,需要将微信的openid保存到数据库中,并且置状态为1。(即新增数据)

4)联动处理(核心)

当遍历两个由openid组成的数组,一个是数据库查出来的openid,一个是微信提供的openid。

指针初始态分别在两个数组的第一个元素。

联动A:如果出现状态A,进行完状态机的处理后,指向数据库openid数组的指针往后移一个元素。

联动B:如果出现状态B,进行完状态机的处理后,指向两个openid数组的指针都往后移一个元素。

联动C:如果出现状态C,进行完状态机的处理后,指向微信openid数组的指针往后移一个元素。

三、具体解法

具体的步骤如下:

1、从微信处拉取1000万条记录,每100万条记录存放在一个文件中。

2、从数据库中拉取1000万条记录,每100万条记录存放在一个文件中。

3、使用归并排序或者快速排序等方式,对这20个文件中的数据,分别进行排序,使得每个文件中都是相对有序的(即在文件内部是有序的)。

4、使用归并排序的方式,分别对微信数据与系统数据的openid进行排序。

两者方式一样,拿系统数据举例。打开10个文件,每次取10个文件的当前行进行比较,最小的文件存到新文件中,并且指针后移,再和其他文件进行比较。如果新文件的记录超过100万个,则新开一个文件。

完成排序后,再删除无序的微信和数据库的数据文件。则分别得到10个按openid有序的微信用户数据文件,和10个系统用户数据文件。

5、新建三个文件,分别是待新增(文件B)、待置状态为1(文件C)、待置状态为0(文件D)文件。

6、(归并排序思想解决方案核心)从微信的第一个文件和系统的第一个文件,分别将全部数据载入到两个数组中,此时内存中有200万条记录,消耗约200MB。用两个指针,从微信的数组和系统的数组中进行遍历,每次两边各取出一条记录。

由于文件都是有序的,因此在比较边的元素的时候,如果从某个数组(微信或数据库)取出一个openid,则表示该数组中比这个openid还要小的元素都已经完成了比较。例如从微信数组取出一个10,则表示比10还要小的openid都已经比较完毕。(注:实际上的openid是一个32位的字符串,这里只是简单举例)

接着,从数组中取出元素,就可以按照上述的状态机以及相应的联动方案,进行比较。当一个数组比较完毕后,则从其相应的文件中取出下一个文件中的全部数据。(例如系统的文件1都已经完成比较,指针指向null,则从系统的文件2中取出全部的100万条数据,记录和微信的数组进行比较)

7、结束条件

如果微信的数据先比较完毕,则表示数据库查出来的剩余文件的数据都是用户已经取消关注的,直接状态都置0即可;如果数据库的文件先遍历完成,则表示剩下的微信的数据都是新关注的用户而未存在数据库中的,直接全部都新增到数据库中并将状态都置1即可。

四、总结

上述做法由于都是在文件中进行的,因此存在的问题是在清洗期间如果存在用户的关注情况变化,会导致这部分数据存在问题。尤其是原先取消关注的用户又重新关注,而在文件中由于其状态是取消关注,则状态还会置成无效,导致其收不到文章。

对于此的解决方案,则是由于这个过程耗时不会太久,数小时内可以完成。因此对于这段时间内关注、取关的用户专门插入到一个临时表中,待上述数据清洗完毕后,在对这部分数据单独处理。由于数据量不会太大(数小时内关注、取消关注量一定不会太大,最多也就是万级别的数量),因此单独处理成本也不会太高。

另外再次申明,近期我有比较重要的事情,因此更新文章速度非常缓慢。我再次深表歉意,也非常感谢仍关注我的各位朋友们。明年开始我准备开始着手机器学习相关的内容,公众号的名称、内容方向也将有所改动,但是我仍然会关注web架构的内容,毕竟这块我还是很感兴趣。明年1月开始文章的发表频率会重新增高,非常感谢各位。

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-11-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

Java虚拟机工作原理之JVM用到的3大计算机核心功能,重点是方法调用

JVM是Java Virtual Machine(Java虚拟机)的缩写,JVM是一种用于计算设备的规范,它是一个虚构出来的计算机,是通过在实际的计算机上仿真模...

693
来自专栏Netkiller

消息队列在使用中的注意事项

消息队列在使用中的注意事项 异步不是万能的,实现异步重要的手段,消息队列在使用中也是有很多注意事项的。 消息队列的瓶颈 消息队列至少有三处容易出现瓶颈,我们一经...

2792
来自专栏WindCoder

网易MySQL微专业学习笔记(十一)-MySQL业务优化与设计

这个系列属于个人学习网易云课堂MySQL数据库工程师微专业的相关课程过程中的笔记,本篇为其“MySQL业务优化与设计”中的MySQL数据类型相关笔记。

391
来自专栏java达人

从JAVA多线程理解到集群分布式和网络设计的浅析

对于JAVA多线程的应用非常广泛,现在的系统没有多线程几乎什么也做不了,很多时候我们在何种场合如何应用多线程成为一种首先需要选择的问题,另外关于java多线程的...

2258
来自专栏后端技术探索

携程异步消息系统实践

今天会跟大家分享一下我们在携程,现在应该是正在推广的一个新的消息系统,主要会偏重于讲一些架构和实现方面的内容。目前我在携程大概一年多都在做新的消息系统Herme...

1012
来自专栏互联网高可用架构

支付平台架构设计评审核心要点与最佳实践【完整版】

1853
来自专栏架构师之路

缓存,究竟是淘汰,还是修改?

允许cache miss的场景,不管是memcache还是redis,当被缓存的内容变化时,是改修改缓存,还是淘汰缓存?这是今天将要讨论的话题。

794
来自专栏性能与架构

又拍网数据库架构案例分析

这篇文章是对又拍网公布的数据库案例的分析总结 又拍网是一个大型照片分享社区,数据库架构也是从简单到复杂发展起来的 数据库进化过程 (1)一主一从 最初...

2766
来自专栏快乐八哥

MongoDB学习系列(1)--入门介绍

MongoDB是一款为Web应用程序设计的面向文档结构的数据库系统。 MongoDB贡献者是10gen公司。地址:http://www.10gen.com 1....

1928
来自专栏Java架构师学习

通过 Java 线程堆栈进行性能瓶颈分析

2216

扫码关注云+社区