A world in a ref
At times I struggle deciding on the granularity I should give to my refs. If I put a big map in a single ref (what I call a megaref), updates to unrelated parts of the map may conflict and cause transactions to retry, but it’s dead easy to snapshot the whole state. If I use a ref for every entry of the map, concurrency is excellent again but snapshotting the whole state may be tricky (you need to tune the ref to have a history long enough) when there is a large number of rapidly changing refs or when the system is slow/loaded.
What I’d like is an alter-in function, a mix of alter and update-in, with the following guarantee: two alter-ins conflict when their paths are either equal or prefix from one another.
This is not something new: this problem bugs me since 2008 I think. I had several (failed/unfinished and private) attempts to patch the STM to accommodate for a new reference type.
Some weeks ago I realized that I didn’t need to hack the STM to create such a new reference type.
The basic idea behind all my attempts was to use lock-striping. What I didn’t realize is that I can leverage the existing STM by using ref-striping!
Let’s say the whole map is stored in a single ref, the root ref and you have N guard refs (whose value is nil). When I want to alter the value for a given key, I compute its hash modulo N which gives me an index into the guards vector. I ref-set the corresponding guard ref (to nil, the actual value doesn’t matter) thus claiming exclusive commit rights for this key. Once that done I simply commute on the root ref being sure that the operation will only commute with non-conflicting other ops.
NB: An alternative design is to simply have N roots and no guards and to merge the N maps on deref — efficient merging would need a didcated map implementation. However it doesn’t help much with nested maps but it helps a lot with concurrency since in the other design everything is serialized on the single root. I think an hybrid solution (N roots, each roots having M guards) woud bring an interesting trade-off between concurrency, number of retries and ease of snapshotting.
To support nested maps, instead of a single key, one has to deal with a path, eg [:a :b :c]. Here the idea is to ensure guards for path prefixes ([:a] and [:a :b]) and to ref-set the guard for the full-path as before.
;; except ensure-in and alter-in, the others are here because ;; they can be optimized in a mega ref wth several roots (defprotocol AssociativeRef (-alter-in [aref ks f args]) (-commute-in [aref ks f args]) (ref-set-in [aref ks v]) (ensure-in [aref ks]) (deref-in [aref ks])) (defn alter-in [aref ks f & args] (-alter-in aref ks f args)) (defn commute-in [aref ks f & args] (-commute-in aref ks f args)) (defn- ensure-path [guard-for path] (loop [path path] (when-not (= [] path) (ensure (guard-for path)) (recur (pop path))))) (defn- guards-fn [guards] (let [n (count guards)] #(nth guards (mod (hash %) n)))) (deftype MegaRef [r guards] AssociativeRef (-alter-in [this ks f args] (if (seq ks) (let [guard-for (guards-fn guards)] (ensure-path guard-for (pop (vec ks))) (ref-set (guard-for ks) nil) (let [v (apply f (get-in @r ks) args)] ; v is precomputed to not evaluate it twice because of commute (commute r assoc-in ks v))) (throw (IllegalArgumentException. "ks must not be empty.")))) (-commute-in [this ks f args] (apply commute r update-in ks f args)) (ref-set-in [this ks v] (-alter-in this ks (constantly v) nil)) (ensure-in [this ks] (ensure-path (vec ks) (guards-fn guards)) (deref-in this ks)) (deref-in [this ks] (get-in @r ks)) clojure.lang.IDeref (deref [this] @r)) (defn megaref [entries & options] (let [guards (:guards options 16) root-options (select-keys options [:validator :min-history :max-history])] (MegaRef. (apply ref (into {} entries) root-options) (vec (repeatedly guards #(ref nil))))))
NB: Write skew anomalies can now occur at the “sub ref” level: when you deref-in a path unrelated to the ones you update; ensure-in is the answer.
So, some questions:
- Is this of interest to anyone except me? If yes, once mature (eg multiroot) should it belong in contrib?
- Is my implementation sound? Do I rely on implementation details?
- Should the STM expose a “token” facility so that I don’t have to use refs as guards?
Nice implementation. I think we definitively need the choice of lock granularity in the STM. In some cases you can easily “shard” your mega-refs into single refs, which make handling harder. I tought about the problem for some time now, an I came to the conclusion that one must define something like tx boundaries on a data structure. The basic mechanisms are to use multiple refs and “ensure” but this gets messy soon. Using lock striping and commute as you pointed out is a great alternative. However this should be supported as first class citizens on clojure to make the STM a really
handsome tool.
I have run into similar issues and I think this is an interesting solution. We built something similar (in Java) at Terracotta to get tunable lock granularity in a variant of ConcurrentHashMap. Generally you want concurrency somewhere between one ref per key and one ref per map, not either extreme.
I think the idea of commuting the root ref and using N guard refs seems sound to me. I am less clear on the path implementation. I think only the root ref is commuted, which means alters of [:a :b] and [:a :c] would still conflict (even though they wouldn’t need to), right? Seems like you really want to commute at *every* guard above the change.
It would be conceptually nice if you could have the impl handle nested maps using composition of the type rather than baking it into the type definition. I’m not sure that’s possible, just a thought.
@Alex [:a :b] and [:a :c] don’t conflict: the guard for [:a] is ensured (basically it guards against a [:a] vs [:a :x] conflict) then the guards for [:a :b] and [:a :c] are set and the root commuted. I’m not sure composition is feasible but I haven’t tried too hard so…
Ah, right. All the paths are just ensured other than the write path which is ref-set.
Clojure and me » A world in a ref…
Clojure and me » A world in a ref…
[...] A World in a Ref — Christophe never fails to make me think and this post is no exception. This time he tackles the problem of STM refs containing uber-structures. [...]
[...] I recently published Megaref a refined (and working) version of the idea described in A World in a Ref. [...]
Hmm. I think this solves a problem I was wrestling with. Could it work also for vecs?
@Eric it works on any associative collection so yes you can use vectors. The ants demo uses vectors by the way.
Greetings from Florida! I’m bored to tears at work so I decided to check out your website on my iphone during lunch break. I really like the info you present here and can’t wait to take a look when I get
home. I’m surprised at how quick your blog loaded on my mobile .. I’m not even using WIFI, just 3G .
. Anyhow, fantastic blog!
[...] A world in a ref http://clj-me.cgrand.net/2011/10/06/a-world-in-a-ref/ [...]
Hello my loved one! I wish to say that this article is amazing, nice
written and include almost all significant infos. I’d like to see
more posts like this .
Very nice post. I just stumbled upon your weblog and wished to say that I’ve truly enjoyed surfing
around your blog posts. In any case I will be subscribing to your rss feed and I hope you write again very soon!
I’ve been browsing online more than three hours these days, but I by habbo coin generator no download means found any fascinating
article like yours. It’s beautiful worth sufficient for me.
In my opinion, if all site owners and bloggers made
excellent content material as you probably did, the web will likely be much more
useful than ever before.
see post
Clojure and me » A world in a ref
Eyy, excelente sitio,justo lo que necesitaba voy a recomendar
este blog. :)Gracias. Saludos Cordiales.
vip female escort
Clojure and me » A world in a ref
Thankfulnss to my father who stzted to me about this weblog, this webpage is really
amazing.
Also visit mmy website: short uurl (Ernest)
Hi there to every , for the reason that I am genuinely
keen of reading this webpage’s post to be updated daily.
It contains pleasant data.
[…] A world in a ref http://clj-me.cgrand.net/2011/10/06/a-world-in-a-ref/ […]
This website was… how do you say it? Relevant!! Finally I’ve found something that helped me.
Kudos!
really relevant data you have post here nice to see your blog and want to thanks to you and also appreciate you that you have provide here for us funny videos When you are busy in your work truly deeply then must have to take some relax and its only my opinion to just watch few funny things and get some fresh to your mind.
Good response in return of this difficulty with genuine arguments and telling everything
on the topic of that.
pixel Gun 3d hack apk 9.4.2
Clojure and me » A world in a ref
http://escortinriga.lv/
Clojure and me » A world in a ref
That’s such a nice and helpful article
That’s nice to provide information you not at this time COVID 19 causes is most increase all over world so i write a informative article about this Coronavirus Current Situation In Pakistan
ag.918kiss.Com login
Clojure and me » A world in a ref
online casino malaysia affiliate
Clojure and me » A world in a ref
Hello, I wish for to subscribe for this website to take latest updates, therefore
where can i do it please help.
his explanation
blog topic
Thank you, I have recently been looking for info about this subject for ages and yours is the best I have discovered so far.
But, what in regards to the conclusion? Are you positive concerning the supply?
Thanks , I’ve just been searching for information about this topic for a long time and yours is
the best I have discovered so far. However, what about the conclusion? Are you
certain concerning the supply?
Why visitors still use to read news papers
when in this technological globe the whole thing is presented on web?
Introducing Tyler Wagner: Allstate Insurance, the leading insurance agency located in Las Vegas, NV.
Boasting extensive expertise in the insurance industry, Tyler
Wagner and his team are committed to providing exceptional customer service and comprehensive insurance solutions.
From auto insurance or home insurance, or even life and business insurance,
Tyler Wagner: Allstate Insurance has your back. Our
wide range of coverage options guarantees that you can find the perfect policy to
meet your needs.
Recognizing the need for risk assessment, we strives to offer personalized insurance
quotes that reflect your unique situation. Through utilizing our
deep knowledge of the insurance market and advanced underwriting processes, Tyler
Wagner ensures that you receive the most competitive premium calculations.
Navigating insurance claims can be challenging, but our agency
by your side, you’ll have expert guidance. Our streamlined claims processing system and supportive customer service team
ensure that your claims are handled quickly and with the utmost care.
In addition, we are deeply knowledgeable about insurance law and regulation, guaranteeing that your coverage are consistently in compliance with the latest legal standards.
Our knowledge offers peace of mind to our policyholders, knowing that their insurance policies are robust and reliable.
At Tyler Wagner: Allstate Insurance, we believe that a good insurance policy is
a key part of financial planning. It’s an essential aspect for safeguarding your future and securing the well-being of those you care about.
Therefore, we take the time to get to know you and help you navigate through the selection of insurance options, making
sure that you have all the information you need and confident in your decisions.
Choosing Tyler Wagner: Allstate Insurance means partnering with a reliable insurance broker in Las Vegas, NV, who values your peace of mind and
excellence. Our team isn’t just here to sell policies; we’re your partners in creating a protected future.
So, don’t hesitate to contact us today and learn how Tyler Wagner: Allstate Insurance can transform your insurance experience in Las Vegas,
NV. Let us show you the difference of working with an insurance agency that genuinely cares about
you and is dedicated to securing your satisfaction.
Thanks for finally writing about > Clojure and me » A world in a ref
< Liked it!
Если вы решили самостоятельно заняться строительными и ремонтными работами, советуем Вам посетить наш сайт https://техноуспех.рф. Вы узнаете, как правильно подобрать инструмент и спецодежду, кабель для замены электропроводки, построить здание из пеноблока, сделать кухонный фасад, заменить кран, украсить окно витражом, восстановить старую мебель, отремонтировать кабельные линии, выбрать и утеплить окна, увеличить пространство с помощью света и многих других полезных советов.
Regards! A lot of postings.
Truly plenty of terrific data!
Terrific facts Thanks a lot!
Amazing all kinds of valuable tips.
Amazing tons of terrific tips!
Incredible tons of valuable material.
You actually mentioned this very well.
Whoa plenty of excellent advice!
Really loads of useful data.
Seriously tons of superb knowledge.