Good morning and welcome to the first Open Infrastructure Summit. Please welcome Allison Randall.  This is the first Open Infrastructure Summit building on a long tradition of OpenStack summits. Now, changing the name is part of a broader strategic movement, recognizing that we are stronger and innovate faster and meet the needs of our users better when we collaborate and integrate across Open Infrastructure communities. So Open Infrastructure involves public, private, and hybrid clouds to gather with other established and emerging areas like containers, CI-CD, edge computing, NFV, 5G, and AI. Now, you'll hear more about all these areas today in the keynotes later this week in the breakout sessions, the forum, the workshops, and trainings. Now, the summits are an important enabler of collaboration. We bring people together from all around the world to get to know each other, exchange ideas, and make plans for upcoming development work. The summits would not be possible without our headline sponsors. So please take time this week to reach out and thank them. You'll find them in the marketplace and around the sessions and events. We also want to thank the sponsors of the project teams gathering later this week, where many projects will have in-depth working sessions. A big round of thanks to the individuals who contributed to the travel support program. They made it possible for community members who don't have the resources to fund their own travel to join us here at the summit. Now, open source is all about participation and feedback, so we have some handy tools to help you do that. The mobile app on Android and iOS helps you keep on top of what's happening, so you don't miss out on opportunities for collaboration. And we want to hear about your experiences with the summit and the breakout sessions so we can improve the summit next year. On the lighter side, getting to know people is a significant part of successful open source collaboration. So there'll be many opportunities for small groups to go out and get to know each other after the events, after the sessions in the evening. But I want to highlight a couple of large group events. One is the mixer in the marketplace tonight at 5.30. And another is the community party tomorrow at 8.30. Make a point of reaching out and talking to people you don't know yet. You never know. It might spark off a great collaboration. So while you're enjoying the summit, this week you can start looking forward to our next summit in Shanghai. This is the first one we have ever had in China, so we're really looking forward to the opportunity to get to know our colleagues in open source collaboration locally who can maybe travel as far as Denver. So keep an eye out for the CFP. And also, we announced that registration is open now so you can get started. So first up today, we have a bit of a blast from the past and a vision from the future from the executive director of the OpenStack Foundation. So please welcome Jonathan Bryce. Good morning, everyone. Welcome to Denver. It's great to see everybody here. As Allison said, it's the Open Infrastructure Summit. How many of you are here for the first time? OK. It's a little bit of a trick question because we're all here for the first time. So Allison talked a little bit about what this event is really going to be about this week. And I think that for me, it's recognizing some of the things that we've learned over the last few years. We've done a lot of events, a lot of different kinds of events. But I think our events that have had the biggest impact are the ones that focused on collaboration, on work, on bringing people together to solve problems in person and then set up really productive work that happens the rest of the year when we're often all of our locations all around the world. And so to me, that's what this week is really all about. And what I think the shift in the event is oriented towards. Let's use this time to get together, to work on problems, and set ourselves up for success the rest of the time. And actually, the event this week, it has a very broad base. We have a couple thousand people from over 50 countries, like we traditionally have. But we have more collaborative working sessions this week than at any event we've ever done. And I think that that is really important. So as we think about what this week is about, it's about getting work done and moving open infrastructure together overall. Today, I wanted to talk a little bit about some of the things that I have learned through OpenStack and also going back to before OpenStack and some of the things that I have come to believe. One of the things that I believe and that I've seen in my life is that technology is a really powerful force for changing lives. And I think that one of the things we've seen in the last few years is that this can be in a good way, sometimes in a not so good way. But technology really does change our lives the way that we work and that we interact. I also have seen that collaboration among individuals is another really powerful force for changing lives. And if you put these together, then I think if you want to have an impact on the world today, involving yourselves in open collaboration to build technology is one of the best places to do it. And I also think that openly collaborating leads to more good outcomes and more good changes from technology than other ways of kind of building technology and other motivations that may come into play. So I want to talk a little bit about some of my personal experiences and also some of what I think we've learned as a community and where we can go from here. And to do that, I want to go way back. I want to start way back. Kids often have dreams about what they want to be in the future, astronauts, firefighters. I, too, had a dream when I was a kid. And I heard the mantra that you should dress for the job you want, not the job you have. So I did this. I wanted to be a rodeo clown. And this is not Halloween, by the way. This is for real. This is just me dressing as a rodeo clown, which I did occasionally, because I thought that that was maybe the coolest job out there in the world. As I got a little older, I got exposed to more things, more ideas. And I had two interests that really developed kind of simultaneously. This is me with my first computer. You can see I've always been exceptionally cool. I was really excited, though, because this was an x86. And it's the computer I learned to program on. But the thing that I was very interested in at the time was music. And this computer had a sound card. And there were a few different applications and programming languages on there that had some of the early support for programming digital music and playing around with a sound card. The other thing that I was really interested in at that time was music. And I played clarinet over time. I picked up other instruments. And I was really convinced that I wanted to have a career in music. I loved it. It's still something that I love and spend time on. And so growing up, I was very focused on music. And computers were kind of a hobby, a thing that I worked into my love of music. But that all changed a few years later, in 1995, when during a summer, I worked in San Antonio, Texas at a commercial cleaning company, cleaning toilets and office buildings and taking out trash and working with this company that my brothers were involved in. And one of my brothers, he knew that I played around with computers. And he said, hey, I heard about this worldwide web thing. And it seems like companies in the future are going to be present on the worldwide web. Do you know anything about it? What would that mean? How do we do that? And basically kind of sent me off to figure out how to create a website and how to put their little company online. And 1995 was actually still pretty early for companies to be doing that. And so to do that back then was there was a lot of manual effort if you really wanted to build a website. And if you wanted to build a dynamic website, which somehow in my head I got the idea that this commercial cleaning company needed a portal and a dynamic back end and all of this. And so I built that for them. And some of their customers then really liked this website and said, hey, how did you get that? Where do we get something similar? And so in 1995, I discovered that technology was actually a pretty good way to make money as a teenager. Definitely easier than mowing lawns and cleaning toilets, which is what I had been doing. So this is when my life took a little bit of a turn towards technology. And then what happened after that point really accelerated my involvement in technology. A few years later, I started working at a little company there in San Antonio called Rackspace.com. This website is a blast from the past. But this is where I got my first exposure to open source. And over the next couple of years, what I worked on within Rackspace was taking open source technologies, integrating them into our systems, and building tools that automated things that our customers were doing. So this was really my first usage of open source and seeing how powerful it was as a way to provide access to technology. What I did after that point is I kind of took all the things that I was learning. And it was one of my best friends, Todd Maury. I started a company that tried to create a self-service, highly automated, expandable system for hosting websites, web applications. Eventually, we added virtual servers and an object storage. And it became the Rackspace Cloud. And during that time, it went from me and Todd, two employees to about 500. It went from two servers to tens of thousands of servers. It went from about $2 a revenue to $100 million a revenue.  And through that, we learned a lot of lessons. But one of the ones that really stood out to me and something that I still believe today is that technology is not a sustainable long-term advantage. And it's kind of weird, perhaps, to say that since we are all in an industry that's called the tech industry.  And if you are trying to build technology that creates that long-term sustainable advantage, it's really an impossible task. And you have to constantly be on this hamster wheel. And if you accept that, and you accept that that is not where your long-term advantage is going to come from, then you realize that you shouldn't take on the burden of trying to build all of the technology you need yourself. And that leads you to open source. And I think of a version of open source that is very much the way we work in this community, which is that open source is not about marketing some kind of other product. It's not a business model on its own. It's really an innovation philosophy. And it's a philosophy of innovation that is about shared innovation. And if you're sharing your innovation, then how do you find the value in that? How do you build a business? How do you pay developers and find a way to open up opportunities? And I think that, again, this goes back to you don't rely on technology alone as your differentiator. You combine the technology with services, with other tools. You make vertical implementations. These are all the things that we've seen become successful business models in the open source world. And one of the most successful versions of that is public clouds, who take a lot of open source, wrap it in services, provide operations expertise, and deliver a lot of value. Sometimes I hear people today say, well, open source is in trouble because public clouds are the only people who are capturing the value. But I think that our community proves that that is completely wrong. We have hundreds of organizations who are here this week who are taking technology, OpenStack, Kubernetes, stuff, different networking frameworks, different storage tools, and they are adding value. Organizations like CERN, who is speaking this week, they are adding a ton of value, and they're taking that same approach that public clouds are, where they're bringing the tools together and delivering an experience for their user. CERN is a really big deployment. You don't have to have a really big deployment, though, to add value. Le Bon Quoi is a French e-commerce company, and they have an OpenStack environment that powers their software development. And their OpenStack environment has less than 20 servers in it. And yet it still adds a ton of value to their organization because it helps them move a lot faster. So all of these things, I think, are concepts that many of us have thought about in the past. But I think they're really important for us to continue to think about today. And at Rackspace, we were definitely thinking through this philosophy and these ideas. And ultimately, that's what led us to say, well, let's take the fastest growing part of our business and actually open source the technology that's underneath it and make it available to the world to try to build a bigger collaboration. It was kind of perhaps a crazy move at the time. But one that I think was actually based on a very sound philosophy and strategy. That was only the start of it, though. That was important, but that really was the start. What happened next, I think, is actually the most awesome part of the OpenStack story, which is the community stepped up and started defining what we wanted our culture to be. And that's ideas like the Four Opens, which is a very high bar for how you collaborate and how you develop technology. We had other principles and tenants that we talked about a lot at the time. Technical people should be making the technical decisions. We want to bring in a lot of use cases. We want to bring in a lot of input to drive the future of the technology forward. We want to actually invest directly in building a community, a global community, that is able to participate and use the software and direct it. And we want to make sure that users are a central part of all of it, that we're going to fight for those users. And as we've gone along, sometimes we forget how far we've come. We just had the OpenStack Stein release, which was our 19th on-time release. Isn't that crazy? 19 releases, that's a long time. But at the same time, what we see is still an incredible velocity within the community. It's one of the top three most active open source projects today. 65,000 changes in the last year went into OpenStack. We have thousands of users and organizations who are running millions and millions of cores in OpenStack Clouds. And there is a very large commercial market. This is a report about the commercial market in 2018. And this is very large for an open source commercial ecosystem. And so OpenStack is one of the most successful projects in history. It's incredible. And all of you who have participated in that, you should feel really good about what we've accomplished. That's a true testament to what this community has done. And it makes me feel so just excited every day to get to work in this community. I think that it also speaks to some of the trends that we've been a part of and that are continuing on. And I think one of the biggest trends is that software is how technology gets built and moves forward. And cloud is the fastest way to deliver software. And this is why more and more people want that cloud experience in every aspect of their life and their technology. And I think along with software, we've seen developers becoming a more and more important part of everything that happens. As Steve O'Grady wrote a book about developers being the new king makers. And he said that the most successful companies today are those that understand the strategic role that developers will play in their success or failure. And I think this is true not just for companies, but also communities. So as we start to think about what we've built and where we want to go, I think this is good to keep in mind. We have a community that grew up around OpenStack that's over 100,000 people in almost every country on the planet. So what are we going to do now? That's an awesome resource and an awesome start. But I think that now what we can do is we can apply the lessons that we've learned and have an even bigger impact on the world. How do we build the best infrastructure systems by collaborating across communities, companies, cultures? How do we take OpenStack and other open source infrastructure systems and use them to drive forward the industries that are really gonna matter over the next 20 years? We're gonna hear about some of that today and throughout the week. People who are building the future right now with Open Technologies, 5G networks, AI and machine learning, industrial automation. This is all happening right here this week and in our world, but it's far from guaranteed that Open is gonna win here. And this is where I think our community has a huge opportunity to have a bigger impact on the world. And this is what we've been thinking about as we've made this transition to open infrastructure over the last couple of years. And I wanna bring up someone who has worked with us at the Foundation and helped us think through this to talk a little bit about her thoughts on where we should go. So please help me welcome Amy Leland. Hi, Jonathan. As Jonathan said, I've been working with the Foundation on thinking through some of the new ways of bringing projects into the Foundation. I love open source. I've been working in open source for the last 13 years. I've been working at Intel and bringing new projects into the community into multiple different communities. These are just a few of the projects that I've worked on and definitely not all-encompassing of the work that I've done within the communities. But there's a lot of things that I've learned building these communities and building these governance models. And a few of them is that there's no one size fits all. In any community, every single project has its special thing. And I learned that bringing in the community early and often is essential and critical to building a healthy ecosystem. I learned that as a company that if you wanna provide community leadership, you have to be able to look at your company goals as equally as important as the community goals and putting those community goals equal. This is a really long quote about governance, but I think it encompasses a lot of what governance and what governance should be providing. And essentially, governance really ensures that in communities there's transparency, that there's stability, and that there is inclusiveness. And a core value that the foundations bring to open source and to our communities and to our projects is that they actually bring that governance to our communities. And I believe that the four opens are critical critical and foundational in good governance. So open source, open design, open development, and open community. It's one of the reasons why we brought Cota Containers and StarlingX as new projects to the OpenStack Foundation. And it's not just because of the transparency, it's not just because of the stability and inclusiveness, but it's also about the things that have come out of the projects that we've been working on. And you'll hear later today about some of the things that they're doing in Cota Containers and what I'm talking about, but what's born out of that is new projects and new innovations. But I also think it's more than that. This is a picture of our Cota Containers launch. And the goal when we brought Cota Containers to OSF is setting up a structure with minimal hierarchy, minimal governance, and just enough to get people together to focus on solving problems across companies. At the end of the day, good governance really isn't about projects. It's about putting people first. And someone once told me that tools follow process and process follows people. And I wholeheartedly believe that. And this community gets it. It puts people first. This community also works across boundaries, works across communities, works across foundations, works across companies, works across industries and knows that every part of the open source community and ecosystem is essential to a thriving and healthy open source ecosystem. The whole point of open source is to not have walled gardens. And at the end of the day, I believe that if we work together and if we focus on putting people first on good governance and work together on solving problems that we can set or that we can solve the next set of challenges within open infrastructure. So, thank you. Thank you Amy. Thank you. So, you know, collaboration without boundaries I think is a theme that has developed over the last couple of years within our community. And what I have seen that's really gotten me excited since we've been talking about this is some of the areas where this is happening specifically. You know, we have a ton of sessions this week that are from a lot of different open source projects. I think we have over 30 different open source projects that are participating in our collaborative sessions this week. And that is really, I think, how we're going to move forward and solve new challenges in new industries and new use cases. Amy mentioned that later on in the keynotes we're going to be hearing about one of these new emerging collaborations. It's called Rust VMM. So, look out for that one. I think, you know, we've seen a lot of interaction between the OpenStack and Kubernetes communities. Our most recent user survey, we asked people, what workloads are you running on top of your OpenStack clouds? 61% of them said Kubernetes, which is really, to me, a proof point that people want these tools to be working together. And so, you know, that to me is what collaboration without boundaries is all about. But it's also, you know, I think that when we talk about collaboration a lot of times we default to tech and open source. I mentioned earlier that music has been a very important part of my life. And a couple of years ago, I saw a documentary. It was called The Music of Strangers. How many of you have heard of Yo-Yo Ma? Okay, this is great.  So, Yo-Yo Ma is one of the top cellists and one of the top classical musicians in the world. And he has had a very successful career. He is a soloist with top symphonies pretty much everywhere, anytime he wants. But a few years ago, he had an idea and he wanted to do something different. He wanted to bring together a group of musicians not to form a traditional symphony where everyone comes together and kind of plays music that you know and does it in a standard way. He wanted to bring people together to collaborate, not to conform. And so, he created this project, the Silk Road Project, Silk Road Ensemble, that was focused around bringing together musicians from all over the world and having them bring their perspective, their experience, sometimes new instruments that you wouldn't normally see in a kind of a standard musical setting to collaborate and to create something new. And it took a little while to figure it out. If you watch the documentary, it's not like they all showed up and in the first hour, incredible things happen. They had to understand how to fit it all together, but over time, they did create something that was really new and beautiful and exciting. And in the movie, there's a quote, and he says, we don't all speak perfect English or Chinese or Persian, but we speak perfect music language. I also recently heard another quote that said, there are only two universal languages, music and code. And so, I think that's a really interesting thing to think about because in some ways, what we do is we bring together people from all over the world with their experiences, their perspectives and their contribution to create something that's also new and special and useful. And occasionally, we also combine music and code. This is a photo from the PTG in Denver that we did last year. And we found a piano and spontaneously decided to do a little bit of a karaoke night. And I think that what it shows is that, like Amy was saying, this community is about people. It's about all of us coming together to contribute to what we wanna build and how we wanna build it. So as we kick off this first Open Infrastructure Summit, I wanna encourage all of us to do that this week, but also going forward over the coming weeks and months and years. Let's bring our different perspectives, let's bring our skills, our contributions together and create something powerful and take the things that we've already made, take them to new areas, take them to new use cases and keep pushing our corner of the world to be more open and more collaborative.


