CSE 426: Distributed Operating System Unit 4:

Distributed File System

Department of Computer Science and Engineering SRM

University AP

April 11, 2025

4/28/2025 1 / 69
Unit 4: Distributed File System

Outline
► File System
► Desirable features of a good DFS
► File Models
► File accessing models
► File sharing semantics
► File caching schemes
► File replication
► Fault tolerance
► Automatic transactions, design principles
► Case study: Google DFS and Hadoop DFS
4/28/2025 Unit-4: DFS 2 / 69
Distributed file system-Analogy-“Library Network”

April 11, 2025 3 / 69

Cont’d

April 11, 2025 4 / 69

Cont’d

Unit-2: RPC April 11, 2025 5 / 69

Introduction

► a file is a named object that comes into existence by explicit creation, is immune to
temporary failures in the system, and persists until explicitly destroyed.

►The two main purposes of using files are as follows:

1. Permanent storage of information. This is achieved by storing a file on a

secondary storage media such as a magnetic disk.

2. Sharing of information. Files provide a natural and easy means of

information sharing. That is, a file can be created by one application and then
shared with different applications at a later time.

4/28/2025 Unit-4: DFS 6 / 69

► A file system is a subsystem of an operating system that performs file
management activities such as organization, storing, retrieval, naming,
sharing, and protection of files.

► A distributed file system provides similar abstraction to the users of a

distributed system and makes it convenient for them to use files in a
distributed environment. The design and implementation of a distributed file
system, however, is more complex than a conventional file system due to the
fact that the users and storage devices are physically dispersed.

Unit-4: DFS
4/28/2025 Unit-4: DFS 7 / 69
In addition to the advantages of permanent storage and sharing of information
provided by the file system of a single-processor system, a distributed file system
normally supports the following:

Remote information sharing.

• User mobility

• Availability

• Diskless workstations

4/28/2025 Unit-4: DFS 8 / 69

Services of DFS

1. Storage Service

•Manages space allocation on secondary storage (magnetic disks).

•Provides a logical view for storing and retrieving data.

•Also known as:

Disk Service

Block Service (when using fixed-size blocks)

4/28/2025 Unit-4: DFS 9 / 69

Services of DFS

2. True File Service

•Manages operations on individual files:

•Accessing, modifying, creating, and deleting files.

•Key design issues:

File-accessing mechanism
File-sharing semantics
File-caching, replication, and concurrency control
Data consistency, access control
Separation from storage service allows use of different
storage methods.

4/28/2025 Unit-4: DFS 10 / 69

Services of DFS

3. Name service:

•Maps human-readable text names to file references (i.e.,

file IDs).

•Uses directories to perform this mapping (also known as

directory service).

•Manages directory-related activities such as

creating/deleting directories, adding/removing files,
renaming files, and moving files
between directories.

4/28/2025 Unit-4: DFS 11 / 69

Desirable Features Of A Good DFS

•Transparency
•User Mobility
•Scalability
•Performance
•Simplicity & Ease of Use
•High Availability
•High Reliability
•Data Integrity
•Security
•Heterogeneity

4/28/2025 Unit-4: DFS 12 / 69

Desirable Features Of A Good DFS

1: Transparency
Transparency allows users to interact with the system as if it were
centralized.

Desirable types of transparency:

Structure Transparency
Access Transparency
Naming Transparency
Replication Transparency

4/28/2025 Unit-4: DFS 13 / 69

Desirable Features Of A Good DFS

Structure Transparency Access Transparency

•Multiple file servers used for: •Local and remote files should be accessed
Performance identically.
Scalability •The file system must:
Reliability Automatically locate the file
•File servers control local secondary storage. Handle data transport seamlessly
•Clients should not: •User experience must remain consistent
Know the number of servers regardless of file location.
Know server/storage locations
•System should appear as a single centralized
file system

4/28/2025 Unit-4: DFS 14 / 69

 Desirable Features Of A Good DFS

Naming Transparency Replication Transparency

•File names should not indicate file •If files are replicated:
location. • Users should not know how
many copies exist or where
•Files can move across nodes without they are stored.
name changes.
•System handles replication and access
•Supports flexibility and ease of access. behind the scenes.

4/28/2025 Unit-4: DFS 15 / 69

Desirable Features Of A Good DFS

2: User Mobility
•Users should work from any node without performance loss.

•File access should be seamless across sessions and locations.

•Example: Automatically bring user’s home directory to the login node.

4/28/2025 Unit-4: DFS 16 / 69

