See "WriterReaderPhaser: A story about a new (?) synchronization primitive" <http://gil-says.blogspot.com/2014/11/writerreaderphaser-story-about-new.html>. WriterReaderPhaser (WRP) was designed for the common pattern of speed or latency critical writers writing and accumulating data into a data structure (e.g. a stats collecting like a histogram), and less-critical background threads occasionally or periodically gathering up that accumulated data is a lossless manner, and provides for wait-free writers and potentially blocking readers. It's a common pattern used and needed when e.g. logging of metrics or other stats is performed periodically, and I've used the pattern often enough that I decided it needs a new synchronization primitive.
For a full code example of how to use this synchronization primitive in e.g. a classic double-buffered approach around a simple data structure, you can see how an implementation of WriterReaderPhaser <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/WriterReaderPhaser.java> is used in HdrHistogram's SingleWriterRecorder <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/SingleWriterRecorder.java> and Recorder <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/Recorder.java> classes, both of which record data into an interval histogram, and provide for lossless reading of that interval histogram. Those are classic examples of stats written by latency critical writers in a wait-free manner, and collected by a non-latency critical background thread, and WriterReaderPhaser can be similarly used to coordinate this sort of work around any sort of stats-gathering data structure. The WRP's current implementation has the writer use a CAS to enter <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/WriterReaderPhaser.java#L73> and leave <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/WriterReaderPhaser.java#L91> the critical section. Single writer cases need no further synchronization, and multi-writer cases would need to coordinate on writing to the common data structure (e.g. a AtomicHistogram <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/Recorder.java#L314> or ConcurrentHistogram <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/Recorder.java#L326> in Recorder, depending on whether or not auto-resizing of the histogram is needed). A java implementation of WRP currently lives in HdrHistogram (which is available on maven central). It is too small for its own package and probably needs a better home. If interest in it grows, Martin can probably find it a home in Agrona. Other implementations have been built in e.g. other language versions of HdrHistogram (e.g. C <https://github.com/HdrHistogram/HdrHistogram_c/tree/master/src>, .NET <https://github.com/HdrHistogram/HdrHistogram.NET/blob/9d82f46d3abfd07d20df901e3fbcf015a8baf665/HdrHistogram/Utilities/WriterReaderPhaser.cs> ). On Tuesday, October 16, 2018 at 4:33:03 AM UTC-4, Mohan Radhakrishnan wrote: > > Hi, > There is streaming data everywhere like trading data , JVM > logs.etc. Retrieval of statistics of this data need fast data structures. > Where can I find the literature on such fast data structures to store and > retrieve timestamps and data in O(!) time ? Should this always be > low-level Java concurrent utilities ? > > Thanks, > Mohan > -- You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group. To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
