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

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

（原创内容，转载请注明来源，谢谢）

一、问题阐述

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

当前有一个千万条级别的用户数据，其中包含用户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月开始文章的发表频率会重新增高，非常感谢各位。