Desirable Features Of A Good DFS

3: Performance
•Performance = time to fulfill client requests.

•In distributed systems, includes:

Local storage access
CPU time
Network overhead

•Should be comparable to centralized systems.

•Users should not need to optimize file placement manually.

4/28/2025 Unit-4: DFS 17 / 69

Desirable Features Of A Good DFS

4: Simplicity & Ease of Use

•User interface should be:

Simple
Intuitive
•File semantics should match centralized systems.

•Minimal commands, support for a wide range of applications.

4/28/2025 Unit-4: DFS 18 / 69

Desirable Features Of A Good DFS

5: Scalability
•Must handle system growth:
New users
New nodes
•Growth should not cause:
Service disruption
Performance degradation
•System should:
Withstand high load
Allow resource integration easily

4/28/2025 Unit-4: DFS 19 / 69

Desirable Features Of A Good DFS

6: High Availability
•System should function under partial failures:
Network issues
Machine or device failures
•Degradation should be proportional to failure impact.
•Requires:
Distributed control and data
File replication for fault tolerance

4/28/2025 Unit-4: DFS 20 / 69

Desirable Features Of A Good DFS

7: High Reliability

•Data loss should be extremely rare.

•Users should not need to back up files manually.

•Techniques used:
Automatic backup
Stable storage

4/28/2025 Unit-4: DFS 21 / 69

Desirable Features Of A Good DFS

8: Data Integrity

•Shared file access requires:

Concurrency control
Synchronization
•Must prevent data corruption.
•Atomic transactions are commonly used for consistency.

4/28/2025 Unit-4: DFS 22 / 69

Desirable Features Of A Good DFS

9: Security
•Protect data from unauthorized access.

•Enforce safe right transfers.

•Design principle:
The fewer trusted components, the better the security.

•Critical in large-scale systems.

4/28/2025 Unit-4: DFS 23 / 69

Desirable Features Of A Good DFS

10: Heterogeneity
•Support for diverse:
• Hardware platforms (Mac, UNIX, supercomputers)
• Storage media

•Users should access files across all platforms seamlessly.

•System must allow easy integration of new platforms and

media.

4/28/2025 Unit-4: DFS 24 / 69

File Models

Unstructured Vs Structured Files

•Unstructured Files:
•Files are an uninterpreted sequence of bytes.
•The operating system is not concerned with file content.
•Interpretation of the data is left to application programs.
•Examples: UNIX and MS-DOS use this model.

•Structured Files:
•Files consist of an ordered sequence of records.
•Records can be of varying sizes.
•Files can be of different types, each with unique properties.

4/28/2025 Unit-4: DFS 25 / 69

File Models

Mutable and Immutable Files

•Mutable Files:
• Most common in operating systems.
• A file can be updated, and each update overwrites the
previous content.
•Immutable Files:
• File cannot be modified after creation.
• Updates are achieved by creating a new version of the file.
• Each version is stored, and only differences are recorded to
save space.

4/28/2025 Unit-4: DFS 26 / 69

File Accessing Models

The file-accessing model of a distributed file system mainly depends on two

factors-the method used for accessing remote files and the unit of data access.

1.1 Accessing Remote Files

a. Remote Service Model :

•Client request is processed at the server's node.

•Request and server response are transferred over the network as

messages.

•Significant overhead due to data packing and communication.

•Server and communication protocols must minimize message overhead.

4/28/2025 Unit-4: DFS 27 / 69
File-accessing Models

b. Data-Caching Model
•Objective: Reduce network traffic by caching data on the client’s node.
•How it works :
• If data is not present locally, it's copied from the server and
cached.
• Client processes requests using cached data.
• Recently accessed data is retained in the cache for future
access.
•Advantages :
• Reduces network traffic and improves performance.
• Increases system scalability.
•Challenges :
• Cache consistency problem: Ensuring data is consistent across
caches and server.
• Write operations incur overhead due to cache synchronization.
4/28/2025 Unit-4: DFS 28 / 69
File Accessing Models

1.2 Unit of Data Transfer

Description: The entire file is transferred in response to a single request.

Advantages:
•Efficient for complete file transfers.
•Reduced network protocol overhead.
•Improved scalability and server load reduction.
•Offers resiliency if the entire file is cached on the client.
Drawbacks:
•Requires sufficient storage on the client’s node.
•Not efficient for large files or diskless workstations.
Examples: Amoeba, CFS, AFS-2, AFS-3.

4/28/2025 Unit-4: DFS 29 / 69

