不知道出于何种原因,我突然决定自己造轮子。索性这个轮子造的好像还不是特别没用。本文将记述我从零开始使用Kotlin实现一个Bencode编解码库。
前言
Java和Kotlin(JVM)具有比较好的互操作性,即便没有给Kotlin设计的库,如果有相应的Java库,在Kotlin上也是可以直接调用的。在此之前我尝试过com.dampcake:bencode
这个库,用起来感觉还不错,但它的操作是类似DOM那种,即所有写入和读出的数据全部存在内存里以供操作。这种操作方式固然简单好用,但是如果你有很多数据的话,你可能更希望采用接近XML SAX的方式。后者是基于流的解析方案,也就是说解析器一边读入数据,一边将解析出来的结果交给你的代码。你可以选择将他们收集起来组装成DOM,也可以选择即时处理然后回收。本文将考虑如何构建一个基于流的Bencode编解码库。
Bencode
Bencode好像是一种不太常见的编码。考虑到早年间的XML,以及现在的Json,好像Bencode并没有什么用武之地?但作为一个P2P爱好者和版权左人,大名鼎鼎的BitTorrent协议就是用Bencode编码数据。这种编码形式以字符为基础,肯定不如ProtocolBuf这种二进制编码高效,同时它的结构比较简单,不太可能像XML或Json在功能上那么丰富(Bencode甚至不支持编码小数)。但从某种意义上来说,Bencode确实是最简单且紧凑的格式。
举个例子。在Json中表示一个结构是这样的:
{
"number": 1234,
"string": "hahaha",
"list": [
"string in list", 2345, [ "list in list!" ], { "name": "object in array!" }
],
"obj": {
"string": "An object",
"list": [ "List in object!" ],
"dict": { "num": 2345 }
}
}
去掉所有多余的空格,一共是195个字符。如果表示成XML,那就更罗嗦了:
<?xml version="1.0" encoding="UTF-8" ?>
<root>
<number>1234</number>
<string>hahaha</string>
<list>string in list</list>
<list>2345</list>
<2>list in list!</2>
<list>
<name>object in array!</name>
</list>
<obj>
<string>An object</string>
<list>List in object!</list>
<dict>
<num>2345</num>
</dict>
</obj>
</root>
XML需要295个字符,而且它还没有保留list in list的部分。这可能是我是用的Json到XML转换器有问题,也可能是XML并没有名且规定列表的格式。
如果将上述数据转换成Bencode,那就显得紧凑了不少:
d4:listl14:string in listi2345el13:list in list!ed4:name16:object in array!ee6:numberi1234e3:objd4:dictd3:numi2345ee4:listl15:List in object!e6:string9:An objecte6:string6:hahahae
Bencode只要179个字符。而这段数据的所有文本内容需要125个字符(数字由对应的字符表示,且丢弃了所有结构信息)。
当然,如果只从格式上看的话,Bencode不是那么的“人类友好”,但这无伤大雅,我对于Bencode的主要用途是简单地导入和导出结构化数据,而不必考虑给人看。
说了这么多,不如我们来看看Bencode的编码规则。
Bencode的编码规则比较简单:
- Bencode使用ASCII字符作为分隔符和元素
- 对于数字,采用
i42e
的形式来编码,其中42是数字42对应的十进制字符串。数字不允许前导0(即00042
是非法的)。负数使用-
作为前缀,即i-42e
,但不允许负0 - 对于字节串(字节序列,并不一定是字符),采用
4:spam
的形式来编码。其中4表示这个字节串的长度,采用十进制字符串表示,冒号表示分割,随后spam是字节串的实际内容。Bencode并没有提及数据无法被编码成ASCII时应当如何处理,在一些具体实现中,人们主要采用UTF-8来应对其他字符,或使用ISO 8859-1来编码字节数据,亦或采用Base64等编码将字节串编码为ASCII字符串 - 一个列表由
l<content>e
表示。一个具有字符串“spam”和数字42的列表应当被表示为l4:spami42ee
。其中首个字符是小写字母L,不是数字1。列表内的元素类型不受限制。 - 一个字典由
d<content>e
表示。在字典中,字符串作为键后面总是直接跟着值。所有键必须按照字典序进行排列。例如字典{"bar": "spam", "foo": 42
应当被表示成d3:bar4:spam3:fooi42ee
。字典的值的类型不受限制。
通过上述这几条规则,基本上就没有Bencode表示不出来的结构。同时字典规定了键的排序,保证了编码结果的唯一性。
流式编码
上面说了半天编码,不如我们就从编码入手,看看怎么基于流来编码。编码器的输入往小了说就是那四个基本类型:整数、字符串、列表和字典,对应Java里面的BigInteger
、String
、List<*>
和Map<String, *>
。因为Bencode并没有规定整数的最大上限,因此使用BigInteger来存储整数。
整数和字符串
对于整数和字符串来说,流失编码好像没有太多的意义:除非一个整数或字符串占用了以G计算的内存,你可能需要流式处理,不然没有必要把他们拆开——就算拆开,字符串还好说,整数怎么拆呢?这个就需要看具体的应用场景了,而作为一个通用的库来说,我们没有办法提供一个不过度复杂同时还通用的机制。因此这两个元素没有什么流式不流式的说法。
列表
对于列表就不一样。这里我们通过循环的方式来模拟对列表内数据的访问和写入。如果我们有400万个Int,他们在内存中大约占用16MB的内存。如果我们将他们转换成BigInteger,都不使用List,就用最紧凑的数据,在128MB的内存限制(-Xmx128M
)下,程序直接OOM了。
val array = IntArray(400_0000) { it }
val list = Array(400_0000) { array[it].toBigInteger() }
println(list.count())
即便没有OOM,这个list所占用的额外内存也必须等待所有数据写完之后才会被垃圾回收——只要编码器还没写完,对于GC来说这个列表就是可达的,那么每一个元素都无法被回收,即便他们的一部分已经被写入了。
好在Kotlin提供了Sequence这个东西。Sequence的好处就是可以根据需求(on-demand)产生数据。也就是说,我通过循环的方式统计个数,而每次我只需要一个数据,处理完成之后这个数据就可以被GC回收了。使用Sequence,整个程序只占用了22MB的内存:
val array = IntArray(400_0000) { it }
val seq = sequence {
for (i in array)
yield(i.toBigInteger())
}
println(seq.count())
我们只要使用Sequence,就可以保证数据只有被编码器需要的时候才会产生。这不就是流式处理吗?
字典
下面我们来看看字典。我们可以借鉴列表的经验,但是Sequence有一个问题:除非提供者保证,否则没法确保数据是有序的,而我们的字典在编码时要求键必须按照字典序排列。要么我们就接受用户的输入,如果检测到违反了字典序,就抛出异常;要么我们就想办法自己构建一个类似Sequence的Map。
好在我并不是第一个遇到这种问题的开发者。在Java中就提供了Supplier这个接口,而Kotlin中也有Lazy这种能够提供延迟求值的工具。但最简单的还是一个Lambda:() -> T
,只要我们将Map的类型设置成Map<String, () -> T>
就可以了。但是这个T怎么取呢?我们的元素有BigInteger、String、List和Map,且不说前两个没有共同的父类,后两者还有泛型擦除的问题,很显然编译器并不能要求传入的List必须是List<String>
,而不能是List<UUID>
。
在传统的Java开发中,这个时候我们就应该已经写出编码器的接口,同时还有BencodeSerializable
接口了,但是我个人并不太喜欢接口满天飞。不过在这种情况下,接口可能是无法避免的:
sealed interface BEntry {
data class BInteger(val value: BigInteger) : BEntry
data class BString(val value: String) : BEntry
data class BList(val value: Sequence<BEntry>) : BEntry
data class BMap(val value: Map<String, () -> BEntry>) : BEntry
}
由于我们接口下面的实现是已知的,毕竟Bencode中就规定了四种元素,因此完全可以使用密封类来修饰接口。这样,当我们使用BEntry作为when的参数时,编译器就会知道,这个参数只有四种可能的情况,而我们上面的T也就可以取值为BEntry了。
编码器
既然有了这个BEntry,我们就可以面向这个接口设计编码器了。我们的BencodeEncoder
在构建时只需要一个Writer
,这个对象负责处理字符的写入,而无需我们考虑字符集编码这些问题。关于成员函数,由于我们的BEntry设计的很清晰,因此只需要一个fun writeEntry(entry: BEntry): Unit
就好了。
为了方便维护,我们可以针对不同的类型设计不同的私有函数,将writeEntry
作为一个集中分派的入口:
fun writeEntry(entry: BEntry) = synchronized(writer) {
when (entry) {
is BEntry.BInteger -> writeBInteger(entry)
is BEntry.BString -> writeBString(entry)
is BEntry.BList -> writeBList(entry)
is BEntry.BMap -> writeBMap(entry)
}
}
这里我们对writer加了锁,这是避免在多线程使用时造成冲突。例如一个列表正在输入,另一个线程突然开始写字典了,很有可能就会得到类似字典把列表截断,而列表又把字典截断的情况。
对于四种类型的写入也比较简单:
private fun writeBInteger(entry: BEntry.BInteger) {
writer.write("i")
writer.write(entry.value.toString(10))
writer.write("e")
}
private fun writeBString(entry: BEntry.BString) {
writer.write(entry.value.length.toString())
writer.write(":")
writer.write(entry.value)
}
private fun writeBList(entry: BEntry.BList) {
writer.write("l")
entry.value.forEach { writeEntry(it) }
writer.write("e")
}
private fun writeBMap(entry: BEntry.BMap) {
writer.write("d")
entry.value.keys.sorted().forEach { k ->
writeBString(BEntry.BString(k))
writeEntry(entry.value[k]!!())
}
writer.write("e")
}
像是字典的键,我们知道它的类型,就可以直接调用writeBString
,而对于值,我们并不知道它的类型,因此较为writeEntry
进行分派。
Writer
有了编码器,但好像还不太够:这个编码器只能面向我们的BEntry工作。如果用户想要编码一个Map,还必须得转换成我们的BEntry.BMap
,有点麻烦。如果我们能直接编码Map对象,甚至任意的对象呢?
我想到了两个思路。
第一个思路比较简单粗暴:提供一个接口,让用户可以实现这个接口,从而提供一个BEntry出来:
interface BencodeEncodable {
fun encodeToBEntry(): BEntry
}
使用的时候看起来是这样的:
data class Point(
val x: Int,
val y: Int
) : BencodeEncodable {
override fun encodeToBEntry(): BEntry = BEntry.BMap(mapOf(
"x" to { BEntry.BInteger(this.x.toBigInteger()) },
"y" to { BEntry.BInteger(this.y.toBigInteger()) }
))
}
第二个思路则相对灵活一些:在实例化Writer的时候提供一系列mapper,他们将对应类型的对象转换为BEntry。如果更进一步扩展这个概念,mapper可以把writer不认识的类型转换成它认识的类型。例如上面那个Point类的mapper可以是:
val mapper = BencodeEncoderMapper<Point> {
mapOf(
"x" to it.x,
"y" to it.y
)
}
你会发现这个Mapper的返回值并不是BEntry,而是一个Map<String, Int>
。而我们的Writer可以把这个Map转换成对应的BMap:只需要将值映射为{ it.value }
就可以了。而完成转换之后,这个mapper返回的map就会被丢弃,从而可以被垃圾回收。不过在Mapper中不能返回lambda,因为JVM在运行的时候比较难判断一个值到底应该被包装成lambda,还是要作为lambda放进Map。
Kotlin在编译时并没有保证两个类型相同的Lambda对于JVM就一定是同一个类型的。因此同样都是() -> BEntry
,他们可能是两个不同的类。当然,使用反射可以解决这个问题,查看一个对象是否具有invoke()
的方法,并且返回值不是Unit
或Nothing
,但我本意是想避免这些黑魔法的。
另外还需要注意这两种思路的细微差别。对于实现接口来说,因为BEntry要求使用Supplier,所以BEntry.BInteger(this.x.toBigInteger())
这一行只有在写入了键x
之后才会被调用,可以认为获取到的值就是最新值了。而Mapper虽然也是在写入时调用,在Writer调用完成后,便得到了一个快照(因为在JVM上,对于Int的赋值是值复制,不是引用复制),也就是说,在Writer调用完成后、Encoder写入完成前,无论原来的Point.x
怎么变,写入的内容都不会变了(在Encoder中调用的Supplier实际上只返回一个Int,这个Int是mapper中对it.x
的求值)。
当然,如果对于数据类都是用不可变类型,那自然是极好的。如果涉及可变类型,那除了保证内存可见性之外,还要考虑将对象转换成BEntry的时机对于编码结果的影响。
总之,在这个库里面我实现了这两种思路,如果是自己编写类的话,建议使用第一种;如果是别人的类,那么就可以考虑使用Mapper在序列化时自动转换。
关于这部分的代码也比较简单,Writer的主要入口:
fun write(obj: Any): Unit = encoder.writeEntry(mapToBEntry(obj))
而负责转换的函数实际上就是一个lookup table:
private fun mapToBEntry(obj: Any): BEntry = when (obj) {
is BEntry -> obj
is BencodeEncodable -> obj.encodeToBEntry()
// for signed value, convert to long
is Byte -> BEntry.BInteger(obj.toLong().toBigInteger())
is Short -> BEntry.BInteger(obj.toLong().toBigInteger())
is Int -> BEntry.BInteger(obj.toLong().toBigInteger())
is Long -> BEntry.BInteger(obj.toBigInteger())
// for unsigned value, convert to long so the value is same
is UByte -> BEntry.BInteger(obj.toLong().toBigInteger())
is UShort -> BEntry.BInteger(obj.toLong().toBigInteger())
is UInt -> BEntry.BInteger(obj.toLong().toBigInteger())
// for ULong, it's bigger than long, thus turn it into string
is ULong -> BEntry.BInteger(BigInteger(obj.toString()))
// for chat and string, just write string
is Char -> BEntry.BString(obj + "")
is String -> BEntry.BString(obj)
// for list, transform it to sequence
is List<*> -> BEntry.BList(obj.asSequence().map { mapToBEntry(it!!) })
// for map, map the key to string and map value to BEntry
is Map<*, *> -> BEntry.BMap(obj.mapKeys {
if (it.key is String) it.key as String else it.key.toString()
}.mapValues { { mapToBEntry(it.value!!) } })
// for general object, search mapper and apply the transform
else -> ((mapper.find { it.canHandle(obj) }
?: error("Mapper not found: ${obj.javaClass}"))
as BencodeEncoderMapper<Any>)
.invoke(obj)
.let { if (it is BEntry) it else mapToBEntry(it) }
}
关于Mapper的设计,也比较简单:
interface BencodeEncoderMapper<T> {
fun canHandle(obj: Any): Boolean
fun invoke(obj: T): Any
}
这个canHandle
是用来询问一个mapper实例能否处理这个类。因为运行时的泛型擦除,Writer除了知道这是一个Mapper之外,并不知道它所实现的泛型是什么,更不要说什么类型间的继承应该如何处理了——有时候子类可以按照父类处理,有时候子类需要它独有的处理方式。
当然,每次实例化Mapper都需要写一个object : Interface { ... }
都怪臃肿的,而且这个接口有两个函数,没法用SAM。但是啊,我们可以用同名函数来实现简化:
inline fun <reified T> BencodeEncoderMapper(crossinline block: (T) -> Any) =
object : BencodeEncoderMapper<T> {
override fun canHandle(obj: Any): Boolean = T::class.java.isInstance(obj)
override fun invoke(obj: T): Any = block(obj)
}
当然了,简化的代价就是要服从一些约定。这里关于能否处理的判断,是调用了泛型类的isInstance
方法。得益于Kotlin的inline和reified,我们可以在内联函数中访问泛型的具体类型。这也是实现第二个思路的关键。如果要我在Java中实现类似的机制,我肯定要舍弃掉第二个思路——无论使写起来还是用起来,都太臃肿了。
写到这里突然想到,使用Mapper可能会出现成环的情况。比如说一个类型A的Mapper返回了类型B,而类型B的Mapper又返回了类型A,这样不停的递归调用就会导致爆栈。
不过话又说回来,这样成环肯定说明这家伙的数据类型设计的很不合理,总之不是我的锅就对了。
解码
说完了编码,再说说解码。你会发现说解码的时候我可没提流式。我在不同的设计方案中思考了半天,最终决定像编码那样提供两个层级的API。底层可以是流式的,但顶层就比较困难了。解码意味着要处理一系列的输入流,而若像编码那样使用Supplier按需解码,就需要解码器能够知道要跳过多少字符以便解析下一个元素,同时还能倒回某一处,在需要的时候解码以前跳过的内容。这对于Reader来说实在是强人所难了。
但是这种限制并不意味着我们必须把一个元素完整的解析到内存中。我们可以根据当前的字符构造状态机啊!
例如我们读到一个字符i
,我们就知道下一个元素应该是一个整数;如果读到1~9中的一个,那么下一个肯定是字符串;类似地,如果读到l
或者d
,那么下一个肯定是列表或字典。而且他们的终止符都是成双成对的,只要输入的是合法的数据,就不会出问题。
举个例子:
data class Person(
val name: String,
val age: Int,
val friends: List<Person>,
val attributes: Map<String, String>
)
我们在读取的时候可以构建一个Builder,根据读到的内容填充builder。例如说:
- 在开始之前应该预期一个字符
d
,因为对象将被处理成字典 - 接下来应该预期字符1~9中的一个,因为字典中总是键值的顺序,而键是字符串
根据读到的键,预期不同类型的数据
- 例如读到了name,就应该预期一个字符串
- 读到age,就预期一个整数
- 如果是friends,那就调用处理
List<Person>
的函数,循环调用当前函数以读取Person列表,最后将读出的列表返回
- 当遇到字符
e
的时候,检查这个Builder是否已经准备好build了。如果还有缺失数据,说明输入的有问题
显而易见地,这是个递归结构。如果你怕爆栈的话,改成链表+循环也可以。但脑子尖的读者应该已经注意到了:这个friends对应的列表,并没有流式解析啊,反倒是只有最顶层的Person是流式解析,而它的内容倒都变成DOM形式了。
对,你说得都对。
这个问题我也思考了很久,最后得出来的结论就是以实际需求为准。我上面那个例子是根据输入还原对象,也就是说无论如何我们都是避免不了DOM形式的。但如果说你是想即时更新数据库,那相比之下就简单了不少:你只需要在读到id之前暂存数据,读到id之后直接采用多个UPDATE语句的形式,读一个就产生一条语句,然后丢弃结果。
总之在这方面,我尽力了。如果一个对象不大的话,那么以对象为单位进行DOM形式的操作,而总体还是流式的话,我反正是能接受的。
解码器
关于解码部分的代码这里就不多说了,只介绍一下API。较为底层的API是BencodeDecoder
,实例化时需要一个Reader
来读入字符,它总共有如下方法:
fun hasNext(): Boolean
fun nextType(): BEntryType
fun readInteger(): BigInteger
fun readString(): String
fun startList(): Unit
fun startMap(): Unit
fun endEntity(): Unit
这其中,hasNext
不必多说,就是看Reader是否已经被处理干净了。如果还没有,那么就读入一个字符。而后nextType
则是根据当前读入的字符来判断类型。这里你会发现我没有用BEntry,一来是它的实现都不是Object,没法直接用,二来是解码时l
和d
表示列表和字典的开始,而e
则单独表示一个实体的结束,没办法与四种类型对应。因此就额外引入了一个Type类,它也是密封接口,而它的实现,除了EntityEnd比较特殊,其他的都是BEntry的四个实现的companion object,也就是说我们可以直接写BEntry.BList
来表示一个BEntryType
,我觉得很是优雅。
后面两个read就不用说了——直接读取对应类型的值,读完之后还要读入下一个字符,以便后续调用hasNext来判断。而至于列表和字典,这个start函数只是检查一下当前的字符是否正确。例如startList
会检查当前字符是不是l
,不是的话就会抛出异常,避免错误地开启列表。剩下的startMap和endEntity也是类似的操作。
Reader
而较高等级的API则提供了一种近似DOM方式的API:
class BencodeReader(
reader: Reader
) {
fun hasNext(): Boolean
fun nextType(): BEntryType
fun readInteger(): BigInteger
fun readString(): String
fun readList(): List<*>
fun iterateList(callback: Consumer<Any>)
fun readMap(): Map<String, *>
fun iterateMap(callback: BiConsumer<String, Any>)
}
前两个就不多说了,唯一值得一提的就是nextType,因为读出来就是完整的对象,所以不存在EntityEnd这种类型。后面的各种read也不必多说,读出来就是对象。
这里额外提供了两个iterate方法,为的是流式遍历顶层对象。比如说一个输入是几百万个小对象组成的列表,那么iterateList就会每次解析一个对象,然后交给callback处理,处理完成后再解析下一个。字典也是一样,每次解析一对键值,然后交给callback处理。
后记
至此这整个库的设计思路就介绍完了。这个库本身比较简单,不像Ktorm那种复杂的库。但碍于我没有设计库的经验,在设计的过程中考虑了好多有用的和没用的细节,以至于文章写起来很罗嗦。另外写文章的时候突然意识到一些问题,就把文章扔到一边修改代码去了,改完代码再接着写文章,难免会有些思路上的跳脱。好在这又不是出版书籍,有点问题就有点问题了。
也许有经验的读者看到我这边文章会说:就设计一个编解码的库,这孙子怎么写的那么啰嗦,这不脱了裤子放屁吗?有的地方还狗屁不通,这写的啥啊这是?我奶奶用脚写的都比这好
对,你说的都对,不爱看滚蛋。不过还是要感谢一下能耐心读到结尾的读者,感谢你们的耐心。
关于这个库,我已经开源到了GitHub上,可以在JitPack上使用相应的制品。
-全文完-
【代码札记】Bencode编解码(Kotlin) 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。