Design (LLD) File System - Machine Coding
22 Jun 202416 min read
Feature Required
Data Structures for Storage Management:
Implementing appropriate data structures like B-trees or indexed allocation methods for efficient storage and retrieval of files.
Designing structures for metadata storage (file attributes, permissions, timestamps) to facilitate quick access and modification.
Allocation Strategies:
Defining allocation strategies for disk space (e.g., contiguous, linked, indexed) to optimize storage efficiency and reduce fragmentation.
Handling file growth and shrinkage dynamically while maintaining performance.
Error Handling and Recovery:
Incorporating mechanisms for error detection and recovery to ensure data integrity in case of system crashes or failures.
Implementing journaling or logging mechanisms to track changes and facilitate rollback in case of failures.
Concurrency Control:
Managing concurrent access to the file system to avoid data corruption or inconsistencies.
Implementing locking mechanisms or transactional support to handle multiple users or processes accessing the file system simultaneously.
Security and Access Control:
Integrating mechanisms for access control (permissions, ownership) to protect files and directories from unauthorized access.
Ensuring robust security measures to prevent data breaches or unauthorized modifications.
Performance Optimization:
Optimizing file access operations (read, write, delete) for speed and efficiency.
Minimizing overhead and latency in file system operations through efficient algorithms and caching mechanisms.
Scalability and Extensibility:
Designing the file system to be scalable as storage needs grow over time.
Allowing for easy extension or modification of features without disrupting existing functionalities.
Design Patterns Used
1. Composite Pattern
Reason: Perfect for representing hierarchical file system structures (files and directories)
Benefit: Allows uniform treatment of individual files and directories
2. Strategy Pattern
Reason: Multiple allocation strategies (contiguous, linked, indexed)
Benefit: Easy to swap strategies at runtime, maintain Open-Closed Principle
3. Observer Pattern
Reason: For monitoring file changes, journaling, and recovery mechanisms
Benefit: Decouples logging/recovery from file operations
4. Proxy Pattern
Reason: For access control and security checks
Benefit: Transparently adds security without modifying core file operations
5. Singleton Pattern
Reason: File system metadata manager and recovery manager
Benefit: Ensures single point of control for critical components
6. Factory Pattern
Reason: Creating different file types and allocation strategies
Benefit: Centralized object creation, easy to extend
Java Implementation
import java.util.*;
import java.util.concurrent.locks.*;
import java.nio.file.attribute.*;
import java.time.Instant;
// ==================== COMPOSITE PATTERN: File System Entities ====================
interface FileSystemEntity {
String getName();
long getSize();
FileMetadata getMetadata();
void setMetadata(FileMetadata metadata);
}
abstract class BaseFileSystemEntity implements FileSystemEntity {
protected String name;
protected FileMetadata metadata;
protected Directory parent;
public BaseFileSystemEntity(String name, FileMetadata metadata) {
this.name = name;
this.metadata = metadata;
}
@Override
public String getName() { return name; }
@Override
public FileMetadata getMetadata() { return metadata; }
@Override
public void setMetadata(FileMetadata metadata) {
this.metadata = metadata;
}
public void setParent(Directory parent) { this.parent = parent; }
}
// ==================== METADATA MANAGEMENT ====================
class FileMetadata {
private String owner;
private String group;
private Set<PosixFilePermission> permissions;
private Instant creationTime;
private Instant lastModified;
private Instant lastAccessed;
private Map<String, String> extendedAttributes;
public FileMetadata(String owner) {
this.owner = owner;
this.permissions = EnumSet.of(
PosixFilePermission.OWNER_READ,
PosixFilePermission.OWNER_WRITE
);
this.creationTime = Instant.now();
this.lastModified = Instant.now();
this.lastAccessed = Instant.now();
this.extendedAttributes = new HashMap<>();
}
// Getters and setters
public boolean hasPermission(User user, PosixFilePermission permission) {
if (user.getUsername().equals(owner)) {
return permissions.contains(permission);
}
// Add group and other permission checks
return false;
}
public void updateLastModified() {
this.lastModified = Instant.now();
}
}
// ==================== COMPOSITE: File ====================
class File extends BaseFileSystemEntity {
private AllocationStrategy allocationStrategy;
private byte[] content;
private final ReadWriteLock lock = new ReentrantReadWriteLock();
public File(String name, FileMetadata metadata, AllocationStrategy strategy) {
super(name, metadata);
this.allocationStrategy = strategy;
this.content = new byte[0];
}
public byte[] read() {
lock.readLock().lock();
try {
metadata.updateLastAccessed();
return content.clone();
} finally {
lock.readLock().unlock();
}
}
public void write(byte[] data) {
lock.writeLock().lock();
try {
this.content = data.clone();
metadata.updateLastModified();
allocationStrategy.allocate(data.length);
FileSystemEventManager.getInstance()
.notifyObservers(new FileSystemEvent(this, "WRITE"));
} finally {
lock.writeLock().unlock();
}
}
public void append(byte[] data) {
lock.writeLock().lock();
try {
byte[] newContent = new byte[content.length + data.length];
System.arraycopy(content, 0, newContent, 0, content.length);
System.arraycopy(data, 0, newContent, content.length, data.length);
this.content = newContent;
metadata.updateLastModified();
allocationStrategy.allocate(data.length);
FileSystemEventManager.getInstance()
.notifyObservers(new FileSystemEvent(this, "APPEND"));
} finally {
lock.writeLock().unlock();
}
}
@Override
public long getSize() {
return content.length;
}
}
// ==================== COMPOSITE: Directory ====================
class Directory extends BaseFileSystemEntity {
private Map<String, FileSystemEntity> children;
private final ReadWriteLock lock = new ReentrantReadWriteLock();
public Directory(String name, FileMetadata metadata) {
super(name, metadata);
this.children = new HashMap<>();
}
public void addEntity(FileSystemEntity entity) {
lock.writeLock().lock();
try {
if (entity instanceof BaseFileSystemEntity) {
((BaseFileSystemEntity) entity).setParent(this);
}
children.put(entity.getName(), entity);
FileSystemEventManager.getInstance()
.notifyObservers(new FileSystemEvent(this, "ADD_ENTITY"));
} finally {
lock.writeLock().unlock();
}
}
public void removeEntity(String name) {
lock.writeLock().lock();
try {
children.remove(name);
FileSystemEventManager.getInstance()
.notifyObservers(new FileSystemEvent(this, "REMOVE_ENTITY"));
} finally {
lock.writeLock().unlock();
}
}
public FileSystemEntity getEntity(String name) {
lock.readLock().lock();
try {
return children.get(name);
} finally {
lock.readLock().unlock();
}
}
@Override
public long getSize() {
lock.readLock().lock();
try {
return children.values().stream()
.mapToLong(FileSystemEntity::getSize)
.sum();
} finally {
lock.readLock().unlock();
}
}
public List<FileSystemEntity> listEntities() {
lock.readLock().lock();
try {
return new ArrayList<>(children.values());
} finally {
lock.readLock().unlock();
}
}
}
// ==================== STRATEGY PATTERN: Allocation Strategies ====================
interface AllocationStrategy {
void allocate(int size);
void deallocate(int size);
boolean hasSpace(int size);
double getFragmentation();
String getType();
}
class ContiguousAllocation implements AllocationStrategy {
private List<MemoryBlock> blocks;
private int totalSpace;
private int usedSpace;
class MemoryBlock {
int start;
int end;
boolean allocated;
MemoryBlock(int start, int end) {
this.start = start;
this.end = end;
this.allocated = false;
}
}
public ContiguousAllocation(int totalSpace) {
this.totalSpace = totalSpace;
this.usedSpace = 0;
this.blocks = new ArrayList<>();
this.blocks.add(new MemoryBlock(0, totalSpace - 1));
}
@Override
public void allocate(int size) {
for (int i = 0; i < blocks.size(); i++) {
MemoryBlock block = blocks.get(i);
if (!block.allocated && (block.end - block.start + 1) >= size) {
// Split block if needed
if ((block.end - block.start + 1) > size) {
MemoryBlock newBlock = new MemoryBlock(
block.start + size, block.end);
blocks.add(i + 1, newBlock);
}
block.end = block.start + size - 1;
block.allocated = true;
usedSpace += size;
return;
}
}
throw new RuntimeException("Insufficient contiguous space");
}
@Override
public void deallocate(int size) {
// Implementation for deallocation with coalescing
usedSpace -= size;
}
@Override
public boolean hasSpace(int size) {
return blocks.stream()
.anyMatch(b -> !b.allocated && (b.end - b.start + 1) >= size);
}
@Override
public double getFragmentation() {
long freeBlocks = blocks.stream()
.filter(b -> !b.allocated)
.count();
return freeBlocks > 0 ? 1.0 / freeBlocks : 0.0;
}
@Override
public String getType() {
return "CONTIGUOUS";
}
}
class IndexedAllocation implements AllocationStrategy {
private Map<Integer, List<Integer>> indexBlocks; // File ID -> Block pointers
private BitSet freeBlocks;
private int blockSize;
private int totalBlocks;
public IndexedAllocation(int totalBlocks, int blockSize) {
this.totalBlocks = totalBlocks;
this.blockSize = blockSize;
this.freeBlocks = new BitSet(totalBlocks);
this.freeBlocks.set(0, totalBlocks, true); // All blocks free initially
this.indexBlocks = new HashMap<>();
}
@Override
public void allocate(int size) {
int blocksNeeded = (int) Math.ceil((double) size / blockSize);
List<Integer> allocatedBlocks = new ArrayList<>();
for (int i = 0; i < totalBlocks && allocatedBlocks.size() < blocksNeeded; i++) {
if (freeBlocks.get(i)) {
allocatedBlocks.add(i);
freeBlocks.clear(i);
}
}
if (allocatedBlocks.size() < blocksNeeded) {
throw new RuntimeException("Insufficient space");
}
int fileId = indexBlocks.size();
indexBlocks.put(fileId, allocatedBlocks);
}
@Override
public void deallocate(int size) {
// Implementation to free blocks
}
@Override
public boolean hasSpace(int size) {
int blocksNeeded = (int) Math.ceil((double) size / blockSize);
return freeBlocks.cardinality() >= blocksNeeded;
}
@Override
public double getFragmentation() {
int freeCount = freeBlocks.cardinality();
return freeCount > 0 ? 1.0 / freeCount : 0.0;
}
@Override
public String getType() {
return "INDEXED";
}
}
// ==================== OBSERVER PATTERN: Event Management ====================
class FileSystemEvent {
private FileSystemEntity entity;
private String operation;
private Instant timestamp;
private byte[] beforeState;
private byte[] afterState;
public FileSystemEvent(FileSystemEntity entity, String operation) {
this.entity = entity;
this.operation = operation;
this.timestamp = Instant.now();
}
// Getters
public String getOperation() { return operation; }
public Instant getTimestamp() { return timestamp; }
}
interface FileSystemObserver {
void onFileSystemEvent(FileSystemEvent event);
}
class FileSystemEventManager {
private static FileSystemEventManager instance;
private List<FileSystemObserver> observers;
private List<FileSystemEvent> journal;
private final int JOURNAL_SIZE = 1000;
private FileSystemEventManager() {
this.observers = new ArrayList<>();
this.journal = new LinkedList<>();
}
public static synchronized FileSystemEventManager getInstance() {
if (instance == null) {
instance = new FileSystemEventManager();
}
return instance;
}
public void registerObserver(FileSystemObserver observer) {
observers.add(observer);
}
public void removeObserver(FileSystemObserver observer) {
observers.remove(observer);
}
public void notifyObservers(FileSystemEvent event) {
// Add to journal first
addToJournal(event);
// Notify all observers
for (FileSystemObserver observer : observers) {
observer.onFileSystemEvent(event);
}
}
private void addToJournal(FileSystemEvent event) {
synchronized (journal) {
journal.add(event);
if (journal.size() > JOURNAL_SIZE) {
journal.remove(0);
}
}
}
public List<FileSystemEvent> getJournal() {
return new ArrayList<>(journal);
}
}
// ==================== JOURNALING & RECOVERY ====================
class JournalingObserver implements FileSystemObserver {
private List<FileSystemEvent> transactionLog;
private boolean inTransaction;
public JournalingObserver() {
this.transactionLog = new ArrayList<>();
this.inTransaction = false;
}
@Override
public void onFileSystemEvent(FileSystemEvent event) {
if (inTransaction) {
transactionLog.add(event);
}
// Write to persistent journal
writeToPersistentJournal(event);
}
private void writeToPersistentJournal(FileSystemEvent event) {
// Implementation for writing to disk/journal file
System.out.println("Journaling: " + event.getOperation() +
" at " + event.getTimestamp());
}
public void beginTransaction() {
inTransaction = true;
transactionLog.clear();
}
public void commitTransaction() {
// Flush transaction log to persistent storage
inTransaction = false;
transactionLog.clear();
}
public void rollbackTransaction() {
// Implement rollback logic using transactionLog
inTransaction = false;
transactionLog.clear();
}
}
// ==================== PROXY PATTERN: Access Control ====================
class SecureFileProxy implements FileSystemEntity {
private FileSystemEntity realFile;
private User currentUser;
public SecureFileProxy(FileSystemEntity realFile, User currentUser) {
this.realFile = realFile;
this.currentUser = currentUser;
}
private boolean checkPermission(PosixFilePermission permission) {
FileMetadata metadata = realFile.getMetadata();
return metadata.hasPermission(currentUser, permission);
}
@Override
public String getName() {
return realFile.getName();
}
@Override
public long getSize() {
if (checkPermission(PosixFilePermission.OWNER_READ)) {
return realFile.getSize();
}
throw new SecurityException("Access denied");
}
@Override
public FileMetadata getMetadata() {
if (checkPermission(PosixFilePermission.OWNER_READ)) {
return realFile.getMetadata();
}
throw new SecurityException("Access denied");
}
@Override
public void setMetadata(FileMetadata metadata) {
if (checkPermission(PosixFilePermission.OWNER_WRITE)) {
realFile.setMetadata(metadata);
} else {
throw new SecurityException("Access denied");
}
}
}
// ==================== CONCURRENCY CONTROL ====================
class FileSystemLockManager {
private Map<String, ReadWriteLock> fileLocks;
private Map<String, Thread> lockOwners;
public FileSystemLockManager() {
this.fileLocks = new ConcurrentHashMap<>();
this.lockOwners = new ConcurrentHashMap<>();
}
public void acquireReadLock(String filePath) {
ReadWriteLock lock = fileLocks.computeIfAbsent(
filePath, k -> new ReentrantReadWriteLock());
lock.readLock().lock();
}
public void releaseReadLock(String filePath) {
ReadWriteLock lock = fileLocks.get(filePath);
if (lock != null) {
lock.readLock().unlock();
}
}
public void acquireWriteLock(String filePath, Thread owner) {
ReadWriteLock lock = fileLocks.computeIfAbsent(
filePath, k -> new ReentrantReadWriteLock());
lock.writeLock().lock();
lockOwners.put(filePath, owner);
}
public void releaseWriteLock(String filePath) {
ReadWriteLock lock = fileLocks.get(filePath);
if (lock != null) {
lock.writeLock().unlock();
lockOwners.remove(filePath);
}
}
public boolean isDeadlock(String filePath, Thread requester) {
Thread owner = lockOwners.get(filePath);
return owner != null && owner != requester;
}
}
// ==================== CACHING MECHANISM ====================
class FileSystemCache {
private Map<String, byte[]> cache;
private Map<String, Instant> accessTimes;
private final int MAX_CACHE_SIZE;
private final long CACHE_TIMEOUT_MS = 300000; // 5 minutes
public FileSystemCache(int maxSize) {
this.MAX_CACHE_SIZE = maxSize;
this.cache = new LinkedHashMap<>(maxSize, 0.75f, true);
this.accessTimes = new HashMap<>();
}
public byte[] get(String filePath) {
byte[] data = cache.get(filePath);
if (data != null) {
accessTimes.put(filePath, Instant.now());
}
return data;
}
public void put(String filePath, byte[] data) {
if (cache.size() >= MAX_CACHE_SIZE) {
evictOldEntries();
}
cache.put(filePath, data);
accessTimes.put(filePath, Instant.now());
}
private void evictOldEntries() {
Instant now = Instant.now();
Iterator<Map.Entry<String, Instant>> iterator =
accessTimes.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Instant> entry = iterator.next();
if (now.minusMillis(CACHE_TIMEOUT_MS)
.isAfter(entry.getValue())) {
cache.remove(entry.getKey());
iterator.remove();
break;
}
}
}
public void invalidate(String filePath) {
cache.remove(filePath);
accessTimes.remove(filePath);
}
}
// ==================== MAIN FILE SYSTEM CLASS ====================
class FileSystem {
private Directory root;
private FileSystemLockManager lockManager;
private FileSystemCache cache;
private AllocationStrategy allocationStrategy;
private static FileSystem instance;
private FileSystem() {
FileMetadata rootMetadata = new FileMetadata("root");
this.root = new Directory("/", rootMetadata);
this.lockManager = new FileSystemLockManager();
this.cache = new FileSystemCache(100); // 100 MB cache
this.allocationStrategy = new IndexedAllocation(10000, 4096); // Default
}
public static synchronized FileSystem getInstance() {
if (instance == null) {
instance = new FileSystem();
}
return instance;
}
public void setAllocationStrategy(AllocationStrategy strategy) {
this.allocationStrategy = strategy;
}
public File createFile(String path, String owner) {
String[] parts = path.split("/");
Directory current = root;
// Navigate to parent directory
for (int i = 1; i < parts.length - 1; i++) {
FileSystemEntity entity = current.getEntity(parts[i]);
if (!(entity instanceof Directory)) {
throw new RuntimeException("Invalid path");
}
current = (Directory) entity;
}
// Create file
FileMetadata metadata = new FileMetadata(owner);
File file = new File(parts[parts.length - 1],
metadata, allocationStrategy);
current.addEntity(file);
return file;
}
public byte[] readFile(String path) {
lockManager.acquireReadLock(path);
try {
// Check cache first
byte[] cachedData = cache.get(path);
if (cachedData != null) {
return cachedData;
}
// Read from file
File file = findFile(path);
byte[] data = file.read();
// Update cache
cache.put(path, data);
return data;
} finally {
lockManager.releaseReadLock(path);
}
}
public void writeFile(String path, byte[] data) {
lockManager.acquireWriteLock(path, Thread.currentThread());
try {
File file = findFile(path);
file.write(data);
// Update cache
cache.invalidate(path);
cache.put(path, data);
} finally {
lockManager.releaseWriteLock(path);
}
}
private File findFile(String path) {
String[] parts = path.split("/");
Directory current = root;
for (int i = 1; i < parts.length; i++) {
FileSystemEntity entity = current.getEntity(parts[i]);
if (i == parts.length - 1) {
if (!(entity instanceof File)) {
throw new RuntimeException("Not a file");
}
return (File) entity;
} else {
if (!(entity instanceof Directory)) {
throw new RuntimeException("Invalid path");
}
current = (Directory) entity;
}
}
throw new RuntimeException("File not found");
}
public void defragment() {
// Implementation for defragmentation
double fragmentation = allocationStrategy.getFragmentation();
if (fragmentation > 0.5) { // Threshold
System.out.println("Performing defragmentation...");
// Defragmentation logic
}
}
}
// ==================== SUPPORTING CLASSES ====================
class User {
private String username;
private String group;
private Set<String> roles;
public User(String username, String group) {
this.username = username;
this.group = group;
this.roles = new HashSet<>();
}
public String getUsername() { return username; }
public String getGroup() { return group; }
public void addRole(String role) {
roles.add(role);
}
public boolean hasRole(String role) {
return roles.contains(role);
}
}
// ==================== MAIN DEMO ====================
public class FileSystemDemo {
public static void main(String[] args) {
// Initialize file system
FileSystem fs = FileSystem.getInstance();
// Set up journaling
JournalingObserver journaling = new JournalingObserver();
FileSystemEventManager.getInstance().registerObserver(journaling);
// Create users
User admin = new User("admin", "admin");
User user1 = new User("user1", "users");
// Test different allocation strategies
System.out.println("=== Testing Allocation Strategies ===");
// Test contiguous allocation
fs.setAllocationStrategy(new ContiguousAllocation(1000000));
File file1 = fs.createFile("/documents/test1.txt", "admin");
file1.write("Hello World".getBytes());
System.out.println("File created with contiguous allocation");
// Test indexed allocation
fs.setAllocationStrategy(new IndexedAllocation(10000, 4096));
File file2 = fs.createFile("/documents/test2.txt", "user1");
file2.write("Another file".getBytes());
System.out.println("File created with indexed allocation");
// Test concurrent access
System.out.println("\n=== Testing Concurrency ===");
Thread writerThread = new Thread(() -> {
fs.writeFile("/documents/test1.txt",
"Updated content".getBytes());
});
Thread readerThread = new Thread(() -> {
byte[] data = fs.readFile("/documents/test1.txt");
System.out.println("Read data: " + new String(data));
});
writerThread.start();
readerThread.start();
try {
writerThread.join();
readerThread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
// Test security proxy
System.out.println("\n=== Testing Security ===");
SecureFileProxy secureFile = new SecureFileProxy(file1, user1);
try {
secureFile.getMetadata();
System.out.println("Access granted");
} catch (SecurityException e) {
System.out.println("Access denied: " + e.getMessage());
}
// Test caching
System.out.println("\n=== Testing Caching ===");
long startTime = System.currentTimeMillis();
byte[] data = fs.readFile("/documents/test1.txt");
long firstRead = System.currentTimeMillis() - startTime;
startTime = System.currentTimeMillis();
data = fs.readFile("/documents/test1.txt");
long cachedRead = System.currentTimeMillis() - startTime;
System.out.printf("First read: %d ms, Cached read: %d ms\n",
firstRead, cachedRead);
// Show journal entries
System.out.println("\n=== Journal Entries ===");
List<FileSystemEvent> journal =
FileSystemEventManager.getInstance().getJournal();
for (FileSystemEvent event : journal) {
System.out.println(event.getOperation() + " at " +
event.getTimestamp());
}
// Defragmentation check
System.out.println("\n=== System Maintenance ===");
fs.defragment();
}
}
This implementation provides a solid foundation for a file system with all requested features, using appropriate design patterns to ensure maintainability, extensibility, and performance.
Issues in Above Design
1️⃣ Singleton FileSystem as a Bottleneck (LLD + Concurrency)
Issue
FileSystem is implemented as a global Singleton.
LLD Problem
Violates Single Responsibility Principle
Couples metadata, locking, caching, allocation strategy, and traversal
Hard to test or run multiple file system instances (e.g., mounts, namespaces)
Concurrency Problem
All threads contend on the same global instance
Becomes a scalability bottleneck under heavy I/O
Impact
Throughput degradation
Difficult horizontal scaling
Poor isolation between workloads