Matt Chung's Site

Author: mattchung

  • Failure: I want more of it.

    Failure: I want more of it.

    Students in the Georgia Tech program collaborate with one another — and collaborate with professors and teacher assistants — through a platform called Piazza. But at the end of the semester, this forum shuts off to read only mode, meaning we all lose connection with one another.

    Because of this, I recently created an e-mail list called computing-systems@omscs-social.com for other Georgia Tech Students who are interested in staying in touch. The motivation behind the mailing list is to share job opportunities, connect with other working professionals, and perhaps most important: provide peer support for one another. This felt like a natural next step since the study sessions (called “war rooms”) that I hosted were pretty successful.

    Piazza post. 70 views. 1 sign up

    But after posting a link on Piazza and sharing the idea, only 1 out of 70 people signed up. Total failure, right?

    Sort of.

    The lack of people signing up for the mailing list reaffirms two of my believes. First, the entire notion of “build it and they will come” is not true. Especially as software developers, we know that we can build the most shiny, most magical, most performant piece of software … and nobody can care.

    The second belief is that failures are a good thing. According to the late Randy Pausch, these setbacks are what we likes to call brick walls:

    The brick walls are there for a reason. The brick walls are not there to keep us out. The brick walls are there to give us a chance to show how badly we want something. Because the brick walls are there to stop the people who don’t want it badly enough. They’re there to stop the other people.

    – Randy Pausch

    In order to grow, you need to fail — a lot — because there’s no linear path to success.

    You can see this pattern of trial and error with Josh Pigard’s most recent venture that he recently sold for $4 million: big success, right? Yes, definitely.

    But notice all his other failed projects listed on his personal website.

    Josh Pigard – projects that were shut down

    On some level, the above are considered failures since the projects ultimately shut down. But that’s not how I see it. I’d like to think that Josh learned a lot of things from those failures, which fed and led him to building and selling his company.

    From this example alone, I think I can take away a lot of lessons learned. In particular, like my wife,  I am a perfectionist. I want — sometimes need — things to be perfect. But that’s surface level, only what maybe the outside can see. There’s a shadow side.

    Really, like many others, I have imposter syndrome. I’m constantly worried that I’m going to get exposed as some sham. My response to imposter syndrome? Striving to be right all the time. And I believe that taken too far, trying to be right all the time can stunt growth because to grow — personally and professionally — I need to constantly be experimenting, tinkering, trying out things that might just fail.

    To wrap things up: will I shut down and abandon the mailing list? Maybe. Maybe not.

     

  • Enterprise Java Beans – notes and summary

    Enterprise Java Beans – notes and summary

    Introduction

    Key Words: EJB, enterprise java beans

    Discuss how we can structure system software for large scale distributed sytem service

    Inter Enterprise View

    Inter Enterprise View: The motivation of using enterprise java beans

    Key Words: monolithic, supply chain model, amalgam, survivability, complexity

    From a user perspective, we view a system (like Ebay or Google) as a blackbox. But in reality, much more complex than that and within the system, there may be multiple enterprise working together and this can be difficult when trying to handle failures, complexity, and so on

    An Example

    Key Words: scheduling, parallel systems, synchronization, communication, atomicity, concurrency, object technology, reuse

    Using a system like Expedia, we face same issues in parallel systems like synchronization and concurrency and scheduling and atomicity and so on

    N-tier applications

    N tier applications

    Key Words: concurrency, parallelism, embarrassingly parallel applications

    Want to reduce network communication (latency), security (for users) by not compromising business logic, and increase concurrency

    Structuring N Tier Applications

    Structuring N tier applications

    Key Words: JEE, protection domain, bean

    We can split the protection domain uses containers, at the client or at the presentation layer, business layer or database layer. Each container contains N beans, bundle of java objects

    Design alternative (Coarsegrain session beans)

    Coarse grain approach. Although this approach protects business logic from outside network, fails to expose concurrency at the EJB container.

    Key Words: monolithic, concurrency

    Each session bean is very granular, the session bean encapsulating most of the logic. The upshot of this approach is that the container offers little service and the logic is not exposed outside the corporate network. The downside is that we do not exploit concurrency. There’s a missed opportunity where the EJB container and pull in data for multiple sessions

    Design Alternative

    Key Words: trade offs, persistent, bean managed persistence, container managed persistence, data access object

    With data access object design, we confront the short comings of the coarse grain session bean, by exploiting concurrency for data access, limiting I/O and network latency when accessing the database. The trade off? Business logic is exposed to the web container

    Design alternative (session bean with entity bean)

    Design alternative: session bean with entity bean. Hybrid approach of coarse grain and data access object.

    Key Words: session facade, design pattern, remote interface, RMI

    We now embed a session facade, that provides concurrency AND does not exposed business logic. To that end, we use RMI (remote interface) to communicate between the containers and/or between the session facade and entity bean

  • 30 different ways to write paragraphs – series introduction

    30 different ways to write paragraphs – series introduction

    This blog post is the first in the series on the different ways to write powerful paragraphs, inspired by Victor Pellgrino’s book “A writer’s guide to powerful paragraphs”.

    According to Victor Pelligrino, a paragraph is a unit of thought that expresses a single idea, communicated through related sentences. And although there are many ways to create powerful paragraphs, you must — first and foremost — identify your topic: “A topic sentence is the most important sentence in a paragraph. Sometimes referred to as a focus sentence, the topic sentence helps organize the paragraph by summarizing the information in the paragraph”

    Put another way, the topic sentence is generally what your “paragraph is about.” That’s it.

    After identifying the main topic, your main goal is to fully develop that topic. You’ll want to anticipate your reader’s questions and answer them. And if, along the way, you discover your paragraph fails to satisfy those questions, then perhaps you need to better understand your subject: Take a step back from the actual writing and pivot.  Do some research.

    But most importantly, throughout the writing process, constantly keep the reader at the center of your mind. Ask yourself, “Who am I writing for … what do they know…. what do they NOT know”. Think about what assumptions you are making about your reader; more often than not, we assume too much of our reader and lose them along the way. We fail to fill in the missing gaps and we fail to logically link our thoughts, failing to use transitional phrases (or sentences).

    In summary, you’ll want to identify your topic, provide descriptions, arguments and examples (maybe one, perhaps two, sometimes even three).

  • Recovery management in Quicksilver – Notes and Summary

    Recovery management in Quicksilver – Notes and Summary

    The original paper “Recovery management in quicksilver” introduces a transaction manager that’s responsible for managing servers and coordinates transactions. The below notes discusses how this operating system handles failures and how it makes recovery management a first class citizen.

    Cleaning up state orphan processes

    Cleaning up stale orphan processes

    Key Words: Ophaned, breadcrumbs, stateless

    In client/server systems, state gets created that may be orphaned, due to a process crash or some unexpected failure. Regardless, state (e.g. persistent data structures, network resources) need to be cleaned up

    Introduction

    Key Words: first class citizen, afterthought, quicksilver

    Quicksilver asks if we can make recovery a first class citizen since its so critical to the system

    Quiz Introduction

    Key Words: robust, performance

    Users want their cake and eat it too: they want both performance and robustness from failures. But is that possible?

    Quicksilver

    Key Words: orphaned, memory leaks

    IBM identified problems and researched this topic in the early 1980s

    Distributed System Structure

    Distributed System Structure

    Key Words: microkernel, performance, IPC, RPC

    A structure of multiple tiers allows extensibility while maintaining high performance

    Quicksilver System Architecture

    Quicksilver: system architecture

    Key Words: transaction manager

    Quicksilver is the first network operating system to propose transactions for recovery management. To that end, there’s a “Transaction Manager” available as a system service (implemented as a server process)

    IPC Fundamental to System Services

    IPC fundamental to system services

    Key Words: upcall, unix socket, service_q data structure, rpc, asynchronous, synchronous, semantics

    IPC is fundamental to building system services. And there are two ways to communicate with the service: synchronously (via an upcall) and asynchronously. Either, the center of this IPC communication is the service_q, which allows multiple servers to perform the body of work and allows multiple clients to enqueue their request

    Building Distributed IPC and X Actions

    Bundling Distributed IPC and Transactions

    Key Words: transaction, state, transaction link, transaction tree, IPC, atomicity, multi-site atomicity

    During a transaction, there is state that should be recoverable in the event of a failure. To this end, we build transactions (provided by the OS), the secret sauce for recovery management

    Transaction Management

    Transaction management
    Transaction management

    Key Words: transaction, shadow graph structure, tree, failure, transaction manager

    When a client requests a file, the client’s transaction manager becomes the owner (and root) of the transaction tree. Each of the other nodes are participants. However, since client is suspeptible to failing, ownership can be transferred to other participants, allowing the other participants to clean up the state in the event of a failure

    Distributed Transaction

    Key Words: IPC, failure, checkpoint records, checkpoint, termination

    Many types of failures are possible: connection failure, client failure, subordinate transaction manager failure. To handle these failures, transaction managers must periodically store the state of the node into a checkpoint record, which can be used for potential recovery

    Commit Initiated by Coordinator

    Commit initiated by Coordinator

    Key Words: Coordinator, two phase commit protocol

    Coordinator can send different types of messages down the tree (i.e. vote request, abort request, end commit/abort). These messages help clean up the state of the distributed system. For more complicated systems, like a file system, may need to implement a two phased commit protocol

    Upshot of Bundling IPC and Recovery

    Upshot of bundling IPC and Recovery

    Key Words: IPC, in memory logs, window of vulnerability, trade offs

    No extra communication needed for recovery: just ride on top of IPC. In other words, we have the breadcrumbs and the transaction manager data, which can be recovered

    Implementation Notes

    Key Words: transaction manager, log force, persistent state, synchronous IO

    Need to careful about choosing mechanism available in OS since log force impacts performance heavily, since that requires synchronous IO

    Conclusion

    Key Words: Storage class memories

    Ideas in quicksilver are still present in contemporary systems today. The concepts made their way into LRVM (lightweight recoverable virtual machine) and in 2000, found resurgence in Texas operating system

  • Software craftsmanship: convey intent in your error codes

    Software craftsmanship: convey intent in your error codes

    ENOTSUP stands for “Error – not supported” and it is one of the many error codes defined in the error header file.

    I recently learned about this specific error code when reviewing a pull request that my colleague had submitted. His code review contained an outline — a skeleton — of how we envisioned laying out a new control plane process that would allow upcoming dataplane processes to integrate with.

    And he kept this initial revision very concise, only defining the signature of the functions and simply returning the error code ENOTSUP.

    The advice of returning relevant error codes applies not only to the C programming language, but applies to other languages too, like Python. But instead of error codes, you should instead raise specific Exceptions.

    Who cares

    So what’s so special about a one liner that returns this specific error code?

    Well, he could’ve instead added a comment and simply returned negative one (i.e. -1). That approach would’ve done the job just fine. But what I like about him returning a specific error code is that doing so conveys intent. It breathes meaning into the code. With that one liner, the reader (me and other developers on the team) immediately get a sense that that code will be replaced and filled in in future revisions.

    Example

    Say you are building a map reduce framework and in your design, you are going to spawn a thread for each of phases (e.g. map, reduce). And let’s also say you are working on this project with a partner, who is responsible for implementing the map part of the system. Leaving them a breadcrumb would be helpful:

    int worker_thread_do_map(uint32_t thread_id)
{
/* implement feature here and return valid error code */
    return -ENOTSUP;
}

