Implement ARC algorithm extension for the vnode free list
Short description: This project would allow a better management of filesystem buffer cache. The goal is to reduce amount of disk access by better managing the vnode list and VM objects. ARC would allow frequently used vnodes to stay in memory even if it has not been used recently. Allowing VM objects to stay in memory would allow vnode layer to hold onto pages even when the vnode is deallocated.
Name: Nohhyun Park
Phone number (include country and area code): 1-612-229-4239
Project title: Implement ARC algorithm extension for the vnode free list
Description of project goals, including details of how the delivered code will operate:
Better management of filesystem buffer cache. The goal is to reduce amount of disk access by better managing the vnode list and VM objects. ARC would allow frequently used vnodes to stay in memory even if it has not been used recently. Allowing VM objects to stay in memory would allow vnode layer to hold onto pages even when the vnode is deallocated.
Another portion I like to see is the actuall performance effect of such optimizations.
Description of Target Algorithm:
LRU: Replacement is based on the recency of access. The goal is to capture how recently an object was accessed.
It assumes that the past recency reflects the future recency.
The overhead is the cost of maintaining the priority list based on the recency.
LIRS: Replacement is based on the reuse distance rather than recency. The goal is to capture the frequency of the access where the objects that are accessed with more frequently are more likely to stay in the cache.
It assumes that the past frequency represents the future frequency.
The overhead is bits required to store the reuse distance + LRU overhead.
CLOCK: Tries to reduce the cost of maintaining the prority list in LRU. the goal is to maintain recency per epoch rather than per access.
It assumes that strictly priortized recency is not necessary since the future information is only captured in a limited sense by the past.
A circular queue with a bit per entry needs to be maintained.
CLOCK-Pro: Simlar to Clock but for LIRS. The goal is to maintain information for hot/cold data per queue entry. The goal is to maintain both the recency and frequency at epoch granularity.
A circular queue with two bits per entry is required. It also requires longer scans through the queue to find revocation candidate since it needs to find "cold" data that has not been used recently.
ARC: Maintains two list, each managing recency and frequency. The goal is to dynamically adjust the size of the two lists for workloads that favors either the recency of the frequency.
The assumption is that of the past hit rate favored recency, more space needs to be allocated to the recency list and vice versa.
The cost is a shadow lost which keeps track of potential hits and misses for each list if the content was not revocated from the list. Probably most expensive interms of both space and computation.
1. Vnode freelist management with various different revocation algorithms (LIRS(Jiang and Zhang2002), ARC (Megiddo 2003), etc). This can be controlled at mount time.
2. Vnode activity monitor.
3. Root vnode that handles VM objects not backed by any vnode. (Not sure if this is the right approach.)
4. Mechanism to pass back the VM object to newly allocated vnodes if the inode number matches. (I am assuming this has to be done. Not exactly sure how.)
5. If time allows, I would also like to embed statistics about the file access in vnode and use it to provides hints to vnode layer what to do with VM object when vnode is allocated and deallocated.
1. Comments on the code.
2. Architectural description.
3. Performance evaluation.
1. Vnode revocation algorithm performance comparison of and their sensitivity to workload.
2. Impact of reusable VM objects and possible optimizations.
Project timeline broken down by week, with details on when each feature
described in the project goals will be available.
- Test framework and development framework setup. (3-4 KVM guests with Dragonfly BSD for testing purposes and a development framework with kernel development framework)
- Current Code Review.
- Concept Discussion.
- Current code review (How vm_objects are handled).
- Test bed design: Trace replay (?)
- Performance metrics definition: number of page faults, IO benchmark testing, etc.
- Allow vnode to pass its vm_object to root vnode before being reclaimed. (?)
- Determine what algorithm should be used to determine which vm_objects needs to be freed.
- Ensure that root vnode frees those vm_objects.
- Ensure different algorithms for vm_object revocation work correctly.
- Stress testing (Memory intensive benchmarks, IO intensive benchmarks, mix)
- First version ready.
- Code Review.
- Code Scrub.
- Current code review (mount operations).
- Allow vnode revocation scheme to be part of mount option (not sure this is a right approach either).
- Test with a dummy option that points to existing LRU functions.
- Debugging and testing.
- Try LIRU algorithm. (Should be a simple changes to LRU)
- Write two-queue algorithm with static division (Both LRU).
- Check that vnodes gets passed between the queues.
- Implement ARC.
- Performance testing.
- Code review.
- Code scrub.
- Presentation (?)
What additional resources as hardware or software will be needed for this project?
It would be great if I can have a machine dedicated to Dragonfly BSD (hopefully with sudo access).
Please include or provide links to prior code related to this area of work.
We also have a set of standards for the students to follow located on the website: