Concurrent Programming Made Simple
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Diegues, Nuno
Riegel, Torvald
This talk will present Transactional Memory, a programming abstraction for managing concurrency, both in multi-threaded programs running on multi-core processors as well as in distributed cloud infra-structures. This talk will present Transactional Memory (TM), a programming abstraction for managing concurrency, both in multi-threaded programs running on multi-core processors as well as in distributed cloud infra-structures. TM allows programmers to declare which parts of a program need to run atomically (i.e., as indivisible steps), while a generic implementation involving compilers, runtime libraries, middleware, and hardware support for TM takes care of ensuring this atomicity at runtime. The two presenters will give an overview of recent advances, standardization efforts (e.g., for C++), and open-source tools providing support for TM (e.g., GCC).
 Tovador Riegel and Nuno Dieg. Thank you very much. Hello, welcome. And my name is Tovador Riegel. I work for Red Hat's toolchain team on various things concurrent on parallel. And I am Nuno Dieg, PG student from Portugal. And we'll tell you something about transactional memory today. So, before I start to get to the beef, let's actually set the scene here, right? So, this talk is about concurrent programming. And concurrent means that things happen at the same time, but they're not independent, right? So this is slightly different to parallel programming where it's say they also have met the same time, but they're usually independent, you know, like parallel lines. And when you have concurrent actions, but usually, you know, one conceptual program state, you need to make sure that the concurrent actions actually synchronize, right? So that it can make sense out of the state transitions. And when you look at multi-course, for example, we have shared memories, or shared state. And we need to synchronize on a shared memory, so we have this thing called shared memory synchronization. Then you add transactions, and then you get the name transactional memory where it comes from. Another topic, or another concept that is very important is atomicity. And in the context of shared memory synchronization, atomicity means that something happens as an indivisible step, right? If you're a database person, think about this as atomicity and isolation combined. And this is why we have hardware instructions such as x86 compare exchange. And to illustrate this a little bit further, why atomicity is important, let us act out a small situation that everybody of you will have experienced already, right? So sometimes you have something like a narrow hallway, right? Just people need to pass each other. So we're working to each other, and usually somebody will step to the side, but sometimes the people do like this, you know? And then they bump into each other. We can't let computers do that. And so what is the problem here? The problem is that we are facing each other, and I see the side, and I think it's empty, right? Nuno sees the same side and also sees things as empty. And then we do the same steps, right? We're in the same situation, and this is what's happening. So what's going on? The problem here is a lack of atomicity. If these two steps of seeing the side and stepping over would be indivisible, we wouldn't have a problem, right? I see it, I go to the side, and then Nuno makes his turn, right? Or on the other way around. So if we had the two actions atomic, then we would not have any problems. So this shows you how atomicity is important, right? So it would be doing something like a test and set that you have in hardware as well. This is how you can remember why atomicity is important. And so coming back to the transactional memory, if you want to remember one thing about transactional memory, then please let it be this, right? Transactional memory is a programming abstraction, and it allows programmers to declare which sequences of code should be atomic, instead of requiring to actually implement how this is done. This is the underlying vision. This is how all the different kinds of TM, you know, what they give you. And instead of the programmer, we have generic implementations that ensures atomicity. So this is not specific to a particular program or something like that, but it's generic, right? And it can be purely software, it can be new hardware, it can be a mix of hardware and software. And our focus in this talk will be TM for high level programming languages. So what we're going to do is that we have the first part in which I will talk about TM for shared memory on a single machine. I'll give you an overview of the proposed C and C++ language constructs. I'll give a peek in the GCCS implementation of that, and I'll make some comments on performance. Next up, Nuno will talk about the TM for distributed shared memory, so multiple machines, but with a shared memory abstraction on them. He will discuss strong consistency and implementation of top-of-infinis band. Afterwards, we'll have a short Q&A. If there's something very short, quick, you know, clarity question that you have, scream it. If it's short, I'll answer it. Everything else goes at the end, please. And one note that I also want to send out is that TM is still rather new. The idea, so the first idea has been proposed 20 years ago, but real research didn't start until about 10 years ago, and it's still ongoing, heavily. Standardization for C and C++ started about five years ago when people got together informally, and we have ISOC++ study group since mid-2012. There's GCC support on the C and C++ site since version 4.7, and we're finally also getting real hardware TM implementations out there. So, it's been out there for a long time, but special purpose, arguably. Blue Gene kind of like it, and it fills real mainstream CPU that has transactional memory hardware on it. Intel's has more, right? If you have a new laptop, you actually might have it on your workstation with that chip. So, how do the C and C++ language constructs look like? So, we have this transaction atomic construct there, and this allows a programmer to declare that the following compound statement must execute atomic way. So, in this case, the load to X and the potential load to Y, and the store to Y will all be executed as one indivisible step. I'll give you an explanation of the specifics of the metrics later on. There are no data annotations necessary or no special data types necessary, right? And in those transactions, you can run existing sequential code. You can do function calls, you can have nested transactions and so on. However, the code in transactions must be what we call transaction safe. And unsafe code, for example, is the use of logs or low-level atomics, assembler instructions, volatile memory accesses, or simply functions not known to be safe. However, the compiler will actually check whether your code is safe, right? So, you get a compile time checking guarantee for that. And because of functions unknown to be safe, for cross-compilation unit calls or for indirect functions, or indirect calls, or function pointers, you need to annotate your functions with this transaction safe attribute. For example, you say here that you make the claim that foo is actually transaction safe. For further information, have a look at the C++ specification best as to just web search for the paper number there, this end thing. Now, this is concurrency, and so there are nasty little details. So, here's a slide about disinconnization semantics. Transactions extend the C11, C++11 memory model. So, the memory model is the thing in the language specification that defines the execution of multi-threaded programs, right? Which behavior you're actually allowed to have. So, transactions, or the semantics of transactions are integrated into this memory model. And the basic guarantee is that all transactions are totally ordered. And this order contributes to the happens before relation. Happens before is basically the relation that models what happens ordered after what other thing in your program if you have a multi-threaded execution. And TM ensures some valid order. So, the TM implementation ensures some valid order that is consistent with happens before for every execution. In other words, this means that one transaction happens after the other, and it makes sense with respect to the other synchronization going on in the program. So, if you have the intuitive meaning, it's actually pretty easy to understand, right? Note, however, this does not imply sequential execution, right? This is a correctness guarantee. If the transactions are actually independent, the implementation is also free to execute them in parallel, for example. But it allows you to reason about the transactions as if they would be executed strictly one after the other. However, there's a gotcha, and that is that data-raised freedom is still required. That is the case throughout all C and C++, right? Whether you're using logs, low-level, Tomics, whatever. And it means that if your program has a data-raise, you get undefined behavior. So, I have a small example there about publishing data, and you have one thread doing initialization of the data, and then it uses some transaction to make the data by setting a flag. And the other thread uses the transaction to use the data if it has been published. This year is correct usage. Doing something like that is not, because if you do the temporary read in front of it, you have a data-raise in your program, and as a result, you get undefined behavior. But as I said, this is something that you'll have to consider anyway with the C and C++ programs. And the reason why we have that is that this actually allows efficient implementations for the compiler. One of the biggest benefits of transactional memory is that it supports modular programming. And so, that means this is because programmers don't need to manage the association between shared data and the synchronization metadata. So shared data here is application data, things that you actually need to synchronize on and define your program state. And the synchronization metadata is something like logs. And the reason for that is that because we have a generic TMA implementation that takes care of ensuring the atomicity. So that's one thing. For example, programmers don't need to have a locking convention or don't need to follow it. The second thing that kind of follows from that is that functions containing only transactional synchronization compose without that lock. So the nesting order of transactions, for example, does not matter. And however, you cannot expect another thread to make progress in an atomic transaction or concurrent with an atomic transaction. This wouldn't make sense, right? You're requiring the compiler and the environment to make your transaction to run in the visible step. You can't go then, oh, this is one in the visible step and oh, and by the way, in between, I want this other thread to make another step. So this would be conceptually incompatible. And at the bottom, I'm giving you an example for that, right? Comparing transactional memory to lists. So the example is that we want to move one element from one list to another. And I have this very little neat small generic function here where I remove from run list, insert into the other. Synchronizing that or making that thread safe with an atomic transaction is easy. You just put it in atomic transaction, say move AB in element 23. If you do this with locks or try to do this with locks, it becomes difficult. First of all, where do you put the locks, right? Are they in the list or externally to the list? So if they're in the list, you need to add an interface for the move functions, for which you can query the locks that the lists actually have in them, right? If you have done that, the next problem is that how do you acquire the locks in a consistent order? Somebody is calling move AB and another threat is calling move BA, right? If you just acquire the lock for the list one here first and then list two second, you'll run into deadlocks. You don't have the problem with transactional memory because the implementation will take care of this. If you try to do something as generic like that, the locks, it becomes messy quickly. Switching gears a little. So how do we do it actually in the implementation? So here's an over look of our peak into GCC's implementation. And it has two sites to it. One is the compiler site and the other is the TM Rantzheim library site. And there are three steps essentially that we do in the compiler except parsing and stuff like that. So first, we ensure the atomicity guarantee. We don't ensure that your program is data-race free, but if we can assume that your program is data-race free, then we can ensure at compile time, at atomicity for your transactions. And this works because we check all transaction-safe code whether it is indeed safe. And transaction-safe code is the code that's either implicitly transaction-safe because you call code from a place that should be transaction-safe or whether you have annotated the functions accordingly. And once we have checked all this code, we create an instrument that clone of this code. And so this code is then the transaction-safe functions and so on. And what we do essentially is that we take all the memory loads and stores and rewrite them into so that they have a call into a TM Rantzheim library that will then perform the memory loads and stores. So we hook into the load and store mechanism essentially. Similarly, we redirect the function calls to the clones. And as a result, we have both an instrumented code path, where the loads and stores are intercepted, and an uninstrumented one where things are just like before. And then finally, we generate begin and commit code for each transaction. And one thing that's worth noting is that we allow the Rantzheim library to decide on every transaction start whether uninstrumented or instrumented code should be executed. And the whole point of delegating to a Rantzheim library is really that we get implementation flexibility. So we don't need to generate synchronization code in the compile time, or at compile time and by a compiler. But if we redirect, we have a little bit more overhead in terms of the function calls, but when we have full flexibility at Rantzheim to do something different and better potentially. So on the Rantzheim library site, and the Rantzheim library is called libITM in case of GCC, this is the thing that actually enforces the atomicity at Rantzheim. And libITM currently contains different software only implementations called STM. So these are TMI implementations that do not need any special hardware. And the default here is one that does write through essentially to memory with undo logging and uses a set of internal logs to protect concurrent accesses to the same piece of memory between different transactions. So the library will manage a couple of logs, do the automatic mapping from the memory to the logs, and then run a kind of a little bit of vault algorithm to actually make this thing. So this uses the uninstruated code path. The currently in libITM also make use of hardware TMI implementations. So HTM. And one thing that you might not be aware of is that all the HTM implementations out there with the exception of a kind of special mode on the PowerPC stuff is that they're all best effort. In the sense that they do not guarantee you that they can run all transactions. For example, if your transaction, you try to access more memory in a hardware transaction than there's hardware capacity to track your accesses, then it will simply fail and that's all you know, can't do. So you always need to have a fallback for your hardware transactions. And that means that, for example, you need to fall back to locking, you need to fall back to an STM and so on. So the HTM by itself is not really a solve-it-all thing. And libITM currently uses HTM with the global lock as fallback. That's very simple, but it's also very non-scalable fallback, obviously. The good thing, however, is that it allows us to use the uninstruated code path for the hardware transactions. So that the hardware transactions really don't have any overhead because of instrumentation. We currently don't have any hybrid STM, HTM implemented yet in libITM, but this is something that we'll hopefully have at some point. The idea there is that we have hardware transactions that are very fast and then we can fall back to something that is actually still scalable. So two more slides about performance. And performance is a difficult topic for TM because TM has seen quite a bit of hype. And so let me first note that, like everything else, it's a tool that's not magic, right? And the performance goal of TM or the performance goal that every sane person implementing TM would give you is that it tries to provide a useful balance between ease of use and performance. It does not claim to provide the most useful balance or the only useful balance, right? But it tries to make concurrency simpler for programmers and still deliver decent performance. The goal is always to make it simpler, you know, except by considering some corner cases. And then we see how good we can get. And currently it looks like performance can be decent. And the other point is that right now I don't think it's meaningful to try to draw conclusions from TM performance. And this is also one reason why I don't give you any performance plots as such here, because it would mostly be misleading. And I'll tell you why. So first of all, the implementations are work in progress. So libITM's work in progress has not seen a lot of tuning. For example, the HTMs are first generation implementations for the hardware implementations. I would claim that they're also work in progress. For example, they lack features that would be very useful for hybrid software hardware TM implementations. And second, performance heavily relies on a lot of factors. Many more than might be obvious. So for example, it relies on the hardware, obviously. It relies on the compiler, what kind of codes it generates, the actual TM algorithm used. The HTM implementation, for example, you know, how many memory accesses can it track for transactions? So use it, what kind of cache or dedicated buffer it uses to actually track accesses? Which other instructions can it handle, right? There was a Spark hardware TM implementation that was so restricted that you couldn't do function calls. That's not useful for general purpose TM, right? It's useful if you use it in a very, very tiny controlled way, but it's not useful for, you know, the high-level TM abstractions. The allocator matters, because the allocator decides, you know, how you end up moving your data around and where your data gets located in memory, and there's false sharing issues and all that stuff. Whether you use link time optimizations or not does matter, because it affects the overhead. And these are all just all the factors that the implementation actually has control over. Only the application and the programmer has control over the actual transaction conflict probability. How long the transactions are, what the load-store ratio is, whether there are many read-only transactions and so on, memory access pattern, data layout, allocation schemes, again. Other code executor transactions and so on. So there's a lot of stuff that's going on. And the third point I want to make is that I mentioned that TM is still fairly new. That means, because it's a programming instruction, that people actually have to use, right, actively, that we are still on the kind of trick and an act situation. So I'd like to, I'd love to tune LibITM for real-world workloads, but we currently have very few of them, right? So any tuning will be guesswork. Nonetheless, let me try to give you a few rough estimates that hopefully still hold in the future for TM performance. TM performance can be characterized by both what's typically called the single-thread performance, so the single-thread overhead, and the multiple-thread performance, so scalability, essentially. Regarding the former, we can say that STM is a slow and sequential code. You have to synchronize, so there will be more stuff, right? On the other hand, how much overhead there will be can vary a lot, from doing just the one critical section to, you know, doing something weird with memory access. STM will probably be a slower or equal-to-course locking. This is because we synchronize, so we at least need to have some kind of atomic instruction, at least if we do a change or something like that. So that's like a lock. HTM will be, or is, about as fast as uncontended critical sections, or even faster, because you don't need to change memory at all. And depends on how it's implemented and so on, but HTM can be very fast, provided the hardware can actually run your transactions, right? If you do a Cisco in your transaction, it's not a good probability that, you know, we will actually be able to do it. It depends on the HTM again, but this is just an example. Regarding scalability, we can say that most STM algorithms out there typically scale very well, right? You say you have a shared data structure, you move elements, there's no real logical conflicts in your transactions, it scales well. But this is less likely the lower the single thread overhead is, right? Because if you want to do, you'll have a lot of scalability, you usually do more, you can't just go coarse-grained lock or something like that. HTM also scales well, but again, the fallback is a problem. So if your fallback doesn't scale well, and you have to use the fallback often, bad. And so this is why I said that hybrid STM-HTM applications will hopefully help you to get the HTM performance out most of the time, but still have a fallback that does not suck in terms of performance. And one point that is worth noting is that the TM runtime libraries adapt at runtime. They currently do this to a little extent, but there's a lot more that they can do. This means that of all the possibilities here, there's a good hope, that automatically the implementation will pick the right thing to do, right? Which would be very hard to do for programmers. Nobody wants to maintain, and it's, you know, in a general library, maintain three different or five different synchronization mechanisms, just to be able to be high performance when it's used in different ways. And if you're still worried about that I didn't give you actual performance data, there's a very easy way to get it, you just need to use it, right? So grab GCC 4.7 or more recent, use dash afknew-tm, and then measure performance on your applications, right? Read the C++ video specification that's out there. Report about your findings, blog about it. If you think there's a bug or an inefficiency in GCC's implementation, report a bug, please. If you have feedback for the constructs specified, then it might be a good idea to get involved with the ISO C++ Tm specification, so this is study group five. And if you really are more interested in the code, please dive into, just dive into the implementation, see what's there. The comments in the libITM code are fairly extensive. So even though this is concurrent code, it should be relatively easy to follow. And there are many interesting things to work on, for example, improving the auto-tuning and so on. And with that, I'll let Nuno discuss something completely different. Alright, and so as you can see now, we're going for a different world, but we'll still be addressing the same problem. And until this point, we were looking at a single machine, and we already understood that we need to make sure that these concurrent accesses to data are regulated. But we typically like to build distributed applications. And there we have many, many of these machines. And the point here is that it would be very interesting if we could explore these independent memories, but look at them as a single shared abstraction. And so what I will show you basically is how to do this. And we will use the same abstraction of transactional memory, but in a different environment. And so the approach that we'll refer to is basically distributed transactional memory. And similarly to what we saw before is that we are bringing transactions to the top of the software stack. So they are no longer buried down deep in your data store engine, but actually they are up there close to the application. And so this allows for dynamic transactions, meaning you do not have to specify a priori how long they are, which positions they will access. And this will be straight embedded into the application logic, which is also favorable for long-lived transactions. But a bit different from what we saw before from Torvult is that now we have to worry about these three things down below. So namely persistence, because people in distributed applications enjoy this a lot. And the distribution itself, because this raises other concerns in terms of, for instance, the costs of communication, and of course, full tolerance, because this is the main driver of why you're building distributed application in most of the cases in first place. And so just to give you a quick list of concepts, imagine you have this set of data up here and you have your distributed system. What we have until these points from Torvult is that we have a single machine. But now we basically just replicate this data because this is not full tolerance. And so this is what we call a fully replicated system. However, if you're going to change a bit of your data, you have to communicate this to everyone. And if you're going to scale to a lot of machines, this starts to become highly costly. And so basically what you do is that you only replicate a given data item in a subset of the machines, which is partial replication. And so considering this, I mean, just try to briefly convince you of why you should use strong consistency in these scenarios. And for that, let's consider what has been quite popular until some years ago and started perhaps 15 years ago, which is eventual consistency. So if you have this client up here which says to the server, I want to change this data item. It's no longer green, it's yellow. And then after a while, it says, I want to read that data item again. And it gets forwarded to a different machine. And actually it sees what was there before and not the most up-to-date thing. And this is a reflex of what we typically say in popular saying that eventual consistency is no consistency at all because it's not formally defined. You have to dig into your system and understand what is providing to you to then realize what you can do of useful with it. And this varies from system to system, and it's terrible for programmers. And so in this case, the problem is that the replication was still ongoing. And so this is a very similar problem to what you might have witnessed on Amazon, for instance, where you say you want to buy something and after a while it's no longer in your buying list. And then it pops up again. Or even in your Facebook posts, you write something and after a while it's not there, and other people can see it. And so this has convinced a lot of people, and in most recent years we are now getting a lot of popular systems which actually give you the abstraction of a transaction. But you might still have transactions which are stronger than others. And one example is that you can use snapshot isolation in transactions. But it's still not perfect. And let me present you an idea of why that is the case. So you have here a game where you have two players and they can never be in two contiguous slots. So what they do is that they look around, they see what's there, and they choose the next move such that they will not collide with the player. And that is what they both do. Then they concurrently move, and they move next to each other breaking the rules. Basically what happens is that the positions that they wrote did not intersect. And snapshot isolation will only abort a transaction if it writes to something that was written concurrently. And this is what is known as a writes queue anomaly. But notice that if they had moved one at a time, as we presented to you earlier, with a notion of sequentiality that comes from the atomicity, this would not have happened. And that's what you get with serializable transactions, is that every execution that is allowed is equivalent to sequential one. So that's very easy for programmers to reason about. And basically that's the approach that we try to take, is that we embrace serializable transactions, which might be costly, but for overcoming that we try to explore several things, such as partial replication that I showed you earlier, and we can build scalable protocols on top of that. And you might have heard of recent proposals such as Google Spanner, which are trying to move into this direction. And so what we are doing here is not trying to save, to solve the hunger in world. We are aiming for simple use case, but hopefully the common one. And for that we try to give a framework, which is easy to bootstrap, has enough, fast enough scalability and performance for most use cases. And this has a lot of details which are hidden from the programmer. Of course, this will not give you the ultimate performance if you really need to have something critical. And the approach that we take starts from a very key point, which is that you specify the domain of your application in a domain-specific language, and all of this in an object-oriented way. And through this we will hide from you concurrency control, persistence, and data placement in your distributed system. For some things we might still need your help as a developer, and for that we give you APIs in an object-oriented manner, for which you can do distributed execution of code and ensure data locality. And then we still have some things only for expert programmers if they want to go there. And so for the rest I will use this guiding example, where we have phone books which have contacts, and the contacts may be shared among phone books. And this typically maps to some Java classes or whatever your preferred language. And then they might have... they will refi these relationships over there via some collections or references, which have to be updated bidirectionally and so forth. And if you consider a typical approach in the industry, which is to use, for instance, Ibernate, you will basically write some codes resembling this. And so you have to put these two collections on the two sides, which you have to manage every time it changes one side, you have to remember to go on the other one and update it accordingly. You have to worry about these annotations and manage the unique IDs of the classes and so forth. And actually this approach we believe has a lot of good things underlying it. And so we will be quite close to this, that's why I'm showing this example. But we'll try to clear up a bit the view and focus on what's actually interesting. And so the DSL that I talked to you about, we call it Domain Modeling Language. And for the example that I provide to you, basically you only have to specify the classes that you have in your domain. In this case it's very simple, have a phone book, a contact, their attributes. And then we say that they are related, and they are related in this many to many fashion. But this is written in separate file, domain file, in a Java-ish syntax, which should be easy for most to understand. And this is all of it. You've already understood it, and then you just saw it for the first time. And so as I told you, it's a DSL, and basically the framework that we have will then use this DSL to generate code. And it will generate code with a well-known interface. And this will basically boil down to mapping the entities to classes with getters and setters hiding all those things that I talked to you about. And then making the relations automatically managed in a bidirectional manner. And so the framework will start from your DML over there. So the application has the domain written by the programmer. Then some code generator will be triggered, generates the classes. And they are placed in the application such that the programmer can extend it, these domain classes, with the behavior, because he only tells us, I have a book with this structure. It does not tell the behavior. That's his job to do. The programmer still needs to do something, right? And then in the end, these interact with the rest of the application. And so an example for the classes that I presented to you are basically these. Is that you have the common getters, setters for all the things. And all the concurrency and persistence distribution are hidden in there. So the interface will always be the same, regardless of the actual code implementation. Pretty much a bit like what we just saw for the GCC. And so then what you can actually do is to choose different transactional managers and backends for persistence. And you do not really have to change the application. You only have to specify this in a configuration file. And for the rest of the talk, I will use the guiding example of using Infinispan, which is a data grid open source from Red Hat. And so what we actually do in this particular example is that we have to map your domain to this persistence. And Infinispan is a key value store distributed one. And so we will somehow do this mapping such that you do not have to worry about it. And then you run your transactions in our application. We will map these two transactions in Infinispan and we will ensure the serializability that you wish. But what matters is that programmers are not aware of these parts. They might even be able to see it if they want, but they don't have to. And that's what's important. And this is regardless of the backend that you're choosing, whether it's Infinispan or any other. And so if you were still using the other process I told you about, like Ibernates, for instance, I told you we wanted to clear up a bit the landscape. And so this is what an application would look like using the domain that I specified. If you go with DML, you can clear up this. And in the end, you only have the atomics here, which are related to what we saw in the first part of the talk. But nothing else is related to concurrency or persistence. It's completely hidden and even distribution. And so if you want to run an app, an application, which resembles what I just described, basically have to specify only a properties file and then have to point to the configuration files which are backend dependent. In this case, I'm using this example. In this example, we need to specify some Jgroups file for communication distributed system. Just use a prebuilt one. We have to configure the Infinispan. Well, it's rather easy. We just say we want strongest consistency. If performance sucks, then we might want to delve a bit into that. But most cases, this should be enough and does not bother the programmer with anomalies. And he can write it in a safe way. So what you can see here is basically that we are asking for serializability. We use an optimistic concurrency control mechanism. It's distributed using partial replication and uses a multi-versioned algorithm. All of this is there for free and independent of the framework. But, okay, you can also configure it in other ways, for instance. You might want repeatable read because you want to shoot yourself in the field. But in the end, it's very easy. So you just build the application with the simple Maven commands, specifying the code generator. You might use another code generator besides Infinispan or others that are available. In this case, I put the example of Ibernator GM. And then you just run it with yet another simple commands. And all dealing with all the boilerplate of the database distribution and so forth, it's hidden from you. And so for some... For quite a long time, so this is a website of my university. And for, I think, over 10 years, this has been used there. And this is serving around 1,500 people. And what is actually cool about it is that it started there. It has made open source, so they built a lot of stuff on top of this framework, which matters to the university itself in terms of issuing diplomas, registering for classes, you know, all that stuff. And actually, this was made... It started to become used in other places as well. And so it's running in many universities in the end. And actually, one cool thing about it is that at some point, they created this map of the object domains. And basically what you're seeing is the instances of the domain model of the university, color it by the part of the university they belong to, whether it's students, professors, and so on. And this system, which is about over 1 million lines of codes, if I'm correct, with bazillions of functionalities for universities, it's running in several places now. That's the cool part about it. And it's using the approach that I just described to you, basically. And so there are plenty of advanced features that I could talk about, but I'll just briefly go over a couple of them. And in this case, I'll just talk about index relations, which is, if you have this design that I told you about, and you now want to disable any contacts from your phone book given in email, you have to write code somewhat like this, which basically you need to go over all your contacts, and then you say, okay, this is the contact I want to disable. But this is crappy if you have a load of contacts. And so what happens here is that you can simply say, oh, I want to index my contacts by a given attribute. And then we'll give you a very efficient index that will solve the problem, and you can just say, okay, I'll get my contacts, and this should be efficient, independent of the backend. So of course, you get these features there. I was just trying to simplify it in the beginning. Another cool thing is about data location. So we don't let the programmer know where things are. And this is important because you might drop servers at runtime, bring new ones to have provisioning. So we cannot let the programmer know exactly where things are. But he can try to play a bit with it. And here what he can say is that he wants to point out that this contact should be placed using this attribute. What this allows him to do is that if he wants to run some code, he can create a task to run in a distributed system, which will use this contact, and then will use the locality of the contact to be placed. And what this means is that this code, this distributed task, will run in a machine where the contact is guaranteed to exist. And so this allows you to have co-location of data and code, which is important in distributed systems to avoid issuing remote operations to other servers. Another cool thing is that you can co-locate data, and that's simply using the same technique where you can place these two contacts in the same machine by using the hints. Of course, ultimately, the framework has the choice of not doing that because you might just put everything in the same machine, and that defines the scalability of the OS service. And so in summary, we know that distributed applications are hard to develop. And in particular, if the programmers are exposed to a lot of low-level mechanisms that they have to tune and configure. And so our take here is that the APIs should hide the complexity every time it's possible, but still allow expressiveness whenever it's needed by the programmer. And so that's exactly what we try to do here. Some references. So this was done in the scope of an European project. The framework I described to you is open source here, with the corresponding documentation, and the university stuff that I told you about, over a million lines of code used in several universities, is there with lots of documentation and nice manuals. And so if you want to get involved in this, there is a research network called Eurotm, sponsored by European Union. And it's basically bringing industry and academia together. It has lots of countries belonging to it. And you can participate in, namely, workshops, which are coming soon in April in Amsterdam. The Eurotm can fund your participation in these workshops. Also training school, which will take place in La Plagne and France also soon, where we'll have speakers from Intel, Red Hat, and even Oracle as well, even other industry members. And you can also collaborate with other institutions and just check the websites for more information. And that's it. Thank you very much. Questions? If you've got any questions, just raise your hand so we can run up to you and give you the microphone. I have a question regarding the cloud part. Can you speak up, please? Or everyone, please be quiet so we can understand the question. I have a question regarding the cloud part. We have seen that why consistency is needed. So what I don't understand, what is the proposed solution? I introduce one central management station, let's say, that is going to handle this, or how I do it in the distributed... So the question is basically whether the proposed solution is using centralized components to deal with the distributed data management. And the answer is no. But that might depend on the backend that you choose. We have backends which manage data in a completely decentralized way, which is favorable for scalability. And we have used this with over 100 machines. But if you choose a backend, for instance, we have support from MySQL, and you can run it with a centralized database. And in that case, you're asking for it and you get it, centralized components. So it's orthogonal and independent. Any other questions? Over there, simply. Hi, I was just wondering what kind of latency you see on the transaction management when it's introduced like this. Okay, so once again, that might depend on the backend that you're using. So the question was what kind of latencies we notice with this service, right? Yeah, do you know what kind of factors are involved? Sure. So one of the main problems is the data placement. So by providing the programmer with this simple abstraction of a domain language where they can specify the domain, and not actually asking the programmer to place the data, you might have a transaction which is spanning a lot of different machines. Kind of if you have a MySQL sharded and now you're talking with a lot of shards. And hopefully this can be fixed and actually there is an internal part to the framework which notices and tracks accesses and moves data to be collocated to make sure that if you access X and Y together a lot of the time, then X and Y will be together. There are several efforts regarding implementation. There are several efforts regarding implementation of transaction memory as far as I understand. So it's a standard, but there are several efforts from GCC and from Microsoft, I assume also. Is there any effort to synchronize those? So one of the efforts is definitely the Study Group 5 on ISOC++. So that is standardizing the language constructs that you have. So the interface that the programmer sees. And there are people involved from Oracle, Redhead, Microsoft currently not, IBM is involved, HP. So quite a set of a large group of people and academia as well. On the ABI level, Intel and Redhead have been standardizing or have a document out there that specifies the ABI that's used by the Intel compiler in GCC. Does it answer your question? You mean the language front-end or? Transactional memory part. Is it the STM is implemented in C++? Visual C++ compiler. Is it to be implemented in Visual C++ compiler? Visual C++. No, I don't know about the micros. Sorry. Okay, one last question. So in case of distributed back-end, could you give an example how is it solved, this problem that you demonstrated with the eventual consistency? Okay, so the main problem is that there is this very known problem in distributed systems called consensus, which is that you have different machines that need to arrive to the same conclusion. So when you have distributed transactions, you basically have to solve consensus. And basically what happens is that if you want serializability, you always have to solve consensus. And if your set of machines is large, you'll be paying a high cost every time. So the main trick there is to make sure that every transaction only touches a little number of machines. And that's why splitting up the data in a smart way, it paves a long way to make these efficient. So if I had to say the main key point that makes this possible is what I presented earlier, has partial replication. So dividing and making sure that you only replicate your data in a subset of the machines, and that you do it in a smart way such that you are resolving consensus between a small number of machines. Let's thank our speakers again.
 Tovador Riegel and Nuno Dieg. Thank you very much.  Hello, welcome. And my name is Tovador Riegel. I work for Red Hat's toolchain team on various things concurrent on parallel.  And I am Nuno Dieg, PG student from Portugal.  And we'll tell you something about transactional memory today.  So, before I start to get to the beef, let's actually set the scene here, right? So, this talk is about concurrent programming.  And concurrent means that things happen at the same time, but they're not independent, right?  So this is slightly different to parallel programming where it's say they also have met the same time, but they're usually independent, you know, like parallel lines.  And when you have concurrent actions, but usually, you know, one conceptual program state, you need to make sure that the concurrent actions actually synchronize, right?  So that it can make sense out of the state transitions.  And when you look at multi-course, for example, we have shared memories, or shared state.  And we need to synchronize on a shared memory, so we have this thing called shared memory synchronization.  Then you add transactions, and then you get the name transactional memory where it comes from.  Another topic, or another concept that is very important is atomicity.  And in the context of shared memory synchronization, atomicity means that something happens as an indivisible step, right?  If you're a database person, think about this as atomicity and isolation combined.  And this is why we have hardware instructions such as x86 compare exchange.  And to illustrate this a little bit further, why atomicity is important, let us act out a small situation that everybody of you will have experienced already, right?  So sometimes you have something like a narrow hallway, right?  Just people need to pass each other.  So we're working to each other, and usually somebody will step to the side, but sometimes the people do like this, you know?  And then they bump into each other.  We can't let computers do that.  And so what is the problem here?  The problem is that we are facing each other, and I see the side, and I think it's empty, right?  Nuno sees the same side and also sees things as empty.  And then we do the same steps, right?  We're in the same situation, and this is what's happening.  So what's going on?  The problem here is a lack of atomicity.  If these two steps of seeing the side and stepping over would be indivisible, we wouldn't have a problem, right?  I see it, I go to the side, and then Nuno makes his turn, right?  Or on the other way around.  So if we had the two actions atomic, then we would not have any problems.  So this shows you how atomicity is important, right?  So it would be doing something like a test and set that you have in hardware as well.  This is how you can remember why atomicity is important.  And so coming back to the transactional memory, if you want to remember one thing about transactional memory,  then please let it be this, right?  Transactional memory is a programming abstraction, and it allows programmers to declare which sequences of code should be atomic,  instead of requiring to actually implement how this is done.  This is the underlying vision.  This is how all the different kinds of TM, you know, what they give you.  And instead of the programmer, we have generic implementations that ensures atomicity.  So this is not specific to a particular program or something like that, but it's generic, right?  And it can be purely software, it can be new hardware, it can be a mix of hardware and software.  And our focus in this talk will be TM for high level programming languages.  So what we're going to do is that we have the first part in which I will talk about TM for shared memory on a single machine.  I'll give you an overview of the proposed C and C++ language constructs.  I'll give a peek in the GCCS implementation of that, and I'll make some comments on performance.  Next up, Nuno will talk about the TM for distributed shared memory, so multiple machines, but with a shared memory abstraction on them.  He will discuss strong consistency and implementation of top-of-infinis band.  Afterwards, we'll have a short Q&A.  If there's something very short, quick, you know, clarity question that you have, scream it.  If it's short, I'll answer it. Everything else goes at the end, please.  And one note that I also want to send out is that TM is still rather new.  The idea, so the first idea has been proposed 20 years ago, but real research didn't start until about 10 years ago, and it's still ongoing, heavily.  Standardization for C and C++ started about five years ago when people got together informally, and we have ISOC++ study group since mid-2012.  There's GCC support on the C and C++ site since version 4.7, and we're finally also getting real hardware TM implementations out there.  So, it's been out there for a long time, but special purpose, arguably. Blue Gene kind of like it, and it fills real mainstream CPU that has transactional memory hardware on it.  Intel's has more, right? If you have a new laptop, you actually might have it on your workstation with that chip.  So, how do the C and C++ language constructs look like?  So, we have this transaction atomic construct there, and this allows a programmer to declare that the following compound statement must execute atomic way.  So, in this case, the load to X and the potential load to Y, and the store to Y will all be executed as one indivisible step.  I'll give you an explanation of the specifics of the metrics later on.  There are no data annotations necessary or no special data types necessary, right?  And in those transactions, you can run existing sequential code.  You can do function calls, you can have nested transactions and so on.  However, the code in transactions must be what we call transaction safe.  And unsafe code, for example, is the use of logs or low-level atomics, assembler instructions, volatile memory accesses, or simply functions not known to be safe.  However, the compiler will actually check whether your code is safe, right?  So, you get a compile time checking guarantee for that.  And because of functions unknown to be safe, for cross-compilation unit calls or for indirect functions,  or indirect calls, or function pointers, you need to annotate your functions with this transaction safe attribute.  For example, you say here that you make the claim that foo is actually transaction safe.  For further information, have a look at the C++ specification best as to just web search for the paper number there, this end thing.  Now, this is concurrency, and so there are nasty little details.  So, here's a slide about disinconnization semantics.  Transactions extend the C11, C++11 memory model.  So, the memory model is the thing in the language specification that defines the execution of multi-threaded programs, right?  Which behavior you're actually allowed to have.  So, transactions, or the semantics of transactions are integrated into this memory model.  And the basic guarantee is that all transactions are totally ordered.  And this order contributes to the happens before relation.  Happens before is basically the relation that models what happens ordered after what other thing in your program if you have a multi-threaded execution.  And TM ensures some valid order.  So, the TM implementation ensures some valid order that is consistent with happens before for every execution.  In other words, this means that one transaction happens after the other,  and it makes sense with respect to the other synchronization going on in the program.  So, if you have the intuitive meaning, it's actually pretty easy to understand, right?  Note, however, this does not imply sequential execution, right?  This is a correctness guarantee.  If the transactions are actually independent, the implementation is also free to execute them in parallel, for example.  But it allows you to reason about the transactions as if they would be executed strictly one after the other.  However, there's a gotcha, and that is that data-raised freedom is still required.  That is the case throughout all C and C++, right?  Whether you're using logs, low-level, Tomics, whatever.  And it means that if your program has a data-raise, you get undefined behavior.  So, I have a small example there about publishing data,  and you have one thread doing initialization of the data, and then it uses some transaction to make the data by setting a flag.  And the other thread uses the transaction to use the data if it has been published.  This year is correct usage.  Doing something like that is not, because if you do the temporary read in front of it,  you have a data-raise in your program, and as a result, you get undefined behavior.  But as I said, this is something that you'll have to consider anyway with the C and C++ programs.  And the reason why we have that is that this actually allows efficient implementations for the compiler.  One of the biggest benefits of transactional memory is that it supports modular programming.  And so, that means this is because programmers don't need to manage the association between shared data and the synchronization metadata.  So shared data here is application data, things that you actually need to synchronize on and define your program state.  And the synchronization metadata is something like logs.  And the reason for that is that because we have a generic TMA implementation that takes care of ensuring the atomicity.  So that's one thing.  For example, programmers don't need to have a locking convention or don't need to follow it.  The second thing that kind of follows from that is that functions containing only transactional synchronization compose without that lock.  So the nesting order of transactions, for example, does not matter.  And however, you cannot expect another thread to make progress in an atomic transaction or concurrent with an atomic transaction.  This wouldn't make sense, right?  You're requiring the compiler and the environment to make your transaction to run in the visible step.  You can't go then, oh, this is one in the visible step and oh, and by the way, in between, I want this other thread to make another step.  So this would be conceptually incompatible.  And at the bottom, I'm giving you an example for that, right?  Comparing transactional memory to lists.  So the example is that we want to move one element from one list to another.  And I have this very little neat small generic function here where I remove from run list, insert into the other.  Synchronizing that or making that thread safe with an atomic transaction is easy.  You just put it in atomic transaction, say move AB in element 23.  If you do this with locks or try to do this with locks, it becomes difficult.  First of all, where do you put the locks, right?  Are they in the list or externally to the list?  So if they're in the list, you need to add an interface for the move functions,  for which you can query the locks that the lists actually have in them, right?  If you have done that, the next problem is that how do you acquire the locks in a consistent order?  Somebody is calling move AB and another threat is calling move BA, right?  If you just acquire the lock for the list one here first and then list two second, you'll run into deadlocks.  You don't have the problem with transactional memory because the implementation will take care of this.  If you try to do something as generic like that, the locks, it becomes messy quickly.  Switching gears a little. So how do we do it actually in the implementation?  So here's an over look of our peak into GCC's implementation.  And it has two sites to it. One is the compiler site and the other is the TM Rantzheim library site.  And there are three steps essentially that we do in the compiler except parsing and stuff like that.  So first, we ensure the atomicity guarantee.  We don't ensure that your program is data-race free, but if we can assume that your program is data-race free,  then we can ensure at compile time, at atomicity for your transactions.  And this works because we check all transaction-safe code whether it is indeed safe.  And transaction-safe code is the code that's either implicitly transaction-safe  because you call code from a place that should be transaction-safe  or whether you have annotated the functions accordingly.  And once we have checked all this code, we create an instrument that clone of this code.  And so this code is then the transaction-safe functions and so on.  And what we do essentially is that we take all the memory loads and stores  and rewrite them into so that they have a call into a TM Rantzheim library  that will then perform the memory loads and stores.  So we hook into the load and store mechanism essentially.  Similarly, we redirect the function calls to the clones.  And as a result, we have both an instrumented code path,  where the loads and stores are intercepted, and an uninstrumented one where things are just like before.  And then finally, we generate begin and commit code for each transaction.  And one thing that's worth noting is that we allow the Rantzheim library  to decide on every transaction start whether uninstrumented or instrumented code should be executed.  And the whole point of delegating to a Rantzheim library is really that we get implementation flexibility.  So we don't need to generate synchronization code in the compile time,  or at compile time and by a compiler.  But if we redirect, we have a little bit more overhead in terms of the function calls,  but when we have full flexibility at Rantzheim to do something different and better potentially.  So on the Rantzheim library site, and the Rantzheim library is called libITM in case of GCC,  this is the thing that actually enforces the atomicity at Rantzheim.  And libITM currently contains different software only implementations called STM.  So these are TMI implementations that do not need any special hardware.  And the default here is one that does write through essentially to memory with undo logging  and uses a set of internal logs to protect concurrent accesses to the same piece of memory between different transactions.  So the library will manage a couple of logs, do the automatic mapping from the memory to the logs,  and then run a kind of a little bit of vault algorithm to actually make this thing.  So this uses the uninstruated code path.  The currently in libITM also make use of hardware TMI implementations.  So HTM. And one thing that you might not be aware of is that all the HTM implementations out there  with the exception of a kind of special mode on the PowerPC stuff is that they're all best effort.  In the sense that they do not guarantee you that they can run all transactions.  For example, if your transaction, you try to access more memory in a hardware transaction  than there's hardware capacity to track your accesses, then it will simply fail and that's all you know, can't do.  So you always need to have a fallback for your hardware transactions.  And that means that, for example, you need to fall back to locking, you need to fall back to an STM and so on.  So the HTM by itself is not really a solve-it-all thing.  And libITM currently uses HTM with the global lock as fallback.  That's very simple, but it's also very non-scalable fallback, obviously.  The good thing, however, is that it allows us to use the uninstruated code path for the hardware transactions.  So that the hardware transactions really don't have any overhead because of instrumentation.  We currently don't have any hybrid STM, HTM implemented yet in libITM, but this is something that we'll hopefully have at some point.  The idea there is that we have hardware transactions that are very fast and then we can fall back to something that is actually still scalable.  So two more slides about performance.  And performance is a difficult topic for TM because TM has seen quite a bit of hype.  And so let me first note that, like everything else, it's a tool that's not magic, right?  And the performance goal of TM or the performance goal that every sane person implementing TM would give you is that  it tries to provide a useful balance between ease of use and performance.  It does not claim to provide the most useful balance or the only useful balance, right?  But it tries to make concurrency simpler for programmers and still deliver decent performance.  The goal is always to make it simpler, you know, except by considering some corner cases.  And then we see how good we can get.  And currently it looks like performance can be decent.  And the other point is that right now I don't think it's meaningful to try to draw conclusions from TM performance.  And this is also one reason why I don't give you any performance plots as such here, because it would mostly be misleading.  And I'll tell you why.  So first of all, the implementations are work in progress.  So libITM's work in progress has not seen a lot of tuning.  For example, the HTMs are first generation implementations for the hardware implementations.  I would claim that they're also work in progress.  For example, they lack features that would be very useful for hybrid software hardware TM implementations.  And second, performance heavily relies on a lot of factors.  Many more than might be obvious.  So for example, it relies on the hardware, obviously.  It relies on the compiler, what kind of codes it generates, the actual TM algorithm used.  The HTM implementation, for example, you know, how many memory accesses can it track for transactions?  So use it, what kind of cache or dedicated buffer it uses to actually track accesses?  Which other instructions can it handle, right?  There was a Spark hardware TM implementation that was so restricted that you couldn't do function calls.  That's not useful for general purpose TM, right?  It's useful if you use it in a very, very tiny controlled way, but it's not useful for, you know, the high-level TM abstractions.  The allocator matters, because the allocator decides, you know, how you end up moving your data around  and where your data gets located in memory, and there's false sharing issues and all that stuff.  Whether you use link time optimizations or not does matter, because it affects the overhead.  And these are all just all the factors that the implementation actually has control over.  Only the application and the programmer has control over the actual transaction conflict probability.  How long the transactions are, what the load-store ratio is, whether there are many read-only transactions and so on,  memory access pattern, data layout, allocation schemes, again.  Other code executor transactions and so on.  So there's a lot of stuff that's going on.  And the third point I want to make is that I mentioned that TM is still fairly new.  That means, because it's a programming instruction, that people actually have to use, right, actively,  that we are still on the kind of trick and an act situation.  So I'd like to, I'd love to tune LibITM for real-world workloads, but we currently have very few of them, right?  So any tuning will be guesswork.  Nonetheless, let me try to give you a few rough estimates that hopefully still hold in the future for TM performance.  TM performance can be characterized by both what's typically called the single-thread performance,  so the single-thread overhead, and the multiple-thread performance, so scalability, essentially.  Regarding the former, we can say that STM is a slow and sequential code.  You have to synchronize, so there will be more stuff, right?  On the other hand, how much overhead there will be can vary a lot,  from doing just the one critical section to, you know, doing something weird with memory access.  STM will probably be a slower or equal-to-course locking.  This is because we synchronize, so we at least need to have some kind of atomic instruction,  at least if we do a change or something like that.  So that's like a lock.  HTM will be, or is, about as fast as uncontended critical sections, or even faster,  because you don't need to change memory at all.  And depends on how it's implemented and so on, but HTM can be very fast,  provided the hardware can actually run your transactions, right?  If you do a Cisco in your transaction, it's not a good probability that, you know,  we will actually be able to do it.  It depends on the HTM again, but this is just an example.  Regarding scalability, we can say that most STM algorithms out there typically scale very well, right?  You say you have a shared data structure, you move elements,  there's no real logical conflicts in your transactions, it scales well.  But this is less likely the lower the single thread overhead is, right?  Because if you want to do, you'll have a lot of scalability, you usually do more,  you can't just go coarse-grained lock or something like that.  HTM also scales well, but again, the fallback is a problem.  So if your fallback doesn't scale well, and you have to use the fallback often, bad.  And so this is why I said that hybrid STM-HTM applications will hopefully help you to get the HTM performance out most of the time,  but still have a fallback that does not suck in terms of performance.  And one point that is worth noting is that the TM runtime libraries adapt at runtime.  They currently do this to a little extent, but there's a lot more that they can do.  This means that of all the possibilities here, there's a good hope,  that automatically the implementation will pick the right thing to do, right?  Which would be very hard to do for programmers.  Nobody wants to maintain, and it's, you know, in a general library,  maintain three different or five different synchronization mechanisms,  just to be able to be high performance when it's used in different ways.  And if you're still worried about that I didn't give you actual performance data,  there's a very easy way to get it, you just need to use it, right?  So grab GCC 4.7 or more recent, use dash afknew-tm,  and then measure performance on your applications, right?  Read the C++ video specification that's out there.  Report about your findings, blog about it.  If you think there's a bug or an inefficiency in GCC's implementation, report a bug, please.  If you have feedback for the constructs specified,  then it might be a good idea to get involved with the ISO C++ Tm specification,  so this is study group five.  And if you really are more interested in the code, please dive into,  just dive into the implementation, see what's there.  The comments in the libITM code are fairly extensive.  So even though this is concurrent code, it should be relatively easy to follow.  And there are many interesting things to work on,  for example, improving the auto-tuning and so on.  And with that, I'll let Nuno discuss something completely different.  Alright, and so as you can see now, we're going for a different world,  but we'll still be addressing the same problem.  And until this point, we were looking at a single machine,  and we already understood that we need to make sure that these concurrent accesses to data are regulated.  But we typically like to build distributed applications.  And there we have many, many of these machines.  And the point here is that it would be very interesting  if we could explore these independent memories,  but look at them as a single shared abstraction.  And so what I will show you basically is how to do this.  And we will use the same abstraction of transactional memory,  but in a different environment.  And so the approach that we'll refer to is basically distributed transactional memory.  And similarly to what we saw before is that we are bringing transactions to the top of the software stack.  So they are no longer buried down deep in your data store engine,  but actually they are up there close to the application.  And so this allows for dynamic transactions,  meaning you do not have to specify a priori how long they are, which positions they will access.  And this will be straight embedded into the application logic,  which is also favorable for long-lived transactions.  But a bit different from what we saw before from Torvult  is that now we have to worry about these three things down below.  So namely persistence, because people in distributed applications enjoy this a lot.  And the distribution itself, because this raises other concerns in terms of,  for instance, the costs of communication, and of course, full tolerance,  because this is the main driver of why you're building distributed application in most of the cases in first place.  And so just to give you a quick list of concepts,  imagine you have this set of data up here and you have your distributed system.  What we have until these points from Torvult is that we have a single machine.  But now we basically just replicate this data because this is not full tolerance.  And so this is what we call a fully replicated system.  However, if you're going to change a bit of your data, you have to communicate this to everyone.  And if you're going to scale to a lot of machines, this starts to become highly costly.  And so basically what you do is that you only replicate a given data item in a subset of the machines,  which is partial replication.  And so considering this, I mean, just try to briefly convince you  of why you should use strong consistency in these scenarios.  And for that, let's consider what has been quite popular until some years ago  and started perhaps 15 years ago, which is eventual consistency.  So if you have this client up here which says to the server,  I want to change this data item. It's no longer green, it's yellow.  And then after a while, it says, I want to read that data item again.  And it gets forwarded to a different machine.  And actually it sees what was there before and not the most up-to-date thing.  And this is a reflex of what we typically say in popular saying  that eventual consistency is no consistency at all because it's not formally defined.  You have to dig into your system and understand what is providing to you  to then realize what you can do of useful with it.  And this varies from system to system, and it's terrible for programmers.  And so in this case, the problem is that the replication was still ongoing.  And so this is a very similar problem to what you might have witnessed on Amazon,  for instance, where you say you want to buy something  and after a while it's no longer in your buying list.  And then it pops up again. Or even in your Facebook posts,  you write something and after a while it's not there, and other people can see it.  And so this has convinced a lot of people, and in most recent years  we are now getting a lot of popular systems which actually give you  the abstraction of a transaction.  But you might still have transactions which are stronger than others.  And one example is that you can use snapshot isolation in transactions.  But it's still not perfect. And let me present you an idea of why that is the case.  So you have here a game where you have two players  and they can never be in two contiguous slots.  So what they do is that they look around, they see what's there,  and they choose the next move such that they will not collide with the player.  And that is what they both do. Then they concurrently move,  and they move next to each other breaking the rules.  Basically what happens is that the positions that they wrote did not intersect.  And snapshot isolation will only abort a transaction  if it writes to something that was written concurrently.  And this is what is known as a writes queue anomaly.  But notice that if they had moved one at a time, as we presented to you earlier,  with a notion of sequentiality that comes from the atomicity,  this would not have happened.  And that's what you get with serializable transactions,  is that every execution that is allowed is equivalent to sequential one.  So that's very easy for programmers to reason about.  And basically that's the approach that we try to take,  is that we embrace serializable transactions, which might be costly,  but for overcoming that we try to explore several things,  such as partial replication that I showed you earlier,  and we can build scalable protocols on top of that.  And you might have heard of recent proposals such as Google Spanner,  which are trying to move into this direction.  And so what we are doing here is not trying to save, to solve the hunger in world.  We are aiming for simple use case, but hopefully the common one.  And for that we try to give a framework, which is easy to bootstrap,  has enough, fast enough scalability and performance for most use cases.  And this has a lot of details which are hidden from the programmer.  Of course, this will not give you the ultimate performance  if you really need to have something critical.  And the approach that we take starts from a very key point,  which is that you specify the domain of your application in a domain-specific language,  and all of this in an object-oriented way.  And through this we will hide from you concurrency control, persistence,  and data placement in your distributed system.  For some things we might still need your help as a developer,  and for that we give you APIs in an object-oriented manner,  for which you can do distributed execution of code and ensure data locality.  And then we still have some things only for expert programmers if they want to go there.  And so for the rest I will use this guiding example,  where we have phone books which have contacts,  and the contacts may be shared among phone books.  And this typically maps to some Java classes or whatever your preferred language.  And then they might have... they will refi these relationships over there  via some collections or references,  which have to be updated bidirectionally and so forth.  And if you consider a typical approach in the industry,  which is to use, for instance, Ibernate,  you will basically write some codes resembling this.  And so you have to put these two collections on the two sides,  which you have to manage every time it changes one side,  you have to remember to go on the other one and update it accordingly.  You have to worry about these annotations  and manage the unique IDs of the classes and so forth.  And actually this approach we believe has a lot of good things underlying it.  And so we will be quite close to this, that's why I'm showing this example.  But we'll try to clear up a bit the view and focus on what's actually interesting.  And so the DSL that I talked to you about, we call it Domain Modeling Language.  And for the example that I provide to you,  basically you only have to specify the classes that you have in your domain.  In this case it's very simple, have a phone book, a contact, their attributes.  And then we say that they are related, and they are related in this many to many fashion.  But this is written in separate file, domain file, in a Java-ish syntax,  which should be easy for most to understand.  And this is all of it. You've already understood it, and then you just saw it for the first time.  And so as I told you, it's a DSL, and basically the framework that we have  will then use this DSL to generate code.  And it will generate code with a well-known interface.  And this will basically boil down to mapping the entities to classes  with getters and setters hiding all those things that I talked to you about.  And then making the relations automatically managed in a bidirectional manner.  And so the framework will start from your DML over there.  So the application has the domain written by the programmer.  Then some code generator will be triggered, generates the classes.  And they are placed in the application such that the programmer can extend it,  these domain classes, with the behavior, because he only tells us,  I have a book with this structure. It does not tell the behavior.  That's his job to do. The programmer still needs to do something, right?  And then in the end, these interact with the rest of the application.  And so an example for the classes that I presented to you are basically these.  Is that you have the common getters, setters for all the things.  And all the concurrency and persistence distribution are hidden in there.  So the interface will always be the same, regardless of the actual code implementation.  Pretty much a bit like what we just saw for the GCC.  And so then what you can actually do is to choose different transactional managers  and backends for persistence.  And you do not really have to change the application.  You only have to specify this in a configuration file.  And for the rest of the talk, I will use the guiding example of using Infinispan,  which is a data grid open source from Red Hat.  And so what we actually do in this particular example is that we have to map your domain to this persistence.  And Infinispan is a key value store distributed one.  And so we will somehow do this mapping such that you do not have to worry about it.  And then you run your transactions in our application.  We will map these two transactions in Infinispan and we will ensure the serializability that you wish.  But what matters is that programmers are not aware of these parts.  They might even be able to see it if they want, but they don't have to.  And that's what's important.  And this is regardless of the backend that you're choosing, whether it's Infinispan or any other.  And so if you were still using the other process I told you about, like Ibernates, for instance,  I told you we wanted to clear up a bit the landscape.  And so this is what an application would look like using the domain that I specified.  If you go with DML, you can clear up this.  And in the end, you only have the atomics here, which are related to what we saw in the first part of the talk.  But nothing else is related to concurrency or persistence.  It's completely hidden and even distribution.  And so if you want to run an app, an application, which resembles what I just described,  basically have to specify only a properties file and then have to point to the configuration files  which are backend dependent.  In this case, I'm using this example.  In this example, we need to specify some Jgroups file for communication distributed system.  Just use a prebuilt one.  We have to configure the Infinispan.  Well, it's rather easy.  We just say we want strongest consistency.  If performance sucks, then we might want to delve a bit into that.  But most cases, this should be enough and does not bother the programmer with anomalies.  And he can write it in a safe way.  So what you can see here is basically that we are asking for serializability.  We use an optimistic concurrency control mechanism.  It's distributed using partial replication and uses a multi-versioned algorithm.  All of this is there for free and independent of the framework.  But, okay, you can also configure it in other ways, for instance.  You might want repeatable read because you want to shoot yourself in the field.  But in the end, it's very easy.  So you just build the application with the simple Maven commands, specifying the code generator.  You might use another code generator besides Infinispan or others that are available.  In this case, I put the example of Ibernator GM.  And then you just run it with yet another simple commands.  And all dealing with all the boilerplate of the database distribution and so forth, it's hidden from you.  And so for some...  For quite a long time, so this is a website of my university.  And for, I think, over 10 years, this has been used there.  And this is serving around 1,500 people.  And what is actually cool about it is that it started there.  It has made open source, so they built a lot of stuff on top of this framework,  which matters to the university itself in terms of issuing diplomas, registering for classes, you know, all that stuff.  And actually, this was made...  It started to become used in other places as well.  And so it's running in many universities in the end.  And actually, one cool thing about it is that at some point, they created this map of the object domains.  And basically what you're seeing is the instances of the domain model of the university,  color it by the part of the university they belong to, whether it's students, professors, and so on.  And this system, which is about over 1 million lines of codes, if I'm correct,  with bazillions of functionalities for universities, it's running in several places now.  That's the cool part about it.  And it's using the approach that I just described to you, basically.  And so there are plenty of advanced features that I could talk about,  but I'll just briefly go over a couple of them.  And in this case, I'll just talk about index relations, which is, if you have this design that I told you about,  and you now want to disable any contacts from your phone book given in email,  you have to write code somewhat like this, which basically you need to go over all your contacts,  and then you say, okay, this is the contact I want to disable.  But this is crappy if you have a load of contacts.  And so what happens here is that you can simply say, oh, I want to index my contacts by a given attribute.  And then we'll give you a very efficient index that will solve the problem,  and you can just say, okay, I'll get my contacts, and this should be efficient, independent of the backend.  So of course, you get these features there. I was just trying to simplify it in the beginning.  Another cool thing is about data location.  So we don't let the programmer know where things are.  And this is important because you might drop servers at runtime, bring new ones to have provisioning.  So we cannot let the programmer know exactly where things are.  But he can try to play a bit with it.  And here what he can say is that he wants to point out that this contact should be placed using this attribute.  What this allows him to do is that if he wants to run some code, he can create a task to run in a distributed system,  which will use this contact, and then will use the locality of the contact to be placed.  And what this means is that this code, this distributed task, will run in a machine where the contact is guaranteed to exist.  And so this allows you to have co-location of data and code, which is important in distributed systems to avoid issuing remote operations to other servers.  Another cool thing is that you can co-locate data, and that's simply using the same technique where you can place these two contacts in the same machine by using the hints.  Of course, ultimately, the framework has the choice of not doing that because you might just put everything in the same machine, and that defines the scalability of the OS service.  And so in summary, we know that distributed applications are hard to develop.  And in particular, if the programmers are exposed to a lot of low-level mechanisms that they have to tune and configure.  And so our take here is that the APIs should hide the complexity every time it's possible, but still allow expressiveness whenever it's needed by the programmer.  And so that's exactly what we try to do here.  Some references. So this was done in the scope of an European project.  The framework I described to you is open source here, with the corresponding documentation, and the university stuff that I told you about,  over a million lines of code used in several universities, is there with lots of documentation and nice manuals.  And so if you want to get involved in this, there is a research network called Eurotm, sponsored by European Union.  And it's basically bringing industry and academia together.  It has lots of countries belonging to it.  And you can participate in, namely, workshops, which are coming soon in April in Amsterdam.  The Eurotm can fund your participation in these workshops.  Also training school, which will take place in La Plagne and France also soon, where we'll have speakers from Intel, Red Hat,  and even Oracle as well, even other industry members.  And you can also collaborate with other institutions and just check the websites for more information.  And that's it. Thank you very much.  Questions?  If you've got any questions, just raise your hand so we can run up to you and give you the microphone.  I have a question regarding the cloud part.  Can you speak up, please?  Or everyone, please be quiet so we can understand the question.  I have a question regarding the cloud part.  We have seen that why consistency is needed.  So what I don't understand, what is the proposed solution?  I introduce one central management station, let's say, that is going to handle this, or how I do it in the distributed...  So the question is basically whether the proposed solution is using centralized components to deal with the distributed data management.  And the answer is no. But that might depend on the backend that you choose.  We have backends which manage data in a completely decentralized way, which is favorable for scalability.  And we have used this with over 100 machines.  But if you choose a backend, for instance, we have support from MySQL, and you can run it with a centralized database.  And in that case, you're asking for it and you get it, centralized components.  So it's orthogonal and independent.  Any other questions?  Over there, simply.  Hi, I was just wondering what kind of latency you see on the transaction management when it's introduced like this.  Okay, so once again, that might depend on the backend that you're using.  So the question was what kind of latencies we notice with this service, right?  Yeah, do you know what kind of factors are involved?  Sure. So one of the main problems is the data placement.  So by providing the programmer with this simple abstraction of a domain language where they can specify the domain,  and not actually asking the programmer to place the data, you might have a transaction which is spanning a lot of different machines.  Kind of if you have a MySQL sharded and now you're talking with a lot of shards.  And hopefully this can be fixed and actually there is an internal part to the framework which notices and tracks accesses  and moves data to be collocated to make sure that if you access X and Y together a lot of the time, then X and Y will be together.  There are several efforts regarding implementation.  There are several efforts regarding implementation of transaction memory as far as I understand.  So it's a standard, but there are several efforts from GCC and from Microsoft, I assume also.  Is there any effort to synchronize those?  So one of the efforts is definitely the Study Group 5 on ISOC++.  So that is standardizing the language constructs that you have.  So the interface that the programmer sees.  And there are people involved from Oracle, Redhead, Microsoft currently not, IBM is involved, HP.  So quite a set of a large group of people and academia as well.  On the ABI level, Intel and Redhead have been standardizing or have a document out there that specifies the ABI that's used by the Intel compiler in GCC.  Does it answer your question?  You mean the language front-end or?  Transactional memory part.  Is it the STM is implemented in C++?  Visual C++ compiler.  Is it to be implemented in Visual C++ compiler?  Visual C++. No, I don't know about the micros. Sorry.  Okay, one last question.  So in case of distributed back-end, could you give an example how is it solved, this problem that you demonstrated with the eventual consistency?  Okay, so the main problem is that there is this very known problem in distributed systems called consensus,  which is that you have different machines that need to arrive to the same conclusion.  So when you have distributed transactions, you basically have to solve consensus.  And basically what happens is that if you want serializability, you always have to solve consensus.  And if your set of machines is large, you'll be paying a high cost every time.  So the main trick there is to make sure that every transaction only touches a little number of machines.  And that's why splitting up the data in a smart way, it paves a long way to make these efficient.  So if I had to say the main key point that makes this possible is what I presented earlier, has partial replication.  So dividing and making sure that you only replicate your data in a subset of the machines,  and that you do it in a smart way such that you are resolving consensus between a small number of machines.  Let's thank our speakers again.
_FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_0_599.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_600_659.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_660_731.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_732_1883.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_1884_2183.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_2184_4727.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_4728_4835.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_4836_5603.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_5604_10715.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_10716_11531.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_11532_11603.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_11604_14519.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_14520_15119.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_15120_15287.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_15288_15575.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_15576_16643.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_16644_17039.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_17040_18719.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_18720_18923.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_18924_19367.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_19368_19655.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_19656_20087.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_20088_20975.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_20976_21803.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_21804_22667.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_22668_23111.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_23112_23219.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_23220_23411.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_23412_25271.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_25272_26135.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_26136_27011.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_27012_27119.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_27120_31259.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_31260_31331.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_31332_31907.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_31908_32411.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_32412_35939.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_35940_36047.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_36048_37235.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_37236_38279.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_38280_38495.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_38496_38999.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_39000_39083.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_39084_39335.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_39336_42251.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_42252_42347.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_42348_46919.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_46920_47219.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_47220_55271.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_55272_55439.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_55440_56699.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_56700_59675.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_59676_59975.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_59976_68675.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_68676_70547.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_70548_70727.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_70728_71075.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_71076_73151.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_73152_73739.png _FOSDEM_2014__Concurrent_Programming_Made_Simple_ZcTVCO98_2U_73740_75040.png