FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted EnvironmentOutlineFARSITE GoalsWhy serverless?Target EnvironmentFARSITE Non-GoalsEnabling TechnologiesSystem ArchitectureSystem Architecture (Cont…)Slide 10CertificatesClient reads a file…..Client writes to file…File System FeaturesReliability and AvailabilitySecurityDurabilityConsistencyEfficiencyManageabilityDifferences from NTFSEvaluationConclusionRelated workFARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted EnvironmentPresented by: Boon Thau LooCS294-4(Adapted from Adya’s OSDI’02 slides)OutlineIntroductionSystem ArchitectureFile System featuresEvaluationConclusionFARSITE GoalsA symbiotic, serverless, distributed file system Symbiotic – works among cooperating but not completed trusted clients.Serverless Runs entirely on client machines.Logically centralized but physically distributed.Ensure user privacy and data integrity.Scalable and efficient.Easy management and self-configuration.Why serverless?Servers are more powerful, more secured, better maintained, but…Reliant on system administrators Do you trust them with your data?Are they competent?Expensive (special hardware)High-performance I/O, RAID disk, special roomsCentralized points of failure High-value targets for attacksTarget EnvironmentLarge university or companyHigh-bandwidth, low-latency networkClients are cooperative but not completed trustedRough scale:105 total machines, 1010 total files, 1015 total bytesMachine availability Lower than dedicated servers, higher than Internet hosts.Uncorrelated machine downtimes.Workload: High access locality, low persistent update rates, usually sequential but rarely concurrent read/write sharing.Small but significant fraction of malicious users.No user-sensitive data persist beyond user logoff or reboot.FARSITE Non-GoalsEfficient large-scale write sharingTransactional semanticsVersioningUser-specifiable importanceHigh-performance parallel I/ODisconnected operation with offline conflicts (Coda-like)Enabling TechnologiesAvailability: enough disk space for replicasLow disk costsUnused disk capacityDuplicate files: ~50% space savings Privacy: fast cryptoSymmetric encryption: 72 MB/secOne-way hashing bandwidth: 53 MB/secDisk sequential I/O bandwidth: 32 MB/secComputing RSA signature: 6.5 msec < Rotation time for a 7200-RPM disk.System ArchitectureFile system construct:Hierarchical directory namespaceNamespace - Logical repository of files (a directory).Namespace root – A virtual file serverCreated by administrator.Machine roles:Client – Directly interacts with usersDirectory group member – Manages file metadata.File host – Stores encrypted replicas of data files.System Architecture (Cont…)Directory Group:Manages file metadata for a namespaceChoice of machines for namespace root assigned by administrator. Subtree of namespace can be delegated to subgroup under heavy load. Separate data and metadata:Use Byzantine agreement protocol in directory group to protect metadata against malicious clients.Replicate and encrypt data in file hosts.Stores cryptographically secure hash of data in directory group for validation.System Architecture (Cont…)CertificatesMachine CertificatesAssociate a machine with own public keys.Establishing the validity of machine.Namespace certificatesAssociate namespace roots to set of managing machines.Administrator grants root certificate.User certificatesAssociate users to their public keysFor read/write access control to files.Certification authorities (CAs)Client reads a file…..1. Send message to directory group.2. Directory group proves its authority (recursively to root) using namespace certificates. 3. Directory Group grants client:•Lease on file for a period for local access.•One-way hash of file contents for validation•List of file hosts storing data.4. Client retrieves replica from a file host:•Validates content using one-way hash•Decrypts using private key.•Works on local cached copy for lease period.Client writes to file…1. Client sends updated hash of file contents to directory group.2. Directory group verifies user permission to write to the file using user certificate.3. Once verified, directory group directs file hosts to retrieve new data from clients.4. Leases on existing clients may be recalled by directory group to satisfy new update request.File System FeaturesReliability and AvailabilitySecurityConsistencyScalabilityEfficiencyManageabilityDifferences from NTFSReliability and AvailabilityGoals:Long-term persistenceImmediate accessibility of file data during request.Directories/meta-data maintained via BFTNeeds replicas to protect against malicious nodes.3f + 1 replicas for tolerating f faultsFiles replicated via simple replicationFile replicas to ensure high degree of availability.f +1 replicas to tolerate f faultsData migration & repairAway from unavailable machinesSwap machine locations between high/low availability file replicas.SecurityAccess controlDirectory groups maintain an access control list (ACL) of public keys of all authorized writers.PrivacyDuring file creation, client generates a random file key used to encrypt the file. File key is encrypted with public keys of all authorized readers of the file. Encrypted file keys are stored with file. Data IntegrityMerkle hash tree over file data blocks.Copy of tree stored with file. Copy of root hash kept in directory group.Logarithmic (in file size) validation time for any file block. Linear validation time for entire file.DurabilityFARSITE does not update at once all replicas of a file:Would be too slow.Use a background delayed update mechanism.Updates to metadata are written in compressed logs on on client’s local disk.Log is sent to directory group periodically, and at end-of-lease.ConsistencyData consistencyContent leases with expiration - Read/write or read-onlySingle-writer multi-reader semanticsRequest for conflicting lease triggers a recall of lease by directory group.Single-client serialization of concurrent non-reads access.Inappropriate for large-scale write sharing.Other leases (refer to paper)Name leases – Allows clients to modify private namespace regions without contacting directory group.Mode leases – Windows File-sharing semantics (read, write,
View Full Document