File-accessing Models

•Data Transfer Unit : Determines how data is transferred

between clients and servers.

4 Common Data Transfer Models :

File-level Transfer Model

Block-level Transfer Model
Byte-level Transfer Model
Record-level Transfer Model

4/28/2025 Unit-4: DFS 30 / 69

File-accessing Models
File-level Transfer Model
•Description : The entire file is transferred in response to a single request.
•Advantages :
• Efficient for complete file transfers.
• Reduced network protocol overhead.
• Improved scalability and server load reduction.
• Disk access routines on the servers can ne better optimized.
• If the entire file is cached on the client, it becomes immune to
server and network failures.
•Drawbacks :
• Requires sufficient storage on the client’s node.
• Not efficient for large files when client have diskless
workstations.
•Examples: Amoeba, CFS, AFS-2, AFS-3.

4/28/2025 Unit-4: DFS 31 / 69

File-accessing Models

Block-level Transfer Model

•Description: Data is transferred in fixed-size blocks.
•Advantages:
• Does not require large storage on the client.
• Suitable for diskless workstations.
• Efficient for partial file access.
•Drawbacks:
• Requires multiple server requests for complete file
access.
• Results in higher network traffic and protocol
overhead.
•Examples: Apollo Domain File System, NFS, LOCUS, Sprite.

4/28/2025 Unit-4: DFS 32 / 69

File-accessing Models

Byte-level Transfer Model

•Description: Transfers file data in units of bytes.

•Advantages:
• Maximum flexibility: Arbitrary subranges of a file can
be accessed.
•Drawbacks:
• Difficult cache management due to varying data
lengths.
•Examples: Cambridge File Server.

4/28/2025 Unit-4: DFS 33 / 69

File-accessing Models

Record-level Transfer Model

•Description: File data is transferred in units of records.

•Use Case:
• Suitable for files structured in records (e.g.,
databases).
•Examples: Research Storage System (RSS).

4/28/2025 Unit-4: DFS 34 / 69

File-Sharing Semantics

Types of File Sharing Semantics

•UNIX Semantics
•Session Semantics
•Immutable Shared-Files Semantics
•Transaction-like Semantics

4/28/2025 Unit-4: DFS 35 / 69

File-Sharing Semantics

UNIX Semantics

•Description: Enforces absolute time ordering for all operations.

•Visibility: A write operation becomes immediately visible to all users with the
file open.
•Challenge in Distributed Systems:
• Network delays can cause request order discrepancies.
• Implementing UNIX semantics in a distributed system is complex.
• Disallowing file caching and managing by a single server may
cause performance and scalability issues.
•Solution: Use special mechanisms like file locks to ensure UNIX semantics.

4/28/2025 Unit-4: DFS 36 / 69

File-Sharing Semantics

4/28/2025 Unit-4: DFS 37 / 69

File-Sharing Semantics

Session Semantics

•File Access Pattern:

• Client opens file, performs read/write operations, and closes it.
• Changes are visible only to the client during the session.
• After closing the session, changes are visible to other clients in new
sessions.
•Challenges:
• Multiple clients may have different views of the file (stale copies).
• Determining the final file image when multiple sessions are closed.
• Nondeterministic final file image.
•Implementation: Session semantics should be used with the file-level transfer
model.
4/28/2025 Unit-4: DFS 38 / 69
File-Sharing Semantics

Immutable Shared-Files Semantics

•File Model: Uses the immutable file model where a file cannot be
modified after creation.
•Changes: Handled by creating a new version of the file (readonly
mode).
•Benefits:
• No need to worry about when changes made by users are
visible to others.
• Files are shared in a read-only manner.

4/28/2025 Unit-4: DFS 39 / 69

File-Sharing Semantics

Transaction-like Semantics

•Transaction Mechanism: Ensures that partial modifications within a

transaction are not visible to others until the transaction ends.
•Key Features:
• File modifications are grouped in transactions.
• Ensures consistency: all transactions appear sequential.
•Implementation:
• Transactions are implicitly triggered by open and close file
operations.
• Typically, transactions are limited to one file.

4/28/2025 Unit-4: DFS 40 / 69

File-caching Schemes

Purpose of File Caching

•File caching improves file I/O performance in centralized time-sharing systems (e.g.,
UNIX).
•Recent file data is retained in main memory to reduce disk transfers.

Effectiveness of Caching
•Locality in file access patterns reduces disk transfers.
•Substantial reduction in disk I/O, improving overall system performance.

