Implement a file system in Java given n-bytes

Problem Statement

Given n – bytes, implement a file system that supports following actions:

• Create File
• Update File
• Read File
• Delete File

If you want a good start point for a small low level design problem, this post on designing a ride hailing service might be a good start.

Demystifying Problem Statement

When the problem says that n-bytes are given, that means we are provided with byte array in java. Something like one below and shown in figure 1:

byte[] memory = new byte[20];

Now, let’s say we insert a new file called f1.txt which has “HELLO” inside. Similarly, f2.txt which has “WORLD” inside. We will store the data in the array as shown in the figure below.

So, In a simple word, we have to store different words in an byte array and provide way to do management of these words.

Design Motivation

The first approach that I could think of was to come up with a MetaData class. One like the one below:

	public class MetaData {
	private UUID uuid;
	private String fileName;
	private int startIndex;
	private int lastIndex;
	private int size;
	}

view raw MetaData.java hosted with ❤ by GitHub

Using this metadata class, I can hold the startIndex and lastIndex of files. For example:

MetaData f1 = new MetaData();
metaData.setFileName("f1");
metaData.setStartIndex(0);
metaData.setLastIndex(4);
metaData.setSize(5);

While this design may work normally, It will fail when we want to do multiple write or update file operation.

Why?

Because let’s say we get two file insert operation at the same time and our array is empty. Both will try to write from first index and will end up corrupting the value.

What now?

I think many of us must have read about 8086 architecture where we create segments of memory. Segmenting memory gives us a powerful way of memory management. With that note, let’s introduce the concept of dataBlock in our design.

For the sake of illustration, we will create a datablock of size 4 and is shown below.

Figure 4 will show you the different datablocks. And in figure 5, it is shown how the two files data will be stored in the array. What was then per byte, is now per data block. As you might have figured out by now, this will mean certain wastage of memory in lieu of better and simple memory management.

Proposed Class Diagram

I think most of the classes here are self explanatory. The only class that I would like to describe a little is MemoryServiceImpl.

As we discussed earlier, the basic building block of memory is now DataBlock and it looks like this:

public class DataBlock {
    private int start;
    private Boolean isOccupied;
}

And the metadata class looks like this now:

public class MetaData {
    private UUID uuid;
    private String fileName;
    private List<DataBlock> dataBlockList;
    private int size;
}

When the program initialises, constructor in MemoryServiceImpl takes number of bytes as input. Then depending upon the size specified for the datablock, it initialises a list of datablocks.

When write operation is done, it iterates through the list of datablocks to find the datablocks with combined memory more than the size of the file. After that, it is simple a write in the array. MemoryServiceImpl gist is below and download link for the project is in next section:

	package files.services;
	import files.models.DataBlock;
	import java.util.ArrayList;
	import java.util.List;
	public class MemoryServiceImpl implements IMemoryService {
	int blockSize = 5;
	byte[] memory;
	int memorySize;
	List<DataBlock> dataBlocks;
	public MemoryServiceImpl(int memorySize) throws Exception {
	this.memory = new byte[memorySize];
	this.memorySize = memorySize;
	this.dataBlocks = new ArrayList<DataBlock>();
	createDataBlock();
	}
	public void createDataBlock() throws Exception {
	if(memorySize == 0){
	throw new RuntimeException("Memory Size given is 0");
	}
	int num = memorySize/blockSize;
	for(int i = 0; i < num; i++){
	DataBlock dataBlock = new DataBlock(blockSize * i,false);
	dataBlocks.add(dataBlock);
	}
	}
	public List<DataBlock> write(String fileData) {
	List<DataBlock> dataBlockList = new ArrayList<DataBlock>();
	byte[] fileBytes = fileData.getBytes();
	int length = fileBytes.length;
	length = getDataBlockToWrite(dataBlockList, length);
	if(length > 0){
	throw new RuntimeException("Memory not available ");
	}
	int index = 0;
	int totalSize = fileBytes.length;
	for(DataBlock dataBlock : dataBlockList){
	dataBlock.setIsOccupied(true);
	for(int i = dataBlock.getStart(); i < (dataBlock.getStart() + blockSize); i++){
	if(index == totalSize){
	break;
	}
	memory[i] = fileBytes[index];
	index = index + 1;
	}
	}
	return dataBlockList;
	}
	private int getDataBlockToWrite(List<DataBlock> dataBlockList, int length) {
	for (DataBlock dataBlock : dataBlocks) {
	if (length <= 0) {
	break;
	}
	if (dataBlock.getIsOccupied()) {
	continue;
	}
	dataBlockList.add(dataBlock);
	length = length – blockSize;
	}
	return length;
	}
	public String read(List<DataBlock> dataBlocks, int size) {
	byte[] fileBytes = new byte[size];
	int index = 0;
	for(DataBlock dataBlock : dataBlocks){
	for(int i = dataBlock.getStart(); i < (dataBlock.getStart() + blockSize); i++){
	if(index == size){
	break;
	}
	fileBytes[index] = memory[i];
	index = index + 1;
	}
	}
	return new String(fileBytes);
	}
	public void delete(List<DataBlock> dataBlockList) {
	for(DataBlock dataBlock : dataBlocks){
	dataBlock.setIsOccupied(false);
	}
	}
	public List<DataBlock> update(List<DataBlock> dataBlockList, int oldFileSize, String newFileData) {
	//oldFileBytes this is for rollback.
	byte[] oldFileBytes = new byte[oldFileSize];
	int numOfBlocks = dataBlockList.size();
	byte[] newFileBytes = newFileData.getBytes();
	int newFileLen = newFileData.getBytes().length;
	int remainingSize = newFileLen – numOfBlocks * blockSize;
	remainingSize = getMoreDataBlocksForUpdate(dataBlockList, remainingSize);
	if(remainingSize > 0){
	throw new RuntimeException("Memory not available for update");
	}
	int index = 0;
	try {
	for (DataBlock dataBlock : dataBlockList) {
	dataBlock.setIsOccupied(true);
	for (int i = dataBlock.getStart(); i < (dataBlock.getStart() + blockSize); i++) {
	if (index == newFileLen) {
	break;
	}
	if(index < oldFileSize) {
	oldFileBytes[index] = memory[i];
	}
	memory[i] = newFileBytes[index];
	index = index + 1;
	}
	}
	} catch (Exception e){
	System.out.println("Exception occured "+e.getMessage());
	e.printStackTrace();
	rollBack(index, oldFileSize, dataBlockList);
	}
	return dataBlockList;
	}
	private int getMoreDataBlocksForUpdate(List<DataBlock> dataBlockList, int remainingSize) {
	if(remainingSize > 0){
	for(DataBlock dataBlock : dataBlocks){
	if(remainingSize <= 0 ){
	break;
	}
	if(dataBlock.getIsOccupied()){
	continue;
	}
	dataBlockList.add(dataBlock);
	remainingSize = remainingSize – blockSize;
	}
	}
	return remainingSize;
	}
	private void rollBack(int i, int index, List<DataBlock> dataBlockList) {
	//
	}
	}

view raw MemoryServiceImpl.java hosted with ❤ by GitHub

Download

Github Link

---

Please subscribe to be updated on the posts.

In case of any doubt, feel free to comment.

If you liked this article and would like one such blog to land in your inbox every week, consider subscribing to our newsletter: https://skillcaptain.substack.com