Author: mattchung

  • Distributed Systems – Active Networks (notes)

    Distributed Systems – Active Networks (notes)

    Introduction

    Summary

    How do quickly and reliably route data

    Routing on the Internet

    How to make router to route communication active?

    Summary

    Key Words: active network

    The idea is that instead of each router performing a simple next hop look up, let’s make the routers smart and inject code in the packet that can influence the flow. How can we do this securely and safely? And without adversely impacting other flows

    An Example

    Real life example of Active Networks

    Summary

    Key Words: Demultiplex

    Nice example from the professor. Basically, packet looks like mutlicast stream. But instead, the sender sends a single message and an edge router will demultiplex the message, sending out that single message to multiple destinations

    How to implement the vision

    How to implement the vision

    Summary

    Essentially, application interfaces with the protocol stack, application sending its quality of service (QoS) requirements. Then, once this packet reaches protocol stack, the protocol stack will slap on an IPHeader with some code embedded inside the packet, the code later read in by routers up stream. But … how do we deal with the fact that not all routers participate? Routers are not open

    ANTS

    Ants toolkit

    Summary

    Key Words: Active Node Transfer System (ANTS), edge network

    To carry out the vision, there’s active node transfer system, where the specialize nodes sit at the edge of the network. But my question still remains, if you need to send it out to multiple recipients, in different edge networks, feels like the source edge node will need to send more than one message

    ANTS Capsule and API

    ANTS Capsule and API

    Summary

    Very minimal set of APIs. Most important to note is that the ANTS header does not contain executable code. Instead, the type field contains a reference and the router will then look up the code locally

    Capsule Implementation

    What happens during capsule arrival

    Summary

    Capsule contains a fingerprint for capsule code, used to cryptographically verify capsule. If router does not have code locally stored in the soft store, will need to ask the prev node for the code (and again verifying capsule). Finally, soft store is essentially a cache.

    Potential Applications

    Potential Applications of active networks

    Summary

    Active networks used for network functionality, not higher level applications. Basically, we’re adding an overlay network (again not sure how this all relates to advanced operating systems or distributed systems but interesting nonetheless)

    Pros and Cons of Active Networks

    Pros and Cons of Active Networks

    Summary

    Pros and Cons of Active Networks. On one hand, we have flexibility from the application perspective. But there are cons: protection threads (can be defended by: runtime safety using java sand boxing, prevent code spoofing using robust fingerprint, and restrict APIs for soft state integrity). From a resource management perspective, we’ll limit the restricted API to ensure code does not eat up lots of resources and finally, flooding the network is not really a problem since the internet is already susceptible to this.

    Quiz

    Summary

    Some challenges include 1) need buy in from router vendors 2) ANTS software cannot match speed requirements

    Feasible

    How feasible of Active Networks

    Summary

    Again, because router makers loath to open up network and software cannot match hardware routing, active networks can only sit at the edge of the network. Moreover, people are worried (as they should be) having arbitrary code running on public routing fabric

    Conclusion

    Summary

    Active Networks way ahead of its time. Today, we are essentially using similar principles for software defined network

  • Distributed Systems – Latency Limits (Notes)

    Introduction

    Summary

    Lamport’s theories provided deterministic execution for non determinism exists due to vagaries of the network. Will discuss techniques to make OS efficient for network communication (interface to kernel and inside the kernel network protocol stack)

    Latency Quiz

    Summary

    What’s the difference between latency and throughput. Latency is 1 minute and throughput is 5 per minute (reminds of me pipelining from graduate introduction to operating systems as well as high performance computing architecture). Key idea: throughput is not the inverse of latency.

    Latency vs Throughput

    Summary

    Key Words: Latency, Throughput, RPC, Bandwidth

    Definitions of latency is elapsed time for event and throughput are the number of events per unit time, measured by bandwidth. As OS designers, we want to limit the latency for communication

    Components of RPC Latency

    The five components of RPC: client call, controller latency, time on wire, interrupt handling, server setup to execute call

    Summary

    There are five sources of latency with RPC: client call, controller latency, time on wire, interrupt handling, server setup and execute call (and then the same costs in reverse, in the return path)

    Sources of Overhead on RPC

    Sources of overhead include: marshaling, data copying, control transfer, protocol processing

    Summary

    Although the client thinks the RPC call looks like a normal procedure, there’s much more overhead: marshaling, data copying, control transfer, protocol processing. So, how do we limit the overhead? By leveraging hardware (more on this next)

    Marshaling and Data Copying

    There are three copies: client stub, kernel buffer, DMA to controller

    Summary

    Key Words: Marshaling, RPC message, DMA

    During the client RPC call, the message is copied three times. First, from stack to RPC message; second from RPC message into kernel buffer; third, from kernel buffer (via DMA) to the network controller. How can we avoid this? One approach (and there are others, discussed in the next video, hopefully) is to install the client stub directly in the kernel, creating the client stub during instantiation. Trade offs? Well, kernel would need to trust the RPC client, that’s for sure

    Marshaling and Data Copying (continued)

    Reducing copies by 1) Marshal into kernel buffer directlry or 2) Shared descriptors between client stub and kernel

    Summary

    Key Words: Shared descriptors

    An alternative to placing the client stub in the kernel, the client stub instead can provide some additional metadata (in the form of shared descriptors) and this allows the client to avoid converting the stack arguments into an RPC packet. The shared descriptors are basically TLV (i.e. type, length, value) and provides enough information for the kernel to DMA the data to the network controller. To me, this feels a lot like the strategy that the Xen Hypervisor employs for ring buffers for communicating between guest VM and kernel

    Control Transfer

    Only two control transfers in the critical path, so we can reduce down to one

    Summary

    Key Words: Critical Path

    This is the second source of overhead. Bsaically have four context switches, one in the client (client to kernel), two in the server (for kernel to call server app, and then from server app out to kernel), and one final switch from kernel back to client (the response)

    The professor mentions “critical path” a couple times, but not sure what he means by that (thanks to my classmates, they answered my question in a Piazza Post: the critical path refers to the network transactions that cannot be run parallel and the length of the critical path is the number of network transactions that must be run sequentially (or how long it takes in wall time)

    Control Transfer (continued)

    Summary

    We can eliminate a context switch on the client side, by making sure the client spins instead of switching (we had switched before in make good use of the CPU)

    Protocol Processing

    How to reduce latency at the transport layer

    Summary

    Assuming that RPC runs over lan, we can eliminate latency (but trading off reliability) by not using acknowledgements, relying on the underlying hardware to perform checksums, eliminating buffering (for retransmissions)

    Protocol Processing (continued)

    Summary

    Eliminate client buffer and overlap server side buffering

    Conclusion

    Summary

    Reduce total latency between client and server by reducing number of copies, reducing number of context switches, and making protocol lean and mean

  • Daily Review: Day Ending in 2020/10/18

    Daily Review: Day Ending in 2020/10/18

    Family and Friends

    • Celebrated Elliott’s 1 year birthday. Jess and I are two weeks late but to be fair, the two of us were in the midst of moving the entire house, making it difficult to celebrate properly. And now that we moved in — but not quite fully unpacked — it’s easy to let that celebration slide and slip away so I’m glad that yesterday Jess pushed to have us celebrate, even if we were two weeks late.
    • Ordered equipment to take care of the yard. I ordered a EGO 21″ self-propelled mower and an EGO Handheld Leaf Blower Kit, the two items totaling roughly $1,000.00. But I’ve done my research, watched several YouTube videos and ready enough reviews to determine that both pieces of equipment are are designed to last many years.
    • Video chatted with friend for 10 minutes over Zoom. Just played catch up since the two of us have not seen each other much (only once, during black live matters protest in downtown Seattle) one COVID-19 kicked in.
    • Dropped by my sisters house so Elliott and can hang out with her cousin. Again, a good reminder that moving to Renton makes these little pop overs feasible, now that it only takes 10 minutes (instead of 40) to drive to my sister’s house.

    Cleaning

    Scrubbing down couch with oxiclean, Metric chilling
    • Mixed up an oxiclean solution and scrubbed down our couch. I’ll post the outcome in a future blog but so far, results look promising.

    Graduate School

    Lectures

    • Finished global memory systems lectures and made it half way through distributed shared memory. I’m still behind a bit behind on the lectures (I would say about one to two days) but I think I should be fairly caught up pretty soon.

    What did I learn

    • Learned about release consistency memory model. Unlike sequential consistency, we can unlock parallelism by waiting for the coherence action to trigger just before a lock is released: this is known as release consistency. We can further optimize this by only generating coherence traffic at the time of (the other) lock acquisition(s), known as lazy release consistency.
    • Feel like I’m getting deeper and deeper into operating systems (exactly what I want). Learning about how to optimize the memory consistency model is amazing: going from sequential consistency to release consistency (i.e. eager release consistency) to lazy release consistency. My head … it’s spinning. But in a good way. And the theory reminds me of work. Eager vs Lazy means push versus pull.
  • How to clean your cleaning tools (notes)

    How to clean your cleaning tools (notes)

    How do you take care of the tools that you use for cleaning?  This is a question I’ve been curious about over the last couple days since currently going through a cleaning phase. To up my cleaning skills, I’ve been searching online for tutorials and discovered an amazing YouTube channel called Clean My Space that published a video titled “7 Expert Cleaning Tips You Need to be Using”. After watching the video, I’m now applying the cleaning techniques to maintain and take care of my home cleaning tools.

    1. Brushes (with Oxiclean) Mix oxiclean and hot water (check manual for right ratio) and then toss your brushes (e.g. toothbrush, bottle brush) in the mixture and allow the bristles to soak anywhere between 30 to 60 minutes.
    2. Sponges Apply the same method as above (or microwave the sponge). Keep in mind that the sponge should be cleaned weekly and replaced monthly
    3. Cleaning Cloths. For cleaning clothes, just toss them in the washer and sprinkle with baking soda. But for microfiber, make sure to first rise them alone then place them in delicate bag. Add a little detergent, thats it. Dry them as you would (gentle cycle). Also, never use micro fiber for greasy, since it ruins the microfiber
    4. Mop Head. Wash and then to dry. Wash monthly.
    5. Broom. Remove broom from broom stick, place in bucket (with Oxiclean). Perform this maintenance every 3 months.
    6. Vacuum. Refer to user guide (or manual), but few good general tips for maintaining include: empty on the regular basis, wash the filter (especially for HEPA vacuum), and lay the entire vacuum flat for 24 hours and cut up stuff that gets tangled in the brush, using warm soap and water and allowing let them rest for 24 hours to let them dry
  • Daily Review: Day Ending in 2020/10/17

    Daily Review: Day Ending in 2020/10/17

    Family

    • Went on a cleaning binge. Not sure why sometimes I get totally obsessed with cleaning but yesterday was one of those spurts. I had watched about a dozen YouTube videos (from Clean My Space) on cleaning tutorials, followed by vigorouly scrubbing down stove tops with baking soda and vinegar, buying cleaning supplies (e.g. micro fiber, empty bottles for home made cleaning supplies) from both Ace Hardware and Big Lots, and ending the day with wiping down the entire marble kitchen counter
    • Got into an argument with Jess around finances. Seems like talking about finances triggers me, the topic putting me in a bad mood almost every time. Although I have some ideas on why this is the case, I cannot exactly pinpoint why I go into fight or flight mode.But if I’m honest, I do find the idea of splitting the money down the middle uncomfortable. But I know that’s ridiculous.  I do want to sort out these feelings but I think they run deep and stem from my awful past experiences with money between me and my family members.

    Graduate School

    Project Work

    • Chatted over the phone with my project partner. After working together on the previous assignment (i.e. Project 2 on Synchronization Barriers), my project partner (Will) and I have decided to work together again for project 3 (using gRPC and building a multi-threaded, asynchronous web server). We’re approaching the division of work a bit differently than last time, when I took on majority of the development and he took on the performance testing and benchmarking. This time around, we’re going to try and parallelize the work and split down the development (and design) right down the middle.

    Lectures

    • Completed lectures on distributed shared memory and started on distributed shared memory. The biggest take away for me (so far) for the distributed shared memory lectures is that from a sequential consistency perspective, the system does not distinguish a read/write for a normal memory data access from a read/write of a synchronization read/write variable. Why does this even matter? At first, I could not my wrap my head around the significance of this idea and how/why this related to distributed shared memory. But the more I thought about, the more it makes sense: if a thread locks a critical section and updates one (or more) variable(s), why generate cache coherence while inside the critical section — why not wait until an unlock happens? Actually, as I type this out, there might be a good reason: for readers of that variable to make forward progress on their (non critical) section.

    Questions I have

    • Why do we have a GCD (global cache directory) and how does this “one level of indirection” help as part of building the larger global memory system?
  • Daily Review: Day Ending in 2020/10/16

    Daily Review: Day Ending in 2020/10/16

    Home Maintenance

    • Watched several YouTube videos on mowing grass. I found an awesome YouTube channel called the The Lawn Care Nut. I had been searching around online on good content that will teach me how to maintain and care for my front (and back) yard.  Now, although the owner of the YouTube channel tailors most of his videos for more intermediate or advanced lawn enthusiast, he’s recorded a quite a few videos for people like me: people who know nothing about lawn care and are trying to learn how to maintain their first lawn.

    Family

    • Elliott and I walked the dogs at cedar river trails. Jess needed an extra 30 minutes of sleep so during that time, which actually turned into almost 2 hours, Elliott and I walked the dogs at cedar river trails, a trail that also has an off-leash dog park (would not recommend for playing fetch, the field practically filled with rocks and dirt)
    • Ran errands for 2 hours, driving from Renton to North Seattle. I picked up two (1/2) gallon bottles of home made Chai from Cloud City, what used to be our local cafe that I had walked to almost every day. Then I drove over to the Grateful bread, picking up Jess (3) loaves of Challah and a baker’s dozen of cinnamon raisin. Then, I ended the trip with stocking up on raw pet food from DD Meats located in Mount Lake Terrace.
    • Roamed around Ikea in Renton. Jess and I bought a couple household items while shopping at Ikea but mainly we spent time walking the show room to collect ideas for our house.
  • Daily Review: Day Ending in 2020/10/15

    Daily Review: Day Ending in 2020/10/15

    Family

    • Difficult time comforting Jess when she’s upset. It’s insane but it’s so easy for me to gently console other people (like friends or even strangers) when they are upset but I find it incredibly difficult to do the same for Jess.  The words just don’t come out. It’s difficult to put into words why I cannot comfort her but I just feel much more vulnerable and my throat chokes when I see her upset, making it difficult for me to even utter any words of comfort.
    • Watched Elliott on my day off work and brought her over to her cousins house for a little play date.  Jess needed time to herself to get some work done so I too Elliott over to her cousins house (10 minutes away, now that we live in Renton) and  I totally get why parents have play dates now. It’s so much easier to watch the kids when they are engaged with one another and you don’t have to be the single source of entertainment.

    What I learned

    • The term anonymous pages. In virtual memory management (VMM), an anonymous page is a page not backed by any particular file1 and is used for things like the stack, or the heap, or copy-on-write pages. The term (anonoymous pages) was brought in the video lectures on global memory systems (see section below: graduate school).

    Graduate School

    Project 3

    • Set up my local development environment using CMake and something called vcpkg. I’m curious why we are using CMake instead of Make: what are the advantages of using the former? And what does vcpkg do?
    • Successfully imported protobuf header in my “store.cc” code. Just like in professional development, the best way to build momentum for a new development project is by committing as small pieces of code that push the project forward, even if its an inch.

    Lectures

    • Watched half the on global memory systems. This is an interesting topic, paging out not directly to disk but to other node’s memory systems using the local area network (LAN) instead. I’m assuming here that the time to spin the head of a physical hard disk exceeds the time to generate a packet and for the packet to traverse the network. Otherwise, what’s the point?

    Relearning from my own notes

    • Unified buffer cache. This term seemed eerily familiar so I searched through my previous blog posts and found the actual post where I learned this concept. It’s always a nice feelings to rediscover your own learning.

    Music

    [fvplayer id=”5″]

    • Played around with different chord options on the guitar. My guitar instructor (Jared Borkowski) shared a beta PDF guide called “Chords with colors” so I spent a few minutes noodling with my guitar and recorded a quick little clip (above).

    References

    1. https://blogs.oracle.com/cwb/so-what-the-heck-is-anonymous-memory
  • Project 3 – Snapshotting my understanding (gRPC)

    Project 3 – Snapshotting my understanding (gRPC)

    Unfamiliar Technologies

    • Never heard of or used gRPC. According to their website, it’s a high performance open source RPC framework. I’m wondering if this package is used outside of academia. Probably is and probably is actually used within Amazon.

    What I do know

    • Google Protobuf. Fortunately, I have some experience with Google Protobufs since we use message serialization format within our stack (and the technology itself is quite ubiquitous)
    • Multi-threading. Prior to joining the OMSCS program, I had little to no understanding how threads worked and how they differed from processes. But since then, I have a much more intimate understanding of threads and even written several multi-threaded applications, both in graduate school and in a professional work setting. So I actually feel quite comfortable and prepared for project 3.

    Questions I Have

    • What does the gRPC framework offer? What advantage does using this framework have over just a simple HTTP framework? What problem does gRPC solve? Is it similar to an OS’s RPC framework but extended so that it works across hosts?
    • What does the wire protocol look like for gRPC? Does gRPC dictate the wire format or not?

    What I’m hoping to learn

    • Best practices for thread pools. Seems pretty straight forward to create a pool of threads and design the system in such a way that each thread will grab work from a (bounded) buffer. But what else should I consider?
    • How I might use gRPC for future projects. In the previous project (i.e. Project 2), I learned about OpenMP and MPI and convinced that if I ever need to write parallel software, I would use those libraries and runtime engines. Maybe the same will be true once I start fiddling with gRPC?

     

     

  • Not putting all your eggs in one basket and Daily Review: Day ending in 2020/10/14

    Not putting all your eggs in one basket and Daily Review: Day ending in 2020/10/14

    Mental Health

    Best Part(s) of My Day

    • Swinging on the swings with Elliott. She was sitting on my lap, facing my direction, as swung us on the swing back and forth. The entire time she was smiling and when her cold chubby cheeks brushed up against mine, some dad love feelings ran through my body.
    • Eating a kick ass lunch. My wife whipped up a delicious Vietnamese dish with bean sprouts and pickled cucumbers and fermented tofu.

    Therapy Session

    • Vented about on call the past week. I shared the handful of times that I was paged out of bed at 03:30 AM and the operational issues that lasted until 10:00 pm on the evenings and being tied to the computer.
    • Shared the sense of betrayal I felt at work. How someone who I thought was in my corner, rooting for me, actually no longer advocates for me after I declined their “opportunity” to lead a project.
    • Declining the project that “sets me back for a promotion” allows me to bring my best self to work. Although one could argue that me not accepting the “opportunity” to lead a project (that would’ve easily tacked on additional 5-10 hours per week) sets me back for my promotion, I did it so maintain a balance between my professional and personal life, which quite frankly is what I am all about: living a balanced life, not one where I am endlessly pursuing the next thing.
    • Realized that I need to build a stronger community of supporters. Take away from this sense of betrayal is that I need to widen my network of supporters and not to put all my eggs in one basket, so to speak.

    Random

    Cool Quotes

    • “Academia is ripe for pursuing ideas on the lunacy fringe”.

    Graduate School

    • Skipping Java and Spring (for now) and jumping into Distributed System lectures. I almost always follow the curriculum in the order prescribed by the syllabus. But I’ve decided to skip (for now) some video lectures on Java and Spring… and this makes me a little bit anxious. Honestly, I find the Java and Spring lectures a bit boring (to be fair, I might actually enjoy them once I start watching the lectures). Right now, I’m interested in learning more about the fundamentals and theories of constructing distributed systems so I’ll jump to those videos.

    Music

    • Dusted off and played the ukulele for Jess and Elliott. I feel like I abandoned the ukulele after picking up the guitar. And strumming my beautiful Soprano ukulele yesterday reminded me that the instrumental has its own vibe and own personality, the strings sounding much more … bright.

    Family

    • Fell asleep at 06:30 pm. I normally fall asleep between 08:30 and 09:30, on both weekdays and weekends. But yesterday I was shattered after my sleep was interrupted several times throughout the night, the most notable when Jess had a coughing fit at around 03:00 AM, at which point I was pretty much unable to fall back asleep.
    • Slept in the same bed as Elliott and Jess last night. This was pretty sweet actually. Although I woke up multiple times throughout the night, I loved having Elliott and Jess in the same bed since I’ve been sleeping alone — well, with the dogs — for the last six months or so.
    • Wrapped a baby net around stair railings. Installing the net (my sister’s idea)  prevents little Elliott from slipping through the rails. Although I do not think her head could possibly squeeze through, the net gives Jess piece of mind and that’s important since she’s the one watching her throughout the day.
  • Daily Review – Day Ending in 2020/10/13

    Daily Review – Day Ending in 2020/10/13

    Family

    • Took Elliott shopping at Safeway while Jess took her work call. We picked up some avocados for our morning smoothies and some blackberries and blueberries (side note: why does a palm sized box of blueberries cost $6.00). While paying for our goods, our cashier awkwardly pulled down her mask for Elliott to see her face. Outside the context of COVID-19, this would be totally normal and even appreciated. But given we are in the midst of the pandemic, I felt awkward but didn’t feel compelled to ask her to put her mask back on given there was a glass screen positioned between us.

    Graduate School

    Lectures

    • Did not read any lectures but did download all the videos for Spring Operating systems. I normally do not download the videos to my laptop however wind was hitting us pretty hard and our lights were flickering so I was preparing for the situation in which our internet disconnected.

    Project Work

    • Completed writing documentation for project 2 submission. This included an analysis of the algorithms that I wrote (i.e. centralized barrier with sense reversal, dissemination and tournament) and why some barriers performed better (or worse) than other barriers.
    • Skimmed through requirements for project 3i.e. build a distributed service using grpc). This project got announced Monday evening and will be due in about 3-4 weeks and I like to get started early to avoid last minute cramming, which leads to unnecessary stress.