High performance and scaling techniques in Golang using Go Assembly
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.
Wessels, Frank
In this presentation we present some optimizations we have developed for theMinio object server. To maximize hashing performances for bit-rot protectionwe have exploited the Go Assembly capabilities to natively optimizing BLAKE2and SHA2 techniques for both Intel and ARM platforms. In addition we willpresent a distributed locking package to aid with scaling a single serversolution into a multi server solution. In this presentation we would like to focus on a couple of developments thatwe have done for the Minio object server in terms of performance improvementsand scaling techniques. Regarding hashing we have developed Go packages for two hashing algorithms(BLAKE2 and SHA256) that take advantage of the Golang (or Plan9) assemblycapabilities. These packages exploit SIMD instructions of Intel and theCryptography Extensions for the ARM platform. The speed up range from 3 to 4times (Intel) to 100X (on ARM). Due to the use of Golang assembly there is noneed for a C-compiler in order to use these packages (when compiling fromscratch). For the Intel platform SSE, AVX, and AVX2 specific version areavailable and the most performant architecture is automatically chosen. In addition we have developed a distributed locking and syncing package forGo. Its main features are: \- Simple design for avoiding many tricky edgecases \- No need for a master node \- Resilient so other nodes are notaffected when a node goes down \- Drop-in replacement for sync.RWMutex-Automatically reconnect to (restarted) nodes \- Limited scalability of up to16 nodes We are successfully using this package for the Distributed version of theMinio Object Server
 Okay, yeah, I'd like to speak about, yeah, some high performance and scaling techniques that we've been doing in Golang. Small breakdown of the presentation, a few slides about myself and some work that we do with Minio. Do you understand me or not? Okay. Is this better? Is it better like this? Okay, great. So, a little intro about myself and Minio. Then I'd like to speak sort of in general a little bit about, yeah, the Golang or Plan 9 assembly capabilities that Go offers. Then discuss two sort of projects that we've done with this, so Blake2B, Acceleration and Char2F6 acceleration, and finally some slides about some, yeah, distributed syncing stuff that we've been doing. One slide about myself. I've been mostly doing software development in sort of what's called the medical imaging space, so that relates to like CT and MR images from scanners, both 2D, 3D, as well as using GPU techniques. The last few years, I've been involved in cloud computing and I'm now with Minio. Minio, as maybe some of you know, is an Amazon S3 compatible, yeah, object storage server. It is, yeah, written in Golang under the Apache 2.0 license. The company was actually founded by Anand Babu Parishyami, who maybe some of you know as one of the guys behind the Gluster FS system, which is in itself a distributed file system, which is now part of Red Hat, actually. If you look at Minio itself, there's actually sort of really, yeah, one project, one binary, but you can run it in sort of three different flavors. So the simplest version is simply run Minio server with a single directory and then, you know, all your objects will be stored underneath this directory structure. And there are also, yeah, two other versions that use a technique that is called erasure coding. So what this essentially does is all the objects are split up into both like data chunks and parity chunks and, yeah, split over, yeah, multiple disks or multiple servers. And the Minio server actually, the Excel backend which splits the data over multiple disks, goes from a minimum of four disks up to a maximum of 16 disks. And it also uses a technique that is called bitwalk protection. So this means that when the data is being read off the disk again, which can be many years later than when it is stored, a hash is computed to detect any, yeah, bitwalk changes. And if that happens, then, yeah, we have other parity blocks to reconstruct the original data. But as you can imagine, this bitwalk protection is a very frequent operation. So any data that's written to disk, hashes have to be computed. And likewise, when data is being read off the disk, yeah, the hash needs to be computed as well before we actually can return, yeah, any information to the client. So that's a pretty important operation for us. And that's why we really looked at how can we get sort of the maximum performance in terms of hashing speeds while still, you know, having a solid proof and hashing technique. So that's actually how we, yeah, did our Lake2B project. But before I go into that, let me explain to you a little bit about, yeah, sort of the goal laying or plan nine assembly capabilities. This is actually a, yeah, an integrated or integral part of the whole go tool chain. And it's actually, it's kind of like a pseudo assembly language in the sense that it's not a direct assembly that you would write for, say, an Intel platform or an ARM platform. So there are some, like, generalized instructions for, like, a move and an add and a compare. And these instructions are then obviously translated to the actual instructions that will run on the underlying hardware platform. Most of the times, it's kind of logical how, like, this pseudo assembly language translates into the underlying assembly running on the CPU itself. Sometimes, yeah, that is not the case. So sometimes a little bit of trial and error there. And also some architectural aspects of the underlying architecture they shine through. So on the ARM, you have, like, conditional instructions and you can do that too. And obviously on an Intel, that will not work. Also, for instance, data flows from left to right. So if you do, like, a move, you have a move R1 to R2. It's actually, R2 becomes R1. And, yeah, like on the ARM platform and the other way around. So there's some things you have to be aware of. There's also some, yeah, like pseudo registers. So they're not actual registers, but kind of like simulated registers for, like, frame pointer, stack pointer, program counter. And also not all instructions that you would want to write are available. However, it is possible to also, yeah, not use sort of the mnemonics, but use the actual op codes that will go into the assembly. So if it's not available, you can resort, yeah, to that. If you talk about, yeah, what are the sort of the advantages that you get with, like, assembly language and obviously, yeah, it sort of gives you the ability to get the maximum performance out of the underlying hardware. And also, if you do this, then, yeah, you still benefit from, you know, the nice quick and fast compilation that Go offers, you know, to get, like, assembly into your code. You can also use, for instance, the Sego route. But, yeah, that has some disadvantages. One is that, yeah, you need to have the Sego, yeah, available. It takes longer to compile because, again, it's more like a C-style compile that happens. And also, when you call into that code, then, yeah, there is some runtime overhead because all the stack needs to be saved and everything. And if you write your own assembly, yeah, you don't have that overhead. And obviously, if you use assembly, you can take advantage of the SMID instructions for Intel or the neon instructions that are available on ARM. It's maybe a little bit kind of a word of caution is that you, yeah, you are a bit on your own if you do this kind of stuff. The documentation is kind of limited and a little bit sparse. There is a considerable amount of kind of example code in the Go repository itself as well for stuff like New Texas and some lower level stuff. So, actually, if you grab for start out as in the Go code, you will see, yeah, a lot of examples there. And, yeah, likewise, we now have a few repositories where there's also some Go code in there. And as an example, basically, this is actually, yeah, also a file where you can sort of see the translation between this pseudo assembly language and the actual ARM instructions as they are being generated. If you want to integrate, yeah, assembly into Go lang, then you have to, yeah, use the.s extension for, yeah, basically assembly. And that is actually prepended by sort of an architecture, yeah, identifier. So, underscore ARM64 means that the assembly is for the ARM 64-bit platform and likewise AMD64 will be for, yeah, the Intel or AMD64-bit platform. And actually, here is a snapshot of a repository. It's a little bit hard to read, but here, actually, you can see actually several versions for the AMD64 platform because in this repository, we actually have a dedicated AVX2, AVX and an SSE version, and then there is an ARM version. I'll talk a little bit more about sort of AVX2 and AVX later on in the presentation. So, kind of one approach that has worked nicely for us is if you do this kind of stuff is to actually start out with, you know, an algorithm at the Go level itself because even if you do this, then you are not likely to do all the work for all the different architectures that are out there. So, it always makes sense to have as a baseline sort of the functionality in Go itself. And then sort of as you start to, yeah, translate that functionality into assembly, what we sort of did is we started out kind of like with small bits and pieces. And so, you comment out most of the Go code in your routine or class or whatever, and then you start to translate small bits and pieces into assembly, maybe initially starting just with passing in the arguments and writing back some results, making sure that all works. And once you got it working, then, you know, you gradually start to translate more and more of your Go functionality into assembly and along the way, yeah, make tests whether the assembly functionality is equivalent to the Go assembly. So, actually, if you look, for instance, at the commit history of the Blake 2B SMID repository, you can actually see how we used this technique. Along the way, we also developed a small utility called SM2 plan 9S, which actually generates byte sequence codes for OCCO or, yeah, assembly instructions that are not natively supported by Go itself. So, actually, it uses the YASM assembler sort of behind the scenes. So, what you do is you basically write your instruction as you would write it regularly in assembly, and then you run the tool on the file and then it will prepend that instruction with, yeah, the actual, yeah, opcodes that will go into the byte stream that will be executed. So that has, yeah, worked nicely for us. If you look at, yeah, what we have done with assembly, we've actually accelerated the Blake 2B algorithm as well as the SHA256 algorithm and we're planning to do one more piece of work which has to do with this erasure coding, which is actually called read solomon. And this uses some, yeah, what they call Galoi field arithmetic polynomial multiplications. And ARM actually has a specific PMO instruction. So we want to use that instruction to accelerate the read solomon computation of the parity blocks for ARM. For Intel, it is already, yeah, accelerated, but we want to do the same for the ARM platform. And, yeah, maybe when there is a need in certain pieces of the code, then, yeah, we will likely do more. Okay, so the first technique that we accelerated is a hashing technique that is called Blake 2B. Yeah, Blake 2B is a hashing technique. It was actually, there was like a SHA3 competition a few years ago and they were one of the five, I think, final contenders. In the end, they were not selected, but it is, yeah, a nice hashing technique with sort of the characteristics that it's, yeah, it's really focused on speed as well as kind of like a relatively simple algorithm to implement while at the same time still offering sort of top of the, yeah, top of the bill security. And it's really optimized for 64-bit platforms. So we developed a repository using the SMID instructions to accelerate the Blake 2B algorithm. And actually, we did it in sort of three flavors. So there's an AVX2 implementation, which is the fastest. Then there's an AVX. And then there's an SSE implementation. So depending on what your CPU support, then obviously the highest level of SMID instructions that are, that is supported, that one will be used. But overall, we were able to achieve close to like a 4x performance improvement over, yeah, the high-level Go functionality. So yeah, that helped us quite a bit because if you look at the table on the right, you can, that's a little bit too small, but we can do about 850 megabytes per second with the Blake 2B algorithm on an AVX2 machine. And this compares to, if you look at SHA256, that is at like 190 megabytes per second. And SHA512 is at about 300 megabytes per second. And as an object storage, you can imagine if you have large blobs of data written on the disk, then again, for us to be able to return like the first byte when people ask for an object, say if it's a one gigabyte object, then having a factor of four there, that means the difference between being able to return something within a second or within it taking four seconds. So that's a pretty significant saving there. And again, yeah, so we developed this technique for the BitRot detection mechanism that is part of Minio. If you look a little bit closer at sort of how it works, at the top line, those are actually, there's a very small portion of all the kind of computations that are happening as part of the Blake 2B hashing. So there's basically four, yeah, additions there. And these are on 64-bit integers. And if you look at the AVX capability for the Intel platform, you can essentially work with 128-bit wide registers. So this allows you to do literally like two additions in parallel. And this is kind of what you see here. So with AVX2, you use what I call the XMM registers. So again, those are 128-bits wide registers. So essentially, this means that whereas here, it's kind of like two lines, you can do it here basically, yeah, in a single line. And likewise, at a second XMM instruction, we'll also take care of two of these guys. So you can sort of go from like four to instructions to like two instructions. And if you go one step further, AVX2 extended the pipeline to 256-bits wide, which means that, yeah, you can use or do essentially four 64-bit additions with a single instruction. So that's actually this guy. And then here you use the YMM registers instead of the XMM registers. And again, those are 256-bit instructions wide. So in a way, this kind of explains why there's kind of a four times speed up between, yeah, like Golang and AVX2. There's a bit more there, but I mean, fundamentally, this explains it quite a bit. If you look at Blake 2B, the algorithm itself, it actually has sort of 12 rounds of, yeah, working on the data. This is kind of like the preamble where first the message is being read in, then it's kind of shuffled around. And then there are two sort of macros that actually do the actual like X-oring and adding and rotations of, yeah, all the bits. Then there's like a diagonalized macro there, which kind of rotates, yeah, values between the different, yeah, values that you are working on. Then there is a second half where you load more from the message. You shove it a little again and you call the same macros again. And finally, you bend diagonalized, so you sort of shift it back. And if you look at, yeah, one of the macros, so in this case, this is the, what's called the G1 macro. It actually consists a little bit of like three columns. So on the right side of the screen, you kind of see the high-level Golang instruction. Then in the middle part of the screen, you sort of see the AVX instruction. And then on the left side of the screen is the actual, yeah, upcodes that are being written into the assembly stream. And so actually what this guy does is here, there's like, this is an addition. This is like an XOR. Here, you actually see a rotation, but the Blake II algorithm has selected like shift values that nicely map onto, yeah, the Intel architecture. So you can actually, while it's a shift over there, it's actually a shuffle. So you shuffle bytes around in between the registers. So, and then there's more additions, more XORing, and then, yeah, get another kind of rotation. And this happens, you know, over and over again, and then in a total of 12 rounds, and that's, you know, how you get your hash out there. Okay. That was about the Blake II B algorithm. We've also done some work on, yeah, a SHA256 algorithm, most notably also for the ARM platform, because the ARM platform actually has specific instructions to accelerate SHA256, yeah, calculations, and they make a tremendous amount of difference, because it literally is 100 times faster than not using those instructions. And actually, Intel also has instructions for SHA256 accelerations, but they seem to be just defined in software, and there seem to be no hardware implementations out there. Otherwise, it would be nice to take advantage of that as well. But actually, the table here at the bottom, you can sort of see, yeah, the speeds that we have, and interestingly speaking, actually, the ARM, just running at 1.2 gigahertz is actually the quickest one out there, so it does about 640 megabytes per second, and then we ran some tests on an Intel Xeon at 2.4 gigahertz. The AVX2 comes in at about 355, then the AVX is running around 300, SSZ still a little bit lower than that, and these are actually the Go versions, so if you do Go on the Intel Xeon platform, you get about 190, and the last one is the ARM version. If you look at how do you actually invoke assembly code from Go, you essentially define kind of the prototype of the function that you're going to call into, so for most of this hashing techniques, you pass in like the digest that you start with, and the message itself, so the digest is basically just a slice of 30 qubit integers, and the message is just a slice of bytes, and here we actually compute the 32-bit integers into the digest, so that's this guy, and then basically the actual message as you go into hash is being passed in directly into what will be the assembly code, and then once you're done, then actually the result is written in this guy, so that is what you return, and this is actually an ARM example, so the first line that's basically how you define the function in the assembly code, and the first thing that you actually do is to read the parameters that were being passed in, and this function takes two slices as inputs, and as maybe some of you know, a slice is actually a structure with like three elements in it, and the first element is a pointer to where the actual data is, and the second is actually the length of the slice, so what we're doing is the first few instructions were reading this here, and because this is running on 64-bit platform, both slices in effect, they take up a total of 24 bytes, so again it's three elements, but each element is eight bytes long, so the first instruction basically fetches a pointer to where the digest is, and the second line fetches a pointer to where the message is, and then the length of the message is being read in the third statement, so it's another eight bytes further than the already 24 bytes which point into the second slice that is being passed in, and then further down here, we do some initialization, so here we load from x0 which corresponds to r0, the digest, we also load obviously from the message itself, and there's also a constant stable, so we get basically a reference to the constant stable that's actually in r3, and r3 corresponds in neon to x3, so here we load values from the constant stable, and this is actually sort of the main loop where the hashing is being done, and again here r1 which is x1 is the pointer to the message, so here actually the values from the message are being read, and well there's some positioning codes to make sure things are in kind of the right order, and then these guys are actually the specialized ARM instructions that give basically the hundred times speed up, and then there's some more shuffling of data around, but yeah, all I have because these are specialized instructions, the actual assembly is pretty short, and then yeah, this is like the end of the routine, so again there's some ARM instruction or SHA extensions, instructions here, and then here it's basically put into v1 and v0 and v1, and here actually you write out the result in like register 4.1 and v1 into x0 which was the pointer to the digest, and then you return out of there, and obviously here, well as long r2 is the length of the message, so you process 64 bytes at a time and when there's more work to do, obviously you loop back. So that's pretty much how a function like this looks a little bit. If you look at some resources that we have that are out there, actually as maybe some of you know, some of the origins of the go architecture and work go back to the whole plan 9, yeah, worked on that has been done, and actually some of the assembly still originates back to that, so some of the documentation out there, yeah, it's literally at the GP.io website, so not everything in those URLs is kind of applicable, most of it is, but it's their generally generally good resources to read through and get an understanding of how this all works and ties in together, and then there's also like a high level SM document and there's also some pointers for ARM, some pointers for Intel about how neon instructions and AVX instructions work. Okay, that was sort of the like the performance optimizations that we've done for, yeah, hashing techniques. We also did some work on something that we called a distributed syncing technique. When I earlier talked about the three flavors of Minio that are there, the last one that was listed is called the distributed version, and that's what we have two versions that can work with erasure coding and then distributing the data across multiple either disks for the Excel version or actually multiple servers for the distributed version, and for the distributed version that can actually run from anywhere of a minimum of four servers up until a maximum of 16 servers, we needed to have a synchronization mechanism between the servers, and yeah, we also looked at some existing protocols and techniques out there, but yeah, we like a technique like RAFT, but we found that a little bit overkill for sort of what we were trying to do. So we designed basically a pretty kind of minimalistic synchronization technique that works well for us. The design goals that we wanted to have was basically keep the design simple, also meaning there's for instance no concept of like a master node, because well, if you have something with a master node and the master nodes go down, goes down, then yeah, your whole system is down, so you need to have backup master nodes and then you already talk about two or three master nodes, and it quickly starts to become more complicated than what you initially think. So in our system, there's no concept of a master node, so all the nodes are basically equal, it's also resilient in the sense that if multiple servers go down, yeah, the system just continues to function, so basically up to a total of yeah, and over two minus one servers can be down, so yeah, you can continue to function. And yeah, we also wanted it to be kind of like a drop-in replacement for the existing primitives that are there in the goal language, so the API or the interface is synonymous to the sync.RWMutex and actually the sync.locker interface. As part of our requirements, we maximized sort of the maximum number of nodes to a total of 15, 16. You could actually, if you wanted to push that number up a little bit, but 16 is yeah, good enough for us. And how this works behind the scene is that all servers basically have a connection to all of the other servers, and when one of the nodes asks for a lock, it basically contacts all the other nodes, and when a majority of the nodes, yeah, return back the lock, then yeah, the lock is grounded on that particular machine. And when you release it, again, it sends out release messages, and so it's relatively simple, but yeah, for us, it works quite well. Here is an example, maybe a little bit difficult to read, but again, the API is compatible with the regular RWMutex, so basically this is an example where you just create a mutex, and well, then you lock it twice, and then there's some go routines that after one and two seconds unlock the read lock, and then here you try to acquire a write lock, and obviously the write lock can only be granted when both of the read locks that were earlier granted were released, so you can sort of see here that, so it's acquiring read lock one, read lock two, and then it's trying to acquire the write lock, but it will block here until both the first read lock and the second read lock are released, and only then will it require the write lock, and obviously running this on a single machine is not really the point, but you can just as well create basically three of these named mutex on three machines and then run one read lock on one machine, another read lock on another machine, and the write on the third machine, and then the whole sequence of events would be identical. In terms of performance, on a 16-note configuration we were able to do like seven and a half thousand locks per second, and then it takes about sort of 10% CPU usage on a regular server, and typically a lock is granted within like one millisecond, so this quite nicely met basically our requirement in terms of an object storage, an object storage does not have the requirement that you're going to write like a hundred thousand objects to it in like a second, so maybe for something like a key value store, this wouldn't work, but in our case it quite nicely met our requirements, and it's nicely bundled with the menu distribution, and actually here's a pointer to the repository, and we also on our blog we have a blog post about this with some more details, so that pretty much brings me to the end of my presentation. Thank you for your attention, and go ahead. So I have a question, so you are using Blake to detect big road, correct, and then you have performance problems, but Blake is a secure hash, so why don't you use a narrow detecting code which is probably much, much cheaper instead of using a secure hash and then, you know. What do you mean by an error detecting code? Well, actually something like read Solomon or probably humming or I don't know something which is cheaper. Well, read Solomon doesn't give you bedrock, I mean read Solomon. It detects bit flips, so. No, not by itself. Maybe read Solomon, I can't do it, I have to look it up, but humming codes for example detect errors and there are much better suited codes for detecting flip, bit flips. No, the problem is there's parity blocks computed in read Solomon, but imagine you have four two data blocks and two parity blocks, and when you lose say two disks, so you're down to two blocks, then if you would just have two blocks you have no way to determine anymore whether there's bit rot or not. So, you're right, if you still have all the data and parity blocks available, you could work out whether a block that you read off the disk has not been unchanged, but it would be not easy to do so. And when you lose those disks, so you're down to the absolute minimum that you need in order to be able to reconstruct, then, yeah, then you have no way to detect bit rot anymore. Right? We talk about this later. I don't agree yet, but let's. Hi. You mentioned that this code doesn't rely on CGO. Is there any complication at all, compiling this kind of programs? No, it does not rely on CGO, but what is your question? Well, is there any complication compiling this program or is it just a go build and that's all? That's it. You will get all the repositories and it just builds normally and you just need to have the go chain installed, but no special other options or features of the go tool chain. Okay, it will just adapt to the platform, to the CPU and it's going to say. Yeah, no, absolutely, yeah. Great. Any other questions? No. Other questions there? Oh, coming. I was just wondering how did you write the assembly? I mean, you showed us all these op codes. Did you use some other assembler and then extract this or how did you? For that we developed basically this tool. So we developed this SM2 plan 9S tool which is also, here you see the repository. So basically this is what you write in your assembly file and then you run SM2 plan 9S on this file and it will prepend like the byte sequence. Oh, okay, sorry, I missed that. Okay, thank you. Yeah, otherwise it's a bit cumbersome. Pretty cumbersome. Any other questions? No? Oh, yes. Okay. Yes, my question was regarding to your SHA256 implementation. Have you thought about contributing it into the central library? Yeah, we were planning to do that but we need to do a bit more work for that but that will be coming, yeah. Just a second question, how come your implementation is faster than the GoSunder library for AMD 64 since both are in assembly and have an evaX2 implementation? So what, did you do something special? Well, I mean, there's different ways to do different things in assembly, right? So I mean, it's not going to be effector 2X but I mean, depending on how you exactly do it, you may see like still minor differences. So just like in regular high level Go, you can also, one maybe way of doing things maybe slightly better than another way of doing it. So. Thank you. Okay, thank you. Thank you.
 Okay, yeah, I'd like to speak about, yeah, some high performance and scaling techniques  that we've been doing in Golang. Small breakdown of the presentation, a few slides about myself  and some work that we do with Minio. Do you understand me or not? Okay. Is this better?  Is it better like this? Okay, great. So, a little intro about myself and Minio. Then  I'd like to speak sort of in general a little bit about, yeah, the Golang or Plan 9 assembly  capabilities that Go offers. Then discuss two sort of projects that we've done with this,  so Blake2B, Acceleration and Char2F6 acceleration, and finally some slides about some, yeah,  distributed syncing stuff that we've been doing. One slide about myself. I've been mostly  doing software development in sort of what's called the medical imaging space, so that  relates to like CT and MR images from scanners, both 2D, 3D, as well as using GPU techniques.  The last few years, I've been involved in cloud computing and I'm now with Minio. Minio,  as maybe some of you know, is an Amazon S3 compatible, yeah, object storage server.  It is, yeah, written in Golang under the Apache 2.0 license. The company was actually founded  by Anand Babu Parishyami, who maybe some of you know as one of the guys behind the Gluster  FS system, which is in itself a distributed file system, which is now part of Red Hat,  actually. If you look at Minio itself, there's actually sort of really, yeah, one project,  one binary, but you can run it in sort of three different flavors. So the simplest version  is simply run Minio server with a single directory and then, you know, all your objects will  be stored underneath this directory structure. And there are also, yeah, two other versions  that use a technique that is called erasure coding. So what this essentially does is all  the objects are split up into both like data chunks and parity chunks and, yeah, split  over, yeah, multiple disks or multiple servers. And the Minio server actually, the Excel backend  which splits the data over multiple disks, goes from a minimum of four disks up to a  maximum of 16 disks. And it also uses a technique that is called bitwalk protection. So this  means that when the data is being read off the disk again, which can be many years later  than when it is stored, a hash is computed to detect any, yeah, bitwalk changes. And  if that happens, then, yeah, we have other parity blocks to reconstruct the original  data. But as you can imagine, this bitwalk protection is a very frequent operation. So  any data that's written to disk, hashes have to be computed. And likewise, when data is  being read off the disk, yeah, the hash needs to be computed as well before we actually  can return, yeah, any information to the client. So that's a pretty important operation for  us. And that's why we really looked at how can we get sort of the maximum performance  in terms of hashing speeds while still, you know, having a solid proof and hashing technique.  So that's actually how we, yeah, did our Lake2B project. But before I go into that,  let me explain to you a little bit about, yeah, sort of the goal laying or plan nine  assembly capabilities. This is actually a, yeah, an integrated or integral part of the  whole go tool chain. And it's actually, it's kind of like a pseudo assembly language in  the sense that it's not a direct assembly that you would write for, say, an Intel platform  or an ARM platform. So there are some, like, generalized instructions for, like, a move  and an add and a compare. And these instructions are then obviously translated to the actual  instructions that will run on the underlying hardware platform. Most of the times, it's  kind of logical how, like, this pseudo assembly language translates into the underlying assembly  running on the CPU itself. Sometimes, yeah, that is not the case. So sometimes a little  bit of trial and error there. And also some architectural aspects of the underlying architecture  they shine through. So on the ARM, you have, like, conditional instructions and you can  do that too. And obviously on an Intel, that will not work. Also, for instance, data flows  from left to right. So if you do, like, a move, you have a move R1 to R2. It's actually,  R2 becomes R1. And, yeah, like on the ARM platform and the other way around. So there's  some things you have to be aware of. There's also some, yeah, like pseudo registers. So  they're not actual registers, but kind of like simulated registers for, like, frame pointer,  stack pointer, program counter. And also not all instructions that you would want to write  are available. However, it is possible to also, yeah, not use sort of the mnemonics, but use  the actual op codes that will go into the assembly. So if it's not available, you can  resort, yeah, to that. If you talk about, yeah, what are the sort of the advantages that  you get with, like, assembly language and obviously, yeah, it sort of gives you the  ability to get the maximum performance out of the underlying hardware. And also, if you  do this, then, yeah, you still benefit from, you know, the nice quick and fast compilation  that Go offers, you know, to get, like, assembly into your code. You can also use, for instance,  the Sego route. But, yeah, that has some disadvantages. One is that, yeah, you need to have the Sego,  yeah, available. It takes longer to compile because, again, it's more like a C-style compile  that happens. And also, when you call into that code, then, yeah, there is some runtime  overhead because all the stack needs to be saved and everything. And if you write your  own assembly, yeah, you don't have that overhead. And obviously, if you use assembly, you can  take advantage of the SMID instructions for Intel or the neon instructions that are available  on ARM. It's maybe a little bit kind of a word of caution is that you, yeah, you are  a bit on your own if you do this kind of stuff. The documentation is kind of limited and a  little bit sparse. There is a considerable amount of kind of example code in the Go  repository itself as well for stuff like New Texas and some lower level stuff. So, actually,  if you grab for start out as in the Go code, you will see, yeah, a lot of examples there.  And, yeah, likewise, we now have a few repositories where there's also some Go code in there.  And as an example, basically, this is actually, yeah, also a file where you can sort of see  the translation between this pseudo assembly language and the actual ARM instructions  as they are being generated. If you want to integrate, yeah, assembly into Go lang, then  you have to, yeah, use the.s extension for, yeah, basically assembly. And that is actually  prepended by sort of an architecture, yeah, identifier. So, underscore ARM64 means that  the assembly is for the ARM 64-bit platform and likewise AMD64 will be for, yeah, the  Intel or AMD64-bit platform. And actually, here is a snapshot of a repository. It's a  little bit hard to read, but here, actually, you can see actually several versions for  the AMD64 platform because in this repository, we actually have a dedicated AVX2, AVX and  an SSE version, and then there is an ARM version. I'll talk a little bit more about sort of  AVX2 and AVX later on in the presentation. So, kind of one approach that has worked nicely  for us is if you do this kind of stuff is to actually start out with, you know, an algorithm  at the Go level itself because even if you do this, then you are not likely to do all  the work for all the different architectures that are out there. So, it always makes sense  to have as a baseline sort of the functionality in Go itself. And then sort of as you start  to, yeah, translate that functionality into assembly, what we sort of did is we started  out kind of like with small bits and pieces. And so, you comment out most of the Go code  in your routine or class or whatever, and then you start to translate small bits and  pieces into assembly, maybe initially starting just with passing in the arguments and writing  back some results, making sure that all works. And once you got it working, then, you know,  you gradually start to translate more and more of your Go functionality into assembly  and along the way, yeah, make tests whether the assembly functionality is equivalent to  the Go assembly. So, actually, if you look, for instance, at the commit history of the  Blake 2B SMID repository, you can actually see how we used this technique. Along the  way, we also developed a small utility called SM2 plan 9S, which actually generates byte  sequence codes for OCCO or, yeah, assembly instructions that are not natively supported  by Go itself. So, actually, it uses the YASM assembler sort of behind the scenes. So, what  you do is you basically write your instruction as you would write it regularly in assembly,  and then you run the tool on the file and then it will prepend that instruction with,  yeah, the actual, yeah, opcodes that will go into the byte stream that will be executed.  So that has, yeah, worked nicely for us. If you look at, yeah, what we have done with  assembly, we've actually accelerated the Blake 2B algorithm as well as the SHA256 algorithm  and we're planning to do one more piece of work which has to do with this erasure coding,  which is actually called read solomon. And this uses some, yeah, what they call Galoi  field arithmetic polynomial multiplications. And ARM actually has a specific PMO instruction.  So we want to use that instruction to accelerate the read solomon computation of the parity  blocks for ARM. For Intel, it is already, yeah, accelerated, but we want to do the same  for the ARM platform. And, yeah, maybe when there is a need in certain pieces of the code,  then, yeah, we will likely do more. Okay, so the first technique that we accelerated  is a hashing technique that is called Blake 2B. Yeah, Blake 2B is a hashing technique.  It was actually, there was like a SHA3 competition a few years ago and they were one of the five,  I think, final contenders. In the end, they were not selected, but it is, yeah, a nice  hashing technique with sort of the characteristics that it's, yeah, it's really focused on speed  as well as kind of like a relatively simple algorithm to implement while at the same time  still offering sort of top of the, yeah, top of the bill security. And it's really optimized  for 64-bit platforms. So we developed a repository using the SMID instructions to accelerate the  Blake 2B algorithm. And actually, we did it in sort of three flavors. So there's an AVX2  implementation, which is the fastest. Then there's an AVX. And then there's an SSE implementation.  So depending on what your CPU support, then obviously the highest level of SMID instructions  that are, that is supported, that one will be used. But overall, we were able to achieve  close to like a 4x performance improvement over, yeah, the high-level Go functionality.  So yeah, that helped us quite a bit because if you look at the table on the right, you  can, that's a little bit too small, but we can do about 850 megabytes per second with  the Blake 2B algorithm on an AVX2 machine. And this compares to, if you look at SHA256,  that is at like 190 megabytes per second. And SHA512 is at about 300 megabytes per second.  And as an object storage, you can imagine if you have large blobs of data written on  the disk, then again, for us to be able to return like the first byte when people ask  for an object, say if it's a one gigabyte object, then having a factor of four there,  that means the difference between being able to return something within a second or within  it taking four seconds. So that's a pretty significant saving there. And again, yeah,  so we developed this technique for the BitRot detection mechanism that is part of Minio.  If you look a little bit closer at sort of how it works, at the top line, those are actually,  there's a very small portion of all the kind of computations that are happening as part  of the Blake 2B hashing. So there's basically four, yeah, additions there. And these are  on 64-bit integers. And if you look at the AVX capability for the Intel platform, you  can essentially work with 128-bit wide registers. So this allows you to do literally like two  additions in parallel. And this is kind of what you see here. So with AVX2, you use what  I call the XMM registers. So again, those are 128-bits wide registers. So essentially,  this means that whereas here, it's kind of like two lines, you can do it here basically,  yeah, in a single line. And likewise, at a second XMM instruction, we'll also take care  of two of these guys. So you can sort of go from like four to instructions to like two  instructions. And if you go one step further, AVX2 extended the pipeline to 256-bits wide,  which means that, yeah, you can use or do essentially four 64-bit additions with a single  instruction. So that's actually this guy. And then here you use the YMM registers instead  of the XMM registers. And again, those are 256-bit instructions wide. So in a way, this  kind of explains why there's kind of a four times speed up between, yeah, like Golang and  AVX2. There's a bit more there, but I mean, fundamentally, this explains it quite a bit.  If you look at Blake 2B, the algorithm itself, it actually has sort of 12 rounds of, yeah,  working on the data. This is kind of like the preamble where first the message is being  read in, then it's kind of shuffled around. And then there are two sort of macros that  actually do the actual like X-oring and adding and rotations of, yeah, all the bits. Then  there's like a diagonalized macro there, which kind of rotates, yeah, values between the  different, yeah, values that you are working on. Then there is a second half where you  load more from the message. You shove it a little again and you call the same macros  again. And finally, you bend diagonalized, so you sort of shift it back. And if you look  at, yeah, one of the macros, so in this case, this is the, what's called the G1 macro. It  actually consists a little bit of like three columns. So on the right side of the screen,  you kind of see the high-level Golang instruction. Then in the middle part of the screen, you  sort of see the AVX instruction. And then on the left side of the screen is the actual,  yeah, upcodes that are being written into the assembly stream. And so actually what  this guy does is here, there's like, this is an addition. This is like an XOR. Here,  you actually see a rotation, but the Blake II algorithm has selected like shift values  that nicely map onto, yeah, the Intel architecture. So you can actually, while it's a shift over  there, it's actually a shuffle. So you shuffle bytes around in between the registers. So,  and then there's more additions, more XORing, and then, yeah, get another kind of rotation.  And this happens, you know, over and over again, and then in a total of 12 rounds, and  that's, you know, how you get your hash out there. Okay. That was about the Blake II  B algorithm. We've also done some work on, yeah, a SHA256 algorithm, most notably also  for the ARM platform, because the ARM platform actually has specific instructions to accelerate  SHA256, yeah, calculations, and they make a tremendous amount of difference, because  it literally is 100 times faster than not using those instructions. And actually, Intel  also has instructions for SHA256 accelerations, but they seem to be just defined in software,  and there seem to be no hardware implementations out there. Otherwise, it would be nice to  take advantage of that as well. But actually, the table here at the bottom, you can sort  of see, yeah, the speeds that we have, and interestingly speaking, actually, the ARM,  just running at 1.2 gigahertz is actually the quickest one out there, so it does about  640 megabytes per second, and then we ran some tests on an Intel Xeon at 2.4 gigahertz.  The AVX2 comes in at about 355, then the AVX is running around 300, SSZ still a little  bit lower than that, and these are actually the Go versions, so if you do Go on the Intel  Xeon platform, you get about 190, and the last one is the ARM version. If you look at  how do you actually invoke assembly code from Go, you essentially define kind of the prototype  of the function that you're going to call into, so for most of this hashing techniques,  you pass in like the digest that you start with, and the message itself, so the digest  is basically just a slice of 30 qubit integers, and the message is just a slice of bytes,  and here we actually compute the 32-bit integers into the digest, so that's this guy, and then  basically the actual message as you go into hash is being passed in directly into what  will be the assembly code, and then once you're done, then actually the result is written  in this guy, so that is what you return, and this is actually an ARM example, so the first  line that's basically how you define the function in the assembly code, and the first thing  that you actually do is to read the parameters that were being passed in, and this function  takes two slices as inputs, and as maybe some of you know, a slice is actually a structure  with like three elements in it, and the first element is a pointer to where the actual data  is, and the second is actually the length of the slice, so what we're doing is the first  few instructions were reading this here, and because this is running on 64-bit platform,  both slices in effect, they take up a total of 24 bytes, so again it's three elements,  but each element is eight bytes long, so the first instruction basically fetches a pointer  to where the digest is, and the second line fetches a pointer to where the message is,  and then the length of the message is being read in the third statement, so it's another  eight bytes further than the already 24 bytes which point into the second slice that is  being passed in, and then further down here, we do some initialization, so here we load  from x0 which corresponds to r0, the digest, we also load obviously from the message itself,  and there's also a constant stable, so we get basically a reference to the constant  stable that's actually in r3, and r3 corresponds in neon to x3, so here we load values from  the constant stable, and this is actually sort of the main loop where the hashing is  being done, and again here r1 which is x1 is the pointer to the message, so here actually  the values from the message are being read, and well there's some positioning codes to  make sure things are in kind of the right order, and then these guys are actually the  specialized ARM instructions that give basically the hundred times speed up, and then there's  some more shuffling of data around, but yeah, all I have because these are specialized instructions,  the actual assembly is pretty short, and then yeah, this is like the end of the routine,  so again there's some ARM instruction or SHA extensions, instructions here, and then  here it's basically put into v1 and v0 and v1, and here actually you write out the result  in like register 4.1 and v1 into x0 which was the pointer to the digest, and then you  return out of there, and obviously here, well as long r2 is the length of the message, so  you process 64 bytes at a time and when there's more work to do, obviously you loop back.  So that's pretty much how a function like this looks a little bit.  If you look at some resources that we have that are out there, actually as maybe some  of you know, some of the origins of the go architecture and work go back to the whole  plan 9, yeah, worked on that has been done, and actually some of the assembly still originates  back to that, so some of the documentation out there, yeah, it's literally at the GP.io  website, so not everything in those URLs is kind of applicable, most of it is, but it's  their generally generally good resources to read through and get an understanding of how  this all works and ties in together, and then there's also like a high level SM document  and there's also some pointers for ARM, some pointers for Intel about how neon instructions  and AVX instructions work.  Okay, that was sort of the like the performance optimizations that we've done for, yeah, hashing  techniques.  We also did some work on something that we called a distributed syncing technique.  When I earlier talked about the three flavors of Minio that are there, the last one that  was listed is called the distributed version, and that's what we have two versions that  can work with erasure coding and then distributing the data across multiple either disks for  the Excel version or actually multiple servers for the distributed version, and for the distributed  version that can actually run from anywhere of a minimum of four servers up until a maximum  of 16 servers, we needed to have a synchronization mechanism between the servers, and yeah, we  also looked at some existing protocols and techniques out there, but yeah, we like a  technique like RAFT, but we found that a little bit overkill for sort of what we were trying  to do.  So we designed basically a pretty kind of minimalistic synchronization technique that  works well for us.  The design goals that we wanted to have was basically keep the design simple, also meaning  there's for instance no concept of like a master node, because well, if you have something  with a master node and the master nodes go down, goes down, then yeah, your whole system  is down, so you need to have backup master nodes and then you already talk about two  or three master nodes, and it quickly starts to become more complicated than what you initially  think.  So in our system, there's no concept of a master node, so all the nodes are basically  equal, it's also resilient in the sense that if multiple servers go down, yeah, the system  just continues to function, so basically up to a total of yeah, and over two minus one  servers can be down, so yeah, you can continue to function.  And yeah, we also wanted it to be kind of like a drop-in replacement for the existing  primitives that are there in the goal language, so the API or the interface is synonymous  to the sync.RWMutex and actually the sync.locker interface.  As part of our requirements, we maximized sort of the maximum number of nodes to a total  of 15, 16.  You could actually, if you wanted to push that number up a little bit, but 16 is yeah, good  enough for us.  And how this works behind the scene is that all servers basically have a connection to  all of the other servers, and when one of the nodes asks for a lock, it basically contacts  all the other nodes, and when a majority of the nodes, yeah, return back the lock, then  yeah, the lock is grounded on that particular machine.  And when you release it, again, it sends out release messages, and so it's relatively  simple, but yeah, for us, it works quite well.  Here is an example, maybe a little bit difficult to read, but again, the API is compatible  with the regular RWMutex, so basically this is an example where you just create a mutex,  and well, then you lock it twice, and then there's some go routines that after one and  two seconds unlock the read lock, and then here you try to acquire a write lock, and  obviously the write lock can only be granted when both of the read locks that were earlier  granted were released, so you can sort of see here that, so it's acquiring read lock  one, read lock two, and then it's trying to acquire the write lock, but it will block  here until both the first read lock and the second read lock are released, and only then  will it require the write lock, and obviously running this on a single machine is not really  the point, but you can just as well create basically three of these named mutex on three  machines and then run one read lock on one machine, another read lock on another machine,  and the write on the third machine, and then the whole sequence of events would be identical.  In terms of performance, on a 16-note configuration we were able to do like seven and a half thousand  locks per second, and then it takes about sort of 10% CPU usage on a regular server,  and typically a lock is granted within like one millisecond, so this quite nicely met  basically our requirement in terms of an object storage, an object storage does not have the  requirement that you're going to write like a hundred thousand objects to it in like a  second, so maybe for something like a key value store, this wouldn't work, but in our  case it quite nicely met our requirements, and it's nicely bundled with the menu distribution,  and actually here's a pointer to the repository, and we also on our blog we have a blog post  about this with some more details, so that pretty much brings me to the end of my presentation.  Thank you for your attention, and go ahead.  So I have a question, so you are using Blake to detect big road, correct, and then you have  performance problems, but Blake is a secure hash, so why don't you use a narrow detecting  code which is probably much, much cheaper instead of using a secure hash and then, you  know.  What do you mean by an error detecting code?  Well, actually something like read Solomon or probably humming or I don't know something  which is cheaper.  Well, read Solomon doesn't give you bedrock, I mean read Solomon.  It detects bit flips, so.  No, not by itself.  Maybe read Solomon, I can't do it, I have to look it up, but humming codes for example  detect errors and there are much better suited codes for detecting flip, bit flips.  No, the problem is there's parity blocks computed in read Solomon, but imagine you have four  two data blocks and two parity blocks, and when you lose say two disks, so you're down  to two blocks, then if you would just have two blocks you have no way to determine anymore  whether there's bit rot or not.  So, you're right, if you still have all the data and parity blocks available, you could  work out whether a block that you read off the disk has not been unchanged, but it would  be not easy to do so.  And when you lose those disks, so you're down to the absolute minimum that you need in order  to be able to reconstruct, then, yeah, then you have no way to detect bit rot anymore.  Right?  We talk about this later.  I don't agree yet, but let's.  Hi.  You mentioned that this code doesn't rely on CGO.  Is there any complication at all, compiling this kind of programs?  No, it does not rely on CGO, but what is your question?  Well, is there any complication compiling this program or is it just a go build and that's  all?  That's it.  You will get all the repositories and it just builds normally and you just need to have  the go chain installed, but no special other options or features of the go tool chain.  Okay, it will just adapt to the platform, to the CPU and it's going to say.  Yeah, no, absolutely, yeah.  Great.  Any other questions?  No.  Other questions there?  Oh, coming.  I was just wondering how did you write the assembly?  I mean, you showed us all these op codes.  Did you use some other assembler and then extract this or how did you?  For that we developed basically this tool.  So we developed this SM2 plan 9S tool which is also, here you see the repository.  So basically this is what you write in your assembly file and then you run SM2 plan 9S  on this file and it will prepend like the byte sequence.  Oh, okay, sorry, I missed that.  Okay, thank you.  Yeah, otherwise it's a bit cumbersome.  Pretty cumbersome.  Any other questions?  No?  Oh, yes.  Okay.  Yes, my question was regarding to your SHA256 implementation.  Have you thought about contributing it into the central library?  Yeah, we were planning to do that but we need to do a bit more work for that but that will  be coming, yeah.  Just a second question, how come your implementation is faster than the GoSunder library for AMD  64 since both are in assembly and have an evaX2 implementation?  So what, did you do something special?  Well, I mean, there's different ways to do different things in assembly, right?  So I mean, it's not going to be effector 2X but I mean, depending on how you exactly  do it, you may see like still minor differences.  So just like in regular high level Go, you can also, one maybe way of doing things maybe  slightly better than another way of doing it.  So.  Thank you.  Okay, thank you.  Thank you.
High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_0_131.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_132_467.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_468_6695.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_6696_15875.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_15876_16667.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_16668_19535.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_19536_19655.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_19656_41939.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_41940_43895.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_43896_51383.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_51384_51467.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_51468_51659.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_51660_51707.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_51708_51779.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_51780_51827.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_51828_52079.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_52080_53687.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_53688_53819.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_53820_53867.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_53868_53987.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_53988_54035.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54036_54083.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54084_54215.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54216_54275.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54276_54359.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54360_54419.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54420_54467.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54468_54575.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54576_54731.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54732_54779.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54780_54839.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54840_54911.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_54912_55019.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55020_55091.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55092_55139.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55140_55295.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55296_55439.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55440_55523.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55524_55571.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55572_55691.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55692_55751.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_55752_56087.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_56088_56147.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_56148_56423.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_56424_56483.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_56484_56687.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_56688_59087.png High_performance_and_scaling_techniques_in_Golang_using_Go_Assembly_59088_59205.png