并发：如何安全地共享缓存哈希？

Question

保护写访问是否足够，还是有必要保护读访问print-columns？

#!/usr/bin/env raku

my @w_list_items;
len_items_list( <car tree house mouse dog mountain snow roof> );
@w_list_items.say;

sub len_items_list ( @list ) {
   my Int $threads = Kernel.cpu-cores;
   while $threads > @list.elems {
       last if $threads < 2;
       $threads = $threads div 2;
   }

   my Int $size = @list.elems div $threads;
   my Array @portions = ( ^$threads ).map: { [ $size * $_, $size * ( $_ + 1 ) ] };
   @portions[*-1][1] = @list.elems;

   my Promise @promise;
   for @portions -> $range {
       my Int %cache;
       @promise.push: start {
           do for $range[0] ..^ $range[1] -> $i {
               my $len = print-columns( @list[$i], %cache );
               $i, $len;
           }
       };
   }

   @w_list_items = ();
   for await @promise -> @portion {
       for @portion {
           @w_list_items[.[0]] := .[1];
       }
   }
}

sub print-columns( $str, %cache? ) returns Int {
   my Int $width = 0;
   for $str.Str.NFC {
       if %cache.EXISTS-KEY( $_ ) {
           $width = $width + %cache.AT-KEY( $_ );
       }
       else {
           $width = $width + %cache.BIND-KEY( $_, char_width( $_ ) );
       }
   }
   $width;
}

sub char_width ( $cp ) {
   # dummy code:
   return 1;
}

Answer 1

如果哈希可以被写入（就像这里的情况一样），那么读取也必须受到保护。

考虑到示例中的具体情况，我可能会考虑几种前进的方法（并根据我喜欢的权衡进行选择）。

每个线程的缓存

如果缓存预计不会增长得非常大（就键的数量和计算值的大小而言），我可能会让每个线程构建自己的本地缓存。这意味着线程之间没有同步成本，因此它们根本不会相互阻塞。代价是使用更多的内存，从而给 CPU 缓存带来更大的压力。

这是一个简单的改变；只需将声明移动到一个范围内即可：

       @promise.push: start {
           my Int %cache;
           do for $range[0] ..^ $range[1] -> $i {
               my $len = print-columns( @list[$i], %cache );
               $i, $len;
           }
       };

很容易推断出这种方法的正确性，因为没有共享！

保护对哈希的访问

使用该OO::Monitors模块将缓存功能封装在一个类中，该类会在每个方法调用周围自动获取锁：

use OO::Monitors;

monitor Cache {
    has Int %!cache{Int};

    method lookup(Int $key --> Int) {
        %!cache{$key}
    }

    method add(Int $key, Int $count --> Nil) {
        %!cache{$key} := $count;
    }
}

举个例子：

       my Cache $cache .= new;
       @promise.push: start {
           do for $range[0] ..^ $range[1] -> $i {
               my $len = print-columns( @list[$i], $cache );
               $i, $len;
           }
       };

并使用它：

sub print-columns( $str, $cache ) returns Int {
   my Int $width = 0;
   for $str.Str.NFC -> $char {
       my $char-width;
       with $cache.lookup($char) {
           $char-width = $_;
       }
       else {
           $char-width = char_width($char);
           $cache.add($char, $char-width)
       }
       $width += $char-width;
   }
   $width;
}

这消除了每线程缓存方法的额外内存成本，而是用锁获取和释放来代替成本。

OO::Monitors是一种使用 a 的结构化方式Lock- 它Lock在其实现中使用。您还可以使用此处创建解决方案Lock，但代价是更难以推理。

使用不可变的 Map 并将其复制到缓存中

当缓存添加相对于查找来说非常罕见并且缓存大小不太可能变得很大时，另一种方法是使用不可变的Map并且每当缓存获得添加时，就使用添加的条目创建一个新的。不变性意味着读取不需要锁。

使用前面方法中封装的缓存功能，可以通过将 替换Cache monitor为class如下来尝试：

class Cache {
    has $!current-cache = Map.new;

    method lookup(Int $key --> Int) {
        $!current-cache{$key}
    }

    method add(Int $key, Int $count --> Nil) {
        my $current = $!current-cache;
        unless $current{$key}:exists { # Another thread won
            $!current-cache = Map.new( (|$current, $key => $count) );
        }
    }
}

当然，这意味着更多的复制，但好处是，一旦缓存内容稳定，那么在所有执行工作的线程（以及 CPU 核心）上共享相同的内存（没有任何锁争用）。人们甚至可以预先使用 ASCII 范围来填充缓存。

请注意，上面的方法并不是获得并发安全的基于复制的哈希的一般安全方法；至少它很容易丢失更新（但由于它是缓存，所以这并不重要）。

使用无锁哈希

不幸的是，还没有人在 Raku 中实现无锁哈希数据结构，但这将是在这种情况下使用的理想选择。我已经完成了Concurrent::Stack（无锁堆栈，关于最简单的无锁数据结构），Concurrent::Trie（无锁特里树，也很容易），以及Concurrent::Queue（已经足够难了，我从文献中选择了一个解决方案）。有一些关于无锁哈希的论文，但实现它们并不是一件容易的事！