Welcome friends. So we have been doing lots of triangles in these sessions, but never mind You know, you know that this is very important part of your syllabus, but right so hence Let's understand another theorem and this theorem is nothing but converse of basic proportionality theorem now basic proportionality theorem says that if there is a line which is parallel to the third side of a triangle then it divides the other two sides in you know in Proportionately right so that's what the theorem says. So let us say this is a b and I have D and E these are the two points where this line is cutting BC. So by basic proportionality theorem if if D e is parallel to BC then then A D upon D B is equal to A E upon EC that's what we learned, right? This is B P T now converse says that So now I'm going to give you the statement of converse of the theorem of B P T and it says if in a triangle in a triangle a Line or a line segment whichever way you want to write it a line divides divides two sides In the same proportion in the same Proportion then the line is Parallel to the third side to the third Side, okay, so in this case in this case, what is it? It is so let me now write it here. So it's given so given a D by D B is equal to a E by EC and you have to prove to prove What do you need to do you need to prove to prove what? D e is parallel to BC so now you understand why is this converse because in the basic proportionality theorem This was given and you had to arrive at this But now in converse of basic proportionality theorem. This is given and now you have to arrive at this That's why it is called converse isn't it so now Let me start with the proof. So how to prove so in this case, we will use something called method of contradiction method of Contradiction one of the very popular and very effective method of Proving results right method of contradiction. What does method of contradiction mean? It means that you assume that whatever is to be Proven is not correct. That is it is wrong and then with logic you prove that your initial assumption itself was wrong and hence The result so what does it mean? So in this question it is being asked to prove that D e is parallel to BC given a D by DB is equal to a E by EC So what I where will I start from I will say let Let D e Not be parallel be not be parallel to BC this is what we have to prove So hence I am starting with this assumption only that this is not true Let it be not true then somehow by a logic if I prove that this assumption of mine was incorrect Then automatically D e becomes parallel to BC. Isn't it? Isn't it so hence we will say that okay? You are saying that D is parallel to BC. You want to prove that I am saying it's not possible Right, so if it is not possible that means there exists a line Let us say D e dash There exists a line D e dash therefore I can write there exists There exists a line D e dash such that such that e dash is on AC and D e dash is parallel to BC Right, so when you're saying that okay, you know D is not parallel then there must exist one line D e dash let us say let us I'm assuming that that line is D e dash such that e dash is on AC and such that D e dash is parallel to BC right? because if you're saying that D is not a parallel line to BC then There must be one line which is passing through D and Which must be parallel to BC there exists a line there is a line BC It must have another line parallel to it which passes through D and let that be D e dash Now if D e dash is parallel to BC then What is the logic? By our BPT now BPT we have already proven and I can use this theorem and say if D e dash is parallel to BC in the triangle ABC then ad by db is equal to a e dash by e dash C Isn't it? This is what? We will get by BPT and now let us say this is this relation was one and This relation by was two so you see the left-hand side of one and two are same So very comfortably I can equate the right-hand sides so I can say a e by e c is equal to a e dash by e dash c right by equating the right-hand side of one and two adding one to both sides you will get a e by e c plus one is equal to a e dash plus e dash c Or other I'm sorry. This has to be step by step. So let me write a e by e dash by e dash c plus one So I have added a plus one to both sides now And this will give you a e plus e c if you take LCM and this is e c This is equal to This is equal to a e dash Plus e dash c divided by e dash C Isn't it now look carefully a e plus e c in the figure Here is the figure. Where is the figure? Yeah, a e. Yeah, so a e plus e c will give you a c isn't it and a e dash and e dash c will also give you a c So hence if you see a e plus e c is a c Now this was divided by e c is equal to a c again because both summed Will give you a c You can check once again if you're not convinced a e dash by a e dash plus e dash c is a c and a e plus e c is again AC right so hence if you see I can strike off a c from both sides this would mean E c is equal to e dash C is it it now? How is that possible that there are two line there are two points e and e dash to a distinct points as well and Are lying on the same line and are collinear so e e dash c are collinear and Right this relationship is also holding this will happen only when only possible only when Only when e and e dash coincide Coincide e and e dash e and e dash Coincide isn't it that means if e and e side coincide e and e dash coincide That means de dash so de dash and De are same Lines That means now we know that de dash was parallel to be see so hence and Since since de dash was parallel to BC therefore Be is parallel to BC so hence proved hence Proved that's what we wanted to prove that de is parallel to the third side if ad by db is equal to a e by Easy, this is the inverse of Basic professionality theorem now we learned lots of corollaries to be PT in the last session so if any of these corollaries are also true then De would be parallel to BC. What do I mean? I mean that if you have a D upon a b is Equal to a e upon a c then also if this is given. Let us say then also De then also Then also de will be parallel to BC Understood. This is called converse of basic proportionality theorem


