By

文章目录
  1. 1. 问题
  2. 2. 校验流程
  3. 3. 其他相关

问题

首先确认一下本文要解决的问题：ADXP的文件传输是将文件分为若干小块进行块传输。在传输过程中，可能因为网络问题而发生文件块的丢失、乱序或者错误。当传输完成时，发送端与接收端会对整个文件做一次MD5比对，若MD5不同，说明接收过程中发生了错误。

问题在于这时文件位于网络中两台不同的机器上，无法确认具体是哪些快出现了问题。因此需要使用一个类似rsync的算法，在两边文件见不到面时确认哪些块不同。

校验流程

  • 分块 首先把接收端接收到的文件平均分成若干个小块，比如每块2048个字节(最后一块会小于等于2048字节)，然后对每块计算MD5
  • 传输 接收端会将上述MD5列表传送到文件发送端。当发送端在拿到列表时，也会以同样的过程生成这个列表
  • 查找 发送端获得列表后，会把数据存到一个以MD5为key的哈希表中，以便获得O(1)时间复杂度的查找性能

  • 比对 此时比较源列表与目标列表中MD5的差集，便可以知道所有需要重传的文件块。这里用HashSet简单示意如下：

    1
    2
    3
    4
    Set<String> s1 = Sets.newHashSet("md1", "md2", "md3", "md4", "md5");
    Set<String> s2 = Sets.newHashSet("md1", "md2", "md4", "m5d"); // 模拟传输中丢失块3，块5有内容错误
    s1.removeAll(s2);
    System.out.println(Arrays.toString(s1.toArray())); // out: "md3" "md5"

Note: 样例代码有所简化，实际中是将MD5与位置属性(比如文件块首尾位置)结合为一个模型对象，实现equals()和hashcode(); Set中存储这个对象即可

  • 缓存
    在上述伪代码中，调用s1.removeAll(s2)时会修改掉s1本身。考虑到可能的重复校验多次情况，每次都要重新生成源文件的MD5列表会引起额外开销，可以引入缓存进行优化(Guava cache或Ehcache等)。这时需要在比对过程中不修改源端列表s1的内容。这样s1便可以被缓存至传输流程结束。 
    1
    2
    3
    4
    5
    Set<String> s1 = Sets.newHashSet("md1", "md2", "md3", "md4", "md5");
    Set<String> s2 = Sets.newHashSet("md1", "md2", "md4", "m5d"); // lost 3 and dismatch 5
    Set<String> result = Sets.difference(s1, s2); // Guava的API返回一个视图，而不是修改集合s1本身
    System.out.println(Arrays.toString(result.toArray())); // out: "md3" "md5"
    System.out.println(Arrays.toString(s1.toArray())); // out: "md1", "md2", "md3", "md4", "md5"

其他相关

在文件传送过程中，我们需要一个用以做标记的数据结构：
它应该对下面操作做到尽可能的高效：

  • 接收到一组文件块，快速做出标记，表示其已收到
  • 快速统计出当前接收到的文件块总数
  • 快速定位到哪个（哪些个）文件块尚未收到

简单思路是，若源端文件被分成比如1000个块，目标端建立一个长度为1000的boolean数据用于标记，接收到文件块时，根据其位置信息快速定位到相应的数组下标，并置为true。这样可以分别以O(1), O(n), O(n)的时间复杂度满足上述三个需求。

以boolean数组为基础，可以进一步的简化：如果能以一串二进制01来标记对应的文件块是否收到，这样可以将内存占用降低到极致。在JDK中正巧有类似的实现java.util.BitSet，不过略微不同的是，BitSet内部实际上以length为 位数>>6 的long数组来存储。另外，用于统计true总数的API cardinality() 由于高效率的位运算实现，遍历次数可以降低为朴素循环遍历的1/64

文章目录
  1. 1. 问题
  2. 2. 校验流程
  3. 3. 其他相关