FARSITE: Federated, Available and Reliable Storage for an Incompletely Trusted EnvironmentPaper highlightsServerless file systemsDesign assumptions (I)Design assumptions (II)Design assumptions (III)Enabling technology trends (I)Enabling technology trends (II)Namespace rootsTrust and certification (I)Sybil attacksTrust and certification (II)Trust and certification (III)Trust and certification (IV)Handling malicious behaviorsSystem architecture (I)System architecture (II)The directory group (I)The directory group (II)The directory group (III)The file hosts (I)The file hosts (II)Semantic differencesReliability and availability (I)Reliability and availability (II)Security (I)Security (II)What is a Merkle hash tree? (I)What is a Merkle hash tree? (II)Durability (I)Durability (II)Consistency (I)Consistency (II)Consistency (III)ScalabilityEfficiencyEvaluationFARSITE: Federated, Available and Reliable Storage for an Incompletely Trusted EnvironmentA. Atta, W. J. Bolowsky, M. Castro, G. Cermak,R. Chaiken, J. R. Douceur, J. Howell,J. R. Lorch, M. Theimer, R. P. WattenhofferMicrosoft ResearchPaper highlights•Paper discusses a distributed file system lacking a central server–Files and directories reside on client machines –Files are encrypted and replicated –Directory metadata are maintained by Byzantine-replicated finite state machinesServerless file systems•Idea is not new–xFS (Anderson et al. SOSP 1995)•Objective is to utilize free disk space and processing power of client machines•Two major issues are–Availability of files–SecurityDesign assumptions (I)1. Farsite is intended to run on the desktops of a large corporation or a university:–Maximum scale of ~105 machines–Interconnected by a high-bandwidth low-latency network–Most machines up most of the time–Uncorrelated machine failuresDesign assumptions (II)2. No files are both–Read by many users and–Frequently updated by at least one user(very infrequent in Windows NT file system)3. Small but significant fraction of users will maliciously attempt to destroy or corrupt file data and metadataDesign assumptions (III)4. Large fraction of users may independently attempt unauthorized accesses5. Each machine is under the control of its immediate user–Cannot be subverted by other people6. No user sensitive data persist after logout or system reboot–Not true for any commodity OSEnabling technology trends (I)1. General increase in unused disk capacity:for 4800 desktops at Microsoft researchYear Unused disk space1998 49%1999 50%2000 58%Enabling technology trends (II)2. Lowered cost of cryptographic operations:–Can now encrypt data at 72MB/s–Faster than disk sequential I/O bandwidth (32MB/s)Namespace roots•Farsite provides hierarchical directory namespaces–Each namespace has its own root –Each root has a unique root name–Each root is managed by a designated set of machines forming a Byzantine-fault-tolerant group•No need for a protected set of machinesTrust and certification (I)•Basic Requirements–Users must trust the machines that offer to present data or metadata–Machines must trust the validity of requests from remote users–System security must trust that machines that claim to be distinct are truly distinct•To prevent Sybil attacksSybil attacks•(Douceur 2002)•Possible whenever redundancy is used to increase security•Single rogue entity can–Pretend to be many and–End controlling a large part of the system•Cannot prevent them without alogically centralized authority certifying identitiesTrust and certification (II)•Farsite manages trust throughpublic-key cryptographic certificates–Namespace certificates –User certificates–Machine certificatesTrust and certification (III)•Bootstrapped by fiat:–Machines told to accept certificates that can be authenticated with some public keys–Associated private keys are called Certification Authorities (CA) •Certificates created either by CAs themselves or by users authorized to create certificatesTrust and certification (IV)•User private keys are–Encrypted with a symmetric key derived from user password–Stored in a globally-readable directory in Farsite•Does not require users to modify their behavior•User or machine keys can be revokedHandling malicious behaviors•Most fault-tolerant file systems do not protect users’ files against malicious behaviors of hosts•They assume that a host will eitherbehave correctly or crash•Malicious behaviors are often calledByzantine failures–One or more hosts act as if they were controlled by very clever traitorsSystem architecture (I)•Each Farsite client will deal with two different sets of hosts–A set of machines constituting adirectory group–A set of machines acting as file hosts •In practice these three roles are shared by all machinesClientFileHostFileHostFileHostMember MemberMember MemberDirectory GroupClient sees one directory groupSystem architecture (II)The directory group (I)•Replicates directories on directory members•Directory integrity enforced through a Byzantine-fault-tolerant protocol– Works as long as less than one-third of the hosts misbehave in any manner (“traitor)–Requires a minimum of four hosts to tolerate one misbehaving hostThe directory group (II)•Decisions for all operations that are not determined by the client request are made through a cryptographically secure distributed random number generator•Issues leases on files to clients–Promise not to allow any incompatible access to the file during the duration of the lease without notifying the clientThe directory group (III)•Directory groups can split:–Randomly select a group of machines they know–Tell them to form a new directory group–Delegate a portion of their namespace to new group•Both user and directory group mutually authenticate themselvesThe file hosts (I)•Farsite stores encrypted replicas of each file to ensure file integrity and file availability•Continuously monitors host availability and relocates replicas whenever necessary•Does not allow all replicas of a given file to reside on hosts owned by the same user•Files that were recently accessed by a client are cached locally (for “roughly one week”)The file hosts (II)•Farsite does not use voting:–Correct replicas are identified by the directory host•Farsite does not update at once all replicas of a file:–Would be too slow–Uses instead a background update mechanismSemantic