Hello, party people. This is the DebConf 14 OpenPGP key signing party. So, I'm DKG. This is Anibal. I want to welcome everybody here. We're going to be passing around two decks of cards. Each deck needs to go across the entire room. You'll get a deck coming in a different direction. Make sure you get the top blue card when the deck hits you and the top red card when the deck hits you. I'll explain what's going on with that later. Just make sure that you pass it so that everybody manages to get one of each card. What do I need to do to break the system? I'm not going to tell you. It's okay if people know what your card is. You don't have to hide the card. And I'm not going to do any sort of magic trick guessing thing. Everybody check that you still have your watch off. So, we're going to start with a little overview about what we're doing here and why we're doing it. And then a little bit of technical detail. And then we'll go ahead with the actual program. You're going to read the hash at some point, right? Yes, we are going to read the hash at some point. So, I recognize that there are some people who are here who have done key signing parties many, many times before. And I suspect that there are some people here who have never done a key signing party ever. So, there's going to be some explanation. I want to encourage people to ask questions if you're not sure why something is useful or why something might happen. I don't think we have time to go into all of the possibilities about what could be done or specific tools to use for every single thing. But, question. Yes, I will speak more slowly. We also have a microphone. We have a microphone for the people with questions in the audience, I think. Any bell has it. So, if you want to ask a question, please raise your hand and wait until you get the microphone to ask the question. Why are we taking a card and passing the rest down? We'll get to that. I promise. Okay. So, primarily what we're trying to do here is to meet each other and to establish connections with each other so that we can continue to have those connections in a secure fashion over the internet in the future. We're establishing the identity of other people who work on the project, getting to know who they are and making sure that we have a secure way that we can communicate offline. So, we're bootstrapping the online communication from this offline meetup. So, that's the purpose of a key signing party. So, many of the people who are here probably sent an email to Anibal with their key and asked for it to be included in the key signing party and that's great if you did that. With the public part of your key, yes, not the private part. I'm sure that there are several people here, if not many people here, who did not get an email to Anibal and that's also okay. So, there are some things that are going to be more convenient for the people who have sent their key to Anibal earlier but if you do not do that, you can still participate. It'll just be a little bit less convenient for you. So, yeah, sorry, for people who came in late, there are two decks of cards going around, a blue deck and a red deck and everyone should get the top card from each deck when it passes. So, make sure you have a blue card and a red card. We'll get to that. So, part of meeting people is knowing who people are. There are some open seats up here if the lurker's in the back when it comes down. But part of it is the cryptographic part is that we want to verify people's fingerprints. So, the fingerprint is a marker for your public key. It is very difficult to forge a fingerprint that matches your fingerprint and normally if you're doing a pair-wise fingerprint verification, then both parties have to read to each other a relatively long string of hexadecimal characters and verify that from the other person. That's kind of a boring task. We're also not very good at it as humans. So, sending the keys earlier, we're going to avoid having to do that many pair-wise fingerprint matches by, as a group, we're going to take a list of all of the fingerprints that everybody has submitted and we're going to collectively verify that we all got that same list and that way when you meet someone whose key was on that list, you'll be able to go, you'll be able to say to that person, oh, I had the same fingerprint hash that you did when we looked at the big list and my key was number 28 and then you can look at the list and you say, oh, it's number 28 and now you've got the file, you've got the fingerprint, you can just work with that. So, the advantage is that everybody verifies one big fingerprint and then we can work with our tools to do the signing afterwards. Does that make sense as to why the process is set up that way? If you did not. So, the steps I have here is everyone has the big list and if you don't have it yet, you can fetch it from there, which may or may not be men in the middle and then we're going to take a digest of the big list and then we're going to, so we'll compare the digest and the other thing, no, not those. They've run out of red cards, wow, all right. Uh-oh, really? How many people do? Well, no, because that's going to put everybody in the same boat here. All right, so if you didn't get a card, then look at your neighbor to your left and note their red card and look at your neighbor to your right and note their blue card and that's yours. I have the last blue card, so these two rows don't have blue cards. Sorry, initially, when everyone was here at the start of the talk, there were less than 80 people in the room and now there are more than 80 people in the room and I apologize that I didn't expect so many people to come in after the talk started. If you came in after the talk started, you're going to choose randomly about the cards later. Sorry, it doesn't work to give out these cards now. Not if you don't have a card. So the critical thing here is that when you look at this list, it's not just about having the group consensus about what the digest is on that list. You also have to verify that your fingerprint on that list is your fingerprint. So if we all agree on the collective digest, but your fingerprint has changed, Johnny Ball was the one who made the list and then it got transmitted over clear text HTTP, make sure that your fingerprint is the right one. If you're not in the list, and I'm sure many people aren't, make sure you've got copies, physical copies of your fingerprint. When we're doing these key signings, you're not going to be reading your full fingerprint to all of your neighbors. So if you have a physical copy that you can hand to your neighbor when you're in the process of doing the verification, that way they've got a copy of it and they can do whatever they want with it. So I want to emphasize here, the fingerprints are for crypto. The goal of all of this is to meet other people in Debian so that you can keep in touch with them and do stuff with them later. Work on projects. So do the people who are... So you can also participate without verifying the fingerprint of the file and you're just not going to be able to correctly verify people's fingerprints. So in which case you probably should not be signing their keys. You can verify the individual fingerprint, but I don't want people to have to be doing that during the group key signing. So sorry, you want the URL there? There you go. So that's deb.ly, KSP, Key Signing Party, Deb Comp 14. So KSP DC 14. Oh, there's way more opportunities than two. So... There's a brown group of foxy. So I want to make sure that everyone... So I want to get around to just... We're going to get out of the way the group verification of the fingerprint of the whole file. And so I want to make sure that everyone who is going to be verifying the fingerprint of the whole file is prepared to do that. So if anyone who is planning on verifying this and is not prepared to verify the fingerprint, please raise your hand. Okay.  So another option for some people, if you want, is to make a note of the finger. If you don't have it, if you're not one of the folks who have it in front of you, you can write down the fingerprint that we are all going to consent on shortly and then you can later fetch the file and try to verify the fingerprint that way. So, yes, you'll need to have an exact copy of the file. It is now. So... Sure, the URL is deb.ly. KSP DC 14. That was a random URL string that it gave me from the URL shortener. I was using dual eCDRBG. So... Sorry. Okay. So, I just put the SHA256 sum of the key signing party list up there and I'm going to read it out loud. So it is four, four, seven, five, eight, one, two, echo, five, two, bravo, thanks, nine, seven, eight, alpha, bravo, foxtrot, echo, eight, zero, bravo, nine, seven, bravo, five, bravo, alpha, echo, nine, six, eight, nine, echo, five, three, six, bravo, seven, delta, three, seven, four, alpha, four, three, nine, eight, six, foxtrot, Charlie, zero, alpha, five, two, three, foxtrot, bravo, five, alpha, foxtrot, nine, one, Charlie. Does anyone have a different fingerprint? No, I am not. I'm only going to read out this one file. This is the canonical file. I don't think we should have separate versions that are multiple, not quite canonical files. So there's some discussion here about what, for people who are listening remotely and don't have the microphone access, there's discussion about whether we're going to verify another file's fingerprint and I want to minimize the amount of fingerprint verification because that's not the point here. The fingerprint verification, the goal is to make sure we have a cryptographic link. This is sufficient to have this cryptographic link and I don't think we should do more. The question is, is anyone going to use the condensed file? Can you bring in the microphone? So there's some discussion about which files are acceptable to use. The canonical version is this kspdc14.txt, not the compressed one. Borland, did you want to repeat that? So the issue I'm pointing out is that at the very least I remember off the top of my head the condensed file does not list the key lengths of the keys. So verifying that checksum doesn't give you the same cryptographic assurance and should not be used. And also, I'm not checking that file so you'll just have to use the real one. Can you hand stand the mic please? So, okay, this is speaking with, I was one of the reviewers for the latest round of the OpenPGP spec when it was approved. It is my understanding that a modern key, and I'd have to go back and look this up, we got to a point where all you needed was the fingerprint. I believe that's correct. But it is absolutely true for DSA keys and especially for PGP-1 keys, that is not true. Yeah. PGP-V3 keys do not, the fingerprint does not encode the length. Yes, we do. Why? I don't want to get into the cryptographic details right now. I want to get on with meeting each other because I think that's the point. Also, I am not verifying any fingerprints that are mine except in that file. So if you were trying to verify some other file, I am not assuring you that your copy of my fingerprint is valid. You must verify that fingerprint to be assured that my fingerprint is valid. Okay. A couple of points here. No one is under any obligation to sign any key. Right? You don't have to sign every key of every person that you meet at this key signing party even if you say that you do, even if you say that you plan to. And if someone decides to not sign your key or if someone is lazy and forgets about it, you can ping them if you want, but it's okay if they don't want to sign your key. We would be happy to have people meet each other and certify each other's identities, but it's okay if that's not what, if somebody doesn't want to sign. So traditionally with key signing parties, people have asked to, you know, we ask people to bring some form of identification. So what kind of ID is okay? I want to point out that the bottom point here is the critical part, which is that different people have different standards. At Debbie and we really want to make sure that we know who each other is, but there are some people here whose government issued IDs don't match depending on what you consider to be actual. Some people here have identities, have identity papers that are not internationally valid like a local driver's license. Some people have just this as their identity and it's up to the person who's doing the certification to decide what kind of ID is sufficient and how many IDs they need to get. So I just wanted to point that out and this is again up to the person who's doing the certifying. And one more point here for folks who have not participated in a key signing party before. We are not actually signing keys at the key signing party. We are taking notes and you will use those notes later to certify whichever keys you decide you want to. But we are not going to do any key certification in this room. I mean maybe some people will because they're crazy, but the point here is to not actually do the key certifying right now. Make notes so that you know what the keys are that you are going to certify and then you can go do that whenever you want. One of the reasons to argue for printing out the sheet is that it's easy to take notes on the sheet with a pen and when you meet someone face to face it's nice to have a piece of paper and a pen. It doesn't feel quite as alienating as a computer. Other people prefer to take notes on the computer. They can process them more easily that way and different people have different note-taking styles. So the way that we're going to... I'm just going to demonstrate with Anibal the way that we would use... the way that we would do this because people who are here have not done this process before. So, okay, so I'm going to say I'm Daniel Kahn-Gilmore. My email address is dkgeathethorstman.net and I have verified the fingerprint that we all agreed on here and I have checked the file and my fingerprint is correct in there so I would say this to Anibal and he would look at his notes and... Did you check the hash? I did check the hash of the file and here's my ID. It's a New York state driver's license. I also have this which doesn't have my middle name on it and I have my healthcare card and I probably have something that I wrote in crayons So, now it's up to him to decide whether or not he thinks that is a sufficient identification. What do you think? I want to see Clayton. Yes. My number is 28. I'm going to check his name with his name on the list. I'll hold the microphone. 28. Fingerprint, you said... I've checked my fingerprint and I've checked the fingerprint of the file. Your ID is okay. Thank you. Sure. So, I would like to get my ID back. Thank you. I did. So, let me say that again because Zobel thinks that I didn't say it. I checked the fingerprint of the file and I looked at the file and I checked that my fingerprint is correct in the file and I am number 28. That was the first thing that I said. Yes. So, there's a hand... Manaj has a hand there. Would it be faster to have us go around and say things like, I'm number 66. I checked the... Check some of the file and... So, the answer is yes, it would be faster but people would not be able to verify whatever identity documents you present. So, the identity can be then checked separately. Well, if you're checking the identity separately at that point, you can also say to the person I checked, I'm in the file, I've checked my fingerprint in the file and I'm number 8. If you're doing that separately, which I encourage you to do after the KSP. Wait. Okay? So, does this process make sense to people? Any other questions? We'll get to the cards. Come on, folks. So, after the KSP, after the KSP, you will process your notes.  I recommend emailing your signatures to the people because that's a way to verify their email address. If I said, hi, my name is Daniel Kahn-Gilmore. My email address is president at whitehouse.gov. You probably don't want to certify that because you can recognize that that's probably not my email address. But you can't tell, really, with other ones. And so if you email your signatures to the person who you signed, then you're verifying that at least they have some way to read that email. So, yes, so there's a tool called CAF from Key Signing Party that automates that and I recommend checking it out. There's also a tool... Sorry, Signing Party. Don't believe what you see up here. I'm not going to change it right now. So there's Signing Party and Monkey Sign and Pius that all offer that. I recommend CAF at the moment. I'm hoping to recommend Monkey Sign in the future. Are these slides available online? They're not right now, but I'll put them online. Was there... Sorry, there's a bunch of people asking questions and I'd like to have one conversation until we can get to the Key Signing. If you receive emails from people that are using CAF, I think it's important to note that that's the signature and then you need to upload that to the server. Otherwise it won't be public. So the email that will... The email that will be sent via CAF will be a message text with the signed key attached, all of that encrypted and then mailed to you. And so when you receive it, you'll need to decrypt the email, extract the attachment, import that into your PGP key ring using probably GPG import or whatever tools you have available. And then if you want that signature to be visible to the rest of the world, you'll then need to send your key to the public key servers. Tom? Yeah, I just wanted... I was trying to find the correct bug number here and I'm not finding it at the moment, but I wanted to just remind people that there is a little bit of a confusing configuration step for CAF. It has its own directory for GPG configuration and it's kind of important before you actually start signing keys to make sure that among other things, the signature strength is set sufficiently high, like SHA-256 or better in that file. I'd be glad to answer anyone's questions about how to do that if anyone has any questions about that. And also just to follow up on the comment that Tigard mentioned earlier, I think it's generally polite to let people upload their own signatures. I like to be the one to upload my own signatures because often if you send me a SHA-1 signed key, I will probably politely ask you to re-sign it and then I'll upload your strong signature to the key servers. Thank you. I think those are good recommendations. So are we ready to learn what the cards are for? Yay! Okay, so everyone has a red card and a blue card, except for the folks who came in late. That's not a blue card! Okay, so the red... you're going to have zero or one red cards and zero or one blue cards. And when I say you're a red card and you don't have a red card, you get to pick a number from one to ten. Okay, so what we're going to do is we're going to split into groups. We're going to split into ten groups and the groups are going to be based on the number that you have on the card. And when you pick a number, you'll just go to the group with that number. And so the goal here, we're going to do this twice. We're going to do it once with the red cards and then once with the blue cards. And in each group, you'll get to meet a small handful of other Debian folks. And within that group, you'll take turns introducing yourself to everyone who's in the group and passing around your ID for them to look at. And then we'll... We're going to do that for about ten minutes and then we're going to switch and we'll do the blue card groups. And the goal of this is we're not trying to get everyone to certify everyone else's key. The goal is to have a bunch of people who have signed... It's going to create sort of a mesh of certifications and it's going to give you a better chance to actually know something about the person whose keys you're signing. So in addition to doing this, you can also meet anyone during the rest of the conference and while you're talking to them, say, hey, I missed you at the key signing party and then have the same exchange and actually have a real conversation with a little bit more time to do so. Okay? So we're going to do ace two... I guess... Let's do ace two, three, four, five, six, seven, eight, nine, ten. Doesn't matter. Red card first, but it's not about whether it's red versus black on the suit. Okay. So look at your red card and ace two, three, four, five, six, seven, eight, nine, ten. And when you're in your group, when you're introducing yourself, you're going to say your name, you're going to show your ID documents, you're going to say whether you confirmed your fingerprint in the file. And you're also... Okay, can everybody... Can I just say one more thing? So in addition to saying... In addition to the critical pieces here, you are also going to say in one sentence, and everybody else in the group, keep people honest, one sentence, what do you do for Debian? One sentence. And then you're also going to say you get food. So we didn't get part either. I don't know why you guys flocked to me. I didn't flock to you. I didn't flock to you.


