Ooof. The core collections in Java are well understood to not be thread-safe by design, and this <i>should</i> have been noticed.<p>OP should go through the rest of the code and see if there are other places where collections are potentially operated by multiple threads.<p>>The easiest way to fix this was to wrap the TreeMap with Collections.synchronizedMap or switch to ConcurrentHashMap and sort on demand.<p>That will make the individual map operations thread-safe, but given that nobody thought of concurrency, are you sure <i>series</i> of operations are thread-safe? That is, are you sure the object that owns the tree-map is thread-safe. I wouldn't bet on it.<p>>Controversial Fix: Track visited nodes<p>Don't do that! The collection will still not be thread-safe and you'll just fail in some other more subtle way .. either now, or in the future (if/when the implementation changes in the next Java release).<p>>Sometimes, a detail oriented developer will notice the combination of threads and TreeMap, or even suggest to not use a TreeMap if ordered elements are not needed. Unfortunately, that didn’t happen in this case.<p>That's not a good take-away! OP, the problem is you violating the contract of the collection, which is clear that it isn't thread-safe. The problem ISN'T the side-effect of what happens when you violate the contract. If you change TreeMap to HashMap, it's still wrong (!!!), even though you may not get the side-effect of a high CPU utilization.<p>---------<p>When working with code that is operated on by multiple threads, the only surefire strategy I found was to to make every possible object immutable and limiting any object that could not be made immutable to small, self-contained and highly controlled sections. We rewrote one of the core modules following these principles, and it went from being a constant source of issues, to one of the most resilient sections of our codebase. Having these guidelines in place, also made code reviews much easier.
FTA: The code can be reduced to simply:<p><pre><code> public void someFunction(SomeType relatedObject,
List<SomeOtherType> unrelatedObjects) {
...
treeMap.put(relatedObject.a(), relatedObject.b());
...
// unrelatedObjects is used later on in the function so the
// parameter cannot be removed
}
</code></pre>
That’s not true. The original code only does the <i>treeMap.put</i> if <i>unrelatedObjects</i> is nonempty. That may or may not be a bug.<p>You also would have to check that <i>a</i> and <i>b</i> return the same value every time, and that <i>treeMap</i> behaves like a map. If, for example, it logs updates, you’d have to check that changing that to log only once is acceptable.
Another way to get infinite loops is using a <i>Comparator</i> or <i>Comparable</i> implementation that doesn’t implement a consistent total order: <a href="https://stackoverflow.com/questions/62994606/concurrentskipset-compareto-instant-infinite-loop" rel="nofollow">https://stackoverflow.com/questions/62994606/concurrentskips...</a>
(This is unrelated to concurrency.)<p>Whether it occurs or not can depend on the specific data being processed, and the order in which it is being processed. So this can happen in production after seemingly working fine for a long time.
> I always thought of race conditions as corrupting the data or deadlocking. I never though it could cause performance issues. But it makes sense, you could corrupt the data in a way that creates an infinite loop.<p>Food for thought. I often think to myself that any error or strange behavior or even warnings in a project should be fixed as a matter of principle, as they could cause seemingly unrelated problems. Rarely is this accepted by whoever chooses what we should work on.
The mention of "could barely ssh in" reminds me of a situation in grad school where our group had a Sun UltraSparc 170 (IIRC) with 1GB HD and 128 or 256 MB of RAM, shared by maybe 8 people in a small research group relating to parallel and distributed processing. Keep in mind, Sun machines were rarely rebooted, ever.<p>So I guess the new user / student was trying to do things in parallel to speed things up when they chopped up their large text file into N (32 or 64) sections based on line number (not separate files), and then ran N copies of perl in parallel, each processing its own set of lines from that one file.<p>Not only did you have a large amount (for back then) of RAM used by N copies of the perl interpreter (separate processes, not threads, mind you!) processing its data, as well, any attempt to swap was interleaved with frantic seeking to a different section of the same file to read a few more lines for one of N processes stalled on IO. Also, probably the Jth process had to read J/N of the entire file to get to its section. So the first section of the file was read N times, the next N-1, then N-2, etc.<p>We (me and the fellow-student-trusted-as-sysadmin who had the root password) couldn't even get a login prompt on the console. Luckily, I had a logged-in session (ssh from an actual x-terminal - a large-screen "dumb" terminal), and "su" prompted for a password after 20-30 minutes of running it. After another 5-10 minutes, we had a root session and were able to run top and figure out what was going on. Killing the offending processes (after trying to contact the user) restored the system back to normal.<p>Edit: forgot to say: had the right idea, but totally didn't understand the system's limitations. It was SEVERELY I/O limited with that hard drive and relatively low RAM, so just processing the data linearly would have easily been the best approach unless the amount of data to be kept would have gotten too large.
Yep, ran into this way too many times. Performing concurrent operations on non thread-safe objects in java or generally in any language produces the most interesting bugs in the world.
I've seen this in production C#. Same symptoms, process dump showed a corrupt dictionary. We thought we were using ConcurrentDictionary everywhere but this one came in from a library. We were using .net framework, IIRC .net core has code to detect concurrent modification. I don't know how they implement it but it could be as simple as a version counter.<p>It's odd he gets so hung up on npe being a critical ingredient when that doesn't appear to be present in the original manifestation. There's no reason to think you can't have a bug like this in C just because it doesn't support exceptions.<p>To me it's all about class invariants. In general, they don't hold while a mutator is executing and will only be restored at the end. Executing another mutator before the invariants are reestablished is how you corrupt your data structure. If you're not in a valid state when you begin you probably won't be in a valid state when you finish.
> Could an unguarded TreeMap cause 3,200% utilization?<p>I've seen the same thing with an undersynchronized java.util.HashMap. This would have been in like 2009, but afaik it can still happen today. iirc HashMap uses chaining to resolve collisions; my guess was it introduced a cycle in the chain somehow, but I just got to work nuking the bad code from orbit [1] rather than digging in to verify.<p>I often interview folks on concurrency knowledge. If they think a data race is only slightly bad, I'm unimpressed, and this is an example of why.<p>[1] This undersynchronization was far from the only problem with that codebase.
What about spotting a cycle by using an incrementing counter and then throwing an exception if it goes above the tree depth or collection size (presuming one of these is tracked)?<p>Unlike the author’s hash set proposal it would require almost no memory or CPU overhead and may be more likely to be accepted.<p>That being said, in the decade plus I’ve used C# I’ve never found that I failed to consider concurrent access on data structures in concurrent situations.
Exceptions in threads are an absolute killer.<p>Here's a story of a horror bughunt where the main characters are C++, select() and thread brandishing an exception: <a href="https://news.ycombinator.com/item?id=42532979">https://news.ycombinator.com/item?id=42532979</a>
The author has discovered a flavor of the Poison Pill. More common in event sourcing systems, it’s a message that kills anything it touches, and then is “eaten” again by the next creature that encounters it which also dies a horrible death. Only in this case it’s live-locked.<p>Once the data structure gets into the illegal state, every subsequent thread gets trapped in the same logic bomb, instead of erroring on an NPE which is the more likely illegal state.
"I could barely ssh onto it"<p>Is there a way to ensure that whatever happens (CPU, network overloaded etc) one can always ssh in? Like reserve a tiny bit of stuff to the ssh daemon?
Does a ConcurrentSkipListMap not give the correct O(log N) guarantees on top of being concurrency friendly?<p>java.util.concurrent is one of the best libraries <i>ever</i>. If you do something related to concurrency and don't reach for it to start, you're gonna have a bad time.
Does it not strike anyone else as odd that if someone said they had a single CPU, and that CPU were running a normal priority task at 100%, and that caused the machine to barely allow ssh, we'd say there's a much bigger problem than that someone is letting on?<p>No 32 core (thread, likely) machine should ever normally be in a state where someone can "barely ssh onto it". Is Java really that janky? Or is "barely ssh onto it" a bit hyperbolic?
What I like here is the discovery of the extra loop, and then still digging down to discover the root cause of the competing threads. I think I would have removed the loop and called it done.
Just to probe the code review angle a little bit: shared mutable state should be a red/yellow flag in general. Whether or not it is protected from unsafe modification. That should jump out to you as a reviewer that something weird is happening.
I was excited to see that not only does this article cover other languages, but that this error happens in go. I was a bit surprised because map access is generally protected by a race detector, but the RedBlack tree used doesn't store anything in a map anywhere.<p>I wonder if the full race detector, go run -race, would catch it or not. I also want to explore if the RB tree used a slice instead of two different struct members if that would trigger the runtime race detector. So many things to try when I get back to a computer with go on it.
Very well said, and very nice to see references to others on point.<p>As a sidebar: I'm almost distracted by the clarity. The well-formed structure of this article is a perfect template for an AI evaluation of a problem.<p>It'd be interesting to generate a bunch of these articles, by scanning API docs for usage constraints, then searching the blog-sphere for articles on point, then summarizing issues and solutions, and even generating demo code.<p>Then presto! You have online karma! (and interviews...)<p>But then if only there were a way to credit the authors, or for them to trace some of the good they put out into the world.<p>So, a new metric: PageRank is about (sharing) links-in karma, but AuthorRank is partly about the links out, and in particular the degree to which they seem to be complete in coverage and correct and fair in their characterization of those links. Then a complementary page-quality metric identifies whether the page identifies the proper relationships between the issues, as reflected elsewhere, as briefly as possible in topological order.<p>Then given a set of ordered relations for each page, you can assess similarity with other pages, detect copying (er, learning), etc.
Anyone else mildly peeved by how CPU load is just load per core summed up to an arbitrary percentage all too often?<p>Why not just divide 100% by number of cores and make that the max, so you don't need to know the number of cores to know the actual utilization? Or better yet, have those microcontrollers that Intel tries to pass off as E and L cores take up a much smaller percentage to fit their general uselessness.
i found this article very/deeply informative , memory-wise , concurency vs optimizations and troubles thereof:<p>Programming Language Memory Models<p><a href="https://research.swtch.com/plmm" rel="nofollow">https://research.swtch.com/plmm</a><p><a href="https://news.ycombinator.com/item?id=27750610">https://news.ycombinator.com/item?id=27750610</a>
Somewhat relatedly, I've always appreciated Go adding some runtime checks to detect race conditions, like concurrent map writes. It's not as good as having safe concurrency from the ground up, but on the other hand it's a lot better than <i>not</i> having detection, as everyone makes mistakes from time to time, and imperfect as it may be, the detection usually does catch it quickly. Especially nice since it is on in your production builds; a big obstacle with a lot of debugging tools is they're hard to get them where you need them...
Should I read this as the Java TreeMap itself is thread unsafe, and the JVM is in a loop, or that the business logic itself was thread unsafe, and just needed to lock around its transactions?
In practice, it's rarely an issue in C# because it offers excellent concurrent collections out of box, together with channels, tasks and other more specialized primitives. Worst case someone just writes a lock(thing) { ... } and calls it a day. Perhaps not great but not the end of the world either.<p>I did have to hand-roll something that partially replicates Rust's RWLock<T> recently, but the resulting semantics turned out to be decent, even if not providing the exact same level of assurance.
> A while back my machine was so messed up that I could barely ssh onto it. 3,200% CPU utilization - all 32 cores on the host were fully utilized!<p>You wouldn't notice the load from 32 cpu pegging threads or processes on a 32-core host when ssh'ing in. Sounds like the OP is maybe leaving out what the load on the machine was, maybe it was more like thousands of spinning threads?
Why does the fix need to remember all the nodes we have visited? Can't we just keep track of what span we are in? That way we just need to keep track of 2 nodes.<p>In the graphic from the example we would keep track like this:<p><pre><code> low: - high -
low: 11 high: -
low: 23 high: -
low: 23 high: 26
Error: now we see item 13, but that is not inside our span!</code></pre>
Has anyone noticed an inability to horizontally scroll the code samples on chrome Android phones? I've noticed it on a few different blogs. The window has to be dragged at lower point on the screen to scroll the code section.
Does CPU utilisation calculations work this way?<p>- 1 CPU at 100% = 100%<p>- 10 CPUs at 100% = 100%<p>- 1 CPU at 100% + 9 at 0% = 10%<p>Is that not right? Or is CPU utilisation not usually normalised?
junior level error, dont understand whats to talk here about... Use ConcurrentSkipListMap and never write our own concurrent data structure unless you Doug Lea
Haha, I was recently running a backfill was quite pleased when I managed to get it humming along at 6400% CPU on a 64vcpu machine. Fortunately ssh was still receptive.