并发的优先队列是一个可线性化到顺序优先队列的数据结构，能够通过常用的优先队列语义提供insert和delete-min操作。
基于堆的优先队列
许多文献中提到的并发优先队列结构，其实是本书前面提到的可线性化堆结构。再一次的，这种结构的基本思想是在个别堆节点上使用细粒度锁，使线程在并行下也能够尽可能的访问数据结构的不同部分。设计这种并发堆的关键问题，在于传统自底向上的insert和自顶向下的delete-min操作有可能造成死锁。Biswas和Brown[17]提出基于锁的堆算法，通过专门的“清理”线程解决死锁。Rao和Kumar[116]建议通过一个将insert和delete-min操作都自顶向下处理的算法[17]来解决问题。Ayani[11]在他们算法基础上做了改善，即通过一种方式在堆两侧进行连续插入。Jones[68]提出一种基于类似斜堆的方案[116]。
阅读全文
本文翻译自《Getting Started With Storm》译者：吴京润 编辑：郭蕾 方腾飞
有时候你可能想使用不是基于JVM的语言开发一个Storm工程，你可能更喜欢使用别的语言或者想使用用某种语言编写的库。
Storm是用Java实现的，你看到的所有这本书中的spout和bolt都是用java编写的。那么有可能使用像Python、Ruby、或者JavaScript这样的语言编写spout和bolt吗？答案是当然
可以！可以使用多语言协议达到这一目的。
多语言协议是Storm实现的一种特殊的协议，它使用标准输入输出作为spout和bolt进程间的通讯通道。消息以JSON格式或纯文本格式在通道中传递。
我们看一个用非JVM语言开发spout和bolt的简单例子。在这个例子中有一个spout产生从1到10,000的数字，一个bolt过滤素数，二者都用PHP实现。
一个被广泛研究的方向是在理想化模型，如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135]。然而，很少有将这些数据结构放在一个真实的多处理器上进行建模的。这里有多种原因，大部分原因跟系统硬件架构与线程异步执行的相互作用有关。想想组合树(combining tree)的例子，虽然我们能通过计算（指令数）得到O(P/logP)的加速比，但这无法反映在实证研究中[52, 129]。真实世界的行为是被上述其他因素支配的，如竞争开销，缓存行为，同步操作(例如CAS)开销，请求到达率，退避延时，数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。 阅读全文
本文翻译自《Getting Started With Storm》译者：吴京润 编辑：郭蕾 方腾飞
本章要阐述一个典型的网络分析解决方案，而这类问题通常利用Hadoop批处理作为解决方案。与Hadoop不同的是，基于Storm的方案会实时输出结果。
我们的这个例子有三个主要组件（见图6-1）
正如前面讨论的那样，非阻塞实现主要目的是为了消除由锁带来的相关问题，为了形式化研究这一概念，多种非阻塞演进条件已经在相关文献有所研究了，如wait-freedom演进条件，lock-freedom演进条件，和obstruction-freedom演进条件。满足wait-free演进条件的操作是指在执行自身包含的有限步骤之后，保证操作必须完成，而不用考虑其他操作发生的时序，满足lock-free演进条件的操作是指在执行自身包含的有限步骤之后，保证某些操作完成。满足obstruction-free演进条件的操作是指在不受其他操作干扰的情况下，执行它包含的有限步骤之后，保证其完成。
在很多数据结构中，内存竞争所带来的不良现象和前文所说的顺序瓶颈带来的影响都可以通过使用细粒度锁机制来减小。在细粒度锁机制中，我们用多个粒度较小的锁来保护数据结构中的不同部分。这样做的目的是允许并发操作在它们不访问数据结构的相同部分时并行执行。这种方法也可以用于避免独立内存位置访问的额外竞争。在一些数据结构中，这种现象经常发生；举个例子，在哈希表中，对那些被哈希到不同哈希桶中的值的操作自然访问的是数据结构中的一部分。 阅读全文
原文链接，译文链接，原文作者： Peter Verhas，译者：有孚，本文最早发表于deepinmind
如果你用过反射并且执行过getDeclaredMethods方法的话，你可能会感到很吃惊。你会发现出现了很多源代码里没有的方法。如果你看一下这些方法的修饰符的话，可能会发现里面有些方法是volatile的。顺便说一句，如果在Java面试里问到“什么是volatile方法？”，你可能会吓出一身冷汗。正确的答案是没有volatile方法。但同时，getDeclaredMethods()或者getMethods()返回的这些方法，Modifier.isVolatile(method.getModifiers())的结果却是true。
immutator的一些用户遇到过这样的问题。他们发现，使用immutator（这个项目探索了Java的一些不为人知的细节）生成的Java代码使用volatile了作为方法的关键字，而这样的代码没法通过编译。结果就是这根本没法用。 阅读全文
对于进程有两个幻觉：一认为自己独享内存；二以为自己独享处理器。我们对于一台机器上的多个进程的幻觉是感觉他们是同时运行。
我们来依次解释下上面的三个幻觉：
关于独享内存不是我们的重点，简单说说。独享内存是指我们每个进程都独享虚拟内存。而虚拟内存地址最终是通过MMU翻译成实际的物理地址。这样做只是为了提供一种逻辑上的连续性，屏蔽内存碎片或是规避因内存有限而扩展到硬盘的各种问题，这样不用考虑实际的的限制从而使应用程序开发变得容易。还有一个值得注意的问题是在这个虚拟内存中如果这个进程是多线程的，那么将共享改空间，除了各自的堆栈、寄存器和所谓的虚拟处理器。这样会导致一个问题就是多个线程的stacksize对进程栈空间的要求呈线性增长，与复杂的多层级递归运算类似，导致stackoverflow。这也是好多语言比如Java的线程模型要求线程创建时指定好stacksize大小的原因。
一个运行在P个处理上的应用程序的加速度是它在单个处理器上的执行时间和在P个处理器的执行时间的比值。这是一种评价应用程序对于机器资源利用程度的衡量。理想情况下，我们想要的结果是线性加速度：当我们使用P个处理器的时候,我们希望可以获得P的加速度(译者注:例如一个应用程序在单处理器的执行时间是10秒,那么在双处理的执行时间理想情况下是5秒)。加速度随着P一起增加的数据结构我们称之为可扩展的数据结构。在设计可扩展的数据结构的时候,我们必须注意：为了同步使用简单的方法会严重破坏扩展性。
阅读全文
本文翻译自《Getting Started With Storm》 译者：吴京润 编辑：方腾飞
正如你已经看到的，bolts是一个Storm集群中的关键组件。你将在这一章学到bolt生命周期，一些bolt设计策略，以及几个有关这些内容的例子。
Bolt是这样一种组件，它把元组作为输入，然后产生新的元组作为输出。实现一个bolt时，通常需要实现IRichBolt接口。Bolts对象由客户端机器创建，序列化为拓扑，并提交给集群中的主机。然后集群启动工人进程反序列化bolt，调用prepare，最后开始处理元组。
阅读全文
本文翻译自《Getting Started With Storm》 译者：吴京润 编辑：方腾飞
你将在本章了解到spout作为拓扑入口和它的容错机制相关的最常见的设计策略。
在设计拓扑结构时，始终在头脑中记着的一件重要事情就是消息的可靠性。当有无法处理的消息时，你就要决定该怎么办，以及作为一个整体的拓扑结构该做些什么。举个例子，在处理银行存款时，不要丢失任何事务报文就是很重要的事情。但是如果你要统计分析数以百万的tweeter消息，即使有一条丢失了，仍然可以认为你的结果是准确的。
对于Storm来说，根据每个拓扑的需要担保消息的可靠性是开发者的责任。这就涉及到消息可靠性和资源消耗之间的权衡。高可靠性的拓扑必须管理丢失的消息，必然消耗更多资源；可靠性较低的拓扑可能会丢失一些消息，占用的资源也相应更少。不论选择什么样的可靠性策略，Storm都提供了不同的工具来实现它。
要在spout中管理可靠性，你可以在分发时包含一个元组的消息ID（collector.emit(new Values(…),tupleId)）。在一个元组被正确的处理时调用ack方法，而在失败时调用fail方法。当一个元组被所有的靶bolt和锚bolt处理过，即可判定元组处理成功（你将在第5章学到更多锚bolt知识）。
阅读全文
随着多个处理器共享同一内存的机器在商业上的广泛使用，并发编程的艺术也产生了巨大的变化。当前的趋势向着低功耗芯片级多线程（CMT）发展，所以这样的机器一定会更加广泛的被使用。
共享内存多处理器是指并发的执行多个线程的系统，这些线程在共享的内存中通过数据结构通讯和同步。这些数据结构的效率对于性能是很关键的，而目前熟练掌握为多处理器机器设计高效数据结构这一技术的人并不多。对大多数人来说，设计并发的数据结构比设计单线程的难多了，因为并发执行的线程可能会多种方式地交错运行他们的指令，每一种方式会带来不同的，甚至不符合预期的输出。这就要求设计者改变他们对运算的认识，理解新的设计方法，采用新的编程工具集。此外，设计可扩展的并发数据结构，使得当机器执行越来越多的并发线程时依旧表现良好也是新的挑战。本文主要介绍设计并发数据结构的相关挑战，和一些重要的数据结构相关内容的总结。我们的总结绝不是全面的；相反，我们特意选取了一些能说明设计的关键问题的流行的数据结构，希望我们提供了足够的背景和知识，让有兴趣的读者接触那些我们没有提到的内容。
阅读全文
(3 votes, average: 3.67 out of 5)
Loading...