File Caching in Distributed Systems

•Locality in access patterns can be exploited for caching in distributed systems.
•File caching improves system performance, scalability, and reliability.
•Remote data can be cached on client nodes, reducing the need for repeated remote disk
accesses.

4/28/2025 Unit-4: DFS 41 / 69

File-caching Schemes

• File Caching in Modern Systems

Almost every distributed file system uses some form of file caching.
AT&T’s Remote File System (RFS), initially avoiding caching, now incorporates
caching.
• Key Design Decisions in Centralized Systems
Granularity of Cached Data: Large vs. small chunks of data.
Cache Size: Large vs. small, fixed vs. dynamically changing.
Replacement Policy: Deciding which data to keep and which to evict.

Key Design Decisions in Distributed Systems

[Link] Location: Where should the cache reside?
[Link] Propagation: How to propagate changes made to cached data.
[Link] Validation: Ensuring cached data remains valid and consistent.

4/28/2025 Unit-4: DFS 42 / 69

File-caching Schemes

Definition:
•Cache location refers to where the cached data is stored in a distributed file
system.
Possible Cache Locations:
[Link]'s Main Memory:
•Access Process:
•File transferred from server's disk to its main memory, then across
the network to the client.
•Cost: 1 disk access + 1 network access.
•Cache in Server's Main Memory:
•Eliminates disk access, improving performance during cache hits.

4/28/2025 Unit-4: DFS 43 / 69

File-caching Schemes

Advantages of Cache in Server's Main Memory:

•Ease of Implementation: Transparent to clients.
•Consistency: Original file and cached data are easy to keep consistent on the same
node.
•Synchronization: Multiple client accesses can be synchronized easily, supporting
UNIX-like file-sharing semantics.

Limitations:
•Network Access: Each file access by a remote client still involves network access
and server processing.
•Scalability & Reliability: Does not contribute to system scalability or reliability.

4/28/2025 Unit-4: DFS 44 / 69

File-caching Schemes

2. Cache Location in Client's Disk

Client's disk cache eliminates network access but requires disk access on a cache hit.
Advantages:
Reliability:
•Cached data survives crashes if stored on the client's disk, as opposed to
volatile memory.
•Data is retained during recovery, avoiding the need to fetch it again from the
server.
Large Storage Capacity:
•Disk cache has more storage space than main-memory cache, allowing more
data to be cached and increasing the hit ratio.
•Particularly useful for systems that use the file-level transfer model, where
entire files are cached.

4/28/2025 Unit-4: DFS 45 / 69

File-caching Schemes

Disconnected Operation:
•Client's disk cache supports disconnected operation by allowing local
servicing of requests without server contact.

Scalability & Reliability:

•Cache hit requests can be serviced locally, improving scalability and reliability
by reducing dependence on the server.

4/28/2025 46 / 69
File-caching Schemes

Drawbacks:
•Diskless Workstations:
•Does not work in systems with diskless workstations.
•Disk Access Cost:
•Requires disk access on each cache hit, resulting in higher access time
compared to server's main memory cache.
•Performance Comparison:
•Server's main-memory cache is faster and simpler but involves network
access on cache hits.
•Client's disk cache eliminates network access but incurs disk access on
cache hits.

4/28/2025 Unit-4: DFS 47 / 69

File-caching Schemes

Cache Location in Client's Main Memory

• Client’s main memory cache eliminates both network and disk access costs.
• Provides maximum performance gain on a cache hit.
Advantages :
• Fastest access : No need for disk or network communication.
• Supports diskless workstations : Suitable for lightweight, low-storage clients.
• Improves scalability & reliability :
• Cache hit requests are served locally without contacting the server.
Limitations :
• Volatile storage : Data is lost on power failure or crash.
• Smaller capacity : Less storage space compared to a client’s disk.
• Lower reliability : Not ideal when high durability or large cache sizes are
needed.

4/28/2025 Unit-4: DFS 48 / 69

 Caching Location Types
[Link] Caching
1. Stores data on the user's machine
2. Reduces latency significantly
[Link] Caching
1. Stores recent file requests at the server
2. Useful in multi-client environments
[Link]-Server Caching (Hybrid)
1. Combines both for optimized performance

4/28/2025 Unit-4: DFS 6749/ /6969

•Write-Through Caching
Every write is immediately sent to the server
High consistency , but high network traffic
•Write-Back Caching
Writes are cached locally and sent to the server periodically
Better performance , but risk of data loss on failure
•Delayed Write (Write-On-Close)
Changes are propagated when the file is closed
Common in NFS (Network File System)