It's a really thin crowd today. It must be either the rain or how boring Monday's lecture was. One of those two things drove people away today. So today will be more interesting, I promise. So what we're going to talk about today will start to talk about some of the challenges in implementing file systems and how things actually work on disk. So we have some idea that there are blocks of data that are stored on the disk. You could probably assume or have guessed that not all of those blocks of data are things that are stored in files. And that's what sets different file system designs apart from each other. It's just how they use the disk, where they put things, the type of data structures they use to accomplish some of the common tasks. Because as you guys have probably noticed, I mean, if you install five or six different file systems, they all feel pretty much the same. They support pretty much some of the same interfaces. And you don't really notice what's different about them. But we're going to talk today about what actually makes them different, even if the interface they provide to you as a user and to applications is pretty much identical. All right, so I think we're done grading the midterms. I think Guru has finally wrapped up the last question. So I am going to, somebody will enter the grades in today. Then we take them over to get scanned. Once they're back, you guys can pick them up. So probably Friday, actually, depends, I guess, now on how long it takes to do the scanning. Once they're available, we'll have them for you. You can come pick it up during office hours. And I'll let you know when that happens. What's that? Is there a midterm grade for the course? What do you mean? What does that even mean? Oh, I did that. Yeah, I gave you guys midterm grades. Yeah, they were just unsat. Yeah, no, they're out there. I did that.  You didn't even check. You just assumed I hadn't done it. I'm insulting. I did that for the first time this year. Yeah, so I did. And I emailed about this, or I posted something on Piazza. I'm pointing with my little finger that needs to make. Yeah, so I did use this feature of the hub. It's very exciting. And I should say, I managed to use the feature of the hub, because at one point, I got stuck and couldn't figure out how to proceed. So the hub won again. It's way ahead of me, in terms of points. So yeah, no, there are midterm grades up. And I only use sat unsat, because that's sort of where we are in the semester. I don't want to give you guys a letter grade that's sort of meaningless, but yeah. So those are a good one. OK, yeah, cool. Cool, we're all good. Yeah, so I checked today. Max score on assignment three, currently 26. So you guys have a ways to go, as far as. Yeah, I kept putting in lower and lower filters, and I was like, really? Anyway, so apparently, this is good. Apparently, you can only get about 26 points if you submit Dumbia, which is good. OK, so any questions about files? Probably not, because you guys already know that stuff. Any questions about files? We're not really going to do any review today, because I think you guys understand about files. We're just going to plunge onward and talk about cooler stuff. OK, so just to finish up, we were talking about the other class. The last thing we finished up with was talking about why I need a tree with a root, so I can produce a unique file name. If I have this, I can't do it. I have circles. I don't know where to start. Even if I know where to start, if I cycle from the graph, I can't necessarily do it. So once I have this sort of structure, now I can actually produce a canonical file. And we distinguish between a couple of different names. So the canonical name is the name that's anchored at the root, does not contain any sim links, and identifies the file uniquely. We also have plenty of relative names. So once you start using dot and dot dot, you can create all sorts of funny names like this. And these are the types of names you guys are familiar with. If you get good at tab completion, you'll get even better at being able to construct these wild and crazy relative path names. So that's another reason to get your tab finger working. Because that's the best way to construct these. And then you can CD anywhere on the system in one command. And I just thought I'd put up the poem that I use for this example because it's cute. You guys can find this on your own. OK, so when we talk about what file systems try to accomplish, so now we know what a file is, now we know how files are named, and some of the conventions about how that works. There's a set of common goals that file systems try to accomplish, and there's a bunch of different interesting designs for achieving these things. So translating names to contents. This is something that happens all the time. Every time you open, every time you navigate through the file system, change directories, there's a constant process where the file system is being asked by the operating system, I have this string. And what do I do with it? Or the file system has to take that string and convert it to a number. And we'll talk later today about how that works through a couple of common cases. So that's one thing that the file system needs to be able to do. I need to allow files to change. So files grow, files, the names of files change. Files have content appended to them, they are destroyed. I want to be able to support these type of operations to files efficiently. That's the second goal. To some degree, there is a certain amount of attention paid to improving performance for single files. So if I think about the type of benchmarks I could write or the type of tests that would stress one file, reading the files sequentially, opening a file a bunch of times, various types of things, there are things that the file system will try to do to optimize this type of usage. You can also start to try to optimize access to multiple files. This starts to get a little more complex because I have to see relationships between multiple files in order to do this. But this is certainly something that file systems are aware of and potentially will try to do. So see patterns, see connections between multiple files, and improve the performance of access to related files. And finally, consistency and fault tolerance. So survive failures and provide a consistent view of the file system. Now, consistency and maintaining all of your data are sometimes at war with each other because sometimes in order to maintain it, the file system at a consistent state, I may need to forget about some of the things that you tried to do right when the system was in the process of crashing. But the worst thing that can happen to a file system is somehow you do something that corrupts its internal data structures and it forgets where things are.  I was very proud of this. It took me a long time to find all those MP3s, of course, in completely legal ways, right? Downloading music was legal in the 90s. And at some point, I accidentally overwrote some of the file system meta data structures. I didn't know what I was doing at the time and now I understand what happened. And the disk, I couldn't recover with the drive. So I bought some software online, that software said, oh, it's gonna help me find, it's gonna find all my data and I was like, this is awesome. So I ran it and it found a lot of the data on the drive. So I was pretty excited. Until I started listening to the MP3s because what I had noticed when I recovered the drive was that there were some of the MP3s had gone missing. They were gone. So maybe 95% of the files were still there but the other five weren't able to be recovered. Well, it turned out that the other five were still there. They were just in tiny little pieces sprinkled out throughout all of the other files. So you'd be listening to, I don't know, Taylor Swift and in the middle, there'd be a little step out of Britney Spears.  And of course, this was incredibly irritating and I eventually just deleted everything and started over. But yeah, so that is the worst possible thing that can happen. There was really nothing to do at that point. And of course, this was my fault, not the file systems but if it had been the file systems fault I would have been pretty upset. Okay, so the file systems that we're gonna talk about, as I mentioned before, support a pretty consistent feature set. There are probably some differences. A lot of times those differences involve things that you guys don't really even notice as users. Storing content and hierarchical names. These are sort of the consistent things that we associate with the file. File systems today support a whole bunch of features that you guys probably don't even notice. For example, how many people have ever used snapshots on a network file system? How many people even know that this is happening? Yeah, maybe a lot. So a lot of network file systems and a lot of certain commodity file systems will periodically record copies of your files. So if you delete something, that file is actually still there. You have to know where to find it. So it's a feature kind of similar to the Trashcan or whatever is supported on Mac and Windows but there are files that support this by default. And those files are usually hidden in special directories that you have to know where they are. All right, now despite the fact that they support this very common feature set there's a lot of differences in terms of what actually happens on disk. So how the disk blocks are used, the data structures that are used and this is the thing that sets different file systems apart from each other. When we start talking about specific file systems we'll point out these differences and talk about how they impact performance and reliability and other features that the file system is trying to provide. Okay, so broadly speaking when we start to talk about file systems you can, so remember the disk provides me essentially with an array of blocks. And there are some performance implications to how that array is laid out but you can think of the disk as just a big array of fixed size blocks of binary data. That's it. The file system to implement a file system we divide those blocks into two categories. If you took your disk and you looked at every block in it roughly those blocks fall into two groups. The first group contain file data. So these blocks contain data that you could access through the file system that's inside a file. Clearly some of the blocks have to be used for this purpose. And then there's other. And sometimes we use the term inodes for as a general term for this although inodes actually have a little bit more of a specific meaning. But then there's the inodes and the metadata blocks that the file system uses to store information that it needs to record names to record other metadata about the file and for its own internal data structures. So there are blocks of data on your disk that do not correspond to file contents. What's one way that you can potentially that you might have noticed this in the past? There's something that, you know, I'm sure you guys have done this where the box from New Egg shows up and there's this new one terabyte hard drive inside and you're really psyched and you plug it in and what do you do? What's that? Well, okay, but in order to make it usable what do you have to do? Format. And then what do you do? Then you're so excited to have a one terabyte disk and then you look at how much free space and how much free space is there? Less than one terabyte. Okay, so why is this? Well there's two reasons why this is actually. The first reason is a little bit of silliness on the part of device makers because hard disk drives are sold in thousands of bytes for some inane reason. So a one terabyte drive is actually one trillion bytes or something like that or one million one K blocks. So when you convert that to actual normal bytes that we talk about megabytes, you lose something already. But it also turns out that when you format the drive one of the things that happens is a certain number of the blocks on disk get converted from general storage into these metadata and nine nodes. And so when the disk reports capacity it's reporting the amount of storage it has available for data. And so some of the storage on the disk has been used for the file system's own internal data structures. This is one of the reasons that your file, your disk is immediately smaller and more disappointing than the disk that you bought. You're so excited about a one terabyte and you only ended up with 998 gigabytes or whatever. Still probably plenty. Okay, so, and again what makes file systems different is how they do this, right? What, how their data structures work on disk and how they recover from crashes. So this is the significant feature that we'll talk about in more detail later. This is something that, you know, the early sort of, you know, I probably characterize early stage file system design is really interested in the first two and more mature file system design is very much interested in crash recovery in fault times. So a lot of techniques for maintaining the consistency of the file system emerged a little bit later in the file system design history. So if you, now what makes this hard, right? So if you think about what a file system is actually doing, it's maintaining this big complex data structure. That data structure needs to be able to find files. It needs to be able to allow files to expand, to shrink, and that data structure is located on disk. That disk is unreliable, that disk sometimes behaves in ways that the file system doesn't quite understand. And the hard part about this is partly because updating, making changes to the file system usually requires updating a bunch of different structures. So let's talk our way through an example white operation. So let's say I want to append some data to the end of a file. I have a chunk of data, you've made a right system call, that right system call eventually is bounced down into a file system implementation. What are some of the things that the file system has to do in order to complete this right? Got one K of data I'm appending to the end of the file. What is one thing the file system has to do? Well, okay, the first thing I need to do is find a block. I need an available block on the disk to store your information, that much is pretty simple. So I need to find that block, how am I gonna do that? Well, that requires probably accessing some data structure stored somewhere else on the disk. Now, actually what Isaac said comes in two parts. So now I have to associate that block where the new data is with the rest of the file, which may or may not be anywhere close to where that block is. Who knows? I have to adjust the size of the file because when the right completes, the metadata associated with the file should reflect the fact that the file is bigger. I actually have to put data into that block. That's important in order for the right to finish. Now from the perspective of the process, all this stuff needs to happen synchronously. When the right completes, all of these changes should be made. There should be fewer free data blocks on the file system. The file that I wrote to should have some new data associated with it. The file size should be updated. But doing all these things takes multiple, involves writing or reading data that's located in multiple spots on the disk.  And that creates two problems. The first, which we'll talk about a little bit later, is of course this problem with consistency, where if I get interrupted in the middle of this, it's possible that I've left the file system in an inconsistent state, and there's something wrong. The file size doesn't match the amount of data. There's some blocks hanging out in the file system that don't belong to a file. It's sort of hanging out, marked as used, but not actually associated with any file. I don't want to do that. I want to use the entire capacity of the disk. There's also a performance issue here, because doing this requires now potentially visiting and updating multiple locations on the disk.  So this is, in a nutshell, what makes file system design difficult, and also really interesting, is trying to optimize on disk layout and the usage of the disk, both to improve performance and to maintain consistency when things go wrong. Okay, so let's start looking actually at some on-disk data structures, and today we're gonna talk about how we translate names, so how we take a name, and we find the block or blocks on disk that store the content and other information associated with this name. So that's a, as I mentioned before, this is something that the file system is doing repeatedly all the time. So once we find some information about the file, we're actually, of course, gonna want to find all the data blocks associated with the file, and we'll talk about how those are organized, and we'll talk a little bit about how iNodes and other on-disk data structures are allocated. So when I'm using examples today, I'm gonna be drawing them from EXT4, which is the, I think, still most up-to-date Linux file system that's what's used in your virtual machine and by default. And this is a nice example of a fairly mature, but also fairly straightforward file system that we can look at. Okay, so some terminology here. A sector is the smallest amount of, the smallest unit that the disk will allow you to write. So a disk has a smallest amount of data. You can't write a byte. You have to write 256 bytes together. If you want to modify one byte, you have to read those bytes, change one, and write it back. This is just a standard feature of disks. However, the file system usually will not write amounts that small. Usually the file system will pick a larger amount that's a multiple of the sector size. We'll call this a block. So this is the smallest amount that the file system will actually write, even if the disk would allow it to write smaller units. And finally, modern file systems, as disks have gotten really big, have introduced this idea of an extent. So an extent is an even bigger chunk of contiguous blocks on disk. So blocks that are right next to each other, whether on the same track or on neighboring tracks, that are used to store content for one file. So frequently now when I create a new file on disk, I allocate a bunch of contiguous space on the drive to store contents that might be associated with that file. So the first question is, why would the file system probably want to avoid writing small chunks of data? Why would I pick, now again, I mean, this sounds awesome. I have all these teeny little 256 byte blocks. They're so cute, right? I've got so many of them, it's awesome. Why wouldn't I take advantage of the ability to write these small amounts of data? Why would a file system choose a block size that in this case is 16 times larger or maybe eight times larger than the sector size? Well, okay, so all this is to make things faster, right? But how, right? Why does that make things faster? Yeah, so remember, or maybe I haven't pointed this out before, contiguous writes are good. Once I've moved the heads to a particular spot on the disk and I've paid that whole latency cost to get the heads there, I wanna write a bunch of stuff. I'm there, I'm hanging out, I'm on this track, the track is spinning around. It's faster to move to nearby tracks than it is to jump all the way across the disk.  And that's the same motivation for extents. So blocks were essentially this earlier idea where I would use something like 4K. Now, why 4K? I mean, the answer's up on the slide.  What is 4K? Yeah, the page size. And when we talk about file system caching, it's also gonna be pretty convenient to use 4K as our block size because it means that a page in the cache now is written to a single place on disk. So if I use a single page to cache file contents, I can write that into one location on disk, which is nice, as opposed to 16 or eight. Extents really motivated by the same reason. Contiguous reads and writes are good and jumping all over the disk is bad. And as files have gotten bigger, file systems have responded by saying, hey, let's just allocate bigger chunks altogether. There's maybe a little bit of a capacity trade-off because I may not fill the extent with data from the file, but it's still probably worth it. Discs are pretty big. Okay, so for EXD4, I have one inode profile. That inode is 256 bytes. And so I store 16 in a block. Actually, did I say, ah, sorry. The sector size that EXD4 uses is actually 512. So I can store two of these in a sector or I store 16 per 4K block. The inode contains, the inode is designed to contain all of the metadata information about the file, that the file system needs to modify it, properties of the file that I might be interested in, and other such things. So the inode has to allow me to find the rest of the file. So starting from the inode, I should be able to find out where all the other data for the file is. Clearly it's not in the inode, the inode is only 256 bytes. The inode contains metadata like permissions, and also timestamps. So creation time, modified time, other types of things. So this is all stored in the inode, and again there's one inode per file. Like everything on your computer, inodes are named and organized by number. So there's no name in the inode. The inode on this system has a number. So here is an example of using, this is something that you guys can try at home, using a tool called debugfs. What I'm doing here is I'm asking it to tell me about inode number two for the file system that's mounted on this device. So this is inside, this was an EC2 virtual machine. So inode number two tells me it's a directory, which we're gonna talk more about in a minute. It gives me information about the mode. So these are the permissions associated with the directory. Who's good with their octal modes? Who can tell me what this is? Oh, Doug, no, no, no, no, no, you. Somebody from this year. Oh, come on, seven, five, five. Yeah. Really?  What's that? Nope, seven, five, five is not a user. It is most definitely not a user. Yeah. Yep. Yep. Right, so seven indicates that the user can, the user who owns the file can read, write, and execute it. Read is four, write is two, execute is one. Five indicates that the other users in the same group can read, read is four, and execute. What does it mean to execute a directory? Who knows? Directories are not executable. So how have I overloaded this bit? Yeah. It means I can list the contents of the directory. So a seven, five, five directory, any user can list the contents. So five is for other. So ignore the top zero, that's for sort of special flags. The bottom three octal nibbles here describe the permissions for the user who owns the file, for other users in the same group, and then for everybody else. So everybody else is allowed to read and list the contents of this directory, which is good in this case. And we'll talk about why that is later, because this is an important directory to be able to read the contents. Okay, so the user and group zero and zero. Again, whose sysadmin hand is very dirty? You can tell me, who is user zero? Root, it's group zero, wheel. So this is the root, this directory is owned by the root user. The size of the directory here is what? 4K, right, one block. So I've only allocated one block to this particular directory. There's some other set of information and then here are all these timestamps that are associated with the directory. And I'm going to admit that I cannot remember what these mean without checking Google. One of them, you'd be tempted to say, oh, it's the creation time, it's the access time and the modification time, and you'd be almost right, except one of them is not the creation time.  Yeah, so I think the C time, I think this is actually the creation time. This is January 8th, Sunday, 2012. And then down here, it's telling me blocks, right? So remember, from the inode, I need to be able to find all of the other blocks that store the data associated with this file. Now again, in this case, this file is a directory, but don't let that confuse you because as we'll point out, minute directories are just special types of files. So there is one block, data block associated with this file, and this gives me the index of that block. So by finding the inode, not only can I find out a lot of information about the file, but I can find where the file is stored on disk. Any questions about this? Okay. So now the question is, how do I find this data structure? So clearly, once I get to this data structure, I'm good. If I can find this block on disk, I'm in good shape. I can find the rest of the information about the file. So it turns out that for EXT4 and similar file systems, I need to be able to start somewhere. And so what EXT4 does is when you format the file system, it creates all the inodes that that file system is ever going to have. And it stores them at well-known locations. So without any other information, or just by reading a small amount of information that's always stored at the same place on the disk, the EXT4 file system can map every inode number to the inode location on disk. This is part of the storage capacity of the drive that you lose when you format it. So when you format a drive using the EXT4, some amount of it is reserved for inodes. So this is what your drive might look like after you format it. There are some inodes here, I've allocated eight of them and the rest of the drive is set aside for actual data. Some amount of capacity is gone. So what are some consequences of this fact? So I create all the inodes at format time and remember there's one inode per file. Yeah, what's that? Oh yeah, no, of course, yeah. If you blow away inodes, you're gone, right? It's just, it's not good. But that's true of most things on disks, to be honest with you. Well, actually, I guess that's, yeah. If you fired a random byte of data at the disk and you hit a metadata data structure, you better hope you hit a timestamp because otherwise you're in trouble. I mean, most of this stuff's pretty important. But what else? All the inodes are created at format time. They're all put there on the disk, yeah. Yeah, so, well, there's two consequences. One is that I can run out of inodes. This actually happened to me once. I had a file system that had a lot of very small files and it turned out that I ran out of inodes before I ran out of data blocks because when you format the disk, the file system has to make a guess about the average file size because it's gonna say, okay, I've got 16 gigabytes of disk space here. How many inodes do I need? And so the file, when you format, you can actually specify this as a parameter. So I don't remember, okay, there it is. The XD4 creates one inode per 16K of data blocks. So if your average file size is a lot smaller than 16K, you're gonna run out of inodes and the disk will report being full. It's not full. It's really irritating. It'll say the disk is full and you'll run your handy DF command and it'll say 50% of it's free. And you'll start scratching your head, but then you'll remember that we had this conversation and you'll run DF-I, which gives you the number of free inodes and you'll see it's zero. And then you'll be in a lot of trouble, actually, because there's really nothing to do at that point. So yeah, so you can run out of inodes before you run out of file contents. The other consequence for how we use the disk is that the inodes are not necessarily going to be close to the contents of the files that they're describing. Remember, the inodes are all of these fixed locations throughout the disk. So in my little diagram, I put them all here. Now, as disks get bigger and bigger, would it still make sense to have all the inodes at the beginning of the disk? No. So what EXD4 actually does is it puts inodes, it puts groups of inodes at various points throughout the drive. It takes the big drive, it sort of carves it up into little mini drives, and then each mini drive has a group of inodes. And I think it tries to use inodes for, it tries to match up the data blocks with the inodes that are close by. But I don't think it's required to do that. It can potentially use an inode close to the beginning of the disk with data blocks that are at the end. Of course, the performance of that file is gonna be potentially problematic. Okay, so now let's come back to talking about directories. You guys might think Howard Directory is implemented, and I just showed you some information about an inode that actually belongs to a directory. So file systems implement directories as just a special kind of file. In a lot of ways, there's nothing different about how directories are named. And there's a special bit in the inode that allows me to tell if this inode, if this inode is a directory. But other than that, directories are just files, except for the fact that the file system maintains the contents of that directory in a way, as its own sort of separate data structure. So the data blocks associated with the directory make up a data structure that allows the file system to map names to inode numbers. So let's talk about how this works. So here is, here's me, so here's a command that will allow you to list the inode numbers of a particular file or directory. So ls-i, here I'm just doing this for the root directory, and it prints out root and two. Why two? I don't know, actually. It's just a magic number. I think it used to be zero, and then maybe EXT3 used one, and so they used two. We'll talk about this in a minute, but there's always a well-known, hard-coded inode number for the root directory of the file system. This is important because I need somewhere to start when I start translating paths, right? So I have to, the file system needs to know what the inode number of root is. From that point, it can bootstrap itself and I can map other types of names. So now let's look at the contents of root. So here's the root directory on a pretty typical Linux system, and this data structure inside the directory is mapping names, bin, to numbers. So it says, inside this, there is a name called bin, and if you wanna know more about bin, check out inode number 131,073. Why is it nice, sorry, question? Sure.  Yeah, so that's a great question. If I created a file system, like you create like a huge file system of 10 thousands of directors, right? Maybe you could do this as some sort of conceptual art project, right? And you could have a computer with like a million directories and nothing in them, right? Maybe you could all have the same name, right? That'd be kind of weird. And people could sort of play with the system and they could, no matter where you go, there's nothing. Anyway, I know it's like a statement about modern life or something. What's that? Every path is equal. Yeah, yeah. Yeah, just like AAA or something, I don't know. So yeah, if you create a lot of directories, you can run out of bin. The directories do have binos as well. That's a good question. So, but why is it nice to allow directories to be like files? This means directories can grow, they can shrink. I can move directories from place to place. Why is it nice to sort of reuse some of these features for directories? Why do I need to? Why can't I have every directory just be a fixed size data structure? Why wouldn't that work? Yeah. Yeah, I mean, essentially if I have a fixed size, then I have a fixed size for this data structure, and so you might try to create a new sub directory and it would say, sorry, I'm full. And of course, that's not how things work. So directories can get arbitrarily large.  If you look, what is the size that LS reports for directories for most of the directories that you've seen in your life? If you guys ever notice when you do an LS, it'll tell you a size for the directory. What's the size that it reports? Anybody want to guess? Yeah. 4k. And that's because there's one block set up for that directory by default. Now, if you take a directory and you put lots and lots and lots and lots and lots of files inside of it, what you'll see is that size will actually start to grow because the data structure that's required to map all those names to numbers has gotten big enough that it's larger than 4k and the file system has started to allocate extra blocks to that directory. So yeah, you can do this at home. Okay, so now I can see here how I've, this is one particular directory and then here I've done this for a subdirectory of root and it's doing the same thing. It tells me that here is there are two directories in here. One is my home directory, the other is the home directory for some Ubuntu user. I don't know why that's there. And here are the I know numbers. And actually, I should back up. All the directory does is names to I know numbers. So it doesn't say anything about what these things actually are. It just says there is a name called Ubuntu. If you wanna find out more, go to inode 394656. Okay, so yeah, so we already talked about this, right? So going back to stat two, you can see this is a directory. Any questions about directories implemented as files? Yeah, no, no, so okay, that's a great question. The root directory, I don't know if the root directory has to be in the same location on the disk. The convention is that the I know number for the root directory is fixed. So let me go through an example. I think they'll make that clear. Okay, well, I'll come back to this, right? So let's say I wanna open a file. So this is one of the things that file systems have to be able to do, right? I have to be able to translate this path to a number. And specifically now, you guys know that what I want is I want an I know number so that I can find out more about this file or directory potentially and figure out what's in there, okay? So I've given open a path and what I need to do is translate this string to an I know number. Here's where it's critical that the root I know is fixed because if it's not fixed, I don't really know where to start. So I have to have a starting point so I can bootstrap the process. So to translate the root, there's no directory above root so there's no directory to look for the root entry in. Instead, I use a convention where it's fixed to be summed up. Does that make sense? This is how I start. So now I start at root and I open up inode two and I know two is a directory, it's the root directory and I interpret the contents of it and I look for ETC. And let's say that ETC exists and I find out that the I know number corresponding to it is whatever, what's the next thing I do, okay? So now I load the inode for 393218. I found out that this is also a directory. Now this could fail at any point, right? I didn't say that this path had to be valid. It turns out it is valid and it is a file but if at some point, like for example, maybe ETC default is a file, not a directory. So what would happen is I would get here and I would try to continue to translate the path and I would realize, oh, I've hit a file and this would fail. So in this case, I find default, default has its own I know number and then I go and I just continue this process. I get an I know number, I load the directory corresponding that, I use that to map the next component of the path name to an I know number and I continue until either I'm finished and I've consumed the entire path or I have an error occurs and I can't continue. There's a missing name or the name is in a directory or whatever and I just keep going. Questions about this? So what does this mean about I know number two? How often is I know number two used? Like a lot, yeah. So this would be a great structure to cache someone, yeah. Oh no, I can cache anything here and I can cache any part of this process. So it's possible that at any point when I'm doing this, what I find is that the file system cache is returning contents rather than going to disk. No, no. I mean, did you see those I know numbers? Where is this? So lost and found maybe, but I think that's a bogus I know number. I think that's made up because lost and found might be a bogus directory. But home, do you think this is a well-known agreed upon I know number? If so, it's weird. I wouldn't use 39321, I would use like two, like three. What's that? Three is dev, yeah. So PROC is one, right? Well, okay, so it looks like I have a problem here. PROC and Sys had the same I know number. What's that? That's lost and found it. Yeah, and that's because PROC and Sys are both are not real files. They're pseudo files that are provided by the OS. So it doesn't matter. If I try to open something in PROC, EXT4 is not involved anymore. So it just gets out of the way. So it doesn't matter. So I wanna go back and show you a little bit about how I can print out information about an EXT4 file system. So this is a tool that reads information from a part of the disk that's known as the super block. So the super block is a data structure that's read by the file system initially and contains sort of all of the information required to interpret the file system. So for example, the locations of the inode, the blocks of inodes would be stored in the super block. So this gives me where this file system is mounted on. This is a root file system. It's a magic number that identifies it as an EXT4 file system. It says it's clean. That's nice. It's shiny and new. That's not what it means. We'll come back to that. It gives me a inode count and a block count. So this is the number of inodes that have been created on the system and the number of data blocks as well. It tells me how many data blocks are free and how many inodes are free. It tells me the block size. Okay, so blocks per group. So you remember before I said that EXT4 divides the file system into smaller chunks? Each chunk has its own inodes. So this is the number of blocks in each group, the number of inodes in each group. Some information about how many times it's been mounted, the maximum mount count before the file system will run some internal consistency checks to make sure that everything is okay. And then on page two, there's actually a lot of information here. I would encourage you guys to run this yourself. It's kind of cool. The number of writes that have gone onto this file system in its entire lifetime, that's kind of cool, right? And then, so down here, and this goes on for a while, this is actually information about each block, sort of each part of the disk. So group, or sorry, each group, right? So each group, this is group zero. Here's where the block bitmap is. That's the data structure I used to allocate data blocks until which data blocks are free. It tells me where the inode bitmap is. That's the data structure I used to allocate inodes. It tells me where the inode table is. That's the actual array of inodes on the disk. And then it gives me information about this particular group. So in this case, you can see that there are no inodes that are free in this part of the disk. However, notice that there are still free blocks. So this particular group has run out of inodes, despite the fact that there's still blocks that are free. Yeah. What's that? The tree data, there has been no tree data structure that we have talked about yet, but we'll get there. Yeah, I mean, again, there's other ways to do this, right? Like, you could set up fancy trees and other sort of cool data structures that you talked about in your algorithms class or in data structures class, and you could apply them to file system design and people have done that. And it turns out that sometimes these easy things are the things that are easiest to get right. For example, having inodes that fix locations on disk is kind of nice. Makes certain parts of the file system pretty easy to build. Okay, so we did this. So now, let's say that I'm actually trying to modify, I don't think we're gonna get through this today, but I'll just sort of introduce this problem. So this is the next problem, which is we've talked now about how file systems map names to I know numbers. Once I have the I know number, then I can find out all the information about the file I need to know. The other challenge is translating the offset within the file to a data block. So let's say this read wants to write some data to a file handle at a particular offset. I need to be able to find any byte within the file, right? Any range of bytes within the file. If you give me a file name or an I know number, in this case, if you've already done the translation, and you say give me byte 62, I need to be able to do that. And so this is the next thing that we'll talk about and we will start up with this on Friday. I'll see you then.


It was my desire to make sure for my mom that there were people at the school house for other mothers who wanted their children to be in a situation where they were safe. People took care of them but more importantly helped them to change their present life situation through a great education. That's why I do what I do. Nothing is more important to me than making sure young people make the right decisions for their lives and they become productive. And here's what you're pushing is don't give up because what you do is you show them what happens when you give up and as long as there's breath in you that says I am not giving up then there's hope. A mentor says hey look I understand what you're going through. I understand the trials and tribulations of life. I get that. I also understand that there's bumps in the road.  But I didn't. And I'm gonna help you through. That's a mentor. That's somebody who cares about your next steps in life. And here's the key and not asking for anything in return. That's a mentor. Join us for American Graduate Day on October 14th.