在Real-time中使用并行和SignalR解决莎士比亚的“百万猴子”问题

[原文发表地址] Solving the Shakespeare Million Monkeys Problem in Real-time with Parallelism and SignalR

[原文发表时间] 2011-11-12 01:09

大约18个月前我跟Stephen Toub（在并行计算方面享有盛名）谈论过并行，以及它可以解决的问题。

我天真地问：“我们可以解决百万猴子的问题吗？”

他说：“这是什么问题？”

“你知道，如果你有无限只猴子，还有无限个键盘，它们就能写出莎士比亚的作品。”

我们对一些想法做了下头脑风暴（因为Steven比我聪明些，所以整个头脑风暴中，他总是若有所思地凝视着空气，而我则坐在那儿什么都不干。）最后，我们决定用遗传算法。我们每秒会培育上千品种（假定的）猴子，然后根据他们写出莎士比亚作品的能力来选定哪几种可以被保留。

我们用.NET 4任务并行库让算法能更容易扩展到可用硬件。我是说，谁都能创造百万以上只猴子，但是那种超过12个处理器并行的循环就需要人才了，对吗？好吧，多少是有点技术含量的。.NET的并行功能已经为你准备好大部分内容了，这才是重点。它是为大量内容而设的并行进程。

我们创建了一个此应用程序的WinForm版本，我们用它来展示在.NET上的并行计算。然后Paul Batum和我上周参加了keeping It Realtime会议，会议上展示了SignalR。我不想再做相同的那种“这是real-time聊天应用程序”或者“这里是一张图表，展示了real-time的结果”这类演示，当然大家都习惯在这种场合做这类东西。我认为我们可以把WinForm莎士比亚猴子演示移植到ASP.NET和SignalR中，这也是Paul正准备着手的内容。

在做这类疯狂的密集运算时，还需要返回real-time结果，你可能会在real-time通知部分运用节点e，然后产生另一个进程，使用C或者其他数学功能，然后让它们互相交流。我们喜爱节点，你可以在IIS上运行节点，或者甚至在 WebMatrix中编写节点。不过，节点有所长，.NET也有所长。

比如，.NET很擅长CPU-bound的密集运算，好比在F#中做并行矩阵乘法。ASP.NET擅长扩展像Bing或者StackOverflow这种网站。说起real-time的时候，你可能不会想到IIS和ASP.NET，但是在使用长轮询以及在实验室中使用像拥有.NET4.5WebSocket支持的 WebSockets 高效协议时，SignalR使用异步处理器和智能技术能获取很棒的扩展。

所以，我们想看看你是否绑定异步背景工作，是否使用了尽可能多的处理器，是否通过SignalR的长轮询或者WebSocket获取real-time的状态更新，以及是否使用C#，.NET, ASP.NET和IIS。

它每秒在成千上万种猴子种类中选取8万种（每种大约200只猴子）来获取哈姆雷特的开场白。所以那就是1600万只猴子来获取文本，正如他们所说，有那么多猴子。

这就是应用程序的整体想法。客户端非常轻量级。只有两个框，两个按钮，一个复选框以及一些文本，包含了一些常用事件，比如运行，取消，完成和更新进程，不过你可以通过$.connection.monkeys看看猴子有什么不同，当然只要关掉$.connection，也可以通过$.connection.foo查看。

这些功能是客户端上的，但是我们通过持续连接在服务器上使用它们，然后更新文本。

  1: <script src="Scripts/jquery-1.6.4.min.js"></script> 
  2: <script src="Scripts/json2.min.js"></script>
  3: <script src="Scripts/jquery.signalR.min.js"></script>
  4: <script src="signalr/hubs"></script>
  5: <script>
  6: $(function () {
  7: $('#targettext').val('To be or not to be, that is the question;\nWhether \'tis nobler in the mind to suffer\n\The slings and arrows of outrageous fortune,\n\Or to take arms against a sea of troubles,\n\And by opposing, end them.');
  8: var monkeys = $.connection.monkeys,
  9: currenttext = $('#currenttext'),
  10: generationSpan = $('#generation'),
  11: gpsSpan = $('#gps');
  12: monkeys.updateProgress = function (text, generation, gps) {
  13: currenttext.val(text);
  14: generationSpan.text(generation);
  15: gpsSpan.text(gps);
  16: };
  17: monkeys.started = function (target) {
  18: $('#status').text('Working...');
  19: $('#targettext').val(target);
  20: $('#cancelbutton').removeAttr('disabled');
  21: };
  22: monkeys.cancelled = function () {
  23: $('#status').text('Cancelled');
  24: $('#cancelbutton').attr('disabled', 'disabled');
  25: };
  26: monkeys.complete = function () {
  27: $('#status').text('Done');
  28: $('#cancelbutton').attr('disabled', 'disabled');
  29: };
  30: $.connection.hub.start({}, function () {
  31: $('#startbutton').click(function (event) {
  32: $('#status').text('Queued...');
  33: monkeys.startTyping($('#targettext').val(), $('#isparallel').is(':checked'));
  34: });
  35: $('#cancelbutton').click(function (event) {
  36: monkeys.stopTyping();
  37: });
  38: });
  39: });
  40: </script>
  41: 

