« July 2022 | Main | September 2022 »

August 12, 2022

空间优先的 protobuffer / json 解码器

今天同事给我转了一个帖子 ,说的是 golang 在处理大量并发 json / protobuffer unmarshaling 事务时,可能产生大量的 (10GB) 临时内存,无法及时回收的问题。

我的观点是:如果一个系统的某个模块有可能使用 10G 这个量级的内存,那么它必然是一个核心问题需要专门对待。核心问题应该有核心问题的考量方法,这不是 GC 之错,也并非手动管理内存一条解决之道。即使手工管理内存,也无非是把内存块之管理转嫁到一个你平常不太想关心的“堆”这个数据结构上,期待有人实现了一个通用方案尽可能的帮你解决好。如果随意使用,一样有类似内存碎片无法合并之类的问题,吃掉你额外的内存。如果它存在于你的核心模块,你一样需要谨慎考量。

在这个具体问题上,我认为还是应该先简化数据结构,让核心数据结构变得易管理。显然、固定大小的数据结构是最容易被管理的。因为如果你的数据结构大小固定,就不再需要堆管理,而是一个固定数组滚动处理临时数据。

json 这样的弹性数据结构看起来不太好用固定大小的数据结构去描述,但稍微想点办法也不难做到。C 在这方面的库不少,我就不一一列举。核心想法一般是:用一个固定数据结构去引用编码数据中的切片。解码后的结构只保留元素的类型以及在原始数据中的位置。如果你能大致知道需要解码的数据元素的数量级,那么就可以用一个固定大小的结构去承载解码结果,不需要任何动态的内存分配。

只不过大多数库把目标都放在时间因素上,让解码更快;少放在空间因素上,让解码过程少使用内存;所以这样的解码方式并不常用。如果你的核心问题于此,你就得去考虑这样的方案。

protobufffer 会比 json 的结构更适合这样做。因为它已经把数据的 key 部分转换成数组 id ,且整体数据结构是明确的。但只是因为 protobuffer 编码更繁杂,不如json 那么简单,反而相关的库更少。


第二、如果你真的有这样的需求:要解码成千上万的数据结构类似的数据包。就应该考虑下列模式:

假设你要解码的数据块的类型是 X ,可以预先生成一个叫做 X 的 accessor 访问器。当你的业务逻辑需要访问 X.a.b 这个字段的时候,应该去调用 X.a.b(binary) ,此处的 binary 指编码过的 json/protobuffer 数据块,X.a.b() 是一个预生成好的访问器函数,它可以用最优化的方法从数据块中提取出需要的数据。

我们还可以进一步的为 X 做一个索引函数,可以预处理 binary ,制作一个固定内存大小的索引信息结构,为具体字段的访问加速。

这个 accessor 对象不太在乎多复杂,因为它可能在整个程序中只初始化一次。

August 05, 2022

为 luaecs 增加内置 64bit ID

去年设计 luaecs 时遗留了一个问题:如何引用特定 entity。一开始,我认为可以灵活使用 tag 系统来解决大部分问题;或者用户自己构建一个 64bit ID 的 component ,采用二分查找的方法来引用特定 Entity 。

今年初,我发现我们的自己的使用者和外部使用者都无法避免引用特定 Entity ,所以增加了一个非侵入式的引用方案

最近又围绕它做了一些讨论,让我重新考虑内置一个 Entity 引用的方案。

原本关联同一个 Entity 的不同 Components 使用了一个 32bits id ,在过去的代码中我称之为 entity id ,这可能造成了一些误解。它虽然是一直递增的,但 32bit ID 在长期运行的系统上无法避免回绕问题,也就是新的 entity 可能会复用已被删除的 id 。我用一个叫 rearrange 的机制来解决这个问题,当 id 超过 31bit 范围后,在update 环节会重新排列系统中所有的 id ,让它们重新变得足够的小。

如果这个 id 并不暴露给上层使用,那么怎么变化它们都无所谓。但如果把 id 暴露出去充当 entity 的引用就会有问题。

一个简单的解决方案是换成 64bit ID ,这样就不会再有回绕问题了。但是,每个 component 都会增加 32bit 的 payload ,查找它们的效率也会随之下降。我认为是不值当的。

所以,新的方案回归了最初的方案:为每个 Entity 生成一个独立的 64bit ID component ,这样可以用来引用 Entity ,又能保持稳定。需要解引用的时候,可以二分查找,最坏的时间复杂度也能控制在 O(Log N) 。最多使用 ecs 的特性是对 Entity 集合的筛选和遍历,并不操作特定 Entity 。

本来,这个方案可以留给上层自己实现。最初 luaecs 还提供了在有序 Component 集合上二分查找的 API 。但是,如果把这个特性内置,不管是空间上,还是时间上,都能实现的更高效。用于关联 Componets 的内部 ID 可以缩减到 24bits ,也就是 3 字节。每次 update 时,如有 entity 删除,就依次向小的数字压缩。这会把整个系统同时可容纳的 Entity 总数限制在 16M 个,对我们现在的应用场合完全够用,同时为每个 Component 节省了一个字节的内存,操作效率或许能有所提高。

另外,今年增加的 group 的特性 可实现的更好。

Group 指:我们可以在构建 Entity 时分配一个 32bit group id 给它。之后,可以给一组 group 的所有 Entity 打上特定的 tag 。然后,利用这些 tag 做快速筛选。我们的引擎目前大量使用这个特性做对象预筛,在特定应用场景下,极大的提高了性能。

原本 group 的实现就单独增加了 64bit ID ,现在两者可以合并了。而且,group 中的对象是只增不减的,只有在 entity 删除时才会去掉;另外,因为只有在 entity 创建的时候才会加入 group ,所以每个 group 中对象的 id 也是单调递增。group 只有一个操作,那就是遍历。没有随机访问的需求。

基于这些,我们甚至并不需要在 group 中用 64bit 数组来保存所有 id 。我采用的方法是保存相邻 id 的差值,并对这些差值进行变长编码。从 1 字节到 10 字节不等。由于数据量极大的减少,所以遍历效率也随之提高。

例如,我们在 group 中需要保存 1, 2, 5, 200 四个 64bit ID ,我们可以先计算出差值为 1, 1, 3, 195 。因为 id 必不相同,还可以把这些差值再减 1 变成 0,0,2, 0xc2 。

储存的时候采用 128bit varint ,即每个字节保存 7bits ,额外的 1bits 表示是否还有后续。以上 4 个差值数字可以表示为 0,0,2, 0xc2, 1 。只需要 5 个字节就可以储存下 4 个 64bits ID 。

Entity 删除并不需要从对应的 group 中删除 id ,而是等下次遍历 group 时,一边遍历一边删除那些已经不存在的 id 。


以上的重构工作暂时放在 v2 分支上