what_is_raft_protocals_and_how_it_works

这里我们来描述Raft协议。

Background

Raft协议解决的是一类叫做Consensus的问题,可以参看这里, Raft协议最开始出自一篇论文,请参看这里

The consensus problem requires agreement among a number of processes (or agents) for a single data value.

这里对Consensus Problem的描述看起来很奇怪(在多个进程中就某个值达成一致),但是实际上,Consensus问题可以认为是保证分布式系统在存在意外错误的情况下的可用性,这类错误包括: 节点突然宕机,网络断线,重传,网络分区等错误(不包括Byzantine fault)。
继续阅读

Red-Black tree delete routine

Red-Black delete routine

Red-Black Tree的删除流程要复杂一些。首先也需要利用search tree的性质找到需要删除的元素位置,没找到就直接返回,找到的话,如果该节点为interior node,那么还需要找此节点的后继节点,并用后继节点代替删除节点,为了方便,可以直接用后继节点的元素值覆盖删除节点的元素值并且不修改删除节点的颜色,那么这样,删除节点位置的红黑树性质就没有违反,相反的是后继节点的性质可能违反了。如果将后继节点和删除的是叶子节点的两种视为真正需要删除的节点,那么可以保证实际删除的节点一定不会有两个孩子。接下来,我们将后继节点和删除的叶子节点叫做删除节点。有以下几种情况:

  • 删除节点为红色。如果删除节点没有孩子节点,那么直接删除掉删除节点即可,如果删除节点有孩子,直接用孩子节点代替即可,之所以可以这样,是因为红色的删除节点删除掉不会对属性产生影响。

接下来考虑删除节点为黑色节点的几种情况:

继续阅读

604-257-3999

Red-Black tree

AVL树和Red-Black 树是两种主要的Balanced Search Tree,他们都有额外的属性保证任意节点的左右子树的深度不会差别太大。比如AVL树保证任意节点的左右子树的深度差不超过1. Red-Black Tree通过以下属性来保证树的深度:

  • 任意节点要么为红色节点,要么为黑色节点。Null节点为黑色
  • Root节点为黑色
  • 任意节点到所有叶子节点的路径含有相同个数的黑色节点
  • 不能有连续的红色节点

通过这些属性,Red-Black Tree能够保证含有N个节点的Red-Black Tree的深度最多为2logN。

Red-Black Tree插入流程

在插入一个元素的时候,与基本的Search Tree类似,首先需要找到插入位置,然后在对应位置插入包含元素的节点(初始设为红色),尽管插入红色节点可以保证不违反属性1,3,但是可能违反2和4,因此可能需要调整,具体来说:

  • 如果树为空,则插入的节点应该为root节点,将该节点设为root节点,颜色为黑色,返回。
  • 如果插入节点的父节点为黑色节点,则属性4也得到了保证,可以直接返回。
  • 如果插入节点的父节点为红色节点,那么违反了属性4,因此需要调整。

当插入节点的父节点为红色节点,需要分几种情况来做调整。如果将新插入节点的父节点记为current节点(current节点为红色节点,且其孩子有一个为新插入的红色节点,current节点和其孩子违反了属性4),current节点的父节点为upper,current节点的兄弟节点为other。可以知道upper节点必定为黑色节点。那么可以分为以下几种情况:

(804) 462-5956

list-circle problem

原文地址:这里

如何在O(N)的时间里判断一个List是否含有一个circle.

Motivation

线性列表是一种非常常见的数据结构. 给定一个单链表,如果某个元素指向前面的元素,那么就会形成一个circle,带有circle的list会导致对list的迭代访问无法终止,那么如何在不知道list表长度的情况下,在O(N)的时间里,判断是否存在Circle呢? (译者注:这一题并不是很难,有趣的是原文作者给出了很多的算法思路,值得一看).

Incorrect Solution

直接遍历列表,如果他一直不退出,那么就存在circle:

/ Incorrect 'solution'
function boolean hasLoop(Node startNode){
  Node currentNode = startNode;
  while (currentNode = currentNode.next());
  return false;
}

问题在于,我们并不知道这个算法运行多长时间合适,因为我们不知道list的长度。

继续阅读

where is Java PermGen ?-转载

where is Java PermGen space in jdk8

本文转载自 : 509-630-6771

在Java虚拟机(JVM)内部,class文件中包括类的版本、字段、方法、接口等描述信息,还有运行时常量池,用于存放编译器生成的各种字面量和符号引用。

在过去(自定义类加载器还不是很常见的时候),类大多是”static”的,很少被卸载或收集,因此被称为“永久的(Permanent)”。同时,由于类class是JVM实现的一部分,并不是由应用创建的,所以又被认为是“非堆(non-heap)”内存。

在JDK8之前的HotSpot JVM,存放这些”永久的”的区域叫做“永久代(permanent generation)”。永久代是一片连续的堆空间,在JVM启动之前通过在命令行设置参数-XX:MaxPermSize来设定永久代最大可分配的内存空间,默认大小是64M(64位JVM由于指针膨胀,默认是85M)。永久代的垃圾收集是和老年代(old generation)捆绑在一起的,因此无论谁满了,都会触发永久代和老年代的垃圾收集。不过,一个明显的问题是,当JVM加载的类信息容量超过了参数-XX:MaxPermSize设定的值时,应用将会报OOM的错误(对于这句话,译者的理解是:32位的JVM默认MaxPermSize是64M,而JDK8里的Metaspace,也可以通过参数-XX:MetaspaceSize 和-XX:MaxMetaspaceSize设定大小,但如果不指定MaxMetaspaceSize的话,Metaspace的大小仅受限于native memory的剩余大小。也就是说永久代的最大空间一定得有个指定值,而如果MaxPermSize指定不当,就会OOM)。在Java虚拟机(JVM)内部,class文件中包括类的版本、字段、方法、接口等描述信息,还有运行时常量池,用于存放编译器生成的各种字面量和符号引用。

注:在JDK7之前的版本,对于HopSpot JVM,interned-strings存储在永久代(又名PermGen),会导致大量的性能问题和OOM错误。从PermGen移除interned strings的更多信息查看这里。

继续阅读

本条目发布于443-579-8005。属于jvm分类。作者是。