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.

Problem description

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:

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:

Download

Github Link


Please subscribe to be updated on the posts.

In case of any doubt, feel free to comment.

Join 27 other followers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: