<p>I'm wondering an idiomatic way of writing a concurrent multi-level map where work is done on the leaves. The constraints I've arrived at are:</p>
<ul>
<li>Deleting a child node should atomically write to both the parent and child nodes (i.e. lock on both N_p and N_c)</li>
<li>Operating on a child node is a write to that child node, but getting a reference or pointer to the node in the first place is a read on the parent node. I think the read on the parent and write on the child should be atomic with respect to other operations on the child node, therefore you must have a lock on the parent node in order to <em>acquire</em> (but not in order to hold) a lock on its child</li>
<li>Work is done at the leaves, so I'd like them to be somewhat parallelizable</li>
</ul>
<p><em>I'm not so much asking if this is correct but if the implementation I use below with a channel indicating when to yield the lock on the parent is idiomatic/understandable</em></p>
<p>What I've arrived at is the following (simplified to two levels to show what removal looks like, but the leaf work could be abstracted recursively):</p>
<pre><code>type childName string
type leafName string
type root struct {
sync.Mutex
children map[childName]*child
}
type child struct {
sync.Mutex
leaves map[leafName]*leaf
}
type leaf struct {
// has some state
}
// adds leaf if not exists and calls leaf.doWork()
func (*r root) DoWork(cName childName, lName leafName) error {
r.Lock()
locked := true
defer func() { if locked { r.Unlock() } }()
// make child if not exists
if _, ok := r.children[cName]; !ok {
r.children[cName] = &leaf{
leaves: make(map[leafName]*leaf)
}
}
// get pointer to child
c := r.children[cName]
// Is this confusing/nonidiomatic?
yieldCh := make(chan bool)
errCh := make(chan error)
go func() {
errCh <- c.doWork(lName, yieldCh)
close(errCh)
}()
// wait for child to obtain lock and close yield, indicating all reads/writes on parent are done
<-yieldCh
locked = false
r.Unlock() // before doWork returns, which can take a while
// return error
return <-errCh
}
// registers leaf if not exists and calls doWork
func (c * child) doWork(lName leafName, yieldCh chan bool) error {
c.Lock()
defer c.Unlock()
close(yieldCh) // done with reads/writes to parent
if _, ok := c.leaves[lName]; !ok {
c.leaves[lName] = new(leaf)
}
// Here I got lazy so for this exercise it's okay for leaves in the same end node to block each other
err := c.leaves[lName].doSomeWork()
return err
}
func (r *root) RemoveLeafButDoWorkFirst(cName childName, lName leafName) error {
r.Lock()
locked := true
defer func() { if locked { r.Unlock() } }()
c := r.children[childName]
// get pointer to child
c := r.children[cName]
// Is this confusing/nonidiomatic?
yieldCh := make(chan bool)
errCh := make(chan error)
go func() {
errCh <- c.removeLeafButDoWorkFirst(lName, yieldCh)
close(errCh)
}()
// wait for child to obtain lock and close yield, indicating all reads/writes on parent are done
<-yieldCh
locked = false
r.Unlock()
// unblocks root
if err := <-errCh; err != nil { return err }
r.removeChildIfNoMoreLeaves(cName)
return nil
}
func (r *root) removeChildIfNoMoreLeaves(cName childName) {
r.Lock()
defer r.Unlock()
if c, ok := r.children[cName]; ok {
if c.canRemove() {
delete(r.children, cName)
}
}
}
func (c *child) canRemove() bool {
c.Lock()
defer c.Unlock()
return len(c.leaves) == 0
}
func (c *child) removeLeafButDoWorkFirst(lName leafName, yieldCh chan bool) error {
c.Lock()
defer c.Unlock()
close(yieldCh)
err := c.leaves[lName].doSomeWork()
delete(c.leaves, lName)
return err
}
// takes time, best to do in parallel as much as possible
func (*leaf) doSomeWork() error { /* does work */ }
</code></pre>
<hr/>**评论：**<br/><br/>tgulacsi: <pre><p>Use sync.RWMutex, copy the child node to be able to release the lock on the parent.</p></pre>egonelbre: <pre><p>What is the purpose of this data-structure?</p></pre>karma_vacuum123: <pre><p>Every Go data structure is subject to race conditions in its scope. I say let the caller control the scope and do their own locking outside of your functions. Your map will be no more susceptible than any other Go data structure. Its not like slices, maps or records have concurrency control built in.</p>
<p>Typically callers will have some set of data structures they will want to have exclusive access to while they manipulate your map...easier for them to take one big lock for all of these instead of having N different packages creating M different locks over and over</p>
<p>There are very few cases I want libraries having an opinion on concurrency...mostly those where an external resource is being accessed (a db, webserver etc)</p></pre>2017asdf: <pre><p>Oh I should have specified this is my design for the control structure (a means to an end) and <code>doSomeWork()</code> does involve I/O. </p></pre>jeffrallen: <pre><p>I can't tell if this is brilliant for insane. :)</p>
<p>Seriously, I don't see any obvious problems here, other than the fact that this is subtle code which is not obviously correct (see: <a href="http://wiki.c2.com/?TwoWaysToDesign" rel="nofollow">http://wiki.c2.com/?TwoWaysToDesign</a>)</p>
<p>Before this was production-ready, it would need some heavy duty test code, which actually triggers races, and then which passes with "go test -race".</p>
<p>It would also need better documentation explaining what problem you are trying to solve, and why this non-standard setup is the solution. Your future self and or colleagues will thank you.</p>
<p>It has happened for me that while trying to explain and measure and justify why I'm doing something tricky that I prove to myself it would be better to just junk the entire thing. Going through that process is valuable no matter what the outcome, if you keep the tricky code or if you chuck it.</p>
<p>Good luck!</p>
<p>-jeff</p></pre>the_web_dev: <pre><p>Maybe put the code in a GIST for syntax highlighting? I wonder if nested locking would work.</p>
<pre><code>var db = map[string]map[string]string {
"one": map[string]string{ "two": "string" },
"two": map[string]string{ "two": "string" },
}
var locks = map[string]*sync.RWMutex {
"one": &sync.RWMutex{},
"two": &sync.RWMutex{},
}
func getNode(parent string, child string) string {
lock := locks[parent]
lock.RLock()
defer lock.RUnlock()
return db[parent][child]
}
</code></pre>
<p>```</p>
<p>In Golang do you need to lock the entire structure or merely the referenced objects being mutated? </p></pre>itsmontoya: <pre><p>Your locked Boolean is a race condition</p></pre>