使用$.connection.hub.start后，神奇的一刻发生了。中心客户端代码实际是在~/signalr/hubs中的。看看它是怎么包含在顶端的。客户端代理是根据服务器端的集线器生成的。

服务器端的结构如下所示：

  1: [HubName("monkeys")]
  2: public class MonkeyHub : Hub
  3: {
  4: public void StartTyping(string targetText, bool parallel)
  5: {
  6: }
  7: public void StopTyping()
  8: {
  9: }
  10: } 

StartTyping和StopTyping.NET方法是可以从客户端通过猴子JavaScript对象来调用的。所以你可以从客户端JavaScript调用服务器端C#，从C#服务器你可以调用客户端上的JavaScript方法。 如果你对它进行调试，然后看看线路上的状况，会很有意义。关键是C#和Json对象可以来回流动，这样会模糊客户端和服务器间的界限。在配置上没什么创新。那就是我们如何在客户端和服务器之间交流的。现在，那些猴子们怎么样了？

你可以查看完整代码，但是StartTyping就偏离了。注意它是如何持续报告给集线器（调回客户端）的。Paul正在使用Hub.GetClients来和所有连接的客户端进行交流。当前只支持每次一只猴子工作。其他连接的客户端可以看到这项工作的进展。

  1: public void StartTyping(string targetText, bool parallel)
  2: {
  3: var settings = new GeneticAlgorithmSettings { PopulationSize = 200 };
  4: var token = cancellation.Token;
  5:  
  6: 
  7: currentTask = currentTask.ContinueWith((previous) =>
  8: {
  9: // Create the new genetic algorithm
  10: var ga = new TextMatchGeneticAlgorithm(parallel, targetText, settings);
  11: TextMatchGenome? bestGenome = null;
  12: DateTime startedAt = DateTime.Now;
  13:  
  14: Hub.GetClients<MonkeyHub>().started(targetText);
  15:  
  16: // Iterate until a solution is found or until cancellation is requested
  17: for (int generation = 1; ; generation++)
  18: {
  19: if (token.IsCancellationRequested)
  20: {
  21: Hub.GetClients<MonkeyHub>().cancelled();
  22: break;
  23: }
  24:  
  25: // Move to the next generation
  26: ga.MoveNext();
  27:  
  28: // If we've found the best solution thus far, update the UI
  29: if (bestGenome == null ||
  30: ga.CurrentBest.Fitness < bestGenome.Value.Fitness)
  31: {
  32: bestGenome = ga.CurrentBest;
  33:  
  34: 
  35:  
  36: int generationsPerSecond = generation / Math.Max(1, (int)((DateTime.Now - startedAt).TotalSeconds));
  37: Hub.GetClients<MonkeyHub>().updateProgress(bestGenome.Value.Text, generation, generationsPerSecond);
  38:  
  39: if (bestGenome.Value.Fitness == 0)
  40: {
  41: Hub.GetClients<MonkeyHub>().complete();
  42: break;
  43: }
  44: }
  45: } 
  46:  
  47: }, TaskContinuationOptions.OnlyOnRanToCompletion);
  48:  
  49: }

如果他愿意，他可以使用.Caller来和调用StartTyping的特定客户端进行交流。在ga.MoveNext中我们决定用并行，或者不基于该复选框。这就是我们随机选取高质配种猴来孕育未来猴子的地方。期望它们会输出像莎士比亚的作品，而不是普通的表达。

通过简单地把Enumerable.Range变为ParallelEnumerable.Range，我们可以开始做简单的并行，还可以使用机器上的处理器。注意代码是一样的。

  1: private TextMatchGenome[] CreateNextGeneration()
  2: {
  3: var maxFitness = _currentPopulation.Max(g => g.Fitness) + 1;
  4: var sumOfMaxMinusFitness = _currentPopulation.Sum(g => (long)(maxFitness - g.Fitness));
  5:  
  6: if (_runParallel)
  7: {
  8: return (from i in ParallelEnumerable.Range(0, _settings.PopulationSize / 2)
  9: from child in CreateChildren(
  10: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
  11: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
  12: select child).
  13: ToArray();
  14: }
  15: else
  16: {
  17: return (from i in Enumerable.Range(0, _settings.PopulationSize / 2)
  18: from child in CreateChildren(
  19: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
  20: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
  21: select child).
  22: ToArray();
  23: }
  24: }
  25: 

我12个处理器的桌面用并行在一秒内做了3800个品种。

非常感谢Paul为SignalR提供了可爱的端口，还要感谢Stephen Toub的算法。

在我的BitBucket上有SignalR猴子演示的代码。现在它需要.NET 4.5和Visual Studio开发者预览版，不过你可以删去几行，然后在.NET 4上运行，这是完全没有问题的。

注意SignalR可以在.NET 4及以上版本上运行，你今天就可以试试了。你还可以登陆https://chatapp.apphb.com，在SignalR 聊天应用程序里的“aspnet”房间和开发者聊天。你只要给自己取个昵称，然后加入aspnet就可以了。

在我写这篇博客的时候，没有猴子受伤。