Design problem- Structural analysis
In these series of articles i want to explore various strategies to approach design problem
Framework
Below are key points to think when you want to solve an problem
- Understand the problem
- Understand the behaviour of Whole system/ List Requirements
- Translate Requirements into High Level design
- Detailed Design
Key Points
Understand the problem - Understand the key concepts/algorithms/data structures/Other similar system which can help in solving the problem.
High Level Design - Break up system into smaller subsystems and how they communicate
Detailed design - Details of interfaces, Logic,Algorithms, Communication between interfaces etc is specified
Further problem usually falls in one of 3 categories
- Known Known - Concepts/DS/Algorithms which you are aware of and know the internals etc. These are fairly easy
- Known Unknown - Concepts/DS/Algorithms which you know exist but don’t know how they work. There could be medium grade problem. Worst case you can convert concept into black box, if you don’t know internals and keep making progress
- Unknown Unknown - Concepts/DS/Algorithms which you don’t know about their existence. These problems are hardest because you will not know what /where to start
Also Note some problems may have all steps and some problems may have few steps. However below is the key take away
- Simplify the problem
- Try to map it to existing problem
- Structural analysis of problem- Break down problem into smaller pieces
- Any module/sub-system, you don’t have knowledge/understanding- treat it as black box and come back later
Problem 1- Design LRU or LFU
- Understand the problem/ Key concepts needed to solve it
Problem pertains to caching and once items are cached, how are the removed from cache
Key concepts
- Caching , Fairly straightforward. If you want you can read about it here
- LRU — Least Recently Used item should be removed
- LFU — Least Frequently Used Item should be removed
Algorithms/DS - No specific algorithm needed . Just pure logic. Below are DS which can help
- HashMap - Standalone implementation
- Redis - More sophisticated and distributed implementation
3. Understand the behaviour/ List down Requirements
- Store Items ⇒ represents behaviour of cache
- Retrieve Items ⇒ represents behaviour of cache
- Have limit on number of Items
- Manage count of retrieval for each item ⇒ used for LRU
- Manage access time for each item ⇒ used for LFU
4. High Level Design
Since only subsystem we skip high level design and directly go to detailed design
5. Detailed Design
In this particular problem, detailed design can be expressed in form of interfaces. Below are possible methods for that interface
- addItem ()
- removeItem ()
- getItemCount ()
- getItemLastAccessTime()
- getTotalSize()
- getCacheType()- LRU or LFU
Above was simple problem and it clearly mapped to framework /steps which we had listed at start
Now lets look at another problem, which is little bit involved
Problem 2- Design a File System
Lets try to see if we can follow steps listed at start of page and if we can get some where
This problem is more involved and expects one to know internals of file system without which it will be difficult to progress
- Understand the problem/ Key concepts needed to solve it
In this case we want to build File system. Its way to store /edit / retrieve files. Couple of important points which we need to understand here
Key concepts
- How are files stored/accessed in disk
- OS internals . How it manages file systems
Algorithms/DS
- Inode - to store meta data about files and directories
2. List down the Requirements
- create directories/folders
- create files
- search files
- list folders and sub-folders
- list files in folders
- access policies pertaining to files and folders
3. High Level Design
Below components are involved in design of File System
Above diagram is divided into 4 main regions
- Data blocks - Data stored in one or more blocks. In our example, below are some more detailsDisk size- 256KB. Each block is of size 4KB
- Inode blocks- each block has one ore more inodes.
- Bitmaps- indicates which inodes/data blocks are free
- Superblock- which nodes are iNodes, which ones are data
Lets further expand the first region to see how it looks
Some calculations, so above diagrams can make sense
- Disk size of 256 KB. (Assumption for our case)
- Total blocks 64 , each block is of 4 KB
- Data Blocks - 224 KB , 56 blocks 4 KB
- Inode - 5 blocks, 20 KB
- Inode bit map - 4 KB
- Data bit map - 4 KB
- Super Block - 1 KB
- Root Inode is located at 2
4. Detailed design
In this case we will specify how Algorithm for read operation works. Other operations (write/search) can be derived easily from this
Reading file
Below steps are performed when file is opened or read . file name “/projects/test”
- FS Will read a block for root. “/” . This is located at iNode2. OnDisk data for root might look like below
2. FS will read through contents to locate directory projects
3. Once it finds the same, it gets inode associated with directory, in this case 10
4. It goes to inode 10, reads data block and locates iNode for file test
5. Goes to inode for file test, gets data block and starts reading
For Listing and Writing exactly similar traversal logic can be used, except different system calls will be used in case of writing
Some other considerations
- OS Keeps track of open files via Global Open File table. One entry per file. File Descriptor of file is stored
- In addition each process has files associated with its self in Per Process File Table. In this table File Descriptor is stored
- Disk Buffer Cache is used for Caching and performance optimisation
References
- Operating System ,Three easy steps
- Videos associated with above book