4/28/2025 Unit-4: DFS 6850/ /6969

 Cache Consistency Mechanisms
•Polling (Client-Initiated) : Client checks for updates periodically

•Callbacks (Server-Initiated) : Server notifies clients of updates

•Leases: Temporary permission granted to cache data for a fixed

time

4/28/2025 Unit-4: DFS 6851/ /6969

File Replication

•File replication involves storing copies of the same file at multiple locations.
•Improves availability, reliability, and performance in distributed systems.
•Helps in fault tolerance – if one replica fails, others can be used.

Objectives of File Replication

•Ensure high availability of data

•Reduce access latency
•Improve read performance
•Provide fault tolerance
•Enable load balancing across servers

4/28/2025 Unit-4: DFS 6852/ /6969

Types of Replication

1. Full Replication
•All files are copied to all nodes
•High availability but costly

2. Partial Replication
•Only frequently accessed files are replicated
•Balances performance and resource usage

4/28/2025 Unit-4: DFS 6853/ /6969

Replication Strategies

1. Active Replication
•All replicas process requests simultaneously
•Requires strong synchronization

2. Passive Replication
•One primary replica processes requests, others are backups
•Used in systems like primary-backup models

4/28/2025 Unit-4: DFS 6854/ /6969

Replica Management

•Creation: When and where to create a new replica

•Placement: Choosing optimal locations for replicas
•Deletion: Removing replicas that are no longer needed
Consistency Models
•Strong Consistency : All replicas reflect the latest update
•Weak Consistency : Replicas may be temporarily out of sync
•Eventual Consistency : All replicas will become consistent over time

4/28/2025 Unit-4: DFS 6955/ /6969

Update Propagation Techniques

[Link] Replication
1. Updates are sent to all replicas before confirming to
the user
2. Ensures strong consistency
[Link] Replication
1. Updates are applied locally and propagated later
2. Improves performance but risks inconsistency

4/28/2025 Unit-4: DFS 6956/ /6969

Trade-offs in File Replication

•Availability vs. Consistency

•Performance vs. Storage Cost
•Update Latency vs. Synchronization Overhead

4/28/2025 Unit-4: DFS 6957/ /6969

Fault Tolerance
•Fault tolerance : The ability of a system to continue functioning despite
failures.
•Essential for reliability and availability in distributed systems.
•DFS must handle failures of nodes, storage devices, and
communication links.
Goals of Fault Tolerance
•Ensure data availability even during failures.
•Provide continuous access to files.
•Minimize data loss and service disruption .
•Support automatic recovery and failover mechanisms.
4/28/2025 Unit-4: DFS 6958/ /6969
Types of Failures in DFS

•Node Failure : A server or client crashes.

•Network Failure : Disruption in communication between nodes.

•Disk Failure: Data loss due to hardware faults.

•Software Failure : Bugs or crashes in DFS software components.

4/28/2025 Unit-4: DFS 6959/ /6969

Techniques for Fault Tolerance

[Link] Replication : Storing copies of files on multiple servers.

[Link] Redundancy : Using RAID or erasure coding to recover lost

data.

[Link] : Periodically saving system state for recovery.

[Link] Mechanism : Regular signals to detect node availability.

4/28/2025 Unit-4: DFS 6960/ /6969

Recovery Mechanisms

•Automatic Failover : Switching to backup server if one fails.

•Replica Re-synchronization : Updating outdated copies after recovery.
•Transaction Rollback : Undoing incomplete operations after failure.
Ensuring Data Consistency

•Atomicity: Operations are either fully completed or not done at all.

•Version Control: Keeping track of file updates and resolving conflicts.
•Quorum-based Access: Ensures that read/write operations are valid
even with partial failures.

4/28/2025 Unit-4: DFS 6961/ /6969

Case Study – Google File System (GFS)

•Fault-tolerant by design

•Uses chunk replication (default 3 copies)

•Master node failure recovered using snapshots and logging

•Ensures high availability even during server failures

4/28/2025 Unit-4: DFS 6962/ /6969

Case study: Google DFS and Hadoop DFS

•Both GFS and HDFS are distributed file systems designed for big data storage
and processing.

•Built to handle large-scale, fault-tolerant, high-throughput workloads.

•GFS is developed by Google, while HDFS is an open-source system based on GFS.

4/28/2025 Unit-4: DFS 6963/ /6969

Google File System (GFS) – Overview

•Proprietary file system used by Google.

•Designed for large distributed data-intensive applications.
•Stores files as immutable chunks (default: 64 MB).
•Uses a single Master server and multiple ChunkServers.

GFS – Key Features

•Chunk-based storage (with replication)
•High fault tolerance via replication (typically 3 replicas)
•Write-once, read-many access model
•Efficient for large files and sequential access
•Metadata management by the Master

4/28/2025 Unit-4: DFS 6964/ /6969

Hadoop Distributed File System (HDFS) – Overview
•Open-source DFS inspired by GFS
•Core component of the Hadoop ecosystem
•Stores large data sets across clusters of commodity hardware
•Optimized for batch processing and large-scale data analytics
HDFS – Architecture
•NameNode: Manages metadata and namespace
•DataNodes: Store actual file blocks
•Files split into blocks (default: 128 MB) and replicated
•Typically 3 replicas per block (configurable)

4/28/2025 Unit-4: DFS 6965/ /6969

Introduction to Atomic Transactions

•Atomic transactions ensure that file system operations are treated as a single,
indivisible unit.

•Atomicity is one of the ACID (Atomicity, Consistency, Isolation, Durability)

properties.

•Essential for consistency and fault tolerance in distributed file systems.

•Helps in maintaining data integrity in case of system failures.

4/28/2025 Unit-4: DFS 6966/ /6969

Goals of Atomic Transactions

•Ensure all-or-nothing execution: Either all operations complete successfully, or none.

•Maintain consistency in distributed environments.
•Enable reliable failure recovery without compromising data integrity.

Key Properties of Atomic Transactions

•Atomicity: All changes are committed or none.

•Consistency: The system transitions from one consistent state to another.
•Isolation: Transactions are independent; intermediate states are hidden from others.
•Durability: Once committed, the transaction's changes are permanent.

4/28/2025 Unit-4: DFS 6769/ /6969

Need for Transactions in a file service

1. To Ensure Consistency of the File System

•When multiple operations (e.g., read, write, delete) are performed as part
of a single logical action, they must all complete successfully for the file
system to remain in a valid state.
•Transactions help maintain this consistency even if a system crash or failure
occurs midway through operations.
2. To Support Concurrent Access by Multiple Users
•In distributed systems, several clients may access and modify the same files
simultaneously.
•Transactions ensure isolation, so each user's actions are independent,
preventing conflicts or data corruption due to race conditions.

4/28/2025 Unit-4: DFS 6869/ /6969

Need for Transactions in a file service- Example

4/28/2025 Unit-4: DFS 6969/ /6969

Need for Transactions in a file service- Example

4/28/2025 Unit-4: DFS 7069/ /6969

Need for Transactions in a file service- Example

4/28/2025 Unit-4: DFS 7169/ /6969

Operations for Transaction- Based file service

• Begin_transaction (TID)
• End_transaction (TID)
• Abort_transaction (TID)

4/28/2025 Unit-4: DFS 7269/ /6969

Recovery Techniques

From the point of view of a server, a transaction has two phases

1. The first phase starts when the server receives a begin_transaction

request from a client. In this phase, the file access operations in the
transaction arc performed and the client adds changes to file items
progressively.

2. In the second phase, the transaction is either committed or aborted.

In a commit, the changes made by the transaction to file items are
made permanent so as to make them visible to other transactions as
well.

4/28/2025 Unit-4: DFS 7369/ /6969

Recovery Techniques- Contd…

4/28/2025 Unit-4: DFS 7469/ /6969

File Version Approach

A basic technique
to ensure file
recoverability is to
avoid overwriting
the actual data in
physical storage.

4/28/2025 Unit-4: DFS 7569/ /6969

Operations for Transaction- Based file service

• The Shadow Blocks technique is a method used to implement file versioning in a

file system, where each update or modification to a file creates a new version of the
file without overwriting the existing data.

• This ensures that the file system can maintain historical versions of files, providing
the ability to recover previous versions or rollback changes when necessary.

• The Shadow Blocks technique relies on the concept of shadowing: when a file is
updated, the new data is not written directly over the old data. Instead, a new block
(or a shadow block) is allocated to hold the new data, and the file metadata is
updated to point to this new block.

• The original block remains unchanged, effectively allowing the file system to
maintain multiple versions of the file.
4/28/2025 Unit-4: DFS 7669/ /6969
 Limitations of Shadow Blocks Technique
