What is Resizable Concurrent Map
In one of the previous posts I told how to implement the world's “simplest lock-free hash table” in C ++. It was so simple that it was impossible to delete records from it or change its dimension. Several years have passed since then, and not so long ago I wrote several multi-threaded associative arrays without such restrictions. They can be found in my Junction project on GitHub.
Junction contains several multi-threaded map interface implementations — even the “simplest in the world” among them, called
You can read the explanation of how the Crude map works in the original post . In short, it is based on open addressing and linear probing . This means that it is essentially a large array of keys and values using linear search. While adding or searching for a given key, we calculate the hash from the key to determine where to start the search. Adding and searching data are possible in multi-threaded mode.
')
The linear map in Junction is based on the same principle, with the following exception: when an array is full, all its contents are transferred to a new array of higher dimension. When the data transfer ends, the old table is replaced with a new one. But how do we still manage to support multithreaded operations? The Linear map approach is based on the non-blocking Hash Map of Clif click on Java, with the exception of a few differences.
To begin with, we will have to slightly change the data structure. Crude map initially had two data elements: the
In the Linear map, the only data item is
The
With such a data structure, we can simultaneously replace the table,
Another difference between the two maps is that the Linear map stores the hash keys instead of the original ones. This allows us to speed up the migration, since in this case we do not have to re-calculate the hash function. The hash function used in Junction is also reversible, so the original key can always be recovered from the hash.
Since the hash function is reversible, the task of finding an existing key is as simple as calculating its hash. Therefore, Junction currently supports only integer keys and key-pointers. (In my opinion, it would be best to provide support for more complex keys by implementing a multithreaded set (set) instead of a map).
Now that you know when to start transferring data, let's consider the migration task itself. In essence, we must find each used cell in the old table and add its copy to the new table. Some entries will be in the same places in the array, some will have higher indices, and some will move closer to their ideal index.
Of course, if during the migration other threads can still change the data in the old table, everything becomes somewhat more complicated. Using a naive approach, we risk losing change. Suppose, for example, that our map is almost complete, but at this time two streams do the following:
At this point, we expect
To avoid the above problem, we can block multi-threaded changes with the help of readers-writer lock , although in this case the definition of “shared-exclusive lock” would be more appropriate. With this approach, any function that changes the content of the table will put a joint lock. The thread transferring data between tables will put an exclusive lock. And thanks to QSBR , no locks are needed for
But the Linear map does not. She is one step ahead - it doesn’t even require joint blocking to change data. The method is as follows: in the process of transferring data from the old table, the
This change affects all map operations. In particular, the
Now, if we allow multithreaded operations during data transfer, then obviously it is necessary to ensure that the same values correspond to each key in both tables. Unfortunately, there is no way to automatically set
In this cycle, competing streams can still change the original
In the current version of the Linear map, even
There are other data elements in the
What if several threads try to start migration at once? In the event of such a race condition, the Linear map uses double-checked locking to prevent duplication of the
In this post, I did not pay enough attention to the
This is how the Linear map looks in general! The Leapfrog map and the Grampa map in Junction are based on the same idea, but expand it in different ways.
Parallel programming is a difficult task, but I think that it is worth developing its understanding, since multi-core processors do not go out of use. That's why I decided to share the experience of implementing the Linear map. Examples are a good way to learn something, or at least become familiar with a new area.
Junction contains several multi-threaded map interface implementations — even the “simplest in the world” among them, called
ConcurrentMap_Crude . For brevity, we will call it the Crude map. In this post I will explain the difference between the Crude map and the Linear map from the Junction library. Linear is the simplest map in Junction, supporting both resizing and deletion.You can read the explanation of how the Crude map works in the original post . In short, it is based on open addressing and linear probing . This means that it is essentially a large array of keys and values using linear search. While adding or searching for a given key, we calculate the hash from the key to determine where to start the search. Adding and searching data are possible in multi-threaded mode.
')
The linear map in Junction is based on the same principle, with the following exception: when an array is full, all its contents are transferred to a new array of higher dimension. When the data transfer ends, the old table is replaced with a new one. But how do we still manage to support multithreaded operations? The Linear map approach is based on the non-blocking Hash Map of Clif click on Java, with the exception of a few differences.
Data structure
To begin with, we will have to slightly change the data structure. Crude map initially had two data elements: the
m_cells pointer and the m_cells integer.In the Linear map, the only data item is
m_root , which points to the Table structure, followed by the cells themselves as a single continuous block of memory.The
Table structure stores a new shared cellsRemaining counter, with an initial value of 75% of the table size. Each time a thread tries to add a new key, it first reduces cellsRemaining . If cellsRemaining becomes less than zero, then the table is full and it's time to transfer data to a new one.With such a data structure, we can simultaneously replace the table,
sizeMask and cellsRemaining in one atomic step, simply by redirecting the m_root pointer.Another difference between the two maps is that the Linear map stores the hash keys instead of the original ones. This allows us to speed up the migration, since in this case we do not have to re-calculate the hash function. The hash function used in Junction is also reversible, so the original key can always be recovered from the hash.
Since the hash function is reversible, the task of finding an existing key is as simple as calculating its hash. Therefore, Junction currently supports only integer keys and key-pointers. (In my opinion, it would be best to provide support for more complex keys by implementing a multithreaded set (set) instead of a map).
Transferring data to a new table is the wrong way.
Now that you know when to start transferring data, let's consider the migration task itself. In essence, we must find each used cell in the old table and add its copy to the new table. Some entries will be in the same places in the array, some will have higher indices, and some will move closer to their ideal index.
Of course, if during the migration other threads can still change the data in the old table, everything becomes somewhat more complicated. Using a naive approach, we risk losing change. Suppose, for example, that our map is almost complete, but at this time two streams do the following:
- Stream 1 calls
assign(2, "apple"), reducescellsRemainingto 0. - Stream 2 performs
assign(14, "peach")and reducescellsRemainingto -1. Migration required. - Stream 2 transfers the contents of the old table to the new one, but does not yet open up access to the new table.
- Thread 1 calls
assign(2, "banana")on the old table. Since the cell already exists for this key, the function does not reducecellsRemaining. She will simply replace “apple” with “banana” in the old cell. - Stream 2 links the new table with the
m_rootpointer, therebym_rootthe changes in stream 1. - Thread 1 calls
get(2)on the new table.
At this point, we expect
get(2) return “banana”, because the key was changed only by one thread, and this was the last value recorded. Unfortunately, get(2) returns the old value of “apple”, which is wrong. So we need a different strategy.Secure data transfer
To avoid the above problem, we can block multi-threaded changes with the help of readers-writer lock , although in this case the definition of “shared-exclusive lock” would be more appropriate. With this approach, any function that changes the content of the table will put a joint lock. The thread transferring data between tables will put an exclusive lock. And thanks to QSBR , no locks are needed for
get at all.But the Linear map does not. She is one step ahead - it doesn’t even require joint blocking to change data. The method is as follows: in the process of transferring data from the old table, the
value field of each cell is replaced with a special Redirect marker.This change affects all map operations. In particular, the
assign function can no longer blindly change the value field of a cell. Instead, it must perform a read-modify-write ( read-modify-write ) operation on value to avoid rewriting the Redirect token if it has been set. If the function finds a Redirect token corresponding to value , then the new table already exists and the operation must be performed on it already.Now, if we allow multithreaded operations during data transfer, then obviously it is necessary to ensure that the same values correspond to each key in both tables. Unfortunately, there is no way to automatically set
Redirect for the old cell and at the same time copy its old value to the new cell. However, we can ensure the integrity of the data by transferring each value in the loop. Linear map uses the following loop:In this cycle, competing streams can still change the original
value immediately after the stream responsible for the migration reads it, since the Redirect marker has not yet been set. In this case, when the stream transferring the data tries to set the Redirect marker using CAS , CAS returns an error, and the stream tries to perform the operation again, already with a new value. As long as the value in the source table changes, the data transfer stream will continue to try, but sooner or later the transfer will be successful. This approach allows multithreaded get calls to safely find values in a new table, while parallel assign calls cannot modify a new table until the migration is complete (Cliff Click hash map has no such limit, so there are a few more steps in its migration cycle).In the current version of the Linear map, even
get calls do not read from the new table until all data has been transferred. Therefore, in the latest version of the cycle is not necessary; Migration could be accomplished by performing an atomic exchange of value in the source table and then simply saving the value in the new table (I realized this when I wrote this post). Now, if the get call bumps into Redirect , it will help complete the migration. Perhaps if he immediately read the value from the new table instead, our solution would be more scalable. This is a topic for further research.Multithreaded data transfer
There are other data elements in the
Table structure that I haven't mentioned yet. One of them is a jobCoordinator . During data migration, a jobCoordinator points to a TableMigration object that reflects the migration process. A new table is stored in it until it is shared with m_root . I will not go into details, but the jobCoordinator allows several threads to participate in the migration process.What if several threads try to start migration at once? In the event of such a race condition, the Linear map uses double-checked locking to prevent duplication of the
TableMigration object. That is why each Table object has a mutex (Cliff's Click clipping is also different here. It optimistically allows the flow of threads to create new tables).In this post, I did not pay enough attention to the
erase function, because it is simple: it simply replaces the cell value with a special NullValue value, which we have already used to initialize it. The hash field, however, remains unchanged. This means that, sooner or later, the table may become overflowed with deleted cells, but when moving to a new table, they will be cleared. There are also a few subtleties regarding the choice of the dimension of the new table, but for now I’ll omit these details.This is how the Linear map looks in general! The Leapfrog map and the Grampa map in Junction are based on the same idea, but expand it in different ways.
Parallel programming is a difficult task, but I think that it is worth developing its understanding, since multi-core processors do not go out of use. That's why I decided to share the experience of implementing the Linear map. Examples are a good way to learn something, or at least become familiar with a new area.
Oh, and come to work with us? :)wunderfund.io is a young foundation that deals with high-frequency algorithmic trading . High-frequency trading is a continuous competition of the best programmers and mathematicians of the whole world. By joining us, you will become part of this fascinating fight.
We offer interesting and challenging data analysis and low latency tasks for enthusiastic researchers and programmers. Flexible schedule and no bureaucracy, decisions are quickly made and implemented.
Join our team: wunderfund.io
Source: https://habr.com/ru/post/324060/
All Articles