HNHacker News
TopNewBestAskShowJobs

NovaX

288 karma · joined May 4, 2011

https://github.com/ben-manes
submissionscomments
NovaX··on DragonFlydb: Cache Design
It is handled by W-TinyLFU where I use this scenario as a stress test [1]. While LIRS / LIRS2 did not pass this one scenario, the quality of the work behind that policy leads me to believe it could be improved to handle that case.

[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...

NovaX··on DragonFlydb: Cache Design
What about MRU-biased workloads? For example an analytical loop or row scanning in a db query? In those cases recency is a negative signal and there may not be much frequency to extract (e.g. equal frequencies in a loop). Instead the policy has to avoid admissions to obtain some hits rather than be flushed for zero hits.
NovaX··on DragonFlydb: Cache Design
frecency sounds similar to Redis' LFU which uses logarithmic counters [1]. Unfortunately many of these algorithms only do a good job in specific workloads and under perform in others. That's perfectly fine if one can narrow to a specific use-case, like a cache server which is LRU-biased [2], so the focus on other optimizations like Dragonfly's optimized storage costs makes a lot of sense.

[1] http://antirez.com/news/109

[2] https://github.com/twitter/cache-trace

NovaX··on DragonFlydb: Cache Design
> TinyLFU does not handle dynamic changes to demand to the cache like 2Q does

That was resolved in a follow up paper [1], though Ristretto does not implement this. It is implemented by Caffeine, mentioned briefly in this article, which is popular in the Java ecosystem.

[1] https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Ma...

NovaX··on Design of a Modern Cache (2016)
Part 2 covers adaptivity and expiration. [1]

There are also slides from Usenix Fast 20, but the video was not released (relevant [2], full [3])

[1] http://highscalability.com/blog/2019/2/25/design-of-a-modern...

[2] https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...

[3] https://drive.google.com/file/d/1oHV8SjrdhSdwgZ6jegJh8Ysrbnz...

NovaX··on Ask HN: Courses explaining well-written codebases?
"Operating Systems: Design and Implementation" is a classic book that was walks through Minix. It was a commonly used as a follow up course with projects to modify its code. Due to the author wanting to keep it dedicated towards education rather than real systems, it did not become a professional project but did inspire Linux' creation. There are similar books for other OSes, such as BSD and Solaris.

A broader but less detailed approach for casual readers are the books "Beautiful Code" and "The Architecture of Open Source Applications".

NovaX··on Rise of J2Cl: Java web development after GWT
In his book on api design, he repeatedly calls himself the next Newton. He rants that others don't recognize his genius yet, but expected to be revered by historians. The actual content in the book was shallow and poor. I hope he received mental help and is doing better now.
NovaX··on Jndi: An irresponsibly bad logging library
It was added by these maintainers in 2.x and did not exist in 1.x. The maintainers are also different from 1.x developers and took the brand. They may regret their past decisions, but it was is irresponsible to claim that it was not their fault and added for backward compatibility.
NovaX··on Object-Oriented Entity-Component-System Design
Unfortunately not. I simply realized later that my application design was conceptually similar to ECS. I could walk you through it over a Zoom, though.
NovaX··on Object-Oriented Entity-Component-System Design
entity = instance id

component = metadata + data

system = metadata processors

This way you can decouple business rules from the model by using metadata to instruct how the entity should be processed. At work we use json schema as our type system to describe our entities, where every instance includes the schemas that it implements. The metadata allows us to render an entity, process it via server-side triggers, store and search, use generic crud routes, etc. In a language like Java, this is the same as using reflection to inspect interfaces and annotations for processing an object.

NovaX··on Growing object-oriented software vs. what I would do
A language's core values is not determined by a small, vocal, subculture of its ecosystem. In Java's case, it was set early on to be a "blue collar" language [1]. If programmers fail to follow the spirit of the language then it will be awkward.

"So, how does Java feel? Java feels playful and flexible. You can build things with it that are themselves flexible. Java feels deterministic. You feel like it’s going to do what you ask it to do. It feels fairly nonthreatening in that you can just try something and you’ll quickly get an error message if it’s crazy. It feels pretty rich. We tried hard to have a fairly large class library straight out of the box. By and large, it feels like you can just sit down and write code."

Please do not push the programming community towards a tribal, us vs them, hostile environment where one belittles their neighbor. We can have interesting, fun, insightful technical debates! There's no reason to devolve into bigotry to "win" an argument, it's a lot more fun to learn from each other and do cool, new things.

[1] https://www.win.tue.nl/~evink/education/avp/pdf/feel-of-java...

NovaX··on Growing object-oriented software vs. what I would do
> In Java it would be a nest of SortComparator interfaces and SortAlgorithm implementors, which would act to hide the algorithm itself.

That is odd because when I look at the Java style, DualPivotQuicksort [1], it seems that the language authors did not do that. This is so very strange! Their methods are long, complex, and highly documented. Maybe they must be really incompetent Java programmers? I mean, they did put this obtuse abstraction by hiding it in Arrays. That's super crazy, just look at this monstrosity!!!

    public static void sort(int[] a) {
      DualPivotQuicksort.sort(a, 0, 0, a.length);
    }
Maybe you need to have an intervention with them? Somehow, in some crazy world, even Java programmers are capable of writing good and efficient code. Its like bad developers might do an awful in job in whatever language they used? Can't be true...

[1] https://github.com/openjdk/jdk/blob/master/src/java.base/sha...

NovaX··on Announcing Vitess 11
The last version, 10, brought in a scan resistant cache (the PR is interesting [1]). It would have made a fun blog post. Hopefully they can write more about the internals when they make these types of improvements.

[1] https://github.com/vitessio/vitess/pull/7439#issuecomment-77...

NovaX··on You can legally get and run WordPerfect for free
I'm disappointed that the author forget about the WordPerfect Suite in Java [1]. That's the cool mid 90s running Java 1.0 on your beefy Pentium 133mhz desktop. You can still freely download and run it (it was unusably slow back then).

[1] http://www.edm2.com/index.php/Corel_Office_for_Java

NovaX··on Show HN: We wrote a book about building business applications in Go
My only experience with Go was to help advise a team when porting a Java cache. They struggled with performance because Go kept fighting them. This was partially due to it having a poor concurrency library, resulting in excessive use of read/write locks whereas Java's advanced capabilities made more things lock-free. The database founder noted that Golang is slow single-threaded but makes up for it via concurrency and low latency.

To my unexperienced eyes, it seemed like a real PITA mostly because the Go authors insisted on artificial limitations externally, but bypassed them internally. I certainly have not found it hard to make Java fast and the core developers have always been open minded when I've talked to them.

NovaX··on Linux Kernel: The multi-generational LRU
That assumes the developer can provide correct hints, which unfortunately is rarely true. In my experience it is better to invest in an algorithm that can detect these patterns, learn from the workload, and optimize accordingly. Modern cache policies are robustly near optimal, but developers don't bother to implement them.
NovaX··on Linux Kernel: The multi-generational LRU
They decided against it, I believe because ClockPro was too complicated (but maybe NIH?). Instead they devised their own algorithm, DClock, borrowing ideas but is also different [1]. They use an ad hoc sizing rule (50%-99%) [2] which can dramatically impact its performance, neither extreme being universally better. When reimplementing their algorithm for analysis, the hit rates skewed towards being okay but not great [3]. You can compare ClockPro [4] and DClock [5] in the simulator.

[1] https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496...

[2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42...

[3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...

[4] https://github.com/ben-manes/caffeine/blob/master/simulator/...

[5] https://github.com/ben-manes/caffeine/blob/master/simulator/...

NovaX··on Segcache: A memory-efficient and scalable key-value cache for small objects [pdf]
A multi-threaded benchmark of a cache should be fully populated and use a scrambled Zipfian distribution. This emulates hot/cold entries and highlights the areas of contention (locks, CASes, etc). A lock-free read benefits thanks to cpu cache efficiency causing super linear growth.

This shows if the implementation could be a bottleneck and scales well enough, after which the hit rate and other factors are more important than raw throughput. I would rather sacrifice a few nanos on a read than suffer much lower hit rates or have long pauses on a write due to eviction inefficiencies.

[1] https://github.com/ben-manes/caffeine/wiki/Benchmarks#read-1...

[2] https://github.com/ben-manes/caffeine/blob/master/caffeine/s...

NovaX··on Segcache: A memory-efficient and scalable key-value cache for small objects [pdf]
Are you comparing a single threaded hash benchmark to a multithreaded cache benchmark? An unbounded concurrent hash table has 1B reads/s on a 16 core machine (~60M ops/s per thread)
NovaX··on Segcache: A memory-efficient and scalable key-value cache for small objects [pdf]
> However, if this design is used as a local cache over shared memory for a high throughput system (trading? ML feature store?) the scalability can be handy.

In that case, one might be concerned about the hit rates. While FIFO & LRU have been shown to work very well for a remote cache, especially in social network workloads, it is a poor choice in many other cases. Database, search, and analytical workloads are LFU & MRU biased due to record scans. I'd be concerned that Segcache's design is not general purpose enough and relies too heavily on optimizations that work for Twitter's use cases.

Unfortunately as applications have dozens of local caches, they are rarely analyzed and tuned. Instead implementations have to monitor the workload and adapt. Popular local caches can concurrently handle 300M+ reads/s, use an adaptive eviction policy, and leverage O(1) proactive expiration. As they are much smaller, there is less emphasis on minimizing metadata overhead and more on system performance, e.g. using memoization to avoid SerDe roundtrips to the remote cache store. See for example Expedia using a local cache to reduce their db reads by 50% which allowed them to remove servers, hit SLAs, and absorb spikes (at a cost of ~500mb) [1].

[1] https://medium.com/expedia-group-tech/latency-improvement-wi...

NovaX··on Multigenerational LRU: more performant, versatile, straightforward than Linux's
Two other papers that may be of interest are RC-Cache [1] (admission policy) and Deep Cache [2] (prefetch policy).

[1] https://ieeexplore.ieee.org/document/9109339

[2] https://dl.acm.org/doi/10.1145/3229543.3229555

NovaX··on Multigenerational LRU: more performant, versatile, straightforward than Linux's
The minimum-increment approach for a frequency sketch is supposed to help improve the sketch's accuracy. Instead of incrementing all of the hashed counters (e.g. 4), it first reads to find the minimum, and then only increments those. When analyzing for the purposes of TinyLFU this wasn't beneficial because it only cares about heavy hitters to judge relative worth so hit rate was unchanged.

The two halves can be any algorithm, but LRU and SLRU were chosen in Caffeine. SLRU uses a probation and protected region (20/80 split) so that on a subsequent hit, the item is moved into the protected region. This more aggressively removes an item that was not used, e.g. inaccurately promoted by TinyLFU due to hash collisions. It is a cheap way to get a good recency/frequency eviction ordering.

The frequency threshold is a direct comparison of the two victims (admission window's and the main region's). If the candidate has a higher estimated frequency than the main's victim then it is admitted, otherwise it is discarded.

The admission window accepts all new items and is placed in front of TinyLFU. TinyLFU implements the doorkeeper, popularity sketch, and reset interval. When reset, the doorkeeper is cleared and the counters are halved.

The optimal admission/main sizes depends on the workload. A LRU-biased workload prefers a large admission window (e.g. blockchain mining), while an MRU/LFU-biased one prefers a smaller window (e.g. loop/scans). The policy is adaptive by using hill climbing to [1] walk the hit rate curve towards the best configuration. The design evolution is described in [2-4].

There is no fast track promotion to the main region. A popular item will end up being promoted. The SLRU ordering and reset interval will age it out if unused. The adaptive sizing will grow or shrink the frequency region based on how effective it is.

Cache admission has not been well studied. While TinyLFU is an admission policy, W-TinyLFU turns it into a promotion strategy by always admitting into the window cache. Prior to TinyLFU, bloom filters were used by CDNs to avoid one-hit wonders from polluting the cache [5]. Afterwards, AdaptSize [6] used entry sizes instead of frequency as an admission criteria. RL-Cache [7] tries to defer to ML to sort it out from a dozen signals. There is a paper under review that optimizes W-TinyLFU for entry size aware eviction.

[1] https://dl.acm.org/doi/10.1145/3274808.3274816

[2] http://highscalability.com/blog/2016/1/25/design-of-a-modern...

[3] http://highscalability.com/blog/2019/2/25/design-of-a-modern...

[4] https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...

[5] https://people.cs.umass.edu/~ramesh/Site/HOME_files/CCRpaper...

[6] https://www.usenix.org/conference/nsdi17/technical-sessions/...

[7] https://ieeexplore.ieee.org/document/9109339

NovaX··on Multigenerational LRU: more performant, versatile, straightforward than Linux's
I would recommend W-TinyLFU [1]. It offers higher hit rates, is adaptive, has lower metadata overhead, is O(1), and is the only policy that is robust against all workload patterns we have tried. This is what I proposed to the Linux folks when analyzing DClock.

I met Kirk McKusick (BSD fame) at Fast'20 where he expressed interest in that for ZFS. We tried introducing the idea to the contributors at FreeBSD, Delphix, and LLNL. There is frustration at ARC being memory hungry and the locking is expensive. Unfortunately while there is interest in replacing ARC, all of our contacts were too busy to explore that option.

[1] https://github.com/ben-manes/caffeine/wiki/Efficiency

NovaX··on Multigenerational LRU: more performant, versatile, straightforward than Linux's
ARC shares the concept of non-resident (ghost) entries with LIRS, but uses that to dynamically adjust the SLRU partition (an LRU where probation entries are promoted to a protected region on a second hit). LIRS has fixed partitions and uses a larger history (~3x) to track the "inter-reference recency". This is a much more complex algorithm, but offers a higher hit rate and is more scan resistant. Linux's DClock calculates the "refault distance" which is their similar concept.

You can compare the code of ARC [1], LIRS [2], and DClock [3] to see how similar they are.

ARC obtained a lot of awareness but the hit rate is not that great. It is modestly better than LRU, but very wasteful in metadata overhead. LIRS is much better, except it is complex and the paper is confusing so almost all implementations are broken. DClock seems okayish by borrowing LIRS' ideas, but I think it performs worse in most comparisons.

[1] https://github.com/ben-manes/caffeine/blob/master/simulator/...

[2] https://github.com/ben-manes/caffeine/blob/master/simulator/...

[3] https://github.com/ben-manes/caffeine/blob/master/simulator/...

NovaX··on Multigenerational LRU: more performant, versatile, straightforward than Linux's
What is the relationship of this change with mm/workingset.c? [1]

That implements a custom algorithm, Double Clock, which is inspired by LIRS. This patch touches related code, but not that file where the core algorithm is described. I tried to reimplement it in a simulator for analysis and found its hit rate varied significantly on workloads due to the percent given to LRU/LFU regions being based on machine's total memory capacity [2]. That caused it to do better in MRU/LFU workloads on high memory systems and better at LRU workloads on low-memory systems [3]. Talking to the author and there were other details not documented that might make those regions adaptive. In the end, I gave up trying to understand the page cache and if there was a benefit of switching to an alternative eviction policy. It is well written but very confusing code that seems scattered if not a kernel developer.

[1] https://github.com/torvalds/linux/blob/master/mm/workingset....

[2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42...

[3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...

NovaX··on Continuous delivery makes JVM JIT an anti-pattern
> Kotlin methods are final by default unless marked open, and thus nonpolymorphic dispatch unless through an interface.

This is a language construct and not enforced within the byte code. There have historically been reasons to allow final to be ignored, such as serialization. Instead the JIT will optimize and deoptimize based on runtime behavior, allowing it to cover cases where overriding is designed for but not done so in the actual runtime environment. There was a nice presentation on "truly final fields" at the 2018 language summit [1].

[1] https://www.youtube.com/watch?v=2HfnaXND7-M

NovaX··on An Introduction to Lock-Free Programming (2012)
In the context of concurrent programming they are well known. We are not discussing how to program a PDP-8 but how to efficiently design multithreaded algorithms. This article recommends Nir Shavit’s book, who has written many well known papers including flat combining.
NovaX··on An Introduction to Lock-Free Programming (2012)
This is known as BP-Wrapper, a batching and prefetching technique, that also coined the term lock amortization. Sometimes this is confused with flat combining, which came out a little later and is a slightly different concept.

[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15...

[2] http://ranger.uta.edu/~sjiang/pubs/papers/ding16_BP-wrapper....

NovaX··on An Introduction to Lock-Free Programming (2012)
Perhaps the author is referring to a technique such as how a cache can be made concurrent [1]. In that case every read is a write, as LRU requires moving entries. Since an LRU is often implemented as a doubly-linked list, it either is a very complex lock-free algorithm or performed under a lock. The lock-free approach doesn't scale because all the recent entries move to the MRU position (tail), so there is contention.

The approach used in that article is to publish the events into multi-producer/single-consumer queues. When a queue is full, then the batch can be performed under a lock to replay and catch-up the LRU. This way the lock is used to ensure single-writer, but does not suffer lock contention. The ring buffer is lock-free, but the cache itself is not. Lock-free can suffer contention or be more expensive algorithmically than if under a lock, so whichever strategy chosen requires careful consideration of the system performance.

[1] http://highscalability.com/blog/2016/1/25/design-of-a-modern...

NovaX··on Why Java Is Dying
I have not used Spring since 2009 (where I used it daily) and have been using Java full time throughout. In that time I have written a lot of code and worked with many excellent teams. I’ve not had any of your problems because we always chose tooling that, for us, struck better balances and gave clear, concise error messages. There are certainly projects which are badly designed, but that is the team’s failing in every one of your complaints. Perhaps you should look inwards and not lash out against a large, diverse community.
← PreviousPage 3 of 6Next →