[Link] Overhead :
1. While shadow blocks are efficient for small changes, they can
lead to significant storage overhead if many versions of large files
are maintained without garbage collection.
[Link] :
1. Managing and linking multiple versions of a file across shadow
blocks can increase the complexity of file system
implementation, particularly in distributed systems.
[Link] :
1. Over time, especially if many changes are made to a file,
retrieving earlier versions or managing large chains of shadow
blocks can impact read performance .

4/28/2025 Unit-4: DFS 7769/ /6969

Concurrency control

Concurrency control refers to the mechanisms used to manage the

simultaneous execution of transactions or operations in a multi-user or
distributed system while ensuring the integrity and consistency of shared
resources (like files, databases, etc.).

In distributed systems, multiple users or processes may attempt to read or

write the same resource simultaneously, which can lead to issues such as
race conditions, deadlocks, or data inconsistencies.

Concurrency control ensures that such conflicts are avoided, and the system
behaves correctly in the presence of multiple concurrent operations.

4/28/2025 Unit-4: DFS 7869/ /6969

For more flexible concurrency control algorithms commonly used
locking, optimistic concurrency control, and time stamps.
Locking
In the basic locking mechanism, a transaction locks a data item before accessing it.
Each lock is labeled with the transaction identifier and only the transaction that locked
the data item can access it any number of times.

Other transactions that want to access the same data item must wait until the data
item is unlocked. All data items locked by a transaction are unlocked as soon as the
transaction completes (commits or aborts).

Locking is performed by the transaction service as a part of the data access operations,
and clients have no access to operations for locking or unlocking data items.

4/28/2025 Unit-4: DFS 7969/ /6969

Optimized Locking for Better Concurrency

1. Types of Locks in Type-Specific Locking:

Read Lock (Shared Lock):
1. Allows a transaction to read a data item but not modify it.
2. Multiple transactions can hold a shared lock on the same data item
simultaneously, enabling concurrent reads without conflicts.
3. Example: If multiple users are viewing the same file or database record, they can
all hold a read lock, and they won't interfere with each other.
Write Lock (Exclusive Lock):
4. Allows a transaction to both read and modify a data item.
5. Only one transaction can hold a write lock on a data item at a time.
6. If a transaction holds a write lock on a resource, no other transaction can hold
either a read or a write lock on the same resource.
7. Example: If one user is editing a document, no other user can read or modify it
until the editing user releases the lock.

4/28/2025 Unit-4: DFS 8069/ /6969

4/28/2025 Unit-4: DFS 8169/ /6969
2. Types of Intention-to-write locks:
for better concurrency, Gifford [1979b] proposed the use of an
"intention-to-write lock" (I-write) and a commit lock instead of a write lock.
Three types of locks are used here.
• if a read lock is set, an I-write lock is permitted on the data item and vice
versa. This is because the effects of write are not observable by any other
transaction until the writing transaction commits.

• If an l-write lock is set, no other transaction is allowed to have an I-write lock

on the same data item.

• A commit lock is not permitted if any other type of lock is already set on the
data item.
4/28/2025 Unit-4: DFS 8269/ /6969
4/28/2025 Unit-4: DFS 8369/ /6969
Two-Phase Locking Protocol
Growing Phase (Acquisition Phase) :
•In the growing phase , the transaction is allowed to acquire locks but cannot release any
locks.
•The transaction can continue to acquire new locks as long as it hasn’t released any locks
yet. During this phase, the transaction can acquire shared locks (for reading) or exclusive
locks (for writing) on any resources.

Shrinking Phase (Release Phase):

•In the shrinking phase , the transaction can release locks but cannot acquire any new
locks.
•Once the transaction releases a lock, it enters the shrinking phase and cannot acquire
additional locks.
•This ensures that once a transaction starts releasing locks, it does not interfere with other
transactions by trying to acquire new locks.

4/28/2025 Unit-4: DFS 8469/ /6969

Optimistic Concurrency Control
This approach for concurrency control by Kung and Robinson [1981] is based on
the observation that access conflicts in concurrently executing transactions are
very rare.

Therefore, in this approach, transactions are allowed to proceed uncontrolled up

to the end of the first phase.

However, in the second phase, before a transaction is committed, the transaction

is validated to see if any of its data items have been changed by any other
transaction since it started.

The transaction is committed if found valid; otherwise it is aborted.

4/28/2025 Unit-4: DFS 8569/ /6969

Optimistic Concurrency Control

• a read set that contains the data items read by the transaction

• a write set that contains the data items changed, created, or deleted by
the transaction.

