About 22 or 23 years ago my mentor at the time, a unix guru, beat more or less that same list into my thick skull with a heavy schtick. It was considered part of "basic competency" for unix. The list, back then, came with a list of bitter exceptions (e.g., vendor X had broken "rename(2)" and it was not reliably atomic on those systems).
Why was it important? The notion was that with a unix file system, and "tiny tools" connected by pipes, you really didn't need an SQL-based relational database for most tasks. You had shell programs like "cut(1)", "join(1)", "sort(1)", "grep(1)", and "sed(1)". In a pinch, you could reach for "awk(1)" but don't overdo it because the joke went "Some people, whenever they have a problem to solve, reach for AWK. Then they have two problems."
A serious relational database would give you transactions and isolation - the ACID properties. (Obtaining "durability" (the D in ACID) meant learning when and how to flush and sync the file system.) Back then, on some historic versions of unix, you could also count on it to be atomic if you appended a text file with a modest length, single line, in a single "write(2)". But even back then, that trick wasn't portable - just sorely missed from the good 'ol days.
Around about 2001 I set out to implement the GNU Arch revision control system. I was steamed at how Subversion was large, complicated, hard to get working, and used a centralized server rather than a distributed and decentralized system. I thought "I can do better than that, easily!" So I set out to prove it.
I wrote the initial self-hosting release of Arch as... wait for it ... shell scripts. Initially, there wasn't a single line of original C code in the system. It was all coded in /bin/sh, /bin/awk, /bin/find, with heavy use of sed, grep, cut, join, and sort. It was sluggish but usable and, was indeed, one of the very first truly distributed and decentralized revision control systems. It also delivered on the "smart merging" algorithms that Subversion had promised but that, to this day, has not succeeded in implementing.
One of the challenges of a revision control system is the critical importance of database integrity. When you check your code in, when you make back-ups, etc -- and when multiple users may be doing the same thing at the same time on the same repository -- it's absolutely critical to keep the database consistent. You need ACID updates to the database.
So, here is a fun puzzle: Using just the atomic unix file system operations, you have to implement (as a shell script), a "write once" list-of-directories structure. I'll illustrate what I mean:
We have a directory called "the-list". Initially, it may contain arbitrary "control files/directories" that you design, but it is empty of "data directories". The data directories we add will be named as numbers. So the first one is "the-list/0", then "the-list/1", then "the-list/2" and so forth.
When a directory like "the-list/1" is installed, it should already contain data files. E.g., "the-list/1/patches.tar.gz". You aren't allowed to just "mkdir the-list/1" and then, after that, install "patches.tar.gz". If "the-list/1" is there at all, it must already contain "patches.tar.gz".
The data directories must be created in order. If two users both try to create "the-list/1" at the same time, one should succeed, and the other be forced to retry, perhaps creating "the-list/2" instead (after "the-list/1" already exists).
Finally, a program that starts to create "the-list/1" but then crashes must not harm the database. It is OK if a user has to type a command like "cleanup-after-crash" but it must be possible to write such a command (as a shell script). It is important that if someone types "cleanup-after-crash" while the program trying to create "the-list/1" is still running, that either the "cleanup" program does nothing, or the programing making "the-list/1" is forced to fail (and know that it failed, and report that to the user).
It sounds like something that should be trivially easy, right? Well, it doesn't take a huge amount of code to solve but solutions to the problem are not obvious. And many obvious attempts to solve the problem have subtle bugs that lose the ACID properties of the database.
GNU Arch source code (and perhaps the documentation, I forget) contains an answer key. It might be more fun, though, if you've nothing better to do, to try to solve it yourself, first.
Something to keep in mind if you are inclined to try solving the puzzle is that solutions ought to work on NFS file systems. Why does that matter?
Well, consider a system call like rename(2) or mkdir(2). Suppose that on a local file system, two programs both try to rename "a" to "b" at roughly the same time. At most one will succeed.
Not so, on NFS! An NFS implementation is permitted to behave this way: (1) Client x issues the rename request; (2) Client y issues the same rename request; (3) The server reports "success" to x; (4) The server reports "fail" to y, but the server's report packets get lost so y doesn't get the message. (5) Client y asks the server "Hey, whatever happened to my rename request?"; (6) Server notices that "a" doesn't exist but "b" does and replies "Success". Then both x and y think that they renamed "a" to "b".
The rename itself took place atomically. It's just unclear to each client which client actually triggered the rename. Similarly for other operations.
In other words, return values from file system calls don't reliably tell you when your process was able to perform some atomic action.
About 22 or 23 years ago my mentor at the time, a unix guru, beat more or less that same list into my thick skull with a heavy schtick. It was considered part of "basic competency" for unix. The list, back then, came with a list of bitter exceptions (e.g., vendor X had broken "rename(2)" and it was not reliably atomic on those systems).
Why was it important? The notion was that with a unix file system, and "tiny tools" connected by pipes, you really didn't need an SQL-based relational database for most tasks. You had shell programs like "cut(1)", "join(1)", "sort(1)", "grep(1)", and "sed(1)". In a pinch, you could reach for "awk(1)" but don't overdo it because the joke went "Some people, whenever they have a problem to solve, reach for AWK. Then they have two problems."
A serious relational database would give you transactions and isolation - the ACID properties. (Obtaining "durability" (the D in ACID) meant learning when and how to flush and sync the file system.) Back then, on some historic versions of unix, you could also count on it to be atomic if you appended a text file with a modest length, single line, in a single "write(2)". But even back then, that trick wasn't portable - just sorely missed from the good 'ol days.
Around about 2001 I set out to implement the GNU Arch revision control system. I was steamed at how Subversion was large, complicated, hard to get working, and used a centralized server rather than a distributed and decentralized system. I thought "I can do better than that, easily!" So I set out to prove it.
I wrote the initial self-hosting release of Arch as... wait for it ... shell scripts. Initially, there wasn't a single line of original C code in the system. It was all coded in /bin/sh, /bin/awk, /bin/find, with heavy use of sed, grep, cut, join, and sort. It was sluggish but usable and, was indeed, one of the very first truly distributed and decentralized revision control systems. It also delivered on the "smart merging" algorithms that Subversion had promised but that, to this day, has not succeeded in implementing.
One of the challenges of a revision control system is the critical importance of database integrity. When you check your code in, when you make back-ups, etc -- and when multiple users may be doing the same thing at the same time on the same repository -- it's absolutely critical to keep the database consistent. You need ACID updates to the database.
So, here is a fun puzzle: Using just the atomic unix file system operations, you have to implement (as a shell script), a "write once" list-of-directories structure. I'll illustrate what I mean:
We have a directory called "the-list". Initially, it may contain arbitrary "control files/directories" that you design, but it is empty of "data directories". The data directories we add will be named as numbers. So the first one is "the-list/0", then "the-list/1", then "the-list/2" and so forth.
When a directory like "the-list/1" is installed, it should already contain data files. E.g., "the-list/1/patches.tar.gz". You aren't allowed to just "mkdir the-list/1" and then, after that, install "patches.tar.gz". If "the-list/1" is there at all, it must already contain "patches.tar.gz".
The data directories must be created in order. If two users both try to create "the-list/1" at the same time, one should succeed, and the other be forced to retry, perhaps creating "the-list/2" instead (after "the-list/1" already exists).
Finally, a program that starts to create "the-list/1" but then crashes must not harm the database. It is OK if a user has to type a command like "cleanup-after-crash" but it must be possible to write such a command (as a shell script). It is important that if someone types "cleanup-after-crash" while the program trying to create "the-list/1" is still running, that either the "cleanup" program does nothing, or the programing making "the-list/1" is forced to fail (and know that it failed, and report that to the user).
It sounds like something that should be trivially easy, right? Well, it doesn't take a huge amount of code to solve but solutions to the problem are not obvious. And many obvious attempts to solve the problem have subtle bugs that lose the ACID properties of the database.
GNU Arch source code (and perhaps the documentation, I forget) contains an answer key. It might be more fun, though, if you've nothing better to do, to try to solve it yourself, first.