Monday, July 21, 2014

Design an in-memory file system


http://www.careercup.com/question?id=13618661
1> Use Structure with n children, on parent pointer , one data field and one name field. 
2> Use this Structure to make N ary Tree with parent Child relationship. We can use inheritance feature of OOPs here. 
3> Now we can use this structure to make Files/Folder accourdingly. 
if Files that it parent pointer points to the Folder where it belongs with all its child pointer pointing to NULL and struct->data is the File Content. 
else if Folder . point it parent point to it Parent Folder while Child still pointing to NULL but its Struct->data as NULL. 
that way we can differentiate between file /folder and maintain its relationship. 

Main Class
AbstractFile
File
Folder
Permission
Singleton FileSystem Manager Object
maybe command line desgin pattern
class TPermission
{
public:
  string    name;
  enum {full_access, read_only, write, read};
};
https://tianrunhe.wordpress.com/2012/03/24/design-an-in-memory-file-system/
Command Interpreter: translate shell command to API call.

MetaData, FileSystem(root class, facada).
struct DataBlock { char data[DATA_BLOCK_SIZE]; };
DataBlock dataBlocks[NUM_DATA_BLOCKS];
struct INode { std::vector<int> datablocks; };
struct MetaData {
    int size;
    Date last_modifed, created;
    char extra_attributes;
};
std::vector<bool> dataBlockUsed(NUM_DATA_BLOCKS);
std::map<string, INode *> mapFromName;
struct FSBase;
struct File : public FSBase {
    private:
        std::vector<INode> * nodes;
        MetaData metaData;
};
struct Directory : pubic FSBase { std::vector<FSBase* > content; };
struct FileSystem {
    init();
    mount(FileSystem*);
    unmount(FileSystem*);
    File createFile(cosnt char* name) { ... }
    Directory createDirectory(const char* name) { ... }
    // mapFromName to find INode corresponding to file
    void openFile(File * file, FileMode mode) { ... }
    void closeFile(File * file) { ... }
    void writeToFile(File * file, void * data, int num) { ... }
    void readFromFile(File* file, void* res, int numbutes,
            int position) { ... }
};
http://www.shuatiblog.com/blog/2014/08/25/design-in-memory-file-system/
A file system consists of Files and Directories. Each Directory contains a set of Files and Directories.

Since Files and Directories share so many characteristics, we’ve implemented them such that they inherit from the same class — Entry.
UML diagram -> composite pattern.
public abstract class Entry {
    protected Directory parent;
    protected long created;
    protected long lastUpdated;
    protected long lastAccessed;
    protected String name;

    public Entry(String n, Directory p) {
        name = n;
        parent = p;
        created = System.currentTimeMillis();
    }
    public boolean delete() {
        if (parent == null) {
            return false;
        }
        return parent.deleteEntry(this);
    }
    public abstract int size();

    public String getFullPath() {
        if (parent == null) {
            return name;
        } else {
            return parent.getFullPath() + "/" + name;
        }
    }
}
public class File extends Entry {
    private String content;
    private int size;

    public File(String n, Directory p, int sz) {
        super(n, p);
        size = sz;
    }
}
public class Directory extends Entry {
    protected ArrayList<Entry> contents;

    public Directory(String n, Directory p) {
        super(n, p);
        contents = new ArrayList<Entry>();
    }

    protected ArrayList<Entry> getContents() {
        return contents;
    }

    public int size() {
        int size = 0;
        for (Entry e : contents) {
            size += e.size();
        }
        return size;
    }

    public int numberOfFiles() {
        int count = 0;
        for (Entry e : contents) {
            if (e instanceof Directory) {
                count++; // Directory counts as a file
                Directory d = (Directory) e;
                count += d.numberOfFiles();
            } else if (e instanceof File) {
                count++;
            }
        }
        return count;
    }

    public boolean deleteEntry(Entry entry) {
        return contents.remove(entry);
    }

    public void addEntry(Entry entry) {
        contents.add(entry);
    }
}

http://www.cs.cornell.edu/slk/jk-0.91/doc/jkernel/tutorial/tutorial-4.html
public class MemFileSystemImpl implements MemFileSystem
{
    Hashtable files = new Hashtable(); // maps Strings to byte arrays

    public void writeFile(String name, byte[] contents)
    {
        files.put(name, contents);
    }

    public byte[] readFile(String name)
        throws FileNotFoundException
    {
        byte[] contents = (byte[]) files.get(name);
        if(contents == null) throw new FileNotFoundException(name);
        else return contents;
    }
}
public class MemFileInputStream extends InputStream
{
    private ByteArrayInputStream bStream;
    
    public MemFileInputStream(String name)
        throws FileNotFoundException
    {
        byte[] b;

        try
        {
            b = MemFileSystemAdaptor.fileSystem.readFile(name);
        }
        catch(RemoteException e) {throw new FileNotFoundException(e.toString());}

        bStream = new ByteArrayInputStream(b);
    }

    public int available() {return bStream.available();}
    public void close() {}
    public int read() {return bStream.read();}
    public int read(byte[] b) {return bStream.read(b, 0, b.length);}
    public int read(byte[] b, int off, int len) {return bStream.read(b, off, len);}
    public long skip(long n) {return bStream.skip(n);}
}

public class MemFileOutputStream extends OutputStream
{
    private ByteArrayOutputStream bStream = new ByteArrayOutputStream();
    private String name;

