可能实现顺序读源文件、随机写还原后的文件的差分格式和还原接口吗

[Pippinrao]

背景：在嵌入式产品中，磁盘空间一般都很紧张，差分的源版本一般都是以压缩文件的形式保存在磁盘中（或者主从架构的主机磁盘中）。 问题：目前的还原是随机读源文件，顺序写目标文件，很多压缩算法是顺序读的，支持随机读取的压缩算法性能上也不是很好。当前的差分文件格式和还原接口，需要将源文件（假设压缩包大小a, 解压后大小3a）解压，然后再还原成目标文件(压缩大小为b, 解压后3b)，需要最大占用空间（不包含差分包）大小为a+3a+3b。若流式压缩输出，占用空间为a+3a+b，但是实际场景一般输出会直接使用不需要压缩，流式输出压缩后还需要再解压浪费算力且增加时长。 方案：如果能够实现顺序读源文件、随机写还原后的文件的差分格式和还原接口，那么就可以流式从压缩包中解压，再随机写入目标文件中，最大占用大小a+3b可以节省掉一部分磁盘空间(3a)和解压后写文件的时间。

[sisong]

“如果能够实现顺序读源文件、随机写还原后的文件的差分格式”
确实存在这种需求，一些设备的bin文件采用的是压缩格式，当前的算法没有为此优化。
要实现这个目标，方案A：不修改diff&patch算法和补丁包的格式，但在diff的时候约束对old数据的访问顺序（对覆盖线进行选择），使得在patch时满足顺序访问old的要求。
关于diff时约束old访问的算法，我已经有一个勉强能用的版本（速度略慢，没有开源）；该方案缺点是补丁包可能会变大很多(比如简单交换一下头尾的数据）。
方案B: diff算法不变，修改补丁包的格式，按old访问顺序对覆盖线重新排序(过长的覆盖线可能需要拆开)； 当然，patch时new数据必须支持随机写。 该方案实现应该不难，补丁大小应该几乎一致或略大。
方案C: 按新需求，针对性的实现一个diff&patch算法，简单描述的话类似于综合了A、B方案。 但实现代价可能有点大。
自己实现的话，推荐B方案

[Pippinrao]

嗯嗯，我理解B方案应该是能比较简单实现的，谢谢sisong

[sisong]

如果bin文件还是需要压缩，这样的新实现，空间复杂度还是 max(a，b)+3b 啊。
而用现有的方案（先解压a，然后删除a，patch的时候压缩得到b）也是这个空间复杂度 max(a，b)+3a 啊，新方案并没有什么优势?

[Pippinrao]

流程应该是，先用压缩包a和差分包（大小c）直接还原，获得还原后的包3b，然后删除差分包c，再升级，升级成功删除a， 然后压缩还原后的包并且删除3b 新方案最大空间占用应该是max(a+c+3b, 3b+b)

对应旧方案是先对源文件a解压3a，和差分包c还原出目标文件3b（直接还原成压缩文件是b），然后删除源文件解压文件3a，再（解压）升级，升级成功压缩目标文件删除3b和源文件a 目标版本最大空间占用是a+3a+3b+c 或者max(a+3a+b+c, b+3b)，这个方案比新方案占用也多大约一个b，并且多了一个升级前解压的时间