8 ms·
Things Unix can do atomically (2010)
- atrust 10y agoIn a few simple words, can someone explain what does "atomically" mean? I personally used this term when talking about some Redis operations, but never knew the real gist of the word and concepts behind it. I have a very brief understanding of the term and if I'd have to explain it to a person, I'd say it's "the operation that does not have any side effects when performing its unit of work". Is my understanding even close to what atomic operation really is?
- sp332 10y agoNot really. It just means that it's indivisible (the original meaning of "atom"). Either it succeeds or fails, you never have to worry about it being half-finished. This includes actions which are so small they are literally indivisible, or actions which roll back to the original state if they fail.
- LukeShu 10y agoNot just about it only completing or failing, but another observer in the system should never be able to find it in the half-way state. To everyone but the implementer of the atomic operation, it has no half-way states.
- lomnakkus 10y agoIn the database terminology that's usually called "Isolation" to keep the concept separate from the rather restricted definition of atomicity.
- atrust 10y agoGot it. Now it makes more sense to me. Now I know people tend to talk about atomicity when it comes to low-level-ish things. But say I create some sort of a web service with a bunch of business logic. Does it worth to follow this principle in that case? For instance, client sends an API request (let's say "Add user to friends"), is it even possible to apply atomicity for these type of things? Edit: Thanks everyone for taking time to explain it to me.
- trungaczne 10y agoThe business logic of your web application should resolve around database calls. Popular databases should already guarantee these atomicity properties for you through transactions.
- toast0 10y agoDatabase guarantees are great until your data doesn't fit in a single database; it's good to examine what your database is providing for you, and to contemplate the costs for providing it in the database level.
- gnaritas 10y ago> The business logic of your web application should resolve around database calls Might, not should. All web apps are not just front ends to a single database where transactions are useful and once you leave the realm of a single database into a more distributed type system then transactions are no longer an option.
- deleted 10y ago[deleted]
- toast0 10y agoYes, depending on how you store the relationships, its possible that when a adds b to its list of friends, a could be added to b's list of 'friendofs'. If they're stored separately, the edit may not be atomic. If it's stored in a single place (queryable from either direction), it's generally going to be atomic, unless you're doing something way outside the norm.
- stormbrew 10y agoYes. To take a larger example action, creating a user could fail to be atomic if, say, it stored the username in a separate table from the user object, wrote the username first, then referenced it from the user object, but didn't roll back the username insert if the user object insert failed. Likewise, for the seemingly simpler example if establishing a friend relationship, you may be tracking that relationship in both directions, in which case one could fail and the other succeed.
- LukeShu 10y agoIt means that the operation can't be divided any smaller--that it is impossible to catch it only part-way completed; it either hasn't happened yet, or has completely happened.
- GauntletWizard 10y agoAtomic means "Does precisely what is is asked to do, or does nothing". This is the core of synchronization primitives, preventing two tasks from doing the same work or trying to access the same resource at once. open(O_CREAT| O_EXCL) for example, open a new file for you, or report an error. Regardless of who else is attempting operations at that moment, at most one of those calls will succeed (they can all fail, for a number of reasons). This allows you to, say, create a lockfile (often named filename.lock or .filename.lock) that serializes access to a shared resource, like a simple database or a printer control port or network connection. This is core to multithreaded programming (At least, imperative multithreaded programming; Functional languages tend to abstract this away by having little-or-no shared state)
- woodman 10y agoAs the others have said, indivisible operations. This is important in the context of race conditions, imagine two threads incrementing a counter with no locks. Using non-atomic ops to read, increment and then store the number will lead to a bad time. Or more on topic, checking if a file exists and then trying to open it - lots of bad things can happen.
- asveikau 10y agoIf something alters an object such that it goes from state A to state B, it might need to do some work along the way (call it "state C"). Atomicity means that if the operation is interrupted or observed while it's going on, the existence of a "state C" never leaks out. It's always in either state A or B; any third state that might exist along the way is never visible. (Hence what people often say: the operation is either completed or didn't happen at all.) Renaming a file is a good example. Within the internal structure of the filesystem, you have a directory entry in an old location. That must be removed. You may have another file with the same name in the destination directory. That file must be overwritten. Internally, these things happen by a multi-step process, eg: remove entry for old name, remove pre-existing entry for new name, create new entry for new name. But the system creates the appearance of just 1 step. You don't get file not found while it's overwriting the destination file. You don't ever see the file having both old and new names at the same time.
- jonaf 10y agoedit: I just realized you said "renaming." Original comment left below, but I edited before I get downvoted for a classic reading comprehension fail. Atomicity requires that the leakage mentioned shall not occur from any context aside from its own internal context. That makes your example somewhat of a simplification because these state transitions are visible to other processes. It is a common mistake to try to use files for locking, for example, instead of using the more robust flock(1).
- asveikau 10y agoNonetheless the reply prompted me to look into the rename case specifically. Apparently on Linux, the replacement of the destination file is atomic (as many of us already knew and take for granted), but there's no guarantee that you won't see both old and new names in flight for a brief moment in time (like the last sentence of my comment). Would not be surprised if all bets are off once you get an NFS mount involved. As always it's a tradeoff between useful behaviors and the cost of synchronizing.
- geofft 10y ago
- deleted 10y ago[deleted]
- agumonkey 10y agoReminds me of graphics double buffering. Back in the days games would write directly in the video buffer, while the graphic chip would scan that same buffer and push the content on screen at the same time. If your code is too slow (a complex effect, too many character at that point), you might not be done writing a full frame when the graphic chips starts to output the pixels. This means your TV is now showing partly old and new state. Nothing important most of the time, it's only games, it's only a few ms of absurd information, people's brain can compensate. It is ugly to see though. You have that weird 'line' somewhere below. Since people changed the structure a bit, with two (or more) buffers, the program computes the new image in one buffer B, while the chip shows another buffer A. When you are done with a picture, the chip will now scan B, while you can write in A. This means the output never shows partial frame anymore.
- tlrobinson 10y agoIt's more about multiple operations taking effect "instantaneously" from the perspective of some observer, and sometimes it also implies that either all or none of the operations take effect, but never just some of the operations.
- syngrog66 10y agoI googled for "atomic operation" and this was top result: https://en.wikipedia.org/wiki/Linearizability https://en.wikipedia.org/wiki/Linearizability
- _pmf_ 10y ago> I'd say it's "the operation that does not have any side effects when performing its unit of work". Is my understanding even close to what atomic operation really is? No. It can has as many side effects as it wants. Atomicity means: when going from state 1 to state 2, no matter how complex the transition, there are no externally observable intermediate states.
- pif 10y agoTranslating in English from Italian Wikipedia: From ancient Greek ἄτομος - àtomos - [indivisible], made of ἄ - a - [Privative alpha] + τέμνειν - témnein - [cut]. Personally, I struggled long time before fully understanding its use in IT, because I learned programming after sub-nuclear physics, thus I had a hard time conciliating the huge atom (a million of billions of times bigger than a nucleus) with the concept of "cannot be split" :-)
- simula67 10y agoIt is helpful to understand what problem it solves. Lets say that we have a banking application that consists of a program which updates someones bank account by $Y every time it is called. Y is the command line parameter. The program's algorithm is like this : 1. Read the current balance amount to X 2. Add Y to X and store it in Z 3. Write Z to the database. This program cannot be called by multiple processes at the same time. Lets say that it is payday, the account holder holds two jobs and each employer is trying to deposit $10 into someone's account, at the same time. Both these processes call the program with Y = $10. What happens ? 1. Process 1 reads the current balance ( $100 ) to X 2. Now, process 2 reads the current balance ( $100 ) to X 3. Process 1 adds 10 to X ( Z = 110 ) 4. Process 2 adds 10 to X ( Z = 110 ) 5. Process 1 writes the updated value to the database ( Z = 110 ) 6. Process 2 writes the updated value to the database ( Z = 110 ) Now the account reflects a balance of $110, when it should have reflected $120. What we need is a guarantee from the system that some actions will not be parallelized ( i.e, they will be atomic ). From TFA it is given that "mkdir" is an atomic operation in UNIX ( i.e, only one process can create a directory at the same time ). You can write the program with the following logic 1. mkdir /tmp/lock_dir 2. If above step was unsuccessful sleep 10 seconds and go back to step 1 3. Read current account balance to X 4. Add Y to X and store it in Z 5. Write Z to database 6. Remove /tmp/lock_dir Multiple processes can invoke this program simultaneously.
- estrabd 10y agoWhy one would like to have an atomic operation is easier to understand. For example, one can use the atomic nature of creating a symbolic link on nix to create a lock file to prevent a race condition in a forking shell script. Say you have two or more processes wanting to do something that can (or should) only be done by one process at a time; one naive solution is to manage access of each process to said action by using a lock file. However, writing or touching a file itself is not atomic. The answer is to throw a symbolic link into the mix. In this scenario, the lock file already exists. However, the lock is not the file itself, but a symbolic link to the file. The protocol for each process to follow is: 1. try to create a symbolic link to lock file (any file really) 2. if successful, proceed; if failed, wait (or exit) 3. when process is done, delete symbolic link to lock file Simply checking for the existence of the symlink is not sufficient since there is a period of time between checking for the symlink (or file) and proceeding with said action where another process can think it has the lock. The OS ensures that one and only one symlink (of the same name) can exist; attempts to create it again (even simultaneously) will result in a failure of one process to create the symlink. There is one winner; all others are losers. This is to say, the kernel ensures that the operation is atomic. As a result, the OS is now arbitrating what process can proceed to action, at the very lowest level. Another way to think about it is that it provides a way to make competing processes serialize - or get in line so that they may complete their action one at a time. In my experience, it is important to experiment and test to make sure that the atomic primitive you're using is actually working as expected. I've run up against some inconsistent implementations of symlink creation that make this action not as straightforward to use as one is lead to believe.
- dmm 10y agorename(2) was not atomic on OS X for years. It was finally fixed in Lion: http://www.weirdnet.nl/apple/rename.html http://www.weirdnet.nl/apple/rename.html
- LukeShu 10y agoIt should also be said that `mv`(1) is only atomic if the source and destination are on the same filesystem.
- mancerayder 10y agoSo that implies that realistically there's a scenario where moving files or directories from one filesystem to another and some interruption occurs can lead to lost data?
- Dylan16807 10y agoIt's easy to design an algorithm that either succeeds with a move or fails with a copy, never losing data, but someone would have to look deeper into what was actually guaranteed and/or implemented.
- deleted 10y ago[deleted]
- Sanddancer 10y agoVery implausible. Mv across filesystems is usually implemented as a copy then delete. Worst case, you'll have the data exist in both locations.
- nshepperd 10y agoIt's possible, in case of physical disconnection or power interruption. There is no guarantee that the copied data will be flushed out of buffers into nonvolatile storage before the delete is (unless the program asks for such a flush and the system honors it).
- throwaway76543 10y agomsync() with MS_INVALIDATE doesn't belong on this list. It has nothing to do with atomic memory access. msync() is used when flushing a mapped file to durable storage. I very often see this mistake of conflating flushing caches with atomic access of memory. What's committed to durable storage has nothing to do with what multiple processes will see when mapping a file. All that's needed is the initial mmap to share a memory segment, then to use atomic operations like CMPXCHG -- the x86 building block the later mentioned gcc atomic macros leverage.
- prodigal_erik 10y agoI haven't tested but I would expect MS_INVALIDATE on a large buffer to be much faster than filling it a word at a time with __sync_val_compare_and_swap (each causing its own bus transaction).
- throwaway76543 10y agomsync() doesn't fill buffers at all. It has no function in the operation you've described. Even if it did, it's not atomic ...
- gpderetta 10y agoMS_INVALIDATE is likely a no-op on any modernish Unix, including Linux. It is there to accommodate old systems with non-coherent mapped files and page caches or even multiple mappings of the same file.
- gpderetta 10y agoRight. Msync is an ordering barrier. Barriers go hand in hand with atomic operations, but they are really about visibility, not atomicity.
- zAy0LfpBZLC8mAC 10y agoIt should be noted that those filesystem operations are only atomic with respect to an observer running on the same operating system incarnation. Whether they are also atomic across power loss depends on the filesystem (though with a modern journaling filesystem, that generally should be the case).
- gpderetta 10y agoThat's what people would expect. But there was some drama around ext4, renames and fsync a few years ago.
- zAy0LfpBZLC8mAC 10y agoYou mean around truncation and rewrite?
- gpderetta 10y agoIt is not necessarily about truncation. IIRC the problem was that rename doesn't (didn't?) act as a full barrier on ext4 and the metadata write that updates the name from the old file to the new file can be committed to disk before the updates to the new file. This means that after a crash the new name might point to a corrupted file. The barrier behavior wasn't explicitly mandated by POSIX, but it is an intuitive release consistency-like model which was implicitly expected by most programmers. edit: spurious words and parens.
- ridiculous_fish 10y agoHere's one that's not super well-known: writes to a pipe are atomic as long as the write size is <= PIPE_BUF, which is at least 512 bytes (on Linux it's a full 4k). So pipes can be used as a naïve message queue: ensure each message is under the limit in size, and they will not be split. Anyone know if there's a similar guarantee for files?
- colmmacc 10y agoThey won't be split, bit one thing to watch out for is that they can be coalesced.
- brobinson 10y agoI read a while back that this PIPE_BUF restriction also applies to multiple writers appending a file.
- deleted 10y ago[deleted]
- adrianratnapala 10y agoI think Linux goes out of its ways to make writes <= 512 bytes atomic. Helpful for writing log files. But I don't think this is a true guarantee in any standardised sense.
- bluetomcat 10y agoThe PIPE_BUF POSIX requirement is about guaranteeing that when multiple processes write less than PIPE_BUF to the same pipe, the reader will not see its input intermingled from different processes. It is often wrongly interpreted as "a single write() of less than PIPE_BUF will be retrieved via a single read() on the other side".
- the8472 10y agoOpening with O_APPEND you get atomic appends if they're <= PIPE_BUF. And the list already mentions atomic memory operations. Those also apply to memory-mapped files.
- netdog 10y agoThe GCC Atomic Builtins mentioned in the article are not specific to Unix. They are compiler constructs, and depend on specific architecture hardware support. All x86 CPUs have such support for some years now. So these atomic operations can also be used in non-Unix software running on x86 CPUs. The GCC documentation lists other non-intel architectures which also have the features required to support the atomic built-ins.
- comex 10y agoAlso, if you can depend on recent compilers you should probably be using the standard C <stdatomic.h> or C++ <atomic> instead.
- kevin_nisbet 10y agoAh the good ol day's, this reminded me of some file transfer problems we used to get. We had multiple systems that generated usage records, and stored them to flat file (think stuff that would end up on a bill). Because FTP the file was a thing, some other system would come in any copy the file, but every once in awhile there would be a partial file copied that would be missing records. Yep, it was the good ol process was still writing to the file when the collector decided to pick it up. The first system I had control over, I made sure the vendor wrote to a temporary directory, and then hard linked to the transfer directory when the file operation was complete, knowing it avoided the race condition. I'm pretty sure I had one of the few platforms that handled this correctly, from what I remember we had corrupt files from almost all the platforms we bought. Anyways, just because the system cost a million dollars doesn't mean it's any good.
- rwmj 10y agoI always thought it would be a good idea for system calls to support transactions. Probably in a limited way because implementing general transactions would require massive changes to the kernel. But it would be nice to be able to do [error checking omitted]: begin (); fp = fopen ("file", "w"); fputs (content, fp); fclose (fp); commit (); It could solve the whole thing with ending up with zero-length files because you didn't use the right incantation to update a file atomically on ext4 (https://thunk.org/tytso/blog/2009/03/12/delayed-allocation-and-the-zero-length-file-problem/ https://thunk.org/tytso/blog/2009/03/12/delayed-allocation-a...). In Unix v7 mkdir was not a system call. It was a setuid program implemented using mknod + link. That was racy so the mkdir(2) system call was added. But it could have been solved more generally (and more elegantly) by adding transactions.
- tobias3 10y agoWindows has it, but not many people seem to use it: https://msdn.microsoft.com/en-us/library/windows/desktop/aa363764%28v=vs.85%29.aspx https://msdn.microsoft.com/en-us/library/windows/desktop/aa3...
- krylon 10y agoBeware, it appears to be deprecated: "Microsoft strongly recommends developers utilize alternative means to achieve your application’s needs. Many scenarios that TxF was developed for can be achieved through simpler and more readily available techniques. Furthermore, TxF may not be available in future versions of Microsoft Windows."
- SolarNet 10y agoWindows has this.
- estrabd 10y agoAlways a nice reminder.
- DonaldFisk 10y agoAll system calls in ITS behaved as if they were atomic, using a mechanism called PCLSRing: http://fare.tunes.org/tmp/emergent/pclsr.htm http://fare.tunes.org/tmp/emergent/pclsr.htm Other systems which took a similar approach were WAITS, the Fluke Kernel, and EROS and its successors.