Comments (4)
Nodes are reference counted using atomic counters and updating operations will access hash tables that are guarded by mutexes. Otherwise the sets and maps are backed by immutable trees that make them inherently thread-safe by design.
You can think of the sets and maps as smart pointers that point to nodes in a forest where all nodes are immutable. Updating a set or a map can add new nodes to the forest and/or delete old nodes that are no longer reachable, but can never modify any existing node that can be reached from other sets or maps. As with smart pointers, one instance of a set or a map should not be updated simultaneously from different threads (as a smart pointer itself is usually not guarded in that way), but it is fine to perform read operations from different threads. It is also fine to use the copy constructor to clone a set or map in O(1) and then update the cloned instances concurrently.
from confluent.
yeah, smart pointer itself is usually not guarded updated simultaneously.
node_ptr node_ in source code will be accessed in different threads, how to addref node and return node ptr atomic?
I am building some tree structure for metadata work with raft, singe write and muliti-read scene, and support O(1) snapshot. node_ptr node_ in map is threadsafe? I think it need atomic load and store to protect concurrent access.
usage:
confluent::map<std::string, std::string> kv1;
thread1:
kv1.insert("test", "value");
......
kv1.remove("test2", "value2");
......
confluent::map<std::string, std::string> kv2 = kv1;
for (it = kv2.begin(); it != kv2.end(): ++it)
serialize_and_dump(it->first, it->second)
thread2-threadn:
kv1.find("test1");
......
kv1.find("testx");
from confluent.
The following is not safe:
thread1:
kv1.insert("test", "value");
thread2:
kv1.find("test1");
An obvoius problem is that thread2 would explore the tree without holding a reference count on the root node, so that the searched nodes could disappear while the find operation is in progress.
I have worked with similar implementations in the past that allow this kind concurrency by making the root node pointer atomic and also increasing the reference count on the root node, to protect against deallocation while operations like find() are exploring the tree. It comes with a severe performance penalty though. First it requires load and store fences in all entry points to ensure cache consistency. Then all usage of atomics, mutexes and memory barriers insert compiler barriers that prevent the optimizations a compiler otherwise could do. With the current implementation read operations performs similar to ephemeral implementations, but that would not be possible if additional synchronization was always added just because it would be useful in rare cases.
On the other hand it should be fully possible to wrap the current implementation to add more synchronization when needed.
The following should be fine:
std::mutex m;
confluent::set<int> s;
confluent::set<int> get() {
std::unique_lock<std::mutex> lock(m);
return s;
}
void update(const confluent::set<int>& s1) {
std::unique_lock<std::mutex> lock(m);
s = s1;
}
thread1:
{
auto s1 = get();
s1.insert(1);
s1.erase(2);
update(s1);
}
thread2:
{
for(int i : get())
std::cout << i << std::endl;
}
from confluent.
yeah, wrap with mutex is simple, and i have a same mutex treap implementation ;-)
from confluent.
Related Issues (1)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from confluent.