    public MemFileOutputStream(String name)
    {
        this.name = name;
    }

    public void close()
        throws IOException
    {
        try
        {
            MemFileSystemAdaptor.fileSystem.writeFile(name, bStream.toByteArray());
        }
        catch(RemoteException e) {throw new IOException(e.toString());}
    }

    public void write(byte[] b) {bStream.write(b, 0, b.length);}
    public void write(byte[] b, int start, int len) {bStream.write(b, start, len);}
    public void write(int i) {bStream.write(i);}
}

http://stackoverflow.com/questions/5629116/simple-in-memory-file-system
http://www.flipcode.com/archives/Programming_a_Virtual_File_System-Part_I.shtml
Java code: https://github.com/marschall/memoryfilesystem
Read full article from Design an in-memory file system | Runhe Tian Coding Practice

No comments:

Post a Comment

Labels

Review (554) System Design (293) System Design - Review (189) Java (178) Coding (75) Interview-System Design (65) Interview (60) Book Notes (59) Coding - Review (59) to-do (45) Knowledge (39) Linux (39) Interview-Java (35) Knowledge - Review (32) Database (30) Design Patterns (29) Product Architecture (28) Big Data (27) Soft Skills (27) Miscs (25) MultiThread (25) Concurrency (24) Cracking Code Interview (24) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Distributed (20) Interview Q&A (20) OOD Design (20) System Design - Practice (19) Security (17) Algorithm (15) How to Ace Interview (15) Brain Teaser (14) Google (13) Linux - Shell (13) Spark (13) Spring (13) Code Quality (12) How to (12) Interview-Database (12) Interview-Operating System (12) Redis (12) Tools (12) Architecture Principles (11) Company - LinkedIn (11) Testing (11) Resource (10) Solr (10) Amazon (9) Cache (9) Search (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Company - Uber (8) Interview - MultiThread (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Scalability (8) Cassandra (7) Git (7) Interview Corner (7) JVM (7) Java Basics (7) Machine Learning (7) NoSQL (7) C++ (6) Design (6) File System (6) Highscalability (6) How to Better (6) Kafka (6) Network (6) Restful (6) Trouble Shooting (6) CareerCup (5) Code Review (5) Company - Facebook (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Be Architect (4) Big Fata (4) C (4) Company Product Architecture (4) Data structures (4) Design Principles (4) Facebook (4) GeeksforGeeks (4) Generics (4) Google Interview (4) Hardware (4) JDK8 (4) Optimization (4) Product + Framework (4) Shopping System (4) Source Code (4) Web Service (4) node.js (4) Back-of-Envelope (3) Company - Pinterest (3) Company - Twiiter (3) Company - Twitter (3) Consistent Hash (3) GOF (3) Game Design (3) GeoHash (3) Growth (3) Guava (3) Interview-Big Data (3) Interview-Linux (3) Interview-Network (3) Java EE Patterns (3) Javarevisited (3) Map Reduce (3) Math - Probabilities (3) Performance (3) Puzzles (3) Python (3) Resource-System Desgin (3) Scala (3) UML (3) geeksquiz (3) AI (2) API Design (2) AngularJS (2) Behavior Question (2) Bugs (2) Coding Interview (2) Company - Netflix (2) Crawler (2) Cross Data Center (2) Data Structure Design (2) Database-Shard (2) Debugging (2) Docker (2) Elasticsearch (2) Garbage Collection (2) Go (2) Hadoop (2) Html (2) Interview - Soft Skills (2) Interview-Miscs (2) Interview-Web (2) JDK (2) Logging (2) POI (2) Papers (2) Programming (2) Project Practice (2) Random (2) Software Desgin (2) System Design - Feed (2) Thread Synchronization (2) Video (2) ZooKeeper (2) reddit (2) Ads (1) Advanced data structures (1) Algorithm - Review (1) Android (1) Approximate Algorithms (1) Base X (1) Bash (1) Books (1) C# (1) CSS (1) Chrome (1) Client-Side (1) Cloud (1) CodingHorror (1) Company - Yelp (1) Counter (1) DSL (1) Dead Lock (1) Difficult Puzzles (1) Distributed ALgorithm (1) Eclipse (1) Facebook Interview (1) Function Design (1) Functional (1) GoLang (1) How to Solve Problems (1) ID Generation (1) IO (1) Important (1) Internals (1) Interview - Dropbox (1) Interview - Project Experience (1) Interview Tips (1) Interview-Brain Teaser (1) Interview-How (1) Interview-Mics (1) Interview-Process (1) Jeff Dean (1) Joda (1) LeetCode - Review (1) Library (1) LinkedIn (1) LintCode (1) Mac (1) Micro-Services (1) Mini System (1) MySQL (1) Nigix (1) NonBlock (1) Process (1) Productivity (1) Program Output (1) Programcreek (1) Quora (1) RPC (1) Raft (1) RateLimiter (1) Reactive (1) Reading (1) Reading Code (1) Refactoring (1) Resource-Java (1) Resource-System Design (1) Resume (1) SQL (1) Sampling (1) Shuffle (1) Slide Window (1) Spotify (1) Stability (1) Storm (1) Summary (1) System Design - TODO (1) Tic Tac Toe (1) Time Management (1) Web Tools (1) algolist (1) corejavainterviewquestions (1) martin fowler (1) mitbbs (1)

Popular Posts