【代码札记】使用Java实现一个只读FUSE文件系统

本文记述了我为我的开源项目hurui200320/Ariteg实现只读FUSE的过程。

一点背景

在开始之前，我想先交代一些背景。看起来我在做毕设期间完全没有在我的网站上提我做了个啥，做完之后也完全没说。我的毕设代码放在了Github上，分为前端和后端两个仓库，毕业论文放在了后端仓库的这里，然后还有设计草稿。关于具体的细节请看我的毕业论文，简单地说，这个毕业设计实现了如下功能：

• 将不需要随时访问的文件归档存储
• 归档存储时对文件分块，采用Mekle树/有向无环图的方式存储
• 使用上述存储方式时，顺便获得了块级去重的能力，使得存储重复数据不占空间，且允许无感知地增量备份
• 服务端采用先进的证书系统对数据访问鉴权，对于用户和系统的管理则采用网页端
• 服务端和数据库全部支持集群部署，并且横向扩展的性能惩罚较小

当然了，最开始我只想做前两条，因为这个是我的实际需求。我需要找到一种方法，既能够安全可靠的存储我下载的各种动漫、电影，同时还能够获得一定量的空间节省。压缩固然最直观，可是每次压缩和解压所用的时间我实在是难以承受。正好那时候又看到了IPFS，感觉它的存储方式非常精妙，于是就受到了启发，借鉴了一下。但是只是做存储的话，好像内容有些简单，于是在毕设导师的指示下，又加了好多花哨但其实没什么用的功能（但我都很用心的设计并实现了）。

做完毕设之后，我当然不想为了存储数据而单独跑一个服务，更何况这个服务还是Java写的，还得要数据库。无论是日常运行还是备份，都未免太麻烦了。但是经过毕业设计验证，我这套自己实现的分块算法和存储结构还是很可取的。经过一些删减（当然了，手法还是比老黄¹的差远了），我实现了一个纯命令行工具：Ariteg。至于为什么叫这个名字，大家可以不用特别纠结，作为资深起名难患者，我一直用uniq.site生成随机名字，只要念着顺口，没啥尴尬的意思就可以了。这个命令行工具执行完必要的操作后就退出，完全不会驻留后台，而所有数据全部都存在硬盘上。后来随着日常使用，也不断支持了新的需求，例如一个简单的脚本系统，目前使用JavaScript来允许用户编写脚本并操作数据。

不过目前为止，所有的读写都是顺序发生的：存放文件时作为数据流将文件分块、打包成树；读取的时候通过先序遍历，不断将数据块写回文件。抛开硬盘空间，这种做法理论上能够容纳无限大的单个数据块（也就是文件）。但是目前的实现方式来看，所有的分块丢在一个文件夹里，这个限制可能会影响整个系统的能力上限。例如NTFS和EXT4最大允许一个文件夹有不到43亿个文件。假设一个文件存储512KB的数据（分块算法允许产生的最小值，不算结尾的残片），那么你只能存储不到2PB的数据。同样的限制到了旧的FAT32上，就变成了但文件夹最大6万多文件，那这个系统只能存储不到32GB的数据。不过这些问题可以通过将文件系统更新为更先进的XFS、BtrFS等来解决，姑且不是问题。（假设这种顺序存放不会带来性能惩罚，如果同一目录下的文件变多会导致访问文件变慢，那么届时我会考虑引入二级或三级文件夹）。

最近我在想，有没有一种可能，让我直接把这里面的数据直接挂载为一个硬盘或者网络位置之类的东西，我可以像Google硬盘那样读取存在这个系统里面的数据。这样使用之前就不必还原数据了。

可行性分析

有了明确需求之后，自然是想这个想法能不能实现。如果不能实现的话，那肯定就歇菜了。

由于我这个存储结构整个学的IPFS，而人家IPFS已经能够实现将给定的ipfs链接挂载成Linux下面的文件系统了，就说明这个存储结构做只读的肯定是没问题。但是我这个程序和IPFS有个本质的不同：人家用Go写的，我这个是Java。要知道，文件系统是相当底层的东西，无论是Windows还是Linux，大概率都不会接受在内核线程中运行一个JVM。

