GitLab It's time to Go!, 23 Aug 2023

Previous Meeting

Next Meeting

⏯

youtube image

►

From YouTube: It's time to Go! Episode 7 - mutex striping

Description

Fixing mutex/lock contention by partitioning the mutex. See https://gitlab.com/gitlab-org/cluster-integration/gitlab-agent/-/issues/386#note_1524010603.

A

Wrong button, um hello: this is it's time to go The Reincarnation of that meeting, thanks for restarting it, and this is the first one and then.

A

New, it's a new new season.

A

And we I don't know what to talk about. Let's talk about what I'm working on, so it's this issue with, say: routing timeouts again, the some customers are getting errors agent not found. Is it connected? And so here this is a screenshot of the old dashboard new dashboard you can see uh this graph is, should be zero or almost zero, but there are occasional spikes, and this is not good. It was worse.

A

um We have fixed at the bunch of problems and yeah it's much better now, but still happens so I'm, not it's not correct and the day I found yet another problem which is looking at the profiler.

A

We see that the lane um in this interesting, it's showing you something else again.

A

B

A

Montana registry something's.

B

Wrong with this.

A

A

um It's showing me okay here, it is.

A

This is okay, and this is okay. If you look at it like this, but if you look at.

A

If you look at it like this, the one percent, we can see that this thing can take up to one and a half second or almost two seconds, so I unlock yeah trying to walk lock the meetings unlock. This is just the method that uh counts the con. The delay I I, think because this metric shows the delay. We are looking at the delay of that new text basic.

A

So it's a lot of time for this.

B

A

Not supposed to be blocked here, basically, I mean semi-toxes are okay to block and wait for a while, and but this one is not one of those. It's not shouldn't be so.

A

I expected this after one of the fixes, but then profiler was not showing this and now today, I found that it has actually showing this and it's not. Okay, so I'll reverse down um yeah and the previous version was even worse. This thing was blocked for up to like 14. something seconds. That's crazy, I, don't know how that even it's possible.

A

B

Is this kid up cast.

A

B

A

Is the profile for guitar introduction uh so.

A

um What this thing does Bridge the tunnel registry. It's.

A

um Its job is to register Thanos from HMK in radius and to find those tunnels across all cast instances. So so God's instances can see each other's registrations of tunnels for agents and then class can route and oncoming request to itself or another class instance based on this data.

A

I see so. The problem here is.

A

A

uh You cannot register this is the thing, so the there are two main methods and the tunnel. This is the one that accepts a connection from agent and registers it and, and then it blocks until it's canceled or the tunnel has been picked up and used, and then it returns a new owner and that is returned. uh Then the other important method is to find the tunnel for this agent ID and.

A

um We try to find it a tunnel in this class. Basically.

A

Or we remember that there is a request to find the tunnel for this, so this parameter for these parameters, agent, ID service method and where to return it and then.

A

Foreign handle it's like a handle for the fine decoration basically, and you can block on it to get the tunnel and that doesn't matter. So what matters here is this mutex, it serializes, so it protects these three Maps and tunnel register is also called when the mutex is held.

A

So here, for example, this is locked registered panel locked so it must be called the mutix health. So we hold the Matrix here and then call it to register the panel. Then there is also yeah. It's also called here to register it and.

B

A

There is an register at this method, uh which is the same. It's called user, Matrix, locked and so the problem is. There are a lot of Agents establishing lots of panels, so they all try to register and register, and all of that creates contention on the mutex. And what makes it worse is that the register and the register IO operations.

A

So we need to talk to radius and to like to set the value there or to remove a value from a hash.

A

So as an optimization, actually, register Tano and registered panel only set the value once they don't. So, if, if there is a cast URL for this agent, capacular of this cast for this agent is there already, then we don't need to do this, basically, no iOS performed, but this is still recording, causing some problems. Looking the based on profile, um so I think this mutex is the bottleneck basically, and that's what we've seen the profiler.

A

So what what do we do about it? Do you have any ideas, any suggestions.

B

So if I understand correctly.

B

um That map data structure is shared among the threat, so we use sync mutex to synchronize them right like these three data structures. Yes,.

A

B

A

Also find request to buy also this one, this one registers also well, we call it within the mutex section I see so maybe action I want to reply.

B

Just just general idea is: um maybe we should think about how we can minimize that critical section like studying, mutex log and the end of transaction. We unlock the mutex, but we need to minimize the transaction right.

B

Only. We have to lock only when it is critical for.

A

B

Structure so, but this is very general, so I'm not sure if it works in this case well,.

A

It it does work we used to. Where is it we used to.

A

Looking for something.

A

Well, it's not it's not here it's in the track. Okay, so we used to run garbage collection in the hash synchronously while holding a mutex, but now we prepare for garbage collection of our holding commuters and then run it without the mutex itself. So this helped quite a bit I see. So this is a way to minimize the critical section, but.

B

A

The other parts like there's even I, don't think there's a way to minimize the critical sections further. So.

A

um Any any other ideas, what what is possible.

B