int worker_thread_do_reduce(uint32_t thread_id)
{
    return -ENOTSUP;
}

    The take away

    The take away here is that we, as developers, should try and convey meaning and intent for the reader, the human sitting behind the computer. Cause we’re not just writing for our compiler and computer. We’re writing for our fellow craftsman.

  • 20s for education, 30s for experience, 40s for career.

    20s for education, 30s for experience, 40s for career.

    In my mid twenties, I was blessed to receive some of the best career, and quite frankly, life advice. During that period of my life, I was working as a director of technology, leading a small group of engineers. But I was getting ready to throw in the towel. I lacked both the experience and confidence needed. So I reached out to my friend Brian, asking him if he knew anyone who could help me with “executive coaching”. Thankfully, Brian connected me with a C level executive: let’s call him Phil (that’s actually his name).

    Prod, provoke, encourage

    When I met Phil at the Jerry’s Deli located in the valley, one of the first things he flat out told me was that executive coaching is bullshit. Despite that belief, he essentially coached me and gave me some sage advice that now I get to pass on.

    Seth Godin once stated that “About six times in my life, I have met somebody, who, in the moment, prodded me, provoked me, encouraged me, and something came out on the other side”.

    Phil is one of those 6 people in my life.

    The best career and life advice

    The sage advice is simple and sounds similar to Nic Haralambous’s advice “Plan in decades. Think in years. Work in months. Live in days”. But Phil’s advice offers a different perspective, another angle:

    20s for education. 30s for experience. 40s for career

    This advice stuck with me and helps me (re) calibrate my goals and values. Of course, life takes its own twists and turns. But as the Dwight Eisenhower said “Plans are worthless, but planning is everything”

    What does that look like in practice?

    20s for education is NOT synonymous with school. It really means soaking up as much as possible. This learning might take place in school but not exclusively. Because learning can happen anywhere and everywhere.

    Fail and fail a lot.

    For us tech folks, this might be learning a new programming language, dissecting the ins and outs of your compiler, picking up marketing or public speaking skills.

    The list goes on and on.

    30s for experience. This is where the rubber meets the road. Where theory and practice intersect. This may mean you want to switch roles (like how I switched from being a systems engineer to a software developer) or switch companies so that you can apply all that hard earned knowledge that you acquired in your twenties.

    Finally, 30s will feed into your 40s, where you get to establish your career. Maybe working for a small company, where you get to wear a bunch of hats. Maybe for a large corporation, where you hone in or specialize in a particular niche. Or maybe as an entrepreneur, building your own product or service.

    Now what?

    I’m actually revisiting these words of wisdom. Right now. For the last six months or so, I’ve been overly focused on an upcoming promotion from a mid to senior level engineer at Amazon. Instead of chasing this new title — cause that’s all it really is — I’d rather redirect my focus and make mistakes, stretch myself and find opportunities that put me in a uncomfortable (but growth inducing) experiences.

  • Three project management tips for software developers

    Three project management tips for software developers

    As a software developer, you will sooner or later lead a software development project. Of course it would be nice and ideal to relegate the responsibility of project management to a dedicated project manager — but not all of us are afforded that luxury. And let’s face it: many of us rather be heads down designing the software or writing the actual code. That being said, if you find yourself in a situation in which you need to manage a project, here are a few tips.

    Write down notes during every meeting and send them out

    During every meeting (related to the project), take down notes. Capture who said what, what did they promise, and when will they deliver that promise. I personally find this difficult because I don’t want to feel like I’m micromanaging or stepping on people’s toes. But really, we’re just communicating and the lack of communication a major contributor to failed project.

    Another reason why I think sending an e-mail once the meeting ends is that keeps others (and ourselves) accountable, partiallyu due to the Hawthorn Effect, which suggests that some people work harder and perform better when they are participants in an experiment (Source: verywellmind).

    Create a work plan and share your estimates with others

    I hate estimating my tasks. Because more often than not, my estimates are off — sometimes by a little, sometimes by a lot — due to hidden assumptions. That being said, there are ways to improve the accuracy of your estimates.

    As humans, we tend to be overly optimistic, assuming that everything will go according to plan. But I recommend a different approach. Be a pessimist. Assume everything will go wrong. Then, after playing devil’s advocate, find the middle (realistic) ground. And if want to take it even further, acknowledge your estimation biases and use formal techniques for mitigating those biases.

    Stop searching for the the perfect project management tool

    Although I wholeheartedly agree that having the right tool for the right job is important, I’ve reached the conclusion based off of my own personal experiences that when I’m constantly hunting for the perfect project management software (e.g. Microsoft Office Project, OmniPlanner) I’m really just procrastinating.

    So, start off simple. Just do a brain dump. Write every task down — lay it all out. Type all the tasks in Microsoft Word or Notepad if you have to. But get it out of your brain. Then, for each task, include the name of the task, a one to two sentence description, an estimate in days, the risks (i.e. low, medium, high), and the dependencies for that task. No need to go overboard and write down an entire novel. Again — strike a balance.

  • A letter from my future self: “Dear 2019 Matt”

    A letter from my future self: “Dear 2019 Matt”

    In 2019, Sal Khan wrote a letter to his past self as a reflection exercise and made that letter public and published it on his blog. Thanks Sal.

    Inspired by his post and this reflection exercise, I decided to write a letter from my future self (Matt in 2029). In other words, I wrote the letter from future Matt (2029) to present Matt (2019). Of course, I wrote this letter before the global pandemic, before my first daughter born. So much has changed since a year ago.  That being said, the exercise is super valuable and allows me to gauge whether I am walking the course that I had once charted.

    And I think you should also do the same reflection exercise. Set aside about an hour. Just lay it all out. Then, set the letter aside and revisit it six months from now, a year from now, five years from now. You’ll be surprised how accurate (and inaccurate) your predictions are.

    A letter to myself

    Dear 2019 Matt,

    You see that wife of yours? Go give her a big wet kiss on the lips. Then throw your arms around her, giving her a big bear hug. Hold it. Now tell her you love her — I’ll wait while you do it — because you really don’t tell her enough. Have no fear: she’s not going anywhere. And while you are at it, kiss Metric on the nose and pat Mushroom on the head. They’re both in doggy heaven now, smiling down on me, 2029 Future Matt.

    Moving on, here are some suggestions.

    First off, up your Vietnamese speaking skills (and your written skills while you are at it). Seriously. You are a Vietnamese American man. Vietnamese — the mother tongue of your two, refugee parents. Use the language to connect (and reconnect) with your loved ones, friends and family, especially your grandma. It’s important Matt — she’s no longer around. Don’t make the mistake of not being able to not only articulate and share your thoughts and feelings and your life story, but listen to her stories. How did she do it all — having kids at 19 and then fleeing Vietnam without a lick of English? Separately, don’t you want your children to speak the language as well?

    Next up, get involved with the community. I understand you are naturally introverted and insular. But you aren’t alone: join a community of like minded people. People who care about the things you care about. Cannot find that community? Make one. Like your wife tells you — you are a community builder. You have this ability to attract and bring people together, make them feel comfortable under their own skin (since that’s something you’ve worked so hard on: learning to accept yourself).

    Keep up the singing and guitar lessons. They’ve come in handy. No — future you is not a rock star and you are not touring across the globe. But you’ve breathed music into your children’s lives. They’re constantly yanking on your t-shirt, inviting you to sing and dance. And of course you do it because you not only love them to pieces but you want to teach them how to be comfortable under their own skin. That’s important to you because you know what it feels like not feel completely okay with who you are.

    Keep plugging away at that Computer Science Master’s program from Georgia Tech. It’s serving a couple purposes. On one hand, you are doing it because you are mastering your craft, learning the ins and outs of your discipline. On the other hand, you know there’s shadow side to why you are doing it: you can feel a bit insecure at times (even though you don’t let it show) since you are in the big leagues, working at Amazon and being surrounded smart folks with their fancy degrees. But once you finish up that program, use that lunch time to actually have lunch with folks instead of studying.

    Now, on the emotional side, keep walking that path of forgiveness. Remember that Oprah interview you watched, the interview with Wade and James, the two brave men speaking out about their sexual abuse from Michael Jackson? Remember what James Safechuck poignantly said: forgiveness is not a line you cross, but a path you take. With that quote in mind, learn not only how to forgive yourself for the things you’ve done and people you hurt but learn how to forgive others around you — like your father. Yes, he’s still around but he’s old now: 70. He doesn’t have that much time left on this earth. Basically, keep up with what you are doing: you no longer imagine what life could be if things were different. No. That’s not you anymore and future you is proud.

    One more thing: reintroduce meditation to your life. Cause 2029 is crazier than you’d expect, even more so than now. You think Trump being the president is ludicrous ? Can you guess who is the president in 2029?

    So far, I’ve been naming a bunch of things for you to do and for to think about. But also take it easy on yourself. Acknowledge how far you have come. You are piling so much on your plate: you are working full time as a software engineer at Amazon, playing husband 24 x 7, walking the dogs at 06:30 AM every morning (from your cozy 2 story Northgate house to Maple Leaf park) because the dogs deserve daily exercise to keep them healthy, taking singing lessons every Tuesday evening, mastering the fret board of your guitar, refining your writing skills.

    I know your mind constantly races. You want to be a good husband (you are). You want to be a good son (you are). You want to be a good brother (you are). You want to be a good father (you will be).

    2029 Matt is really proud of you

  • Interesting research papers on database transactions

    Interesting research papers on database transactions

    While reading Advanced Operating Systems research paper, I found myself following the citations, flipping to the last page and scribbling down the referenced papers because I want to learn more about database systems. In particular, I’m interested in learning more about building reliable software that withstand unexpected failures by using transactions, the techniques and methods. On a separate note, I really do think that Georgia Tech’s OMSCS program should offer a more advanced database course since the introduction to database system seems to only cover high level concepts such as SQL queries and writing web applications, two areas that I’ve already been exposed to in the past.

    Papers

    • Concurrent programming and building highly-concurrent transasctional objects: M. Herlihy and E. Koskinen. Transactional boosting: A methodology for highly-concurrent transactional objects. In PPoPP, 2008.
    • Creation of a transactional operating system called TxLinux: H. Ramadan, C. Rossbach, D. Porter, O. Hofmann,
      A. Bhandari, and E. Witchel. MetaTM/TxLinux: Transactional memory for an operating system. In ISCA,
      2007
    • One of the most cited books on database transactions (my guess is Gray is the father of database systems): J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
    • Introduces a new primitive called a transactional spinlock: C. Rossbach, O. Hofmann, D. Porter, H. Ramadan,
      A. Bhandari, and E. Witchel. TxLinux: Using and managing
      transactional memory in an operating system. In SOSP, 2007.
    • Concurrently writing to lists – M. Herlihy and E. Koskinen. Transactional boosting: A methodology for highly-concurrent transactional objects. In PPoPP, 2008.
    • Skip lists – W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33:668–676, 1990.
    • Two phased commit protocols – J. Gray. Notes on data base operating systems. In Operating Systems, An Advanced Course. Springer-Verlag, 1978.
  • Operating System Transactions – Summary and notes

    Operating System Transactions – Summary and notes

    This post is a cliff notes version I scrapped together after reading the paper Operating Systems Transactions. Although I strongly recommend you read the paper if you are interested in how the authors pulled inspiration from database systems to create a transactional operating system, this post should give you a good high overview if you are short on time and need a quick and shallow understanding.

    Abstract

    • System transactions enable application developers to update OS resources in an ACID (atomic, consistent, isolated, and durable) fashion.
    • TxOS is a variant of Linux that implements system transactions using new techniques, allowing fairness between system transactions and non-transaction activities

    Introduction

    • The difficulty lies in making updates to multiple files (or shared data structures) at the same time. One example of this is updating user accounts, which requires making changes to the following files: /etc/passwd, /etc/shadow, /etc/group
    • One way for ensuring that a file is atomically updates is by using a “rename” operation, this system call replacing the contents of a file.
    • But for more complex updates, we’ll need to use something like flock for handling mutual exclusion. These advisory locks are just that: advisory. Meaning, someone can bypass these control, like an administrator, and just update the file directly.
    • Although one approach to fix these concurrency problems is by adding more and more system calls. But instead of taking this approach of constantly identifying and eliminating race conditions, why not percolate the responsibility up to the end user, by allowing system transactions?
    • These system transactions is what the paper proposes and this technique allows developers to group their transaction using system calls: sys_xbegin() and sysx_xend().
    • This paper focuses on a new approach to OS implementation and demonstrates the utility of system transactions by creating multiple prototypes.

    Motivating Examples

    • Section covers two common application consistency problems: software upgrade and security
    • Both above examples and their race conditions can be solved by using ”’system transactions”’

    Software installation or upgrade

    • Upgrading software is common but difficult
    • There are other approaches, each with their own drawbacks
    • One example is using a checkpoint based system. With checpoints, system can rollback. However, files not under the control of the checkpoint cannot be restored.
    • To work around the shortcomings of checkpoint, system transactions can be used to atomically roll forward or rollback the entire installation.

    Eliminating races for security

    • Another type of attack is interleaving a symbolic link in between a user’s access and open system calls
    • By using transactions, the symbolic link is serialized (or ordered) either before or after and cannot see partial updates
    • The approach of adding transactions is more effective long term, instead of fixing race conditions as they pop up

    Overview

    • System transactions make it easy on the developer to implement
    • Remainder of section describes the API and semantics

    System Transactions

    • System transactions provide ACID (atomic, consistent, isolation, durability) semantics – but instead of at the database level, at the operating system level
    • Essentially, application programmer wraps their code in sys_xbegin() and sys_xend()

    System transaction semantics

    • Similar to database semantics, system transactions are serializable and recoverable
    • Transactions are atomic and can be rolled back to a previous state
    • Transactions are durable (i.e. once transaction results are committed, they survive system crashes)
    • Kernel enforces the following invariant: only a single writer at a time (per object)
    • If there are multiple writers, system will detect this condition and abort one of the writers
    • Kernel enforces serialization
    • Durability is an option

    Interaction of transactional and non-transactional threads

    • Serialization of transaction and non-transational updates is caclled strong isolation
    • Other implementations do not take a strong stance on the subject and are semantically murkey
    • By taking a strong stance, we can avoid unexpected behavior in the presence of non-transactional updates

    System transaction progress

    • OS guarantees system transactions do not livelock with other system transactions
    • If two transactions are in progress, OS will select one of the transactions to commit, while restarting the other transaction
    • OS can enforce policies to limit abuse of transactions, similar to how OS can control access to memory, disk space, kernel threads etc

    System transactions for system state

    • Key point: system transactions provide ACID semantics for system state but not for application state
    • When a system transaction aborts, OS will restore kernel data structures, but not touch or revert application state

    Communication Model

    • Application programmer is responsible for not adding code that will communicate outside of a transaction. For example, by adding a request to a non-transactional thread, the application may deadlock

    TxOS overview

    TXOS Design

    • System transactions guarantee strong isolation

    Interoperability and fairness

    • Whether or not a thread is a transactional or non transactional thread, it must check for conflicting annotation when accessing a kernel object
    • Often this check is done at the same time when a thread acquires a lock on the object
    • When there’s a conflict between a transaction and non-transactional thread, this is called asymmetric conflict. Instead of aborting the transaction, TxOS will suspend the non-transactional thread, promoting fairness between transactions and non-transactional threads.

    Managing transactional state

    • Historically, databases and transactional OS will update data in place and maintain an undo log: this is known as eager version management
    • ”Isn’t the undo log approach the approach the light recoverable virtual machine takes?”
    • In eager version management, systems hold lock until the commit is completed and is also known as two-phase locking
    • Deadlocking can happen and one typical strategy is to expose a timeout parameter to users
    • Too short of a timeout starves long transactions. Too long of a deadlock and can starve performance (this is a trade off, of course)
    • Unfortunately, eager version management can kill performance since the transaction must process its redo log and jeopardizes system’s overall performance
    • Therefore, TxOS uses lazy version management, operating on private copies of data structures
    • Main disadvantage of lazy versioning is the additional commit latency due to copying updates of the underlying data structures

    Integration with transactional memory

    • Again, system transactions protect system state: not application state
    • Users can integrate iwth user level transaction memory systems if they want to protect application state
    • System calls are forbidden during user transactions since allowing so would violate transactional semantics

    TxOS Kernel Implementation

    Versioning data

    • TxOS applies a technique that’s borrowed from software transactional memory systems
    • During a transaction, a private copy of the object is made: this is known as a the shadow object
    • The other object is known as “stable”
    • During the commit, shadow object replaces the stable
    • A naive approach would be to simply replace the stable pointer, since the object may be the target of pointers from several other objects
    • For efficient commit of lazy versioned data, need to break up data into header and data.
    • ”Really fascinating technique…”
    • Maintain a header and the header pointers to the object’s data. That means, other objects always access data via the header, the header never replaced by a transaction
    • Transactional code always has speculative object
    • The header splits data into different payloads, allowing the data to be accessed disjointly
    • OS garbage collects via read-copy update
    • Although read only data avoids cost of duplicating data, doing so complicates the programming model slightly
    • Ultimately, RCU is a technique that supports efficient, concurrent access to read-mostly data.

    Conflict detection and resolution

    • TxOS provides transactions for 150 of 303 system calls in Linux
    • Providing transactions for these subset system calls requires an additional 3,300 lines of code – just for transaction management alone
    • A conflict occurs when transaction is about to write to an object but that object has been written by another transaction
    • Header information is used to determine the reader count (necessary for garbage collection)
    • A non-null writer pointer indicates an active transactional writer. Similarly, an empty reader lists means there are no readers
    • All conflicts are arbitrated by the contention manager
    • During a conflict, the contention manager arbitrates by using an osprio policy: the process with the higher scheduling process wins. But if both processes have the same priority, then the older one wins: this policy is known as timestamp.

    Asymmetric conflicts

    • non-transactional threads cannot be rolled back, although transactional threads can always be rolled back. That being said, there must be mechanism to resolve the conflict in favor of the transactional thread otherwise that policy always favor the non-transactional thread
    • non-transactional threads cannot be rolled back but they can be preemted, a recent feature of Linux

    Minimizing conflicts on lists

    • Kernel relies heavily on linked lists data structures

    Managing transaction state

    • TxOS adds transaction objects to the kernel
    • Inside of transaction struct, the status (probably an alias to uint8_t) is updated atomically with a compare and swap operation
    • If transaction system call cannot complete because of conflict, it must abort
    • Roll back is possible by saving register state on the stack at the beginning of the system call, in the “checkpointed_registers” field
    • During abort, restore register state and call longjmp
    • Certain operations must not be done until commit; these operations are stored in deferred_ops. Similarly, some operations must be done during abort, and these operations are stored in undo_ops field.
    • Workset_list is a skip list that contains references to all objects in the transaction and the transaction’s private copies

    Commit protocol

    • When sys_xend (i.e. transaction ends), transaction acquires lock for all items in (above mentioned) workset.
    • Once all locks are acquired, transaction performs one final check in its status word and verifies that the status has been set to abort.

    Abort protocol

    • Abort must happen when transaction detects that it lost a conflict
    • Transaction must decrement the reference count and free the shadow objects

    User level transactions

    • Can only support user-level transactions by coordinating commit of application state with system transaction’s commit

    Lock-based STM requirements

    • Used a simplified variant of two-phase commit protocol
    • Essentially, user uses sys_xend() system call and must inspect the return code so that the user application can then decide what to do based off of the system call’s transaction

    TxOS Kernel Subsystems

    • Remainder will discuss ACID semantics
    • Example will include ext3 file system

    Transactional file system

    • Managed versioned data in the virtual filesystem layer
    • File system only needs to provide atomic updates to stable storage (i.e. via a journal)
    • By guaranteeing writes are done in a single journal transaction, ext3 is now transactional

    Multi-process transactions

    • Forked children execute until sys_xend() or the process exits

    Signal delivery

    • Application can decide whether to defer a signal until a later point
    • If deferred, signals are placed into queue

    Future work

    • TxOS does not provide transactional semantics for all OS resources
    • If attempting to use transaction on unsupported resource, transaction will be aborted