通过一些搜索，我了解到IPFS是使用FUSE来实现这个功能的。简单地说，FUSE就是一套接口，定义了内核与用户空间应用程序的交互规范。当内核收到一个文件操作请求，发现它是FUSE的话，就直接通过这个接口把文件操作的请求转发给用户空间的程序，程序处理完了再把数据返回给内核，内核返回给操作者。这样就实现了无需修改内核，便可以开发自己的文件系统了。但，我用的是Windows啊。

我又看了看之前用的MountainDuck，这个软件能够将网络位置挂载到Windows的盘符上。我不在乎它是本地硬盘还是网络位置，只要能在资源管理器中浏览就好了。由于这个是闭源软件，我只能在它的关于页面找到一些蛛丝马迹。我发现这个软件应该是用Java做与存储后端的交互，我看到诸如S3等后端的Java SDK，同时还有.NET库，然后还有JNA（Java用于访问原生库的库）。但是具体来说，我不清楚这个挂载发生在Java还是发生在.NET侧，但我推断应该是Java以某种方式调用了由.NET之类的库进行挂载。

既然Java有“Write once, run everywhere”的口号，我想我也应该多少响应一下这个口号。我找到了两个库，分别是Dokan-Java和jnr-fuse。二者的文档都非常拉垮，但至少后者还有两个examples供我模仿。前者也号称有example，但打开一看：

This class is currently a stub. Help to implement it (;

有例子，但不完全有。属于是以后再说系列。

jnr-fuse原生支持Linux，在MacOS上通过osxfuse实现，在Windows上通过winfsp实现。好，很有精神。

偷懒一时爽，拓展火葬场

虽然这个存储结构是学的IPFS，但是并没有完全学。目前来看，主要有两个问题。

第一个问题是文件名的问题。不同的操作系统对文件名有要求，而我在设计存储结构的时候对自己说：

没有什么限制名字的必要嘛，用户可以自由的命名节点，我也不用写额外的代码去检查规则，双赢！

结果等到需要实现文件系统的时候就坏菜了。虽然从文件系统中写入文件夹，文件名是合法的。但是这个存储结构本身并不限制文件名，理论上还是会出问题。怎么解决呢？我想了半天，最后得出的结论是：不解决。

自由有自由的代价，那么考虑到文件系统这么多，要求还都不一样。如果简单的在程序中审查文件名，那未来要是文件系统或者操作系统更新了，这部分代码反而会成为负担。所以这一点就靠用户来保证了。而且定性分析的话，大多数使用情况应该是从硬盘上的文件导入到这套系统中，一般来说文件名都是合法的。少部分情况，或者说，这是一种更高级的使用方法，由用户自己命名链接的名称，只有这个时候才会违反文件系统的限制。

第二个问题是早期设计的时候偷懒，因为顺序读写用不上每个片段的大小，所以我就没存。但是实现文件系统的话，首先你要知道整个文件的大小，其次要随机读写的话，你不可能顺序跳过offset，那硬盘不得直接爆炸？

于是我考虑再三，得出了两种解法：

1. 额外建立切片大小的索引。在首次遇到分片时计算并保存它的大小。因为这个系统内的数据都是不可变的，所以这个索引不怎么需要修改，只需要考虑怎么清除已经删掉的分片就好了。
2. 修改底层存储结构，在链接中加入size字段。代价是用户升级的时候需要迁移，我也需要编写对应的迁移工具。（或者不写，让用户自己在旧版导出数据，然后重新导入到新版）

在我看来，第一种更像是一个补丁（Patch），即便是没有历史包袱的新用户也要忍受这种方案。而第二种则更像是一种修复（Fix），老用户疼一下，然后就再也没有历史包袱，都可以轻快的玩耍了。我选择第二种方案。

编写FUSE

清除了各种障碍之后便可以开心的编写文件系统了。只读文件系统还是非常简单的，没有写入，没有并发，也没有锁，总之就是一个非常简单的文件系统。

要实现这样一个文件系统，主要需要实现FUSE中的以下几个函数：

• getattr：这个函数负责提供请求的路径的属性信息，例如它是文件还是目录，有多大，所有者是谁，权限是什么之类的
• readdir：这个函数负责处理目录相关的东西，准确的说就是，如果请求的路径是个目录，这个函数就负责告诉调用者这个目录下都有哪些条目
• open：这个函数是可选的，主要用于调用者打开文件时，FUSE需要做的操作（例如更新atime之类的）
• read：这个函数负责读取给定的路径
• statfs：这个函数是可选的，主要负责返回FUSE的基本信息，例如文件系统的大小、空闲空间等

解析路径

当然了，在开始实现这些函数之前，先要考虑怎么将文件系统的路径（字符串）解析成图中的节点（链接）。

对于目录类型的结构，我们有Tree这个结构来处理，它相当于一个具有顺序的文件夹。每次向系统内写入数据，数据都会被表示为一棵树。而众多的树在一起，构成了一个森林，这一部分是由Entry来表示的。Entry中记录了这棵树的创建时间等具有共性的信息（此外还避免了冲突²）。在Tree结构中，构造函数会确保一个Tree中不会出现两个同名的文件，但Entry不会。Entry的唯一性是由其ID来保证的。经过一阵思考，我决定使用这么一个粗糙但有效的方案：

/<EntryId> <EntryName>/sub folder name/part/of/the/path

其中根目录会给出所有Entry。由于FUSE在访问时只能给出字符串形式的路径，因此我们得把能够唯一区分Entry的信息写在路径里，但同时为了让人类可读，还得加上Entry的名字。找到Entry之后，就可以一步一步寻找他的子节点了。如果中途没有找到，或者请求的路径的一部分是个文件，那么FUSE可以返回对应的错误代码。如果成功找到了路径做指向的节点，那我们就指向这个节点的链接作为解析结果返回。

获取属性

接下来我们看看怎么定义属性。属性决定了这个路径的性质：文件还是文件夹。同时还提供了对应的信息，例如所有者、权限、大小、创建时间等。

对于所有者和权限，这两个是作为挂载时的参数传入的。被挂载的文件具有统一的所有者（通过uid和gid表示），同时针对文件夹和文件，设计了两种权限。因为执行（x）权限对文件来说是允许执行，而对文件夹来说则是允许切换。也就是说，即便其他用户没有权限读这个文件夹，如果有x权限，那么它是可以cd进入这个文件夹，即便进入之后也无权ls。当然了，因为这个是只读系统，即便你给了w权限，也没办法写——因为我压根儿就没实现write函数。

在处理路径的时候，根据上述设计，需要分两种情况处理：

1. 当路径是根目录，也就是/（由于是FUSE，即便在Windows上，winfsp也会贴心的帮我们把Windows的分隔符翻译成Linux的），我们只需要设置好权限信息就好了。
2. 其他情况下，我们需要解析路径，并根据解析结果进行处理。

第一种情况好理解，就不多说了。第二种情况又细分出三种情况：

1. 如果解析失败，那就返回对应的错误代码。可能是文件不存在，也可能是读取错误（解析路径时底层数据被删了）
2. 解析成功，如果链接指向的是TREE，那说明这个路径是目录，需要打上目录的属性，附上目录的权限
3. 解析成功，如果是LIST或者BLOB，就说明这是个文件，需要打上文件的属性，附上文件的权限，然后给出文件的大小和访问时间（可选）

文件大小的话，因为我们给链接加了size字段，所以可以直接遍历这个List的所有子Blob，累加即可。

读目录

类似地，读目录也需要分别处理两种情况：

1. 如果是读根目录，需要将所有Entry列举出来，作为文件夹内容返回

2. 否则需要解析路径：

   1. 若解析失败，或解析结果指向LIST或者BLOB，返回内容不存在
   2. 否则根据TREE的内容填写文件夹内容

这个比较好理解，就不多说了。这里我做了一个简单的检查，就是当文件名包含\或/的时候，这多半会导致文件系统工作不正常。所以每当检测到这种情况的时候，在控制台打印一个警告来撇清我的责任。

查询文件系统信息

读文件我们先暂且放一放，说说查询文件系统信息。这个其实也挺好实现的，无非就是算出所有blob加起来有多大，然后为了保持只读，把空闲空间设为0就行了。

真的没啥好说的。

读文件

最后我们说说读文件。每一次读请求有三个关键参数：

• path：文件的路径
• offset：从哪里开始读
• size：读多少

我们的文件是树状存储的，这一点不利于随机读。当然，我们可以先序遍历这棵树，记录已经读过的字节数，找到offset之后，再开始读数据。但遍历树的时候，每个List都要去请求一下存储后端，这会带来延迟，并且增大后端的压力。当然，一个简单粗暴的方法就是在内存中缓存这些List。反正它们都不大，也是不可变的，可以一次请求，缓存到退出。

但是这样未免太粗制滥造了一些。如果我们能够将一个文件展开成纯Blob构成的线性表，那么我们就可以跳过读List这个环节：每次需要找offset的时候，直接遍历这个数组然后累加。访问内存可比访问存储后端快多了。

我们还可以更进一步：每次读都要累加寻找offset，这种重复的工作完全可以能省就省。如果在打开文件的时候对展开的blob遍历，记录下每一个blob的offset，这样之后读取的时候就可以直接循环对比，而不再需要累加了。这就相当于是对文件建立了一个索引，但是这带来了一个额外的问题：open文件构建索引，构建完成的索引存到Map中以供读取之用，但什么时候释放呢？多个针对同一个文件的open可以直接共享同一个索引，但是这个时候就必须引入“引用计数”来决定什么时候可以释放这个索引，否则第二个程序正用着文件呢，第一个程序release了，你就把索引删了，那第二个程序怎么办？

引用计数做起来太麻烦了，考虑到读请求是多线程的，如果处理不慎，可能就会导致并发问题。秉着能麻烦别人就不麻烦自己的思路，我引入了Caffeine这个缓存库。把建立好的索引放到缓存里，如果超过5分钟没有访问索引，就把这条缓存设置为过期，以供回收。之后如果需要用到，那就再构建一个。

展开文件的代码如下：

    private fun flatten(link: Link): List<Link> {
        return when (link.type) {
            Link.Type.BLOB -> listOf(link)

            Link.Type.LIST -> getCachedList(link)!!.content.flatMap { flatten(it) }

            else -> emptyList()
        }
    }

构建缓存的代码如下：

    fun getIndex(link: Link): List<FileIndexEntry>? {
        // return if found
        blobIndexCache.getIfPresent(link.hash)?.let { return it }
        // not found
        return try {
            val flattened = flatten(link)
            var offset = 0L
            val result = flattened.map { l ->
                (FileIndexEntry(offset, l)).also { offset += l.size }
            }
            blobIndexCache.put(link.hash, result)
            result
        } catch (t: Throwable) {
            CmdContext.logger.error(t) { "Failed to build index for $link" }
            null
        }
    }

得到索引之后，我们就可以开始读文件了：

    override fun read(
        path: String, buf: Pointer, size: Long, offset: Long, fi: FuseFileInfo?
    ): Int {
        // resolve path
        val (link, errorCode) = resolvePath(path)
        if (link == null) return errorCode
        // the link should be list or blob.
        if (link.type == Link.Type.TREE) return -ErrorCodes.EISDIR()
        // try to get index, and find the first blob we need
        val blobs = (getIndex(link) ?: return -ErrorCodes.EIO())
            // starting offset + size of blob <= offset, skip it
            .dropWhile { (blobOffset, blobLink) -> blobOffset + blobLink.size < offset }
            // take only if starting offset is in range
            .takeWhile { (blobOffset, _) -> blobOffset <= offset + size }

        // read in a loop
        var readCount = 0L
        for (i in blobs.indices) {
            val objLink = blobs[i].link
            // if this is the first blob, we need to account the skipped part
            // else, reading from 0
            val iOffset = if (i != 0) 0 else offset - blobs.first().offset
            // find out how much data we read
            val iSize = min(objLink.size - iOffset, size - readCount)
            try {
                // read the blob
                val blob = RandomAccessCache.getCachedBlob(objLink) ?: return -ErrorCodes.EIO()
                // copy data
                buf.put(readCount, blob.data, iOffset.toInt(), iSize.toInt())
                readCount += iSize
            } catch (t: Throwable) {
                logger.error(t) { "Error when reading $link at path $path" }
                return -ErrorCodes.EIO()
            }
            if (readCount >= size)
                break
        }
        return readCount.toInt() // return the number of actual bytes read
    }

至此，一个简单的只读FUSE就完成啦！

缓存

挂载如上实现的文件系统，好像用是可以用，但太慢了：Windows资源管理器在访问文件夹时会尝试构建缩略图。我这里面存的全都是视频。Windows会尝试遍历文件夹，然后针对每个视频构建缩略图，带来巨大数量的读请求。而这个FUSE读的不够快，导致Windows资源管理器又卡又慢。而打开一个文件，视频能播放，但是拖动进度条的时候似乎有写卡顿。这怎么优化呢？

怎么优化呢？我都铺垫到这里了：上面既然都引入了缓存库，那只缓存一个文件索引，不免有些物未尽其用了。由于Entry、Tree这些都是小文件，每次解析路径都必须访问他们才能找到对应的链接，而解析路径在每个环节都必不可少。如果能把Entry和Tree缓存起来，自然能节省不少时间。Tree缓存没得说，因为Tree是不可变的，但是Entry不是啊。如果要缓存Entry，就得考虑修改的问题。这种修改主要有更新和删除两种。Entry更新时，就必须要更新子文件夹中的内容。如果Entry删除了，那解析的时候应该提示内容不存在，而非根据内存中缓存的结果继续返回数据。解决办法嘛，也好办：设置一个过期规则，每一个Entry缓存在创建10秒钟后失效，从而迫使程序读取硬盘上的最新数据。

此外，Tree和Entry都缓存了，List其实也不大，不如也一块缓存了。因为是不可变的小文件，而其可达性由其所属的Entry决定。但是为了避免不断缓存List导致内存泄漏，在缓存时采用了softValue策略，即通过软引用的方式来保证内存不足时可以回收这些List。

最后一点锦上添花的缓存就是对于Blob的缓存。Blob的平均大小在1MB左右，缓存他们代价非常高昂。但缓存他们又能获得性能提升。考虑如下场景：一个Blob的offset是1.5MB，大小是3MB。假设一个程序从1.7MB开始读，每次读32KB。如果我们不缓存Blob，那么每一次读32KB，我们都得完整的请求一个blob（因为存储后端除了支持随机读的磁盘，还有不支持随机读的S3）。如果我们能够在第一次读的时候把Blob缓存起来，后续读就能节省不少时间。岂不美哉？

总体来说，关于缓存，我的策略如下：

• 对于文件索引的缓存，使用强引用保证其不会被垃圾回收。但设定15分钟不访问则回收内存，避免一直缓存无用条目。
• 对于Blob、List和Tree的缓存，全部使用软引用。内存够用就一直缓存，不够用就回收掉它们。
• 对于Entry的缓存，除了具有生存时间的限制，还要做软引用，以便提前回收，给其他数据腾地儿。

经过这么一通缓存，程序启动时（因为Windows构建缩略图而被填充的缓存）占用内存2.2GB，高强度使用一段时间（逐渐填充Blob缓存）后内存占用为5.5GB。毕竟Java嘛，你再怎么优化也逃不开GC的魔掌。什么？内存不够用？加钱换内存啊！

测试的时候同时播放了12个视频（受制于显卡的视频解码器），来回在不同视频中拖动进度条，没有卡顿的感觉。你说这内存占用的值不值？我有64G内存，我觉得值（笑）。

-全文完-

---

【代码札记】使用Java实现一个只读FUSE文件系统 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。