A world in a ref

unsorted — cgrand, 6 October 2011 @ 13 h 00 min

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?

34 Comments »

  1. 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.

    Comment by Philipp Meier — 6 October 2011 @ 14 h 43 min
  2. 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.

    Comment by Alex Miller — 6 October 2011 @ 17 h 15 min
  3. @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…

    Comment by cgrand — 6 October 2011 @ 17 h 26 min
  4. Ah, right. All the paths are just ensured other than the write path which is ref-set.

    Comment by Alex Miller — 6 October 2011 @ 21 h 49 min
  5. Clojure and me » A world in a ref…

    Clojure and me » A world in a ref…

    Trackback by pligg.com — 11 October 2011 @ 6 h 16 min
  6. [...] 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. [...]

    Pingback by fogus: The best things and stuff of 2011 — 31 December 2011 @ 17 h 01 min
  7. [...] I recently published Megaref a refined (and working) version of the idea described in A World in a Ref. [...]

    Pingback by Clojure and me » Follow-up: A world in a ref — 21 September 2012 @ 8 h 35 min
  8. Hmm. I think this solves a problem I was wrestling with. Could it work also for vecs?

    Comment by Eric Normand — 22 September 2012 @ 3 h 36 min
  9. @Eric it works on any associative collection so yes you can use vectors. The ants demo uses vectors by the way.

    Comment by cgrand — 22 September 2012 @ 8 h 48 min
  10. 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!

    Comment by espresso maker — 18 June 2013 @ 2 h 11 min
  11. [...] A world in a ref http://clj-me.cgrand.net/2011/10/06/a-world-in-a-ref/ [...]

  12. 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 .

    Comment by how to set up google authorship — 27 August 2014 @ 17 h 29 min
  13. 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!

    Comment by m88 — 18 December 2014 @ 3 h 59 min
  14. 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.

    Comment by habbo coin generator no download — 19 March 2015 @ 21 h 30 min
  15. see post

    Clojure and me » A world in a ref

    Trackback by see post — 28 March 2015 @ 4 h 45 min
  16. Eyy, excelente sitio,justo lo que necesitaba voy a recomendar
    este blog. :)Gracias. Saludos Cordiales.

    Comment by gigantictorpor969.wordpress.com — 17 May 2015 @ 21 h 06 min
  17. vip female escort

    Clojure and me » A world in a ref

    Trackback by vip female escort — 29 May 2015 @ 9 h 11 min
  18. Thankfulnss to my father who stzted to me about this weblog, this webpage is really
    amazing.

    Also visit mmy website: short uurl (Ernest)

    Comment by Ernest — 16 June 2015 @ 7 h 27 min
  19. 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.

    Comment by دانلود فیلم بدون اکانت — 23 August 2015 @ 9 h 11 min
  20. […] A world in a ref http://clj-me.cgrand.net/2011/10/06/a-world-in-a-ref/ […]

  21. This website was… how do you say it? Relevant!! Finally I’ve found something that helped me.
    Kudos!

    Comment by Apple — 24 October 2015 @ 20 h 43 min
  22. 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.

    Comment by funny videos — 27 October 2015 @ 17 h 57 min
  23. Good response in return of this difficulty with genuine arguments and telling everything
    on the topic of that.

    Comment by Lorrie — 10 November 2015 @ 5 h 13 min
  24. pixel Gun 3d hack apk 9.4.2

    Clojure and me » A world in a ref

    Trackback by pixel Gun 3d hack apk 9.4.2 — 10 December 2015 @ 5 h 20 min
  25. http://escortinriga.lv/

    Clojure and me » A world in a ref

    Trackback by Http://escortinriga.lv/ — 11 December 2015 @ 6 h 38 min
  26. That’s such a nice and helpful article

    Comment by desirulez — 11 May 2020 @ 18 h 15 min
  27. 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

    Comment by desirulez — 16 May 2020 @ 20 h 09 min
  28. ag.918kiss.Com login

    Clojure and me » A world in a ref

    Trackback by ag.918kiss.Com login — 3 May 2021 @ 17 h 15 min
  29. online casino malaysia affiliate

    Clojure and me » A world in a ref

    Trackback by online casino malaysia affiliate — 19 May 2021 @ 13 h 54 min
  30. Hello, I wish for to subscribe for this website to take latest updates, therefore
    where can i do it please help.

    Comment by nawata — 11 June 2021 @ 4 h 13 min
  31. his explanation

    blog topic

    Trackback by his explanation — 22 September 2022 @ 19 h 15 min
  32. 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?

    Comment by discuss — 7 November 2022 @ 0 h 56 min
  33. 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?

    Comment by summer concert — 17 August 2023 @ 10 h 52 min
  34. Why visitors still use to read news papers
    when in this technological globe the whole thing is presented on web?

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2024 Clojure and me | powered by WordPress with Barecity