【原创】Java多线程断点下载理论

希望你转载文章的时候，麻烦保留作者信息。（夏威夷雪人 or 书虫）

1、断点下载的基本原理
　　
　　其实这个是HTTP协议的一部分。在HTTP 1.1，支持断点下载，断点HTTP请求跟一般的HTTP请求基本相同，只有两点不同：
　　
（1）发起请求是HTTP的版本必须是HTTP/1.1
（2）在Header有这样一个节点：Range，格式是Range: bytes=起始字节-结束字节
　　
　　如果HTTP返回的状态码是206，则代表对方支持断点下载，否则就是不支持。另外我用HttpURLConnection的时候，找不到设置HTTP版本的方法，虽然在下载的时候很多网站照样支持，但感觉不是很踏实。希望可以找到解决的方法。（当然可以自己用Socket实现一个Http协议，不过重复轮子的事情貌似不好，也不怎么想用HttpClient这个大块头）
　　
2、任务的分配算法
　　
　　如果我们认真看一下FlashGet的下载栏目，一定可以看到它有一堆表示进度的格子，这里，每个格子就代表固定长度的字节，从这里我们可以清晰地看到下载的进度以及每一部分下载的情况。我们这里也使用类似的方法，把整个文件按照固定的长度（4K）分成很多“格”，然后进行多线程下载。这里就产生一个问题：怎么决定每个格子哪个线程去下载？我们知道，下载的时候，发起连接现对来说是一个比较耗时的操作，所以，我们需要把任务尽可能平均分配，较少连接的次数。
　　
　　我们根据每一个未下载的格子的“相连”情况，分成若干“条”“任务链”。这里的“相连”，是指按顺序的每一个未下载的格子都是相连的，没有跳跃。任务刚开始的时候，只有一条“任务链”，但当开始之后，当某些部分格子下载完毕之后，就被分割成不止一条“任务链”了。同时因为可能每一个线程的下载速度各不相同，所以，每一条任务链的长度可能都不相同。这就产生一个问题，当某个线程先一步完成了，我们当然是让这个线程继续下载，这时，我们就需要重新分配“任务链”。（如果我们用FlashGet下载一个文件，观察它的“格子”，对这个“任务链”的概念应该会更加清楚）
　　
　　整个分配算法，抽象出来，其实就是：有m条绳子，需要对这些绳子合共剪n刀，如何剪法才能使剪出来的绳子的最长跟最短的差距最小？
　　
　　首先我们需要明确的是，无论是何种剪法，都需要遵守这个原则：对每条绳子的剪都必须是平均剪。至于原因，读者可以自己思考。
　　
　　开始的时候，我是打算枚举所有剪法，然后计算每一种的剪法中，最短跟最长的差距。不过发现算法不容易写（粗略想了一下，貌似是排列组合的问题），而且时间复杂度貌似有O（n的平方）这么多。
　　
　　后来才发现自己原来是绕了个大弯。剪法其实很简单，首先在这m条绳子里找到最长的一条，放下一个剪刀，这是第一轮；然后在这m条绳子里再找到最长的一条，找的时候，如果遇到放有剪刀的绳子，按照剪刀的数目重新计算平均的绳子长度，例如加入绳子有6，放有2把剪刀，我们就算他为6÷（2＋1）＝2，然后，又在最长的那里放下一个剪刀；……这样一直循环，直到放完所有剪刀。算法非常简单，而且时间复杂度只有O（n）。
　　
3、缓冲写的功能
　　
　　一般的下载工具都有缓冲写的功能，这个功能貌似对硬盘保养有一定的帮助。由于我们的下载是多线程下载，一般的方法是每个线程每次下完一个格子之后然后把这个格子的数据放到一个List里面，然后检查这个List里面的数据时候超过一个额度，如果超过，就把这些数据写道文件里面。这里有两个问题：
　　
（1）当这个线程写文件的时候，这个List我们当然要上锁的，这个时候，其余线程就不能往这个List里面放数据，被阻塞了。（解决方法很简单，把这个List的数据搬到另外一个B List里面，然后清空List的数据，再在这个线程根据B List慢慢写文件，这样其余线程就不会阻塞了）
　　
（2）这种方法需要浪费一个本来是下载的线程来写文件。
　　
　　第二个问题解决的方法是另起一个线程来专门写文件。每次每个线程下载完一个格子之后，把这个格子的数据放到一个地方（可以是List，也可以是其它），然后通知那个专门写文件的线程。那个线程检查数据的数量，如果超过一个额度就写文件。
　　
　　很明显，这是一个典型的生产/消费模型。Java5已经帮我们准备好了一个接口——BlockingQueue，就不需要再重复造轮子了。
　　
　　最后差点忘了说，这里写文件由于需要跳跃写，所以需要使用RandomAccessFile，同时建议一开始就分配空间，减少产生文件碎片的可能。
　　
4、使用NIO代替多线程＋BIO
　　
　　貌似现在越来越流行NIO了，连Tomcat6都是NIO，我们也把我们的下载工具改造成NIO。具体的NIO原理就不在这里细说了，读者可以上网查查，不过由于HttpURLConnection和HttpClient都是基于BIO的，所以很遗憾，如果你要用NIO，你不得不自己实现Http的协议，虽然不是很难。