CS162 Lecture 22: Transactions (Con't), End-to-End Arguments, Distributed Decision Making

welcome back everybody uh to um cs162 we're going to continue our discussion of ways of uh getting reliability out of file systems and then we're going to dive into some interesting material on distributed decision-making um if you remember last time we were talking about one of the ways that we get performance out of a file system and that's with a buffer cache and the buffer cache of course is the um chunk of memory that's been set aside to hold various items including dis blocks and the example that I've shown here was basically that uh when we talk about a file system and we have uh directory data blocks and iodes and data blocks Etc they're actually put into the buffer cache which is typically handled lru and uh is the temporary Waypoint for data moving in and off the dis and this is of course the starting point for allowing us to read and write single bytes of data at a time but it also is an important uh performance enhancer and we and we talked among other things about um keeping dirty data in the buffer cache and not pushing it out to disc right away and that that had some pretty important uh performance benefits it also has some potential issues with reliability If You Should Crash and the dirty data is still only on in memory and not on dis so um the other thing uh that we started talking about then in that along those lines was what I like to call the ilities and so that's availability durability and reliability uh and keep in mind that availability is kind of the minimum um bar to meet and it's not a very good one oftentimes so availability is typically the fact that you can actually talk to the system and it will respond to you it doesn't say that it'll respond correctly and um the other thing that's often the case is uh we'll talk about number of nines of availability so three nines typically means that there's a 99.9% probability that the system will uh respond to you more important than availability in my opinion at least is durability and reliability durability says that the system can recover data despite the fact that things are failing and uh reliability is the ability of the system to essentially uh perform things correctly and that's really what you want is you want reliability not availability okay all right and and by the way the example I like to give about the difference between durability and availability for instance is that uh if you think about the Egyptian pyramids there was a time when people didn't know what the various hieroglyphs meant that those uh what was written on the pyramids was extremely durable but it wasn't available because people couldn't uh decipher it okay and it became available only after the Rosetta Stone was discovered so the other thing uh we talked about last time is we started talking about ways to protect bits not necessarily ways to protect the Integrity of the operating system and file system so to speak but Integrity of the bits and we talked about raid which you know from 61c and in general raid uh X you know whatever your level is is a type of eraser code which is uh a code in which you know certain discs are gone and you fill in the missing discs using the code okay that's called an eraser code and the reason you're able to do that is essentially because the diss uh have error correction codes on them that let them recognize when the discs themselves are bad and then you treat the whole disc as an eraser and you bring in the raid codes and what I did say was that today discs are so big that raid five which is what you learned about in 61c for instance is really not sufficient because uh it can only recover from one failed disc and uh discs are so big now that while you uh are busy recovering that disc by putting a new one in uh it might fail again and at that point you just lose all your data so if you ever have a big file system on a big file server make sure you pick at least raid six which is a possibility of two failed discs and um for instance even odd is a is a code that works for two diss uh there that's available on the readings in general you can do something that um called a a general read Solomon code like um this based on pols and if you remember um as I I mentioned this last time but I thought I'd put this out there uh when you were learning about polinomial back in grade school what you learned was that if you have a an Min minus one degree polinomial here uh as long as you have M Points then you can reconstruct the coefficients okay and so the the clever trick uh with readed Solomon codes is you start with something that behaves like real numbers called a gallawa field we can talk about that offline if you like and then you put your data at the coefficients and then you just generate a bunch of points and here's an example where I generate n points where n is bigger than M and as long as I get M of them back then I can recover the polinomial and then I can get back my data and so that's an eraser code because I can erase any number of these uh points here as long as I still have M left so I can erase up to n minus M of them and still get my data back and that's a pretty powerful code and you can choose how many uh you need to recover from how many failures okay and so oftentimes in Geographic replication you can arrange to be able to lose uh you know 12 out of 16 chunks of data and that's extremely efficient good so um I'm glad that cs170 also talked about this in in general um the uh other thing we talked about last time by the way was there were there any questions on on eraser codes at all so um well you know that raid five is a simple as uh xoring um even odd is is a slightly different type of xoring so that's those are all very fast operations the readed Solomon um codes come in a bunch of different forms some of which are fast and some of which aren and so um there's a bunch of different types of read Solomons which are all isomorphic to this idea but they're rearranged in a way where it's really fast to encode um in some instances and then it's it's pretty fast but um typically the decoding phase is an N squared uh complexity so decoding can be uh when you failed it can be expensive um so the other thing I talked about uh was well we we' were looking at file systems like the fast file system and NTFS which are overwritten when you write new data so when you put new data into a file you overwrite the blocks that had the old data in it an alternative uh which you might imagine is a lot more um reliable as copy on write file system so here's an example of a file system where um I'm just showing you a bi a binary tree think of these as the uh the pieces of the iodes and the old version of the file sort of the blocks are down here in blue and they're in this tree and the idea behind a copy on write system is that if I want to say write some new data at the end or overwrite something I don't actually overwrite the original data but I build a whole new version of the file that uses as much as the old one as possible so here was an example where I took this old block here I added some new data to it and I made a new block with a copy and now by time uh my new iodes in with the old ones I have uh by following the new version you can see that we've got a new version of the file with this is updated but the old version's still there and so if I have a really bad crash in the middle of writing the new version I can still recover the old version and I can pull various tricks to decide how much of the old version to keep around or how many old versions to keep around and um this is much more resilient to random failures okay and and there's uh file systems that are like that now it would be um potentially the question here is this more expensive in space or time it's certainly is uh more expensive in space if you want to think of it that way but what you're getting back is um extreme resilience to crashes and failures and the ability if you decide that this uh that you wrote something incorrectly you can go back to a previous version so this has some pretty nice benefits you get from the space overhead because you notice that we're um we're not deleting old data right away um and it's can be a little bit more expensive in time if uh you have to worry about how these things are laid out maybe it doesn't have as fast of a read performance as something like the fast file system might be so um what about more General reliability Solutions well if we wanted to go back to the fast file system let's say because we were worried about performance and we wanted to make sure that the file system and the operating system couldn't crash in a way that leaves things uh vulnerable then what might we do and one of the things we talked about was very carefully picking the order you write the blocks and then you write the iodes and then you put the iodes in a directory and so on and you do this in an order such that if it fails at any point you can kind of throw out the things that weren't quite finally committed and um go through a pass on the file system and find everything that's disconnected and you're good to go the problem is that requires very careful thought so more general idea here is to use a transaction which youve probably heard about if you've taken any of the database classes but the idea here is that when you go to update a file you're going to use transactions to provide automic updates to the file system such that there's a single commit point in which the new data is uh or the new version of the file system is ready to go and until you reach that commit Point any of the things that you do to the file system can be undone now if you think back to this copy on wrs uh example as I'm writing everything here and producing my new version the old version is fine so if anything gets uh screwed up including just throwing out the new version uh the old version's still there and if the only thing I need is to swap the old version for the new version which with a single operation that's a single point of commit for the new file system okay and so that's kind of like a transaction um the transactional ideas are a little bit more General okay and so we're going to use transactions to give us clean commits to the uh Integrity of the file system and then of course we're going to use redundancy to protect the bits so the bits can be protected with uh read Solomon codes and eraser other error correcting codes raids Etc okay now just to remind you a little bit about what we mean about transactions it's closely related to critical sections uh that we talked about earlier in the term they extend the concept of atomic updates from memory which is where they came up originally in ear part of the term to stable storage and we're going to automically update multiple persistent data structures with a single transaction and as a result we'll never get in a situation where the file system is partially updated and therefore corrupted so there's lots of ad hoc approaches to this transactional like thing I just talked to you through the copy on right the fast file system uh they originally would order sequences and updates in a way so that if you crashed you could do uh a process that scanned the whole file system called fsck to recover from that those errors um but again that's very ad hoc so this idea of a general transaction is like this you start with consistent state number one in the file system and you want to get to consistent state number two maybe consistent state number one uh is the original file system and number two is what you get when you add some new files and directories and data and the transaction is a atomic way to get from the first state to the second one and we know underlying the uh those that single Atomic view change here there's going to be a whole bunch of underlying um a whole bunch of underlying changes to individual blocks the question in the uh the chat here is what did I mean by ad hoc what I mean by ad hoc is that a person sits down and they very carefully think through well if I update this and then I update that and then I update that and then I update that and the final thing I do is this then I know that if it crashes anywhere along the way I'll be able to recover the original file system so ad hoc here means that you come up with a A solution that is uh maybe it works but you've had to go through a long process of thinking it through to make sure it works and it's possible that you've got it wrong okay so that's what I mean by ad hoc here we want something a little more systematic okay so um and we're going to use transaction for this um so Atomic here Atomic is really the process of making sure that uh either everything happens or nothing happens okay and atomic in the log will happen even if the machine gets unplugged you want to make sure that we still have that Atomic property probably if you unplug it and you've got this Atomic property what's going to happen is your changes aren't going to happen Okay so let's let's walk through this a little bit more so transactions are going to extend this idea from memory to persistent storage and here's a typical structure of course you start the transaction you do a bunch of updates if anything fails along the way you roll back if there are any conflicts you roll back um but then once you've committed the transaction then that mirror Act of the of the commit operation causes everything to be permanent now okay and so we'll talk about how to do this in a moment but um this do a bunch of updates thing could be arbitrarily complicated it could be allocating new iodes it could be grabbing some new blocks it could be linking them it could be doing all sorts of stuff and the point is that none of that is going to be permanently affecting the contents of file system until we commit and so that's what we're going to try to figure out how to do okay that's the atomic here is all of a sudden it it happens or it doesn't happen at all now um of course a classic example you know uh transfer $100 from Alice's account to Bob's account you see there's a bunch of these different pieces right Alice's account gets debited 100 uh the branch account uh that 100 goes to the other uh bank and then um Bob's account somehow gets the balance and so on and so uh there are a series of operations in different parts of various people's databases and if only some of them happen then the banking system becomes inconsistent um for instance if it crashes the whole system crashes between de debiting Alice's account and incrementing Bob's account then not only did Alice lose money well she didn't get her $100 but Bob didn't get it either and so that would be bad okay and so this idea of beginning transaction ending committing transaction is one in which none of these things happen until the commit now modern operating systems uh the question is do they expose the transactions to the user um depends a little bit on uh which file system you've got certainly there are some Notions of transactions that are available others are uh others are less available right now what we're going to talk about is mostly under the covers in a way that the user doesn't have access to so the concept of a log to make all this work is the following if you look at all of these pieces I've got here that represent parts of a global transaction I'm going to write them in a chunk of memory slisk that sort of uh think of this as a this is the log and think of this as a big chunk of dis and all of these things are going to be in there and they might be interleaved with other transactions but what we're going to do is View this log serially starting from the left and going to the right and uh we're going to start the transaction by putting a start transaction marker in the log and then we can go ahead and do all of our stuff and everybody else can do their stuff and it's only when we put a commit transaction at the end that now all of a sudden these actions automically happen okay now a couple of things that should be clear from this one is when I put start transaction that needs to get committed to the log kind of before anything happens and then when I put my various actions in here before the final commit happens it has to be the case that all of these other things are in the log so it can't be the case that I do a commit it gets on disk but all of these other things are still in memory somewhere because then the machine could crash and I see well start transaction commit transaction but I have no idea what I just committed and that would be bad okay okay so um the log is is clearly going to be something that we're going to need to be pushing out to disk and it's going to be have an ordering requirement that's very important in order to make this all work and the other thing that I'll point out here is notice that if I write these uh operations in the log dump dump a b c d dump and then I say Commit This doesn't necessarily mean that I've actually put them into the file system or actually produced the actions yet what it means is that if if I were to crash and I hadn't done them yet I'd be able to uh wake up after the crash and go through the log and figure out what the the state of the system is supposed to be so the state of the system is not only what's on disk in the file system but also what's in the log and um and ordered in a way that I can go back and reconstruct after a crash and I'm going to show you um a couple of animations here just to give you a better idea how that works all right okay so the commit is like sealing an envelope and saying the transaction now happened now um so now the question is uh and shouldn't things be logged after they happen well uh in this type of log we're we're doing um something in which it's called write ahead logging we're actually writing into the log before it's put into the file system okay and the reason for that is so it's the opposite of the way you're thinking of this I think um we want to write in the log first rather than modifying the file system so that if the commit never comes because we crash then the file system's okay if we were to start modifying the file system and then put the commits into the log now we're in a bad situation where we might have already corrupted the file system by doing a partial update okay so this is uh I'm glad you asked that question this is the opposite maybe of the way you were thinking so thanks for that clarification question um so here's a transactional file system uh example so we're going to get better reliability through the log a log changes are treated as transactions and a transaction's committed once it's written to the log data is going to be forced uh to disk to get for reliability uh there's a possibility of using nonvolatile Ram or Flash or whatever to make this faster because we can put things into non-volatile RAM maybe maybe more quickly than we can write it to the dis so perhaps the EnV Ram can serve as the head of our log um and alth the file system may not be updated right away the data is going to be in the log now the question here is does the log negate the performance benefits of a buffer cache uh and the answer is it depends um it depends on what you're logging not everybody uh not all versions of journaling file systems we'll talk about that in a moment write all the data to the log first and then back to the file system okay um so let's just uh let's go forward a few more here before um I answer that last question in the in the chat here and then maybe I'll answer it for you hold on one second okay so the difference by the way between a log structured and a journal file system is in a log structured file system uh all the data is only in the log it doesn't even go to the file system whereas in journaled file system the log is really just helping us get reliability okay and um when do we start logging well as soon as we've started up the file system we start the logging okay all right now um maybe I will uh just give you a little bit of a preview here the question that's in the chat which I hadn't answered yet is if not all actions have been completed and you crash how do you figure out which have and haven't uh been completed and let me let's just hold that question and see if this gets answered okay so we're going to focus in the next several slides on something called a journaling file system where we don't modify the data structures on the disk directly uh right away we write updates in as a transaction into the log kind of typically called a journal or an intention list and um then when we commit then we're going to have the potential to put them into the file system okay once changes are in the log they can be safely applied uh to the file system modifying IE pointers directory mappings Etc and the question that's uh in the chat here about well do we have to have all of our operations be idempotent to make this work the answer is no and we'll see how this works in just a second so well some of them need to be idempotent but um let's see if this answers your question so garbage collection is uh going to be a possibility here so once we've actually applied things out of the log successfully into the file system then we can remove things from the log okay now Linux essentially took the original fast file system called it EXT2 uh and then they added a journal to it to get ext3 so ext3 is really just like a fast file system Linux Style uh with a journal okay and there are a bunch of options that Linux gives you about whether for instance to write all the data to the to the uh log first and then to the file system uh and that double writing surprisingly enough uh doesn't always hurt you from a performance standpoint because the log remember is is sequential and so it's very fast so a lot of other examples of journaling file systems NTFS Apple HFS plus Linux xfs JFS C xt4 there's bunch of options here okay so let's create a file but this no journaling yet so think of this is like Fast file system or ext3 so we can see where we're going with this so when you create a brand new file and write some data there's a bunch of independent things that have to happen so first thing is you got to find some free data blocks so here's an example let's call this yellow thing a single free data block have to find ourselves a free inode entry so on in the iode table find a an insertion point in the directory so maybe there's some blocks on the directory we're going to change excuse me all right and then we're going to link things together so we're going to write uh the map which basically says uh Mark which blocks are in use okay we're going to um write the iode entry to the blocks we're going to write the directory entry to point to the iode all right and when we're done uh now we've got a a new um pointer in a directory this a mapping between a name and an i number that points to an iode which we've allocated which points to a dis block and now so notice all these different individual pieces uh and and the free space update uh have all happened just to create a file and write to it and if we sort of partially do this and we crash then we're going to end up with dangling blocks uh like for instance if we didn't successfully write the directory entry then we could have an note entry pointing to a data block and it's not in any directory and it's effectively lost okay so let's see how we could add a log to this or a journal so if you notice here um we're going to put this log in some non-volatile storage flash or on disk for instance is the simplest thing it's going to have a head and a tail so the head is the point at which we write the tail is the point at which we read okay and let's go through and see what happens when we write our new file so we're going to first find a free data block and notice that I found the block but what I'm going to do is I'm actually going to find my free I note entry going to find my directory insertion point but I'm not going to actually do anything instead what I'm going to do is I'm going to write a start transaction in the log I'm going to uh write the free space map I'm going to uh write the inode entry uh pointing at the uh you know which where it's supposed to go so I'm going to excuse me write an iode entry here without actually writing the disk and then I'm G to write a directory entry without actually writing it on disk okay and notice that all of these things are reversible because if I crash at any point up until now I haven't actually modified anything in the file system so the file system is going to look exactly like it did before I started this process okay now when I hit commit poof all of a sudden it's committed now think this through for a second notice there's no changes to the disk okay and yet the mere Act of writing commit to the log now makes that file committed and the reason is that the state of the file system is considered what's on disk Plus what's in the log okay and so if I crash at any point after the commit gets written in there what I'm going to do is I'm going to scan the log and at that point I can apply the updates to the file system and things are going to look okay and I can keep crashing so these are idempotent this was a question earlier because uh the um the log has basically been choosing blocks for us but we can keep overwriting the same block over and over again with the same data and it's not going to matter and so I can keep trying until I eventually get past the commit at which point the file system will actually be updated to reflect this change so the mere Act of writing the commit in the log means that that file has been written when it with its new data okay so after commit we can replay the transaction like I said supposing we don't crash we can replay the transaction by just writing stuff on the disk eventually copying everything there and once it's copied then I can start moving the tail see how I'm applying stuff and if I get past the commit at that point then I can throw out everything that's in the log okay now here's a good question in the in the um chat here so what about reads do they have to scan the log for changes that haven't been flushed yet no this is where the block cache comes into play right so the block cache has the most up-to-date state of the blocks uh as as reflected by the total state of the file system including what's on the log and what's on disk and so the block cache uh since the block cache filters the reads and writes from the user uh it basically makes everything fast regardless of whether it's actually only in the log or if it's on disk okay so the block cache is important aspect of making things fast here now uh the question here you can't flush until you commit uh that's correct so this is again right ahead uh logging here well right ahead logging says that you have to get the log values on the in the log before you hit commit once they're in the log then you can flush things out to dis so yes you have to get them to the log first and then they can be flushed onto uh onto the file system on the disk well if the cach is full and it's a really large right then uh then you have to make sure that uh you've committed first okay um so there's a lot of uh potentially complicated questions about scheduling here and when you're allowed to schedule things Etc um I don't want to go into it too much right now but what I will say is you can imagine that uh the file system knows when it's in TR when it might be in trouble by allowing too many rights uh before the log has been cleared and all it has to do is put the clients to sleep uh until things have been properly flushed and then it can wake the clients up okay and so this is you just have to keep track of what the current state is so that you always have this right ahead logging property okay now um once we've committed everything then we can just throw out the log and the tail has moved here all right um what's the size of the log that's changeable so um depends on how much data you want to have now notice by the way that what we've got in this particular log actually didn't log the data necessarily so we could write our data to uh the disk and it's only the metadata that's logged that's one of the modes um that's one of the modes that basically uh the Linux file system has in another mode is one in which the data first goes into the log and then goes back out on disk okay now uh if the system crashes after commit but before we've fully applied everything that's okay because we can just keep restarting because we don't remove things from the log until we've actually gotten past commit uh with the thing not crashing and everything pushed out to dis that's a point at which we do a single atomic move of the tail which uh throws out this particular entry so we don't really need to know exactly which changes are have been applied we just take wherever the tail was you know so the tail might be here and uh we're trying to apply and we keep crashing over and over again well we just we can restart um and it's back after we get past the commit that we can then uh throw that log entry out okay this particular version of this the changes are empit there are other ways you can do things but we're going to leave it this way for now okay now um let's look at this uh and situation here where we started that process and we crashed um and notice this is what it looks like after crash so maybe we found our blocks and we started to write our updates we didn't get a commit record in here then all we do is we just uh detect at this point that we've crashed and all we have to do is we just throw everything out that hasn't been uh committed yet and we're we're good to go all right and all of this stuff can be thrown out I didn't quite have a a good um example here but you can basically throw out things that you haven't touched and um transactions without commit records that are ignored from that point on all right um the other thing is if uh we recover and we have complete transactions we scan the log we find complete start commit uh um examples and at that point we can just redo as usual and um in the process we update our uh block cache and then once we got past that part of the boot then everything works as normal all right so I've just given you the start but I I hope it gave you the idea what's going on so why do we go to all this trouble the answer is that updates become Atomic even if we crash okay so we either get all it's either a applied entirely or not at all and so all of these physical operations and there potentially many of them are single logical unit okay we get an atomic update um now you might ask isn't this expensive well it is expensive if we are in the mode where we're writing all the data twice except the log is typically um sequential on the dis and so the cost of writing to disk in the log is actually much faster than trying to write all of the different pieces throughout the file system so that's actually faster than you might think and there are some circumstances where this right to the log with your data and then put it into the file system can actually give you some boost in performance under some circumstances okay especially when you've got a bunch of random rights then you can get them out on the dis quickly um so modern file systems give you an option to to do metadata updates only in the log and this is where you're going to record the file system data structures like Dory entries iode use and and Etc and what happens in the worst case where you crash but you haven't flushed your data is now you get a file with garbage in it but you don't lose a bunch of files okay and so that's a trade-off between uh reliability and performance it gives you sort of an option uh to do slightly less than uh full atomicity when it comes to the data itself okay now um a full buffer cache is is uh could be an example yes where your right call comes back and not everything's been written that's correct okay all right now let's talk briefly about something that I wanted to remind everybody of are there any more questions okay and so by the way ext3 is the uh is the version of the Linux EXT2 file system fast file system that's got a journal in it and all they did was they took that file system and they had a special file that serves as the journal so all right so I wanted to remind everybody because we've had some people that I think have forgotten a little bit about the collaboration Pro uh policy for cs162 so you got to be careful okay we we do not want uh people importing parts of code from other people okay so things that are okay here are for instance explaining a concept to somebody in another group could be okay but don't explain exactly how to do something if it's a concept that for instance I talk about in class that's a perfectly okay thing to talk about okay um discussing algorithms or strategies at a high level is probably okay okay discussing de debugging approaches like um sort of using you know how do you produce uh print FS that you can go through easily to find out what's going on or you know what is your overall structure for testing those kind of things are okay uh searching online for generic algorithms like hashtables that's okay all right things that are not okay are things that are likely to get caught by our uh catch by uh the code that we run to to uh catch collaboration cases all right so sharing code or test cases explicitly with group or write out uh copying or reading another group's code so you shouldn't be even looking at other people's code okay or their test cases uh copying or reading online code or test cases from prior years that's not okay okay so if if you're straying into specifics about a particular uh project or homework you're you're probably in the Red Zone okay helping somebody in another group to debug their code that's also not okay um we did have a good example in a past term uh where somebody sat down with a group that was having trouble and they were helping him debug and um but they this person sat with them for so long that as they kept kind of incrementally changing their code the code ended up with a structure that looked so much like uh this uh the helpers group's code that the two groups uh were flagged for over collaboration and that that's a problem okay so uh um be very careful not to do that okay because we want you to be all doing your own personal work on homeworks and uh exams of course and your own groups work in group work okay so we compare all the project submissions against prior prior year submissions online Solutions Etc and we will take actions uh against offenders that um have sort of uh violated this code okay and you can take a look on um on the homepage we have uh discussion of this in more detail um so and don't put a friend in a bad position by asking for help that they shouldn't give you okay we've had in past terms we've had people that have pleaded with friends of theirs uh until the person just gave them some code to get them to leave them alone and um that ended up uh ending not well for both of the people so just uh try to do your own work okay and I remind you this because we we have caught uh what appear to be a number of collaboration cases and uh we've only gone through some some of the things so try to try to not put yourself in a bad position okay all right now that we have stunned everybody into silence Let's uh let's talk about some real topics again here so I'm gonna assume that everybody will be very careful okay so let me um take this idea of logging that we just had in journaling and take it to its extreme okay so one extreme is called the log structured file system which is an actual research file system on the Sprite operating system that was uh I have a paper up in the resources page you can take a look at it and in this case it's like what I just told you with the journal but there is no file system underneath so the log is the storage okay so the log is one continuous sequence of blocks that wraps around the whole dis inodes get put into the log when they're changed uh data is put into the log Etc and everything's just in the log okay so here's an example where we create two new files deer one file one deer two file two um and write new data for the files and here's the log and notice this is a Sprite log structure file system and notice what happens is that there were some blocks and stuff in the files uh there were some parts of the file system in the log prior to this picture but we're writing file one and what we do is we write some data which goes into the log and then we uh we change the iode for the directory that also goes into the log okay and then we write some data for the second file and for the directory and all that stuff goes into log and ultim ultimately uh if the since the inodes for deer 1 and deer 2 have changed then we're going to put uh the updated iodes for say the root file system also in the log and when all is said and done all of our data is in the log it's just in the in the order in which it was written all right and um we never take it out of the log just stays in the log and then if we overwrite say uh part of file one what'll happen is we'll put the new overwritten data and then we'll put a new iode which links to it and so on and at some point the data is uh going to be kind of obsolete in parts of the log there'll be a bunch of holes and at that point we're going to do some garbage collection but up until that point the log is the file system okay and it's kind of like git yep there's a little bit of of that aspect so here's an example of the Unix file Sy fast file system where when we write data we're actually um writing the data on the Block groups where it was intended to be close to the inodes um for that directory so here's an iode for the directory we write some directory data here's an iode for the file we write some file data it's in a specific spot on the disk it's been laid out in a way to try to make it fast and if you notice the data here is laid out to be fast for reading but the rights go all over whereas the data in the log structure file system is made to be very fast for writes but reads will suffer and the whole if you read that paper which is which is a classic what you'll see as a justification for this is right bandwidth is often at premium so you're going to make it the rights go really fast and um you're going to rely on the Block cach to be big enough to give you really fast read performance okay and um so the other interesting aspect of this is as as we've been talking about transactions is that um this fact that things are structured as a log means that we can really easily undo things if we've got a failure okay and so part of what's in here are commit records and so if we crash in the middle of writing then we just go back to an earlier part of the log and our file system is good to go without any changes so the log structured file system kind of has built into it this idea of journaling because the log is the file system okay now um so the logs what's recorded on disk uh file system operations to figure out what's going on kind of logically replay the log to figure that out and put things in the block cache to make it fast okay everything gets written in the log um large and Portion uh large important portions of the log is cached in memory which is how we get things to be fast and you do everything in bulk so the log is a collection of large segments on the discs that are uh completely uh sequential relative to each other to make things f fast and if you read the paper you'll see that rather than what I first told you where there's a single log that goes through the whole disc in fact there's a whole series of these big segments and they garbage collect in segments all right um and the way you get free space back is you got to garbage collect um all of the holes that are in the log after you've overwritten data and so there's a garbage collection process too that we won't go into for now all right now the reason I brought this up is one thing I promised you a couple of weeks ago but never did what about flash file systems okay how are they different from the fast file system and I wanted to remind you what flash is like so this is a um a camos transistor which you've uh probably seen in some of your early classes and the idea here is that um when this floating gate is uh High then uh we end up with essentially turning a switch on so that the data can flow through this switch and when this uh floating gate is low then the switch is turned off so without this extra gate we um or say no floating gate just the control gate we end up with a transistor the way that flash works is uh don't want to say that yet the way that flash works is we actually trap electrons in this floating gate uh which has oxide on either side of it and the result of trapping the the electrons in there give us enough of a difference that we can detect and that's a way that we can store a one or a zero in here uh in distinguishing from the um non charge trapped State okay the thing that's funny about this is we can't write it once we've written it we cannot overwrite it until we erase it so if you remember um I talked about this a couple of weeks ago you can never overwrite Pages what you need to do is you need to erase Big Blocks of bits and then you keep them on a free list and you get these uh 4K byte pages that you use off the free list to build your file system with and then eventually um you garbage collect a big block and erase it again okay and so this is a little different from say a disc okay um and another thing that's important here is that these the way I write as I as I alluded to is I trap electrons on this floating gate now the way that that happens is I raise this word line so high that the electrons go zooming across the insulators and get on the floating gate and if I go even higher I can encourage them to go away and clear the gate off well that's a pretty uh harsh process and eventually electrons get trapped uh in the ins in the insulator and then this doesn't work as well and so the flash actually wears out and so anybody making a file system out of this has to be careful not to erase and overwrite too many times okay and uh yes we trap electrons to uh to store Reddit po post and CAD videos and um as I mentioned uh because we're trapping uh things in here this is a higher energy State it's technically it's heavier and so you can go look at where I talked about a few lectures ago uh the fact that a Kindle is technically heavier once you've put uh books on it okay now the the part that one of the parts that makes this easier is what's called The Flash translation layer which uh basically says that unlike a dis where we number all the sectors and then the system says I want you know sector 5,496 what happens in a Flash or SSD is there's actually a translation layer so when you ask for a particular number that goes through a translation layer and tells you which block on the flash is actually the current version of 5,226 and as you go through overwriting that from the uh operating system level the underlying flash translation level will keep changing which physical block there is okay okay and so that underlying flash transation layer automatically takes care of wear leveling and making sure we're not wearing out our bits but the question might be is there something we could do with the file system and make that work better okay and um there's firmware that run on ssds and so on and so the question is can we take uh advantage of this information to do something with it and the answer is yes so the flash file system um the f2fs file system which is actually used on mobile devices like pixel 3 from Google it was originally from Samsung um is actually a file system that's been adapted to use the properties of flash um it assumes that this SSD interface which looks like a dis for all practical purposes has underneath it a a flash translation layer the fact that random reads are very fast they're as fast as sequential reads and that random wrs are essentially bad for flash storage and the reason is that if I randomly then I make it a little harder for uh for the underlying flash translation layer to erase Big Blocks because to erase a big block where you have a bunch of random blocks written you actually have to copy the data out of the blocks um onto some pristine ones and then you can erase and so that actually ends up wearing the flash out a little bit more if I do random rights okay and so we're going to minimize rights or updates and try to keep rights sequential and so what they do is they actually start with a log structured file system uh with Co and a copy on write file system made out of it um keeping wrs as sequential as possible and there's a a node translation table to help us keep things sequential and you can for more details you can actually uh check out paper in the reading session section as well um called the f2fs a new file system for flash storage okay um but just to show you a little bit uh the log in the flash file system which I'm showing you here is actually split into a whole bunch of segments and those segments are ones that get written a lot versus ones that aren't written as frequently and so they actually lay out a bunch of different logs to try to manage how how busy the file system area is um there's a translation table um inside the operating system in addition to the one that's on the SSD and they try to classify blocks as being written frequently and not okay and there's a checkpoint operation and so on I'm not going to go into great detail on this but I did want to mention some of these things so if you're curious you can take a look um for instance here is uh an index structure of iodes and if you look at the log structured file system what you see is that if I update a file file data I write that in the log then I've got to write the uh direct pointer block over again into the log then I got to write the indirect pointer and then I got to write the inode and then I got to write the inode maps and so on I got to write a whole bunch of blocks just because I changed some data in the log structured file system and that's because uh I never update in place in the log structured file system I work my way through uh by writing all of the change things into the log while this means that there's a lot more changes and so one of the things that they do in this f2fs is they actually use a second translation table to to uh translate so that the inode for instance at a higher level has a name for this block and that block is in a translation table okay and so they make some interesting modifications to log structured file system all right I'm not going to go into this in any more detail but I just wanted to give you some ideas of what you might go through to try to make things faster okay and to take advantage of the fact that you can do random reads but random wrs are uh expensive and wear the file system out okay all right now time to switch gears um unless there were any additional questions on log structured file systems or transactions or what have you maybe I'll pause for a second while everybody's digesting the thoughts here so in both of f log structured file system and in the f2fs files are just in the log right there is no file system there's no other file system underneath it so log structured file systems are good for rights can anybody answer why the log structured file system might be good for rights it's a good question right the log is sequential so therefore uh it on a dis it goes on the track rather than randomly writing all over and so doesn't matter what your rights are they all go right at one after another on a sequential set of tracks on the dis and so they're very fast because you're avoiding seek time in the uh f2fs the advantage is is a little bit different but you're sequentially writing a whole bunch of blocks so that um when you go back to overwrite them again the uh the log can be erased as a group of blocks can be erased and so it's it uh matches up with with the underlying um architecture of the system so the the log structured file system does lead potentially to fragmentation in the sense that you got a lot of holes in Old parts of the log and that's where Garbage Collection comes into play and so if you take a look at the papers you'll see that what really happens is the log as as time goes on the old parts of the log have more and more holes in them because you've overwritten data that is in those places and at some point you just take the data that's remaining you copy it to a new part of the log and then you uh reclaim everything that was in that old part of the log so it's a type of garbage collection all right good now so Switching gears um if you remember I think the first day I kind of said what's what's cool about operating systems is they are part of this huge worldclass uh system everything from little tiny devices tied into local networks to cars to uh phones to refrigerators and computers and up in through big machine rooms and the cloud and so on all are part of one huge system and um the when I when I think about um when I think about what I'm interacting with on a day-to-day basis I like to think about how the the things I do down at the small scale are actually utilizing resources spread throughout the globe okay and it's amazing when you think about it um sometimes when I think about the whole thing it's it's astounding to me that it all works somehow and sometimes it doesn't entirely work but it mostly works but the interesting question that comes to mind is sort of how do you get all of these things that are spread uh geographically and in domains of fast local connection but really slow longdistance connection Etc get them to all work together and so uh for the last few lectures um we're getting down to the last like five or six lectures here I'm going to talk a bit about um distributed systems and how they can all work together to do for instance distributed decision making which is a topic we're going to start today um and so to start that topic let's bring back some what it turns out to be very old terminology but I thought I'd make sure we were all on the same page here so a centralized system is one in which there's a central component a server of some sort that is uh performing all the major functions and you have a bunch of clients that are all talking to the server and that's typically called a client server model okay and um many of the things that you deal with with your cell phone for instance where the cell phone is one of the clients and something in the cloud is a server that's actually that's actually like a modern analog of this traditional client server uh situation here the question that immediately comes to mind with a centralized server is well how do you scale this I mean what happens if you've got not three clients but a 100 thousand or a million clients clearly one server can't do it okay and so you know we know that in the cloud there are many servers but the question might be how do you structure them to do something intelligent when you've got many components okay now a completely different model is what I like to call the peer-to-peer model with in which um every component in the peer-to-peer model is a peer of the other components so if you notice in this client server model we really had uh the server was kind of King and uh the clients were subjects or something like that whereas in the case of the peer-to-peer model we we have a whole bunch of peers that are all interacting with each other and uh you know you might ask the qu you know in the client server case it's pretty obvious who's responsible for what you get in the peerto peer model it becomes unclear okay but the peer-to-peer model is uh kind of a good starting point for if we want to try to make this server idea uh spread and handle a really high load so for instance maybe we could draw a box around a bunch of these guys working in peer-to-peer mode and treat that as a server okay um so what's the motivation for Distributing in that way rather than having a single client and you know you could come up with lots of reasons right why do people do anything well here maybe it's cheaper and easier to build lots of little simple computers rather than a huge server in the middle or maybe it's e easier to add power incrementally so what I mean by that is if I've got a good peer-to-peer model and I and I need more power I just add some more computers to it right and if things work then by adding a few more servers or whatever now I've got a more powerful system than I started with okay and I can do that incrementally um maybe users have complete control over some of their components so maybe that big peer-to-peer system I've got some that I own and yeah I'm going to help everybody else a bit but I have full control over my hardware and I can bring it back when I want and of course collaboration um is an obvious goal here because maybe by putting together a peer-to-peer model it's easier to collaborate um so the promise of these distributed systems is really that it's they're much more available because there's more components that are likely to be up uh it's better durability so maybe by copying my data to lots of different machines it's more likely it'll survive a crash and maybe there's more security because each piece is smaller and maybe easier to make secure okay now you should be questioning some of these statements here for a moment um the reality uh is typically different okay so this is Lesley Lamport uh he's he's done all sorts of really uh cool system stuff and we'll talk a little bit about um a couple of them uh in the next lecture and a half but uh what he liked to talk about is the fact that the reality behind a lot of distributed systems are actually disappointing so the availability is worse rather than better because it depends on every machine being up he's got a very famous quote uh which is a distributed system is one in which the failure of a computer you didn't know existed can re render your own computer unusable all right it could have worse reliability because you lose data if any machine crashes uh it could have worse security of course because anyone in the world can break into one component and if they're all tied together they've broken into everything so distributed systems have a high promise but you got to be really careful how you use them right coordination becomes very difficult so you got to coordinate multiple copies of shared State information and what would be easy in a centralized system because everybody's going through one Central Computer becomes a lot more difficult when you've got things distributed and of course trust security privacy denial service these are all words that you've heard a lot of but um many new variants of these problems arise as soon as we start Distributing so um can you trust other Machines of a distributed application enough to uh perform a protocol correctly I think there's a corollary of lamport's quote that I like to to think of which is a distributed system is one where you can't do work because some computer you didn't even know existed is successfully coordinating an attack on your system all right that's the standard DDOS so U what are some goals of this kind of system so you'd like transparency which is the ability of the system to mask its complexity remember earlier I said well the way we go from a server system to something that can handle lots of clients 100 thousand or a million is we put a bunch of things together but we draw a box around them and we make it transparently behave the same way as a single computer would okay so we don't have to know about the complexity so what are some transparencies we might come up with well one is location transparency where you don't have to know where resources are located pretty much anybody who's dealt with the cloud has uh understood what location transparency is like perhaps migration so that resources can move around maybe for better performance or better durability or what have you without us having to know uh that they've been moving maybe replication well perhaps I pay to make sure my data doesn't go away and so underneath the cover is a syst system transparently increases the number of copies or maybe it does eraser coding uh transparently in a way that I don't need to know about but makes my data much uh more durable um maybe I don't have to know how many users are out there so uh one of the things that has worked pretty well about the cloud is everybody's kind of interacting Point too between their phone and something out there uh without having to know how many other people are acting with something out there okay and so that level of concurrency uh works pretty well if you're just working uh one to one on something now if you're actually collaborating on something then that gets a little more tricky and so concurrency uh is is problematic under some circumstances parallelism so the system May speed up large jobs by splitting them into small pieces transparently without telling you fall tolerance okay that's kind of like what I said about replication maybe the system is going to hide the fact that things are going wrong um and do so in a way that you still make forward progress okay so transparency and collaboration require some way for different processors to communicate with one another and of course that's going to lead to the need for networks and so on and we're going to talk about networks um in more detail in a lecture or two but for now um I want to talk about uh this idea of decision making being spread across a bunch of nodes because that's kind of the beginnings of how we do this particular thing so um the question about is it a goal for us to not be able to tell where resources are located uh I I would say yes and no I think it's better to think of it as I don't want to know have to know where the Lo where the um resources are unless I care right I'd like the system to transparently adapt them as long as it's within the uh boundaries of my policies and my goals for privacy and what have you I'd like to system to deal with that without me having to deal with it and if I care then another goal would be able to selectively break the transparency to meet some goal for why I wanted to care but then the rest of the transparencies are still there um so it's really the desire to not have to know um and a really important transparency by the way is what happens when a machine crashes that's storing some of your data you don't want to have to somehow go log into your um application and change an IP address uh to point to a different server just because some surger crashed you'd like that process to be transparent okay so think of these uh goals as things that I would like to be transparent unless I care okay um perhaps you think of it as opacity but I think it's really transparency it's uh masking complexity behind Okay so I don't have to know um so how do empties communicate well some sort of protocol so clearly there's going to be um communication through a uh a network of some sort of messages and a protocol is really an agreement on how to communicate including things like syntax how does a communication uh structured and uh specified and semantics about what a communication means so actions taken where uh transmitting receiving when a timer expires Etc okay um the uh so I'm noticing on the chat here so masking equals transparency so that is a funny uh a funny use of terminology perhaps but um You' like things to um be uh invisible to you happening under the covers that's where the word transparent so sort of the you see the functionality uh without having to know what's happening underneath and so that's that's often called a transparency I realize it seems it seems a little little strange but that is a use of that terminology um so for instance um Protocols are often described uh by a state machine on either side so here's an example where I've got two State machines and part of what the protocol is doing is it's tracking the states on both sides so that both sides have the same notion of the state of the world and um the protocol is responsible for making sure that that state is maintained so that if both sides suppose this is separate sides of the world and the state machines are being transparently replicated that's again the use of the word transparent then um then I can act on the current state of the system here say at Berkeley uh in Beijing and I'm and I have confidence that I'm working on the same information as the other side um and so you usually there's some stable storage that's part of this state replication um you could even think of uh a simple example might be that these are two versions of the same file system there's a transparent protocol and the states represent the state of the file system and it's keeping things in sync okay so that's another example of uh of a good protocol okay and so um you know we want among other things stability in the face of failure so even when parts of the system are failing or the storage falls apart in one place but it's there's still storage in other places we'd like the state machine replication to uh continue to work properly it may be that endpoints uh are selectively failing but if I were to vote let's say among the states of all the different uh participants so suppose I've got three participants and one of them fails a voting process could uh maybe be employed to figure out what the real state of the system actually is and we'll talk about some of this in a moment so examples of protocols in human interaction I mean I thought I'd put this down just for the heck of it you know you got you got a phone you pick up the phone call somebody you listen for the dial tone okay so maybe you don't do that on a cell phone but see you have service you uh you dial the number you hear ringing and the colag says hello you say hi it's John or U hi it's me um that's my favorite kind of goofy introduction it's like well what's that about who's who's me um but then uh you kind of say uh Hey do you think blah blah blah blah blah and they say yeah blah blah BL blah blah and you say goodbye and they say goodbye and you hang up now uh this is probably a conversation that you had um late at night sometimes including the blah blah blah blah I know I've had a few of them myself but really you're thinking about a protocol because there's a protocol which goes from ringing to answering at the other side uh to responding so the answer comes back and now you know that that connection's been uh set up uh or the caller says something the collie responds with a response and then there's some process for hanging up and so this protocol of synchronizing the states between the person that made the call and the other person is is a human interactive version of uh what we would like to do in our protocols okay and um the problem is you know there's many pieces of Hardware this has been our standard issue throughout this whole term where we talked about the fact that Hardware is vastly different uh at you know at the io level and so how do we deal with that and so if you look here uh when we're talking about communicating we have a bunch of applications at one level we have a bunch of ways that things are communicating you know maybe a coax or cable or fiber optics or whatever and the question is um the the many different applications have to communicate over a bunch of different media and um there many different styles and what do you do well you don't want to make a point-to-point uh application where Skype talks uh one way through coaxial and another through fiber optic and another through Wireless and so on because you're going to very rapidly get nsquared uh blow up in complexity right so for instance we added some new application like HTTP it shouldn't be the case that we have to write a new communication module for every type of thing that we're going to communicate okay communicate to and similarly if we come up with a new uh way to communicate like a packet radio or something we don't want to have to do an N squared uh communication between every application and every new communication media you know this this looks silly when you think about it but clearly there's a level of abstraction kind of like our device drivers uh that needs to be employed here and if you takeen uh you know if you take a networking you certainly know what that's about right so how does the internet avoid this well we put a layering in here okay we put intermediate layering and um a set of abstractions provi providing Network functionality and Technologies and so as a result new application uh that we add on here like HTTP really has to figure out how to communicate with this intermediate layer which is often called the narrow waist of the Internet Protocol um looks kind of like an hourglass um and you know if I put some new communication technology um I B basically have to figure out how to match the intermediate layers to communication technology and I've just made my problem much simpler because of abstraction okay and of course this is the typical hourglass that everybody sees when they take an an IP class networking class um where IP is the protocol of choice at the narrow layers it wasn't always that way but it's became become that way and now all of the layers above have to just send IP packets and all the layers Below have to uh communicate IP between different sites and if we do that then we basically have the internet okay and um it's astonishing how well this has worked uh to to basically connect a whole bunch of devices and computers and storage and everything simply by standardizing uh IP in the middle here okay um so what are the implications of this hourglass so there's a single internet layer module that's the IP protocol allows arbitrary networks to operate uh any technology that supports IP can exchange packets it allows applications to function on all networks so applications that can run on IP can use any network um it supports simultaneous Innovations above and below so um you know you can do all sorts of stuff to the above the application layer uh you can do all sorts of stuff below the the physical layers you can have many different physical layers but changing IP itself has turned out to be very challenging so um there's a funny story about IPv6 which has been the you know the next IP protocol for the last 20 years um only in the last I would say five years has it really taken a hold and started to become a reasonable protocol um it's been very hard to swap out ipv4 which is the traditional one with IPv6 because it had been so uh embedded in the world um so some drawbacks however of layering are the kind all of the drawbacks that you could imagine especially now that you've been through 162 so you know layer n may end up duplicating stuff that layer n minus one is doing or layers need a bunch of the same information so you end up communicating a bunch of information up and down the layers and you got a bunch of memory copies and it's expensive um layering may hurt performance well that you know the any API could potentially be made Faster by flattening the API out uh but then again you know if you do this the wrong way you end up with this N squared communic or N squared pattern again and that's not a good idea right so there's this tradeoff between performance and uh and apis and and layering and it turns out that without IP that's been an extremely powerful tradeoff okay now um the what I'd like to talk about is uh the end to end argument um there was a hugely influential paper which again is on the resources page um by sulzer reeden Clark from 1984 um so I realize that's ancient history now but it's one of these papers it still has uh some very important philosophy uh in it that I think I want to make sure everybody gets here so it's the some would call it the sacred text of the internet um there's been endless de debate sorry talking too long endless disputes about what it actually means um Everybody cites it as supporting their position um you know uh you could imagine that that's true of pretty much any good document uh that lots of people read um they'll get into philosophical arguments about it um the message however is pretty simple which is that some type YP of network functionality can only be correctly implemented from end to end uh and things like reliability security Etc are examples of such okay and because of this the end hosts can basically satisfy the requirements without the network help and therefore um and they must do it anyway and therefore you could imagine that the network didn't have to do that okay so the the way that this paper ends if you go to read this is basically that you don't have to go out of your way to implement stuff in the network because you got to do it at the endpoints anyway all right and the simplest example here um that they give which I think is very uh telling is the idea of you got two hosts and host a has a file they want to send to host B and of course you've got uh applications for the file transfer you've got the operating system you got networks Etc all of these are parts of that and you might ask yourself well how do I transmit well um you know the application reads it off the disk uh it sends it to the operating system which then you know sends it out of a socket um which then comes up the operating system the other side um goes into the application which then writes it to the disk and the question is how do you make that reliable well one option is you make everything reliable okay so you make it 100% reliable that you load the file off the dis and then 100% reliable that uh things get trans transfer from the application to the OS so that transfer might not be so bad but then you got to somehow uh make sure that when it goes across the network um every link that's in the middle so if we're transmitting from Berkeley to Beijing uh there's a whole bunch of other things there's transatlantic cables you know there's a bunch of Hops at different levels and there's a lot of uh detail in this link that we're not talking about right now and we'd have to make sure that every link was 100% reliable okay and that way we compen everything together and we get 100% transfer okay except it never works that way right it's very hard to make something 100% reliable and furthermore it's still possible that um you missed something and uh one of the things that is uh is interesting about that paper is they relate a story from uh 1984 in which uh they were transmitting um copies of the kernel source code from one host to another and it was only going across a few buildings or whatever but there were a lot of hops in between and they were carefully check summing and catching every hop along the way to try to make sure that this was never screwed up except what they didn't realize with the was that in some of the routers along the way um even though each of the links were carefully check summed and made to be reliable the routers actually had a bug in them that would uh I think it would transpose bits every million bytes that it transmitted in memory because there was a bug in the source code of the router and as a result even though they check summed everything along the way the data got slowly corrupted and the uh the colel had been transferred back and forth across these links a coule couple of times many times and as a result the data was slowly getting corrupted okay we used to call that bit rot all right and it was totally unexpected and it uh things got so corrupted they had to pull things back off of tape in order to fix it okay so this idea of making things uh reliable by fixing everything in the middle is uh not only very hard it might not be the right thing so what's the other option is you take it from uh point a and you transmit it as well as you can to point B and then you check at the end you say well did I uh did I get the file that I was expected and so I compute a a hash or a check sum at one end I send it to the other I check it out and either I've got the file or I don't and if I don't then I can retransmit okay and so what's good about this end to endend approach is it actually makes up for all sorts of problems in the middle by catching uh bad transmission okay now of course what's pointed out in the paper is uh if you've got a A 1 kilobyte File versus a versus a you know gigabyte file the problem is the more data you're transmitting so the gigabyte file is more likely to fail in the middle than the one kiloby file and so if you have a really large file and you wait until the very end before you check Summit you're going to have a lot of failures before you succeed and in fact it may take a very long time and so that's why you want to break things into chunks and uh sort of individually check and add but the point of this uh example is that if things have to be done at the end points then maybe you don't need to do them as carefully in the middle as you might otherwise okay and and then as a result any reliability you might do in the middle is really for per improving performance okay now um so the second option is basically uh saying well here's the check sum of what I got it goes back and as a result um you pull the file off the dis and this application the original one checks it and sees whether uh you're good to go okay now um solution one as I said was incomplete because if the memory is corrupted the receiver has to do the check anyway solution two is complete because you you had to do it anyway and so um is there any need to implement reliability at all at the lower layers okay and the end to- endend argument by the way if you know anything about the history of the internet is kind of what was used to justify the um the structure of the basic internet as it is right now which is a datagram service we'll talk more about that um in a lecture or two where packets of of small size are sent across and they either make it or they don't but um uh we don't worry about that because we're checking everything at the end to end okay and so this paper and the end to end uh philosophy in general was kind of the reason the internet's the way it is now um it could be more efficient though to do something okay so as I mentioned yes we could just send the the uh the data to the other side and hope it gets there and retransmitted if it doesn't but at some point that might be too expensive to keep retransmitting if I had a really bad Link in the middle and so there's a performance reason for improving things in the middle but there isn't a functionality need to improve things in the middle and so this discussion leads to a trade-off of about how much work do you want to do in the middle okay so implementing complex functionality in the network doesn't reduce the host implementation complexity because you still got to do it and it does increase the network complexity probably gives you delay and overhead on every application even if they don't need it so this is kind of arguing that maybe you don't need to do something in the middle if you have to do it at the ends okay but implementing things in the network can enhance performance in some cases like very lossy links now uh what's interesting is a consern conservative interpretation of the end to end argument just like there's always conservative and liberal interpretations of pretty much anything could say well don't bother implementing it at all at the lower level unless it can be completely implemented at that level and doesn't need to be in the end points um or unless you re actually relieve burden from the host don't bother a modern interpretation or a moderate I like to think of moderate as well is basically think twice before implementing something in the network if the host can do it correctly then um implement it in the lower layers only if it's going to be a performance enhancement uh or has a good justification and only do it if it doesn't impose burden that uh on apps that don't need it okay and this is the interpretation that I always use and that I suggest in this class and you might ask well is this still valid uh and there are some instances where this particular monitor interpretation is in fact uh not even quite enough okay which is what about denial of service so somebody is going to attack a communication stream from outside there might actually be a pretty good argument for um putting firewalls and check sums and everything on intermediate links to basically prevent the denial of service so in that instance uh even though the end to end communication still has to happen you're enhancing the overall path in the middle by putting functionality in there or privacy all right if I want to prevent privacy putting firewalls in the middle Mak sense okay or maybe there's things that have to be done in the network so certain routing protocols which pick paths from point A to point B have to be done in the network they can't really be done too well end to end all right so how do you actually program a distributed application so this is going to be our topic for next time you need to synchronize multiple threads running on different machines uh there's no shared memory there's no test and set so all of the stuff that we talked about earlier in the term really isn't quite available to you in this simple view of the world which is a bunch of messages I send from one thing and I receive on the other so there's one abstraction over the network um it's already Atomic so no receiver gets a portion of the message because typically we check some things and so if a bad message goes through we stop uh we throw it out and retransmit so the interface is sort of like a mailbox where the sender directs a message at a receiver's mailbox as a temporary holding area at the destination um and we have the idea of a send of a message to the mailbox and a receive which is blocking often to wait for a message to show up now what we're going to do next lecture is we're going to say can we take this basic idea and can we build something interesting on top of it that will allow us to build these distributed applications will allow us to do um to synchronize State machines amongst uh multiple machines and ultimately lets us do pretty interesting uh distributed peer-to-peer style applications so that'll be for next time so in conclusion um I brought back this idea of the ilities okay availability is how often is the resource available durability how often is it preserved against faults reliability how often is the resource performing correctly we talked about preserving the bits so I like to think of eraser codes AR raid as preserving the bits copy on write is about preserving the Integrity not the bits so with by copy on write I make a bunch of changes that are new by not overwriting anything but rather sort of using pointers to the old data that's copy on write and that allows us to uh basically preserve the Integrity of the old data even while I'm changing it uh we talked talked about how logs can improve reliability um we talked about Journal file systems such as ext3 and NTFS as similar and in general we talked about transactions over a log as a general solution um and hopefully uh the examples that I gave there worked out well we talked started talking about protocols between parties uh that will help us build distributed applications we spent some time with the end to end argument which will hopefully uh inform us as we go forward and next time we'll start talking about distributed decision making such as two-phase commit um didn't quite get there this time but we'll definitely do that next time so I'm going to say goodbye to everybody I'm sorry for going over I guess I've been doing that a lot this term my apologies but I hope you have a good evening and we will see you on Wednesday