• To validate a transaction, its read set and write set are compared with the
write sets of all of the concurrent transactions that reached the end of
their first phase before it.

4/28/2025 Unit-4: DFS 8669/ /6969

 Optimistic Concurrency Control

Advantages of Optimistic Concurrency Control (OCC):

[Link] Parallelism:
1. OCC allows transactions to execute in parallel without the need
for locks, enabling maximum parallelism.
2. All transactions proceed independently, and the system does
not enforce waiting, resulting in higher throughput and better
system utilization.
[Link] Deadlock:
1. Since OCC does not use locks, the system is inherently free from
deadlock.
2. There is no possibility of transactions getting stuck in a circular
waiting condition, as transactions are not blocked by others
during execution.
4/28/2025 Unit-4: DFS 8769/ /6969
Disadvantages of Optimistic Concurrency Control (OCC):

• Retention of Old Versions

• Unlike locking or timestamping protocols, where data versions may not need to be
retained, this leads to additional storage overhead for maintaining historical versions.
• Starvation
•Although OCC preventsdeadlock, it may cause starvation for some transactions.
•Transactions that fail validation repeatedly due to data conflicts may beaborted
and restarted many times.
•If these transactions keep running into conflicts with others, they mightnever pass
validation, resulting in continuous abortion and retrying.
• Increased Overhead in Overloaded Systems
•In overloaded systems, the frequency of transactionabortions due to
data conflicts can increase significantly.
•This increases overhead because transactions need to bere-executed after being
rolled back, leading to ahigher system load and potential performance degradation.
4/28/2025 Unit-4: DFS 8869/ /6969
Timestamp Ordering Rules:
There are two key rules that govern how transactions interact under Timestamp
Ordering:
[Link] timestamp Rule :
1. A transaction T1 can read data item X if the following condition is met:
1. T1's timestamp < timestamp of the last transaction that wrote to
X.
2. If T1's timestamp is greater than or equal to the timestamp of the
last writer, then a conflict occurs , and T1 must be aborted .
[Link] timestamp Rule :
1. A transaction T1 can write data item X if:
1. T1's timestamp < timestamp of the last transaction that read or
wrote X.
2. If T1's timestamp is greater than or equal to the timestamp of any
transaction that has already written or read X, then a conflict
occurs, and T1 must be aborted .
4/28/2025 Unit-4: DFS 8969/ /6969
Challenges in Distributed File Systems

•Concurrency: Multiple users accessing and modifying files simultaneously.

•Failures: Node crashes, network failures, or disk issues.
•Communication: Latency and the need for synchronization between nodes.
•Replication: Ensuring consistency across replicas during transactions.

Techniques for Atomic Transactions in DFS

•Two-Phase Commit (2PC) Protocol
•Ensures that a transaction is either committed or aborted across all nodes.
•Phase 1: Coordinator asks participants to prepare.
•Phase 2: Participants either commit or abort based on coordination.
•Three-Phase Commit (3PC) Protocol
•Extension of 2PC that improves fault tolerance.
•Adds a prepare-to-commit phase to handle crashes more gracefully.

4/28/2025 Unit-4: DFS 6990/ /6969

File-Level Atomicity

•Write-once, Read-many: Files are written only once and read multiple times.
•Supports atomic updates to ensure the file is in a consistent state at all times.
•Transactional file systems often use logs to record changes before they are applied.
Commit Protocols
•Write-Ahead Logging (WAL):
•Before modifying a file, changes are first written to a log.
•Durability: Ensures no data loss in case of a crash.
•Common in systems like journaling file systems.
•Undo/Redo Logging:
•Undo Log: Records actions that allow rollback.
•Redo Log: Ensures the transaction can be reapplied if the system crashes.
4/28/2025 Unit-4: DFS 6991/ /6969
Consistency and Recovery in DFS

1. Crash Recovery:
•If a system fails during a transaction, the log helps restore the system to a consistent
state.
•Transactions are either rolled back or committed upon recovery.

2. Replicated Transactions:
•Ensures consistency across multiple replicas of a file.
•Synchronization techniques like quorum-based voting ensure that only committed
transactions are reflected.

4/28/2025 Unit-4: DFS 6992/ /6969

Trade-offs in Atomic Transactions

•Performance vs. Reliability: Protocols like 2PC and 3PC introduce overhead in terms of
communication and computation.

•Consistency vs. Availability: Strict atomicity can compromise system availability in the face
of network partitions.

4/28/2025 Unit-4: DFS 6993/ /6969

 Thank You

4/28/2025 94 / 69