用Kotlin实现一个超简陋的BitTorrent客户端(一)

用Kotlin实现一个超简陋的BitTorrent客户端(一)

前段时间没事做,然后朋友安利了一下手写torrent的项目。喵了一眼各种新手向的实现,有C++的也有go的,但是没有kotlin的,就想手写一个了。然后发现简直就是超级大坑,从一个坑跳到另一个坑……

从零开始用Kotlin写一个超简陋的BitTorrent客户端

不管怎样,目前的状态是可以(仅可以)从一个叫academictorrents的网站的单文件种子里面提取出链接,然后去获取Peers的程度了。接下来的工作涉及到:

  • 和Peers沟通握手
  • 进行信息交换
  • 管理Pieces
  • 多线程下载
  • 合并下载完的文件

一看就是更大的坑了((

考虑到已经踩了不少的坑,也许是时候先把到这个阶段为止的坑先记录下来吧。

Bencode解析

要想下载文件的话,得知道这些文件叫什么,去哪里才能找到它们还有一些其他额外的信息。这些信息在torrent文件里用一种叫Bencode的编码方式来保存,所以首先要做的就是解析这个Bencode。关于Bencode的编码的规范可以看这里

Bencode的库的话,Kotlin可以说是没有,Java倒是有那么一个。我一开始想上Parser Combinator来着(嗯,想偷懒),但是这玩意看起来还是个上下文有关的,写不了。找了一下,找到个看起来很美的思路

这个思路是利用了PeekingIterator,首先在顶层函数decode进行模式匹配(因为每个token的第一个字符肯定要么是i要么是l不然就是d或者数字),然后根据匹配到的情况递归地调用对应的解析函数。每个解析函数再调用readNreadWhilereadUntil或者递归地调用decode函数。这三个函数的具体实现则是作为Iterator的扩展函数,在符合条件的时候一边移动this的指针一边build一个字符串,最后把字符串包装成Result<>类返回出去。拿到了Result<String>,就可以在Decoder里面用flatMap和map了。最后得到的是一个Result<Bencode>,包装了一个解析的结果,这个结果可能是成功的(Result.Success),也可能是失败的(Result.Failure),通过给结果flatMap一个回调函数来进行进一步的变换。

因为Kotlin自带的Result不能用于返回类型,然后感觉没太必要上工业级的Result库,所以就把之前啃的The Joy of Kotlin书里面的Result库复制过来将就着用了。当然,这个库缺少了一些函数得自己手写。不过也不是很难的事情。

同样的,原repo用了google.common.collect.Iterators,看了一眼感觉只是为了使用PeekingIterator的话自己手写一下也好,就自己手写了一个。

顺便提一下这个解析用到了一个叫fanout的函数,感觉有点意思,实现放在这里:

1
2
3
4
5
inline fun <V, U> Result<V>.fanout(crossinline other: () -> Result<U>): Result<Pair<V, U>> {
return this.flatMap { outer ->
other().map { outer to it }
}
}

看样子,是获得了一个A的Result后,同时传入一个返回B的Result的lambda,最后获得一个A to B的Result(大概)。

简单测试了一下,对d3:abce之类的例子看起来都没问题,就算解决了吧。看起来很美是吧,然而,后来才发现这里面隐藏着个大坑(

提取Torrent的信息

上一步只是把Bencode编码的字符串提取成Result<Bencode>的类型,这个类型可以理解为是一棵树,每一个子树都是Bencode的子类型。但是,并不能直接从这棵树里面简单地提取出想要的信息的。回过头看一下.torrent的文件结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
d
8:announce
41:https://academictorrents.com/announce.php
7:comment
90:Torrent of academic paper https://www.tandfonline.com/doi/abs/10.1080/09515089.2012.729488
10:created by
14:uTorrent/3.5.5
13:creation date
i1566236877e
8:encoding
5:UTF-8
4:info
d
6:length
i150932e
4:name
22:MoralPsychHandbook.pdf
12:piece length
i16384e
6:pieces
200:�����PS�^��... (字符串长度为200的二进制数据)
e
e

这里面需要的字段有:

  • announce - Tracker的URL
  • info - 存放了和文件有关的内容
    • length - 文件的长度
    • name - 文件名
    • piece length - 每个文件分块的长度
    • pieces - 每个文件的Sha-1编码串接起来的一个二进制数据

那么就开始建模吧。

1
2
3
4
5
6
7
8
9
10
11
data class TorrentInfo(
val pieces: String, val pieceLength: Long, val length: Long, val name: String
)

data class TorrentSeed(
val info: TorrentInfo, val announce: String, val infoHash: String
)

data class TorrentFile(
val announce: String, val infoHash: String, val pieceHashes: List<String>, val pieceLength: Long, val length: Long, val name: String
)

(这里补充一下,一开始没在TorrentSeed里面提取infoHash,而是想着在提取出TorrentInfo后再去encode,以为可以通过拼接字符串来重新生成bencode编码,结果证明是不可以的(而且代码也变得非常面条)。最后还是决定在BencodeParser里面实现encode函数,encode函数实现倒是非常简单,但这个函数接受的是一个Bencode类型的实例。于是就在转TorrentInfo的时候顺便提取出info(一个字典,也就是Bencode的子类),并且从这个info生成encoded的编码来进行hash了,这也算是一个坑吧?)

因为这棵树里面,总是从一个字典里面获取其他类型(字符串/数字/列表或者字典)的Bencode子类,所以可以写出这样的辅助函数:

1
2
3
4
5
6
fun DictionaryLiteral.getIntAttr(attr: String): Result<BigInteger> = this.of[ByteStringLiteral(attr)]?.let {
when (it) {
is IntLiteral -> Result(it.value)
else -> null
}
} ?: Result.failure("Cannot get IntAttr $attr from dictionary")

其他的三个类型的话函数结构类似,只是要改变content的类型来跟要提取的值的类型对的上号。其实本质上说,这个函数的意思类似于Dictionary[attr]然后去判断结果的类型是否Int。

有了辅助函数,就可以进一步写从Result<DictionaryLiteral>生成TorrentSeed然后生成TorrentFile了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
fun Result<DictionaryLiteral>.getInfo(): Result<TorrentInfo> =
this.flatMap { dict ->
dict.getIntAttr("length").flatMap { length ->
dict.getStringAttr("name").flatMap { name ->
dict.getIntAttr("piece length").flatMap { pieceLength ->
dict.getStringAttr("pieces").flatMap { pieces ->
Result(TorrentInfo(length = length.toLong(), name = name, pieceLength = pieceLength.toLong(), pieces = pieces))
}
}
}
}
}

// 这里调用了getInfoHash()函数,也就是在Result内部顺便计算了infoHash然后传给要返回的TorrentSeed里
fun Result<DictionaryLiteral>.getSeed(): Result<TorrentSeed> =
this.flatMap { dict ->
dict.getStringAttr("announce").flatMap { ann ->
dict.getDictAttr("info").flatMap { info ->
Result(info).getInfo().flatMap { infos ->
Result(info).getInfoHash().flatMap { ih ->
Result(TorrrentSeed(info = infos, announce = ann, infoHash = ih))
}
}
}
}
}

一大堆flatMap吓到我了 – n0099

1
2
3
4
5
6
7
do
dict <- this
ann <- getStringAttr dict "announce" -- 返回的TorrentSeed的第二个参数
info <- getDictAttr dict "info" -- 这个info会被接下来两行consume掉
infos <- getInfo (return info) -- TorrentSeed的第一个参数
ih <- getInfoHash (return info) -- TorrentSeed的第三个参数
return TorrentSeed infos ann ih

这样翻译的话可能看起来会清晰一点?因为kt里面没有do-notation所以只能用flatMap套lambda来表达同样的思路了(据说可以写个fmap函数然后用applicative,但是又不是不能用.jpg)

测试

看起来很顺利就完成任务了,接下来就是写Tracker的部分(这里略过,下文再提),写完PeerRetriever后开始测试,吓了一跳:两个种子,一个死循环了另一个报错。

死循环看来问题出在Parser上。试着把前文提到的那个kt的Parser实现下载下来,发现那人的源代码也跑不动(摔

鉴于kt上也没像样的bencode解析库,这一环节是绕不过的。就debug一下看看是怎么回事吧。于是发现问题出在列表或者字典的decode过程上。以列表为例,解码的过程中有一个循环while (!iter.consume(ENDING_MARKER).getOrElse(false)),假设有一个字符串列d3:abcde,这里的3:abc会被decodeString(firstDigit:)吃掉,指针指向d,这时并没有读取到e这个结尾符,会试图调用decode()函数,但是decode()函数里面只是peek喵一眼这个d字符然后发现不匹配就返回了个Result.failure了。因为被包装在Result<>里面所以不会报错,但是指针也不会再移动,就无限死循环了(

解决方案是在decode()里面把peek()改成nextChar()吃掉下一个字符,然后把这个字符传给各函数作为它们的参数(实际上只需要传给decodeString(marker:),因为其他的函数都只会吃那么一个固定的字符)。

这样的话死循环就变成报错了。

分析一下报错的原因,有可能是因为数据结构不匹配(毕竟采用的是最简单的那种假设),但是这里还有一个问题,就是pieces的长度和字符串前面声明的那个数字(这里是200)对不上号。这一部分接下来在Encoding里面再讲吧。

技术选型

于是做到这里,我们有了一个简陋的Bencode编/解码的实现,而且是基于Result<>的。接下来的问题就是该用什么技术抄哪篇blog教程了。虽然是对照着那个go的教程走下来的,但是我是很不想看go的代码的,同样的,也希望能用较为接近fp、声明式的写法。

但是以有限的对fp的知识来说,如果要在monad里面套个网络编程的IO副作用,感觉写起来会非常复杂(

找到了个用Haskell来写的blog [1] [2],好耶,是声明式的写法。不过这里有两个问题:

  • 要用到Functor、Applicative等概念,Kotlin里面没有HKT,不过这个可以用ArrowKt来模拟出来。
  • 涉及到网络编程和Socket的领域,Haskell的库提供的是纯FP的写法,但Kotlin应该是命令式的写法,怎样把Socket和网络副作用封装到monad里面呢?估计得自己手写了……复杂度++(

最后还是放弃FP的想法了。于是就在Result<>里面加了Result<T>.unsafeGet(): T函数备用了。

Encoding

前面提到那个pieces长度和声明的200不匹配(只有193)的问题,想了半天,用Hex Fiend看也是200个字节,最后想到应该是encoding的问题,然后就把encoding改成了ASCII,用了File.readText(Charsets.US_ASCII),解码顺利完成。然而,这里有个大坑。

另一个坑是在反复测试bencode的过程中,因为intellijIDEA不能正确显示二进制内容,把种子里的一部分文本内容和二进制内容搅在一起了,就选择了bidi显示的left-to-right,结果,种子的内容被改变了(直接影响后面的一个环节)。

解码成功了就开始测试和Tracker沟通的环节吧。结果服务器返回错误说Hash对不上,然后一算Hash人傻了,算出来奇怪的东西(

首先,可以保证Sha1计算是没问题的,因为用了这里的样例测试过了。

从头开始吧,下载Bencode Editor,对着info算Hash,结果是9049……DCF6,然后找了几个在线编码Sha1还有字符串转Hex的网站,拼凑了一下,证明了info的字段加起来可以得到正确的Hash。考虑到之前encode实际上是采用的拼接字符串,会不会这里面有问题呢,于是就改成从Bencode里面直接encode的实现(前文提到过),还是不行。之后也试过读取后把字符串换成ByteArray,也是不行的。

然后进debug对比info列的字符值和种子里面的内容,发现了一堆3f,一顿测试修改后发现是从字符串转为ByteArray的时候不能用toByteArray(Charsets.ASCII)方法,要用this.map { it.code.toByte() }.toByteArray()

然后发现了一堆fd……同样的,因为之前打开文件的时候用了ASCII编码所以丢信息了。解决方案是打开文件的时候用File.readBytes().map { it.toChar() }.joinToString(""),因为无论选择哪个encoding来readText,得到的都是错误的编码。

然后发现Hash还是对不上。原因是之前在IDEA里面选择了left-to-right的bidi改变了种子文件的内容……坑真多(

和Tracker沟通

获取了正确的Hash了,该和服务器沟通了吧。结果无论是把原Hash发过去,还是发的urlEncoded的Hash,还是hexDecoded的Hash(这个肯定不行),都报错说Hash对不上号。

问了知乎那边的作者,那边说用浏览器打开拼接的URL没问题。于是就有了个思路,用postman去测试,也得到了正确的结果了。但是为什么同样的参数在程序里面就不行呢。

最后还是注意到了%25这个奇怪的表现了,在khttp的这个issue里面也提到了,url里面的百分号会被再次encode成%25。这个库也很久没更新了,只好换库。换了Ktor后还是同样的结果,好在,Ktor提供了关闭UrlEncode的选项。于是就这样写了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
val rsp = client.get<HttpResponse>(urlString = announceUrl) {
url {
parameters.urlEncodingOption = UrlEncodingOption.NO_ENCODING // 关闭把parameter自动urlencode的机制
parameters.append("info_hash", infoHash.hexToUrlEncode())
parameters.append("peer_id", peerId)
parameters.append("port", this@PeerRetriever.port.toString()) // 这里的port会和ktor内部的参数clash,用this@PeerRetriever来获取我们指定的port
parameters.append("uploaded", "0")
parameters.append("downloaded", byteDownloaded.toString())
parameters.append("left", "${fileSize - byteDownloaded}")
parameters.append("compact", "0")
// 不知为何返回的永远是不compact的结果,所以和教程不一样,这里改为0了
// 以后再来完善好了
}
timeout {
requestTimeoutMillis = TRACKER_TIMEOUT
}
}

然后就可以获得Peers的列表了,大概像这样的:

1
d8:intervali30e5:peersld2:ip14:189.191.137.567:peer id20:-BW122Q-ZgXOsz6y725Z4:porti6881eed2:ip13:46.232.211.957:peer id20:-lt0D60-f͔����4:porti62483eeee

Peer解包也很简单,这里就不重复解释了。

然后呢……

很遗憾,目前就只实现到这里了(

接下来的步骤难度只会更大,因为不能每个模块单独实现然后写个maina来单独测试每个模块的功能了(或者说很大程度上不同模块是互相耦合在一起的)

接下来可能得花上好几个月慢慢磨了(

那么就姑且写到这里,也当是个备忘录吧。