From 0fa8ef26259488af039a5f85bd0c3c457e13f264 Mon Sep 17 00:00:00 2001 From: Benjamin Barenblat Date: Fri, 22 Oct 2021 10:30:34 -0400 Subject: Check in design for laptopfs --- DESIGN.md | 415 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ LICENSE | 202 ++++++++++++++++++++++++++++++ 2 files changed, 617 insertions(+) create mode 100644 DESIGN.md create mode 100644 LICENSE diff --git a/DESIGN.md b/DESIGN.md new file mode 100644 index 0000000..e4e1101 --- /dev/null +++ b/DESIGN.md @@ -0,0 +1,415 @@ +laptopfs +======== + +Benjamin Barenblat, +October 16, 2021 + + +Objective +--------- + +Build a highly available network file system. + + +Requirements +------------ + +laptopfs is a network file system designed for use on laptop home directories. +This means it is + + - a file system, allowing the users to manipulate files and directories using + established working patterns. + + - highly available and partition-resistant, supporting offline operation just + as well as it supports online operation. + + - secure by default, ensuring confidentiality and integrity whenever data + leave the laptop, including when they are stored on file servers. + + - designed for multiple concurrent active sessions. + + - disk- and bandwidth-efficient, transferring and storing only the data users + actually need. + +laptopfs is not + + - designed for collaboration. If two clients modify the file system at the + same time, the server will reject one client’s write; while the unfortunate + client will likely succeed on a second attempt, this does not scale well and + should generally be avoided. + + - a completely POSIX-compatible file system. In particular, laptopfs does not + support hard links, device nodes, or IPC mechanisms (named pipes, sockets, + etc.). + + +Out of Scope +------------ + +Though laptopfs encrypts data whenever they leave the laptop and ensures the +user’s data are encrypted remotely, it does not encrypt data while they are +stored on the local disk. If a user requires this level of security, they should +leverage the functionality built into their operating system. + +laptopfs clients use file system modification times to resolve certain types of +writer–writer races. To ensure that races are resolved in an unsurprising way, +clients should be well-synchronized to a coherent clock source. NTP (or even +SNTP) should be sufficient for this. + + +Background +---------- + +Distributed computing has captured both public imagination and corporate +attention for over half a century. The stories of Arthur C. Clarke envision a +distant future where mainframes are shared between entire neighborhoods. Later, +Sun Microsystems promised a distributed future, proclaiming that “The network is +the computer”. So-called distributed operating systems like Plan 9 from Bell +Labs continue to draw attention decades after their development mostly stopped. + +However, the promised land of distributed computing has mostly failed to +materialize. Comparing visions against reality, it’s easy to see why: Today’s +world consists not of a vast network of computers communicating at the speed of +light, but rather a vast archipelago of high-speed, high-reliability network +fabrics joined by comparatively slow, sketchy, and expensive links. It is +telling that even security-conscious corporations have had to make firewall +exceptions for Mosh, a remote terminal protocol that supports low bandwidth and +high latency, and that the world’s most popular “distributed” version control +system, Git, is the one that allows users to work productively with no network +connection at all. + +While researchers and developers have made incredible progress building fast and +secure file systems that operate on individual machines and on high-speed +network fabrics, there currently exists no file system that truly embraces the +archipelago model. NFS and AFS can be configured to support low bandwidth and +high latency, but neither allows disconnected operation. Past efforts to add +support for true disconnected operation to existing network file systems have +stalled. Most users thus access their remote files either by creating working +copies on local disk (cf. Dropbox, Unison) or by offloading computing elsewhere +(cf. Google Docs, Overleaf). These solutions satisfy most users’ requirements +but also present considerable drawbacks, ranging from cognitive overhead from +tracking multiple copies to philosophical frustration from using closed-source +software. + + +Related Work +------------ + +No past effort to create a network file system that supports disconnected +operation has yet succeeded. Most have definitively failed, crushed under their +own complexity. + +[Coda](http://coda.cs.cmu.edu/), a fork of AFS that aims to support disconnected +operation, has been under development since 1987. Dormant for many years, it has +recently received a burst of new activity. Reflecting its origins in the 1980s, +Coda’s code quality and RPC protocol leave something to be desired, though work +is occurring to bring it up to modern standards. Despite this work, Coda still +includes significant known security bugs and is not yet suitable for production +deployment on the internet. + +[Bazil](https://bazil.org/) was an attempt to create a decentralized, +distributed file system that supported disconnected operation. Though the +project produced a high-quality [Go FUSE library](https://github.com/bazil/fuse), +development on Bazil itself seems to have stalled around 2015. + +Robert Mustacchi’s bachelor’s thesis, [StashFS: Generalized Disconnected +Operation](https://cs.brown.edu/research/pubs/theses/ugrad/2010/mustacchi.pdf), +described a FUSE overlay file system that added disconnected operation to _any_ +network file system. Because it operates as an overlay file system, StashFS is +somewhat constrained in the assumptions it can make, but it seems fundamentally +sound. Unfortunately, its code is not publicly available, and the author did not +respond to email asking for a copy. + +[Dropbox](https://dropbox.com/) and [Google Drive](https://drive.google.com/) +are premier proprietary cloud storage offerings. However, they are +synchronization services, not file systems, which means they are fairly heavy on +disk usage. Furthermore, each uses proprietary server software and RPC +protocols, making them impossible to self-host and difficult to reliably extend. + + +Detailed Design +--------------- + +A laptopfs network consists of one server and zero or more clients. The server +holds the entire file system and passes hunks of it to interested clients; it +also notifies connected clients when the file system has changed. The clients +get hunks of the file system from the server, upload new hunks, and present the +contents of the file system to users via FUSE. + + +### The Server ### + +Fundamentally, the laptopfs server implements an RPC-accessible key-value store. +It has a few extra bits to facilitate use of that store as a file system, but +the basic RPC interface to laptopfsd looks an awful like the interface to a hash +table: You can request a hunk of data by ID, or you can upload a new hunk of +data. Unlike most hash tables, however, clients see laptopfsd’s key-value store +as append-only: They cannot delete or modify entries in the store. This prevents +reader–writer races between clients. (Writer–writer races are addressed later.) + +Using the append-only key-value store, it’s fairly easy to implement a +copy-on-write file system by differentiating between three types of hunks: + + - A data hunk stores raw data. + + - A file hunk is a hunk containing a serialized vector of IDs, offsets, and + lengths, each triplet representing a slice of a data hunk. Retrieving those + data hunks, slicing them appropriately, and concatenating the slices yields + the contents of the file. + + - A directory hunk is a hunk containing a set of file hunk IDs as well as a + name, mtime, mode, etc. for each file. + +The server tracks the ID of the root directory, and clients can update that ID +using a special RPC. This is the one destructive operation that a client can +perform, and it has several safeguards built into it. Notably, an update-root +RPC does not simply request that the server update the root to a new value; it +requests that the server update the root _from_ an old value _to_ a new value. +If the old value does not match the current root ID, the server will reject the +transaction. This enables a client to detect that its change would have +clobbered another client’s changes, at which point the client can initiate a +merge process and try again. + +Because mutating the file system necessarily involves at least two changes (one +to upload the new root directory and one to set it as the root), the server +allows clients to group mutations into transactions. To avoid round trips during +the transactions, the server requires clients to generate new IDs; it will +reject a transaction if the transaction attempts to use an ID already in use. + +Since clients see the store as append-only, the server must garbage-collect it +periodically to avoid unbounded growth. This means the server needs to know the +links between hunks in the file system. To facilitate this – while leaving the +server as oblivious as possible to the actual contents of the file system – +clients use AEAD to reveal the relevant parts of file and directory hunks. + + - Data hunks encrypt everything, leaving the associated data region empty. + + - File hunks encrypt data hunk offsets and lengths, leaving the data hunk IDs + in the associated data region. + + - Directory hunks encrypt file names, mtimes, modes, etc., leaving the file + hunk IDs in the associated data region. + +The server implements a simple mark-and-sweep garbage collection algorithm and +runs it at thresholds configurable by the administrator. During the collection, +the server will reject transactions that mutate the file system, but since this +is strictly more favorable to the client than completely disconnected operation, +clients can cope. + +To allow clients to detect changes, the server allows clients to subscribe for +updates to the root. + +The final RPC interface for the server, in pseudo-gRPC, thus looks like this: + + message Hunk { + message AssociatedData { + repeated bytes referenced_hunk_ids + } + + bytes id + AssociatedData associated_data [security = signed] + bytes data [security = signed+encrypted] + } + + message GetHunkRequest { + repeated bytes ids + } + + message GetHunkResponse { + repeated Hunk hunks // any requested hunks that exist + } + + + message TransactionOperation { + message PutHunk { + Hunk hunk + } + + message UpdateRoot { + bytes old_id + bytes new_id + } + + oneof op { + PutHunk put_hunk + UpdateRoot update_root + } + } + + message ExecuteTransactionRequest { + repeated TransactionOperation ops; + } + + message ExecuteTransactionResponse {} + + + message RootIdRequest { + bool include_hunk + } + + message RootIdResponse { + bytes new_root_id + optional Hunk new_root + } + + + service Laptopfs { + rpc GetHunk(GetHunkRequest) returns (GetHunkResponse) {} + rpc ExecuteTransaction(ExecuteTransactionRequest) returns (ExecuteTransactionResponse) {} + + // This returns the current value immediately and then streams updates as + // they happen. + rpc RootId(RootIdRequest) returns (stream RootIdResponse) {} + } + + +### The Client ### + +Since the laptopfs server is oblivious to most data in the system, most +complexity appears in the laptopfs client. The client has three roles: It must +maintain a local disk cache of the state that exists on the server, it must +reveal that state to the user through a FUSE interface, and it must push user +changes back to the server. + +The laptopfs client implements its on-disk cache using both a key-value store +(like the server’s) and a log. The key-value store is a pure cache of the server +state; the client never mutates it except in response to an announcement +received from the server. The log, then, stores a record of all mutations that +the client has made but not pushed to the server. This allows the client’s file +system bits to mimic the implementation of a log-structured file system, a +well-understood design that is both relatively simple and fairly performant. + +One set of client worker threads are responsible for maintaining the client’s +store. At startup, the client starts a `RootId` RPC with the server to get the +current ID of the root directory. It then executes a breadth-first search of the +file system, fetching all directory and file hunks. Data hunks are not fetched +in advance – instead, they’re fetched as the user tries to read them. (The +client can apply whatever heuristics it wants to try to make reads as +low-latency as possible, but basic readahead, triggered on open(2), lseek(2), +and read(2), should cover most basic cases.) The end result is that while file +access might lag a bit, navigating through the file system itself should always +feel snappy. As the root directory ID changes, the client restarts its +breadth-first search, optionally after waiting for the file system to settle. + +As the client receives hunks from the server, it decrypts and verifies their +integrity; before it uploads new hunks to the server, it encrypts them. Data +hunks are thus stored on disk simply as their contents, while file and directory +hunks have more structure: + + message Timestamp { + uint64 seconds + fixed32 nanoseconds + } + + message FileHunk { + message HunkSlice { + uint64 offset + uint64 length + } + + repeated HunkSlice slices + + // The actual last time the data in the file changed. + Timestamp true_modification_time + } + + message DirectoryHunk { + message FileInfo { + message Xattr { + bytes name + bytes value + } + + bytes name + uint32 mode + Timestamp mtime + repeated Xattr xattrs + } + + repeated FileInfo files + + // The actual last time the data in the directory hunk changed. + Timestamp true_modification_time +} + +As the user interacts with the FUSE frontend, the client computes a view of the +file system from replaying the log on top of the store and adds entries to the +log to correspond to user changes. Log entries are all timestamped; each can be +one of the following operations: + + - WRITE(data, path) (creating the file if it does not yet exist) + + - DELETE(path) + + - RENAME(path, path) + + - SETMTIME(path, timestamp) + + - CHMOD(path, mode) + + - SETXATTR(path, name, value) + +The algebra for replaying these changes is based on “last one wins” semantics. + +Every few seconds (with the delay configurable by the user), the client updates +the server on anything that has changed locally. The client first compacts the +log. It then computes the minimally sized transaction that will apply the +changes contained in the log to the store. Finally, it attempts to commit this +transaction to the server. If the transaction succeeds, the client drops the +uploaded changes from the log. If it fails, the client does nothing and tries +again later. + +Like the server, the client uses a mark-and-sweep garbage collector to prevent +its store from growing arbitrarily large. The client also can drop data to keep +its disk usage small; it implements a simple least recently used scheme to +determine when to drop data the user is likely no longer interested in. + +laptopfs supports one important operation beyond the standard Unix file system +API: the ability to pin files to local disk. The client maintains a list of +files the user would like to have locally at all times and fetches them whenever +it discovers they have changed. These files are exempt from cache drops. + + +### Future Work ### + +This design is highly extensible. Provided clients and servers all implement the +RPC interface with the same semantics, multiple client and server +implementations can coexist. The RPC interface is even transport-agnostic, and +one could envision a client that supported multiple transports via plugins. + +The client has virtually unlimited latitude to heuristically prefetch and drop +data, and heuristics will be an area of active exploration after the initial +implementation. + + +Security and Privacy Considerations +----------------------------------- + +laptopfs encrypts most data stored in the file system using 256-bit AES-GCM with +a key accessible only to the user. This produces fairly good privacy properties: + + - Integrity: Neither the server nor an active adversary can modify data that + the user has uploaded. A malicious server could serve old data, but clients + can detect if it throws away a transaction (as it will not signal a root + invalidation after a transaction successfully completes). + + - Confidentiality: The file system data are fully confidential, but metadata + are not. In particular, the server knows the general tree structure of the + file system and can estimate the number of files in each directory. The + server does not, however, have access to file names and can only make + educated guesses at file sizes. + + - Availability: The server or an active adversary can deny service at any + time. On the other hand, laptopfs is designed to work with a disconnected + server. + + +Work Estimates +-------------- + +You can always stop at any time. + + +TODO: We need a slightly better log interface – this one doesn’t do very well +when you’re trying to change a small part of a very large file (e.g., updating +metadata in a ripped Blu-Ray). diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..d645695 --- /dev/null +++ b/LICENSE @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright [yyyy] [name of copyright owner] + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. -- cgit v1.2.3