uh Other idea is so we find this issue at the production right.

B

um The reason why we found it in production might be because there are many data too many data in the production, so can we reproduce it in locally and so that maybe we can test it and find some bottleneck easier and just the idea.

B

Like writing some tests test on this case, with like generating a lot of mock data and yeah, run it and see.

A

It's actually a good good idea. I haven't tried that, but we see that from from the profiler that this Matrix is seeing some contention so.

A

What they actually want to do is there's a technique called lock, striping. It's. The idea is to partition that they what okay advancement the idea is to partition the the data so that each partition has its own mutex.

B

Yes, partition and then.

A

Instead of one mutex, everybody tries to grab, you have n mutexes, the number of.

B

A

And clients grab some mutexes depending on the client ID. In this case, partitioning key is client, ID and agent ID, in this case, I.

B

A

That's why that's how you can do it?

A

So it's theoretically, each agent ID only needs to be uh operations for each agent. Id only need to be synchronized serialized for that agent IG, but that can be difficult to actually implement um just.

B

Because you have this.

A

Structured, this expiring hashes structure.

A

So yeah this is something that is a wrapper on top of radius hash, which is just a hash map, but it's a two level hash mark. So he.

A

Is the key of by that key will find the hash itself in radius? Then, within that hash we have he within the head and then we have value about key. So it's a real two level hash, basically or a clash of hashes. If you, if.

B

You want pretty interesting, but so what? uh What? What brings you to this like two level hash, very.

A

Interesting, so we use it on multiple places. uh First, um in this case, that's where we store um tunnels by agent ID, so key is Agent ID.

B

A

The second key within the hash is the cast URL and the value is nothing so it's a set. Basically, it's not a hash, it's a set in this case, so it's a hash offsets where first key first level is Agent ID and the second is a set of cast URLs for this agent ID.

A

So that way we can look up a list of cast URLs that have a connection from this agent ID and there are a few other places where we use this, for where value is not new and yeah. So the purpose of this is to add expiration to to the second level of Road mapping, because in the radius you can have an expression on the whole hash, but not on a key value pair in inside of the hash.

A

So I see we just implement this ourselves by putting it time to leave them in there and periodical scanning everything and deleting what has expired um and or updating what hasn't fixed by what we don't.

B

A

B

Nearly added by you.

A

B

A

I see wow, this is uh yeah. We use this in several places.

A

um Well at least agent, director and tunnel tracker and.

B

A

Anyway, so currently, this is a single single structure here in the radius tracker.

A

Yes for all the agent ideas and then internal registry, we also have a single.

A

Structure, a set of tunnels and the set of are not set again a first offset. Basically- and this is a hash offset as well so Thanos by agent ID and find requests by agent. Peggy I mean it could have been at least, but it's a set so that I can delete from the set by by the point correlation.

A

Simplified, so what I want to do is I want to partition all of this by agent ID.

B

Mm-Hmm I understand and.

A

Then each partition will have its own view, text.

A

And that way everything will be more complicated, but we will get rid of the contents.

B

Yes, then, the maximum number of um mutex will be the number of Agents ID or some number.

A

We can configure.

B

A

And we, as I said, we don't want to do a PR agent IG, because it will be difficult to shuffle the code like this um yeah. This whole expiring hash will not work like this.

B

A

Yeah I haven't came up with a way to do it.

A

Without completely rewriting everything here, but I don't want to do that.

A

No, it shouldn't be necessary, so what I'm thinking is just using, maybe so I will prepare this stripe already. I think which is you can see the good explanation of this whole idea in go out. Actually, uh it's a Java library for Google virus version blocks and.

A

This is the idea basic.

A

Ally, so this sounds the problem to Dynamic to select trade. Those you can carry some other consumption, so what I have done here is basically.

A

um A single stripe is this: mutex plus m a value values some value using a generic, and then we have a list of those things and we use power of 2 to use bitwise operations to get the remainder of the division instead of actually using your Division and remember, division because that's much faster, we just and with the mask and get the lowest significant M lost bits using just end with the mask, and we prepare the mask here.

A

um So this is all Beats set maximum integer 64. uh signed integer, so it doesn't matter so all all bits set. Then we move move it.

A

And bits and then we negate that using bitwise not to set or lost n Bits, basically.

B

A

Or we could we could move right with 64 minus and something like this doesn't matter um yeah. So this is our masks mask and we just pick the slot in this slice and in that slot we have a mutex and the value this. This is our striped value, mutex plus beta, not just the mutex but mutex plus, it is just more convenient to use and we have a lock for this ID.

A

This will be the agent ID and then unlock for that for the key and then try a lot as well, because so then I want to use it.

B

A

And the value will be.

A

A

A

A

When do you think about this, is it too crazy.

A

Also, the register.

A

Because this thing requires GTM refresh so I'm at the same time, I'm removing a text. Let me show I'm removing the text from here from registracker and removing garbage collection and refresh from here as well. You see removing the music, because now the register will be responsible for calling the garbage collection and refresh because.

B

A

