Concurrent Revisions v0.1.0

News
1

Just published concurrent_revisions.cr an implementation of the Concurrent Revisions.

What’s the Concurrent Revisions?

Concurrent Revisions is a concurrency control model managing shared resources based on analogy of the version management.

Now, I lightly describe some central concepts in Concurrent Revisions.

Revision

Revisions represent the basic unit of concurrency. Revision is similar to branches in source control systems.

fork and join

We can fork and join revisions much like asynchronous tasks that are forked and joined, and may themselves fork and join other tasks.

Isolation Types

Isolation Type contians two types, Versioned and Cumulative. Versioned has a value and we can check whether it has been modified in the revision since it was forked. Cumulative type is Versioned type has customizable merge function.

When the programmer joins a revision, all write-write conflicts are resolved deterministically as specified by the isolation type. If there is a conflict on a variable of type Versioned(T), the value of the joinee always overwrites the value of the joiner.

Examples

Following code represents the Figure 2 in the paper in my concurrent revisions implementation. We can see the value x on main revision is overwrited by it on r revision when join revision to main revision.

x = Versioned(Int32).new(0)
y = Versioned(Int32).new(0)

r : Revision = rfork do
  x.set(1)
end
x.set(y.get)
rjoin(r)

puts "#{x.get} #{y.get}" # => 1 0

Also we can use user-defined merge function with Cumulative(T).

Fig2
Fig2447×509 25.6 KB

merge = ->(original : Int32, master : Int32, revised : Int32){
  master + revised - original
}

x = Cumulative(Int32).new(0, merge)

r2 = nil

r1 = rfork do
  x.set(x.get + 1)
  
  r2 = rfork do
    x.set(x.get + 3)
  end
end

x.set(x.get + 2)
rjoin(r1)
x.set(x.get + 4)

rjoin(r2.as(Revision))

puts x.get # => 10
2 Likes
2

Looks interesting I didn’t new about Concurrent Revisions. Thanks for sharing!

Did you check how it behaves on MT?

3

Thank you for reading!

I didn’t check on MT because at this moment there’s only a single thread executing my code in Crystal as far as i known. So, I will check and fix bugs on MT when Crystal support MT.

4

You can opt into experimental MT with the -Dpreview_mt flag. More: https://crystal-lang.org/2019/09/06/parallelism-in-crystal.html

5

Thank you very much! I will check promptly it on MT.

6

:heart:
In the future I will only ever spell it like this :)

Certainly looks interesting for data that can be merged with 2 (or more) sets of changes.

1 Like
7

Instead of this:

merge = ->(original : Int32, master : Int32, revised : Int32){
  master + revised - original
}

x = Cumulative(Int32).new(0, merge)

I suggest to define the constructor like this:

module ConcurrentRevisions
  class Cumulative(T)
    def initialize(value : T, &@merge_func : T, T, T -> T)
      @versions = {} of Int32 => T
      set(value)
    end

The above means that a block is expected to be passed to new, and it’s captured and stored in @merge_func.

With that, you can use it like this:

x = Cumulative(Int32).new(0) do |original, master, revised|
  master + revised - original
end

Note that all of the necessary types you need to put in a proc are gone, because they are specified on the method definition.

A Proc exists to represent the notion of a captured block. You can also create it with a literal, but it’s so much easier to use blocks, it feels more natural and there’s less typing.

The same reason a Tuple exists to represent variadic arguments, and that a NamedTuple exists to represent named arguments. They have their own literals, but I would try to use them as less as possible.

2 Likes
8

Thank you for feedback!

I understood blocks are better than literal for creating Proc. And I applied this changes to my code.