diff options
Diffstat (limited to 'static/src/_posts/2022-01-23-the-cryptic-filesystem.md')
| -rw-r--r-- | static/src/_posts/2022-01-23-the-cryptic-filesystem.md | 258 |
1 files changed, 0 insertions, 258 deletions
diff --git a/static/src/_posts/2022-01-23-the-cryptic-filesystem.md b/static/src/_posts/2022-01-23-the-cryptic-filesystem.md deleted file mode 100644 index 1c4138b..0000000 --- a/static/src/_posts/2022-01-23-the-cryptic-filesystem.md +++ /dev/null @@ -1,258 +0,0 @@ ---- -title: >- - The Cryptic Filesystem -description: >- - Hey, I'm brainstorming here! -series: nebula -tags: tech ---- - -Presently the cryptic-net project has two components: a VPN layer (implemented -using [nebula][nebula], and DNS component which makes communicating across that -VPN a bit nicer. All of this is wrapped up in a nice bow using an AppImage and a -simple process manager. The foundation is laid for adding the next major -component: a filesystem layer. - -I've done a lot of research and talking about this layer, and you can see past -posts in this series talking about it. Unfortunately, I haven't really made much -progress on a solution. It really feels like there's nothing out there already -implemented, and we're going to have to do it from scratch. - -To briefly recap the general requirements of the cryptic network filesystem -(cryptic-fs), it must have: - -* Sharding of the fs dataset, so each node doesn't need to persist the full - dataset. - -* Replication factor (RF), so each piece of content must be persisted by at - least N nodes of the clusters. - -* Nodes are expected to be semi-permanent. They are expected to be in it for the - long-haul, but they also may flit in and out of existence frequently. - -* Each cryptic-fs process should be able to track multiple independent - filesystems, with each node in the cluster not necessarily tracking the same - set of filesystems as the others. - -This post is going to be a very high-level design document for what, in my head, -is the ideal implementation of cryptic-fs. _If_ cryptic-fs is ever actually -implemented it will very likely differ from this document in major ways, but one -must start somewhere. - -[nebula]: https://github.com/slackhq/nebula - -## Merkle DAG - -It wouldn't be a modern network filesystem project if there wasn't a [Merkle -DAG][mdag]. The minutia of how a Merkle DAG works isn't super important here, -the important bits are: - -* Each file is represented by a content identifier (CID), which is essentially a - consistent hash of the file's contents. - -* Each directory is also represented by a CID which is generated by hashing the - CIDs of the directory's files and their metadata. - -* Since the root of the filesystem is itself a directory, the entire filesystem - can be represented by a single CID. By tracking the changing root CID all - hosts participating in the network filesystem can cheaply identify the latest - state of the entire filesystem. - -A storage system for a Merkle DAG is implemented as a key-value store which maps -CID to directory node or file contents. When nodes in the cluster communicate -about data in the filesystem they will do so using these CIDs; one node might -ask the other "can you give me CID `AAA`", and the other would respond with the -contents of `AAA` without really caring about whether or not that CID points to -a file or directory node or whatever. It's quite a simple system. - -As far as actual implementation of the storage component, it's very likely we -could re-use some part of the IPFS code-base rather than implementing this from -scratch. - -[mdag]: https://docs.ipfs.io/concepts/merkle-dag/ - -## Consensus - -The cluster of nodes needs to (roughly) agree on some things in order to -function: - -* What the current root CID of the filesystem is. - -* Which nodes have which CIDs persisted. - -These are all things which can change rapidly, and which _every_ node in the -cluster will need to stay up-to-date on. On the other hand, given efficient use -of the boolean tagged CIDs mentioned in the previous section, this is a dataset -which could easily fit in memory even for large filesystems. - -I've done a bunch of research here and I'm having trouble finding anything -existing which fits the bill. Most databases expect the set of nodes to be -pretty constant, so that eliminates most of them. Here's a couple of other ideas -I spitballed: - -* Taking advantage of the already written [go-ds-crdt][crdt] package which the - [IPFS Cluster][ipfscluster] project uses. My biggest concern with this - project, however, is that the entire history of the CRDT must be stored on - each node, which in our use-case could be a very long history. - -* Just saying fuck it and using a giant redis replica-set, where each node in - the cluster is a replica and one node is chosen to be the primary. [Redis - sentinel][sentinel] could be used to decide the current primary. The issue is - that I don't think sentinel is designed to handle hundreds or thousands of - nodes, which places a ceiling on cluster capacity. I'm also not confident that - the primary node could handle hundreds/thousands of replicas syncing from it - nicely; that's not something Redis likes to do. - -* Using a blockchain engine like [Tendermint][tendermint] to implement a custom, - private blockchain for the cluster. This could work performance-wise, but I - think it would suffer from the same issue as CRDT. - -It seems to me like some kind of WAN-optimized gossip protocol would be the -solution here. Each node already knows which CIDs it itself has persisted, so -what's left is for all nodes to agree on the latest root CID, and to coordinate -who is going to store what long-term. - -[crdt]: https://github.com/ipfs/go-ds-crdt -[ipfscluster]: https://cluster.ipfs.io/ -[sentinel]: https://redis.io/topics/sentinel -[tendermint]: https://tendermint.com/ - -### Gossip - -The [gossipsub][gossipsub] library which is built into libp2p seems like a good -starting place. It's optimized for WANs and, crucially, is already implemented. - -Gossipsub makes use of different topics, onto which peers in the cluster can -publish messages which other peers who are subscribed to those topics will -receive. It makes sense to have a topic-per-filesystem (remember, from the -original requirements, that there can be multiple filesystems being tracked), so -that each node in the cluster can choose for itself which filesystems it cares -to track. - -The messages which can get published will be dependent on the different -situations in which nodes will want to communicate, so it's worth enumerating -those. - -**Situation #1: Node A wants to obtain a CID**: Node A will send out a -`WHO_HAS:<CID>` message (not the actual syntax) to the topic. Node B (and -possibly others), which has the CID persisted, will respond with `I_HAVE:<CID>`. -The response will be sent directly from B to A, not broadcast over the topic, -since only A cares. The timing of B's response to A could be subject to a delay -based on B's current load, such that another less loaded node might get its -response in first. - -From here node A would initiate a download of the CID from B via a direct -connection. If node A has enough space then it will persist the contents of the -CID for the future. - -This situation could arise because the user has opened a file in the filesystem -for reading, or has attempted to enumerate the contents of a directory, and the -local storage doesn't already contain that CID. - -**Situation #2: Node A wants to delete a CID which it has persisted**: Similar -to #1, Node A needs to first ensure that other nodes have the CID persisted, in -order to maintain the RF across the filesystem. So node A first sends out a -`WHO_HAS:<CID>` message. If >=RF nodes respond with `I_HAVE:<CID>` then node A -can delete the CID from its storage without concern. Otherwise it should not -delete the CID. - -**Situation #2a: Node A wants to delete a CID which it has persisted, and which -is not part of the current filesystem**: If the filesystem is in a state where -the CID in question is no longer present in the system, then node A doesn't need -to care about the RF and therefore doesn't need to send any messages. - -**Situation #3: Node A wants to update the filesystem root CID**: This is as -simple as sending out a `ROOT:<CID>` message on the topic. Other nodes will -receive this and note the new root. - -**Situation #4: Node A wants to know the current filesystem root CID**: Node A -sends out a `ROOT?` message. Other nodes will respond to node A directly telling -it the current root CID. - -These describe the circumstances around the messages used across the gossip -protocol in a very shallow way. In order to properly flesh out the behavior of -the consistency mechanism we need to dive in a bit more. - -### Optimizations, Replication, and GC - -A key optimization worth hitting straight away is to declare that each node will -always immediately persist all directory CIDs whenever a `ROOT:<CID>` message is -received. This will _generally_ only involve a couple of round-trips with the -host which issued the `ROOT:<CID>` message, with opportunity for -parallelization. - -This could be a problem if the directory structure becomes _huge_, at which -point it might be worth placing some kind of limit on what percent of storage is -allowed for directory nodes. But really... just have less directories people! - -The next thing to dive in on is replication. We've already covered in situation - #1 what happens if a user specifically requests a file. But that's not enough -to ensure the RF of the entire filesystem, as some files might not be requested -by any users except the original user to add the file. - -We can note that each node knows when a file has been added to the filesystem, -thanks to each node knowing the full directory tree. So upon seeing that a new -file has been added, a node can issue a `WHO_HAS:<CID>` message for it, and if -less than RF nodes respond then it can persist the CID. This is all assuming -that the node has enough space for the new file. - -One wrinkle in that plan is that we don't want all nodes to send the -`WHO_HAS:<CID>` at the same time for the same CID, otherwise they'll all end up -downloading the CID and over-replicating it. A solution here is for each node to -delay it's `WHO_HAS:<CID>` based on how much space it has left for storage, so -nodes with more free space are more eager to pull in new files. - -Additionally, we want to have nodes periodically check the replication status of -each CID in the filesystem. This is because nodes might pop in and out of -existence randomly, and the cluster needs to account for that. The way this can -work is that each node periodically picks a CID at random and checks the -replication status of it. If the period between checks is calculated as being -based on number of online nodes in the cluster and the number of CIDs which can -be checked, then it can be assured that all CIDs will be checked within a -reasonable amount of time with minimal overhead. - -This dovetails nicely with garbage collection. Given that nodes can flit in and -out of existence, a node might come back from having been down for a time, and -all CIDs it had persisted would then be over-replicated. So the same process -which is checking for under-replicated files will also be checking for -over-replicated files. - -### Limitations - -This consistency mechanism has a lot of nice properties: it's eventually -consistent, it nicely handles nodes coming in and out of existence without any -coordination between the nodes, and it _should_ be pretty fast for most cases. -However, it has its downsides. - -There's definitely room for inconsistency between each node's view of the -filesystem, especially when it comes to the `ROOT:<CID>` messages. If two nodes -issue `ROOT:<CID>` messages at the same time then it's extremely likely nodes -will have a split view of the filesystem, and there's not a great way to -resolve this until another change is made on another node. This is probably the -weakest point of the whole design. - -[gossipsub]: https://github.com/libp2p/specs/tree/master/pubsub/gossipsub - -## FUSE - -The final piece is the FUSE connector for the filesystem, which is how users -actually interact with each filesystem being tracked by their node. This is -actually the easiest component, if we use an idea borrowed from -[Tahoe-LAFS][tahoe], cryptic-fs can expose an SFTP endpoint and that's it. - -The idea is that hooking up an existing SFTP implementation to the rest of -cryptic-fs should be pretty straightforward, and then every OS should already -have some kind of mount-SFTP-as-FUSE mechanism already, either built into it or -as an existing application. Exposing an SFTP endpoint also allows a user to -access the cryptic-fs remotely if they want to. - -[tahoe]: https://tahoe-lafs.org/trac/tahoe-lafs - -## Ok - -So all that said, clearly the hard part is the consistency mechanism. It's not -even fully developed in this document, but it's almost there. The next step, -beyond polishing up the consistency mechanism, is going to be roughly figuring -out all the interfaces and types involved in the implementation, planning out -how those will all interact with each other, and then finally an actual -implementation! |