Kind of doesn't make sense to hold the lock in a nested way, like I have the lock in the second layer layer if the first layer holds the lock already always so. I'm yeah I decided to remove it from here and to every single layer of locking to simplify things and speed things up as well, but yeah I'm. Thinking of doing it like.

A

It's gonna be that.

A

ah Maybe I don't mean uh eight bits.

A

um The arcade wants to type parameter: okay,.

A

A

We need a lot of this registers.

A

How will that work.

A

A

A

Anyway, so I'm trying to do this craziest thing to partition or the state.

B

A

It should reduce the problem too.

A

Okay, this will be for the register, so I will do the unlock for.

A

A

And a little bit you know and then.

A

Before this unlock.

A

This will be used here in the registration yeah. um This look looks messy because yeah I am not. I have only started trying to implement this idea. This may be not. This will likely be not separate Fields, but actually maybe a single field. So sorry, single struct, with a single striper.

B

B

How, how did you decide um just n and eight in the line yeah.

A

I mean good to have some space. Maybe it should be like 6 or 64 partitions I.

B

Still don't freely understand that that bitwise operation uh like mask so giving here the number six or eight so.

A

A

um This is my playground all right.

A

This will be once shifted by six will be 64. or 64 partitions.

B

So two to six I guess.

A

Yeah two power: six.

B

Power over six yeah I see so it it. It will create 64.

A

B

A

64 partitions containing each campaign, the state that we want to Partition.

B

A

A

It will be a single struct value and then there will be I, don't know state, and then this will contain all that.

A

A

A

Ump on there and then log out.

A

Yeah, this will be striped mutex around all these things.

A

And when we need to grab a lock, we will do.

A

A

And then this will be our.

A

Photography, I, don't know yeah. This needs to be updated.

A

Now, let's say arranged.

A

Support this I don't know, I will come up with a battery and by the way this needs to be a typical planter. No, it can be faster.

A

And then we'll have.

A

A person that works, I, guess.

A

It might be yeah.

A

B

Okay, another question um so you have can I. Could you go to the data structure of s state or estate? um Oh yes,.

B

What actual value or struct oh.

B

Like, for example, these tons right inside the tons so key is the pointer to toenail and having what what kind of struct do they have uh this? Yes,.

A

It's an abstract, meaning that it's abstract with no Fields, so no nothing is in there. Oh, this means it's a set. Basically, it's a map with some keys, but values are empty.

A

So it's a set set is.

B

A

Cash without values.

B

um I see so is it same for the tons by agent ID yeah inside the.

A

Map yeah, it's a typical pattern in go where to build a set. You just use a map where.

B

Values are struck.

A

B

A

And I think compiler actually optimizes this to not take any space of ideas, so we don't actually have I, have the map that only has keys and has no values in memory.

B

Okay, I see thanks.

B

This is something very uh technically challenged, challenging and.

A

B

It looks very to me, it looks very complicated but very interesting.

A

Now it unfortunately, it has to be complicated like this to to what it does I don't know would be nice to simplify, but how to simplify it. Further.

B

Yeah but I think that's very nice approach to having like many like increase the number of partition and.

A

B

That maybe yeah, like data yeah I, think it's no it's kind of a data race right. So maybe we can decrease the load of data race.

A

um Yeah we can decrease contention by having no mutexes, basically just.

B

A

The Music Center multiple.

B

A

And I'm thinking 64 should be okay, maybe even more because memories not that expensive. It's not going to use a lot more memory, but if we can reduce contention a little bit more, a little bit more memory is okay. If you refuse a little bit more.

A

That's probably single digit megabytes, maybe even before but I don't know. We can estimate that, but I don't I mean it's all of that will be less than one megabyte. So who cares? It's not yeah through.

B

I will have a look about that cover Library.

A

In there they have a lot of interesting things there, but yeah lots of that is not applicable to go.

A

People just might do without those interesting Collections and other things, um because it wasn't possible to write such libraries before before generics.

A

um It's always generics. People will probably start writing defense collection, libraries and proceed.

A

Okay, this is this is what I have so far with this issue. I yeah I only started working on this several hours ago. As you see it's, it's not become a compile.

B

A

Yeah but I wrote some tests for the value like working, unlocking and then trying to do the same index, dialogue and then same stripe like one and five will be in the same stripe for four shards, so two bits of four values so.

A

I just maturity, even you know we'll wrap around. It will have the least significant bit set only and that's why one and five are in the same stripe. So.

A

If you lock, one try lock, five should fail to work because it's the same stripe and we already have already hold the mutex for this stripe and once we unlock it, we can log 5.

A

and that, once you have locked right, we cannot lock one.

A

And I see working multiple Stripes is okay,.

A

uh Actually, we can.

B

A

Yeah different straps.

A

Yeah, which should be okay as well.

A

We can also use zero here called consistency.

A

And these are different um yeah.

A

Okay, I'll probably continue this tomorrow.

A

Hey, yes, do you have any any other questions anything else.

B

I think I already asked yes enough. Questions yeah, okay,.

A