liangshang / liangshang.github.com Goto Github PK

View Code? Open in Web Editor NEW

6.0 6.0 1.0 427 KB

Ruby 30.63% JavaScript 0.12% CSS 49.45% HTML 19.79%

liangshang.github.com's People

Contributors

Stargazers

Watchers

Forkers

movinghera

liangshang.github.com's Issues

Loading, Linking and Initializing in Java - Run-time Constant Pool

先试着说一下自己对 run-time constant pool 的理解吧。

"Run-time" Constant Pool vs Constant Pool

首先为啥是 "run-time" 的常量池呢？因为与还有一个东西叫做 Constant Pool。常量池是 .class 文件里的一部分。本质上来讲是一张符号表，记录了 literal 和 symbolic reference。literal 类似于常量，比如说 static final int PI = 3; ，而 symbolic reference 包含以下几种

类和接口的全限定名
字段名称和描述符
方法名称和描述符

那么为什么需要 Constant Pool 呢 ？在 JLS里面有这样一段话

Java Virtual Machine instructions do not rely on the run-time layout of classes, interfaces, class instances, or arrays. Instead, instructions refer to symbolic information in the constant_pool table.

也就是说JVM的指令并不依赖于运行时....的layout，而是依赖于这个constant_pool表里的信息。这段话到底是什么意思呢？就要继续看 Run-time Constant Pool 和创建类的linking.resolution阶段了。

Run-time Constant Pool and Resolution

首先解释一下Run-time Constant Pool，是 Constant Pool 在运行时的表示（representation）。它是在JVM的方法区里。当一个class/interface被创建时，它的运行常量池也被创建。当创建运行常量池的时候方法区内存不够的时候会抛 OutOfMemoryError。

Resolution则是JVM创建类的一个步骤。这一步的作用是将 run-time constant pool 里的symbolic reference替换为 concrete value。简单来说就是将某个值的symbolic reference 替换为 memory reference，也就是实际的内存地址。这样 JVM instruction 在执行的时候就可以找到值了。

Loading, Linking and Initializing in Java

这一篇记录一下JLS里class初始化的过程。在Specification里主要是下面几节

然后也做个Index吧

Java7新增的特性

from The Well-Grounded Java Developer

switch 可以使用 String
异常处理可以使用 |
try-with clause
钻石（diamond） <>
函数调用允许泛型可变参数 foo( T ... ts)

[译] Rescore in Elasticsearch

from https://www.elastic.co/guide/en/elasticsearch/reference/current/search-request-rescore.html

Rescore 可以对 query 和 post_filter 出来的结果进行重新排序。通常来讲放在 query 里的都是简单的查询用来筛选并排序出少量的文档，而 rescore 则是相对复杂的查询来对那些少数的文档进行更精确地排序。

the rescore phase is not executed when search_type is set to scan or count.

An Example

curl -s -XPOST 'localhost:9200/_search' -d '{
   "query" : {
      "match" : {
         "field1" : {
            "operator" : "or",
            "query" : "the quick brown",
            "type" : "boolean"
         }
      }
   },
   "rescore" : {
      "window_size" : 50,
      "query" : {
         "score_mode": "multiply",
         "rescore_query" : {
            "match" : {
               "field1" : {
                  "query" : "the quick brown",
                  "type" : "phrase",
                  "slop" : 2
               }
            }
         },
         "query_weight" : 0.7,
         "rescore_query_weight" : 1.2
      }
   }
}
'

通过上面的例子我们可以看到 query_weight 和 rescore_query_weight 用来调整 query 和 rescore_query 的权重。score_mode 用来调整 query 和 rescore_query 的值的作用方法。主要是以下几种：

total Add the original score and the rescore query score. The default.
multiply Multiply the original score by the rescore query score. Useful for function query rescores.
avg Average the original score and the rescore query score.
max Take the max of original score and the rescore query score.
min Take the min of the original score and the rescore query score.

window_size 则是控制每个shard上的 topN 作为结果被 rescore。

Multi-Rescores

curl -s -XPOST 'localhost:9200/_search' -d '{
   "query" : {
      "match" : {
         "field1" : {
            "operator" : "or",
            "query" : "the quick brown",
            "type" : "boolean"
         }
      }
   },
   "rescore" : [ {
      "window_size" : 100,
      "query" : {
         "rescore_query" : {
            "match" : {
               "field1" : {
                  "query" : "the quick brown",
                  "type" : "phrase",
                  "slop" : 2
               }
            }
         },
         "query_weight" : 0.7,
         "rescore_query_weight" : 1.2
      }
   }, {
      "window_size" : 10,
      "query" : {
         "score_mode": "multiply",
         "rescore_query" : {
            "function_score" : {
               "script_score": {
                  "script": "log10(doc['numeric'].value + 2)"
               }
            }
         }
      }
   } ]
}
'

第一个 rescore 得到 query 的结果并计算。第二个 rescore 得到第一个 rescore 的结果。所以它们的 window_size 是非递增的。

Conclusion

这篇文章介绍了 Elasticsearch 的 rescore 方法。通常是更复杂的 query，作用在前面的 query 返回的结果上。

Loading, Linking and Initializing in Java - Binding Native Method and JVM Exists

Binding Native Method Implementations

Binding is the process by which a function written in a language other than the Java programming language and implementing a native method is integrated into the Java Virtual Machine so that it can be executed. Although this process is traditionally referred to as linking, the term binding is used in the specification to avoid confusion with linking of classes or interfaces by the Java Virtual Machine.

Binding 就是把一个非 Java 写的并且实现了 native method 的方法给集成进 JVM 使得 JVM 可以执行它的过程。虽然这个过程有时也被叫做 Linking，但是为了避免和 Class 初始化的 Linking 阶段相混淆，这里叫 Binding。

Java Virtual Machine Exists

The Java Virtual Machine exits when some thread invokes the exit method of class Runtime or class System, or the halt method of class Runtime, and the exit or halt operation is permitted by the security manager.
In addition, the JNI (Java Native Interface) Specification describes termination of the Java Virtual Machine when the JNI Invocation API is used to load and unload the Java Virtual Machine.

当调用以下方法并且这些方法被 security manager 所允许时，JVM会退出。

Runtime.exit()
Runtime.halt()
System.exit()

此外，当 JNI 去 load 和 unload JVM 时也会终止 JVM。

How ClassLoader Works in Java?

from http://javarevisited.blogspot.com/2012/12/how-classloader-works-in-java.html

What is ClassLoader

ClassLoader 是用来加载class file的类。Java里一共有三个默认的ClassLoader。

Bootstrap ClassLoader
Extension ClassLoader
System or Application ClassLoader

每个classloader都预先定义了一个位置，它们会从这个位置来加载class文件。Bootstrap ClassLoader 负责从rt.jar文件里加载标准JDK的class file。而且它是Java里所有的ClassLoader的parent，而它自己并没有parent。Bootstrap class loader 也叫作 Primordial ClassLoader。

Extension ClassLoader会将类加载请求委托给它的parent，也就是Bootstrap ClassLoader。如果parent加载失败的话它会负责从 jre/lib/ext 这个目录或是系统变量 java.ext.dirs 指向的目录里加载。JVM里的Extension ClassLoader 由 sun.misc.Launcher$ExtClassLoader 来实现。

最后一个 JVM 默认使用的ClassLoader是 System or Application class loader。它是负责从 CLASSPATH 里加载Java Application用到的类。这个CLASSPATH可以由命令行指令 -classpath、-cp来指定，也可以从 JAR 文件里的Manifest文件里的Class-Path字段来获取。Application class loader是 Extension ClassLoader的child，它由sun.misc.Launcher$AppClassLoader这个类实现。

除了 Bootstrap ClassLoader 是用 native language 来实现的以外，其它的Java class loader的实现都使用了java.lang.ClassLoader。

上一张图来总结一下

How ClassLoader works in Java

ClassLoader 遵循着三个原则：

Delegation
Visibility
Uniqueness

Delegation Principle

当我们需要加载一个class，比如说Foo.class时，加载请求会先给到 Application ClassLoader。Application ClassLoader会先将这个请求代理给它的parent，也就是Extension ClassLoader。同样的，Extension ClassLoader会代理给Boostrap ClassLoader。如果类没有被找到的话，加载请求就会回到child上去。如果找到了的话，child自然就不会再找了。

再上个图来看一下

Visibility Principle

简单来说就是 child class loader 可以看到 parent class loader 加载的类但是反之不可以。当 class Foo 被 Application ClassLoader 加载后使用 Extension ClassLoader强制再加载一遍就会抛异常 java.lang.ClassNotFoundException。比如下面的例子

package test;

import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Java program to demonstrate How ClassLoader works in Java,
 * in particular about visibility principle of ClassLoader.
 *
 * @author Javin Paul
 */

public class ClassLoaderTest {

    public static void main(String args[]) {
        try {          
            //printing ClassLoader of this class
            System.out.println("ClassLoaderTest.getClass().getClassLoader() : "
                                 + ClassLoaderTest.class.getClassLoader());


            //trying to explicitly load this class again using Extension class loader
            Class.forName("test.ClassLoaderTest", true 
                            ,  ClassLoaderTest.class.getClassLoader().getParent());
        } catch (ClassNotFoundException ex) {
            Logger.getLogger(ClassLoaderTest.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

}

Output:
ClassLoaderTest.getClass().getClassLoader() : sun.misc.Launcher$AppClassLoader@601bb1
16/08/2012 2:43:48 AM test.ClassLoaderTest main
SEVERE: null
java.lang.ClassNotFoundException: test.ClassLoaderTest
        at java.net.URLClassLoader$1.run(URLClassLoader.java:202)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:190)
        at sun.misc.Launcher$ExtClassLoader.findClass(Launcher.java:229)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:306)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:247)
        at java.lang.Class.forName0(Native Method)
        at java.lang.Class.forName(Class.java:247)
        at test.ClassLoaderTest.main(ClassLoaderTest.java:29)

Uniqueness Principle

这个原则是说一个类被 parent class loader 加载完了后就不应该被 child class loader 再加载一遍了。

如果非要写一个class loader 来违背 Uniqueness 和 Delegation 的话也不是不行，只是这样做没啥好处。所以在自定义 class loader 的时候要遵循以上的三个原则。

ClassLoader 能用来做啥？

(这个地方没太懂。。直接原文吧。。。)

ClassLoader in Java is a powerful concept and used at many places. One of the popular example of ClassLoader is AppletClassLoader which is used to load class by Applet, since Applets are mostly loaded from internet rather than local file system, By using separate ClassLoader you can also loads same class from multiple sources and they will be treated as different class in JVM. J2EE uses multiple class loaders to load class from different location like classes from WAR file will be loaded by Web-app ClassLoader while classes bundled in EJB-JAR is loaded by another class loader. Some web server also supports hot deploy functionality which is implemented using ClassLoader. You can also use ClassLoader to load classes from database or any other persistent store.

大概的意思是说使用不同的class loader可以从不同的地方加载相同的类，而它们在JVM里被当做不同的类来对待。

[转] 使用SimHash进行海量文本去重

from http://www.cnblogs.com/maybe2030/p/5203186.html

本文介绍的SimHash是一种局部敏感hash。假设我们有海量的文本数据，我们需要根据文本内容将它们进行去重。对于文本去重而言，目前有很多NLP相关的算法可以在很高精度上来解决，但是我们现在处理的是大数据维度上的文本去重，这就对算法的效率有着很高的要求。而局部敏感hash算法可以将原始的文本内容映射为数字（hash签名），而且较为相近的文本内容对应的hash签名也比较相近。SimHash是Google公司进行海量网页去重使用的主要算法。

SimHash 和传统 Hash 函数的区别

传统的Hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上仅相当于伪随机数产生算法。传统的hash算法产生的两个签名，如果原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别很大。所以传统的Hash是无法在签名的维度上来衡量原内容的相似度，而SimHash本身属于一种局部敏感哈希算法，它产生的hash签名在一定程度上可以表征原内容的相似度。

我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hash签名也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hash却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“**妈喊你回家吃饭哦，回家罗回家罗” 和 “**妈叫你回家吃饭啦，回家罗回家罗”。

通过simhash计算结果为：

通过传统hash计算为：

大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hash却不能做到，这个就是局部敏感哈希的魅力。

SimHash 算法**

SimHash通过将原始的文本映射为64位的二进制数字串，然后通过比较二进制数字串的差异进而来表示原始文本内容的差异。

SimHash 流程实现

simhash是由 Charikar 在2002年提出来的，本文为了便于理解尽量不使用数学公式，分为这几步：
（注：具体的事例摘自Lanceyan的博客《海量数据相似度计算之simhash和海明距离》）

分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5）雇员（3）称（1）内部（2）有（1） 9架（3）飞碟（5）曾（1）看见（3）灰色（4）外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”，把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。

整个过程的流程图为：

SimHash 签名距离计算

我们把库里的文本都转换为simhash签名，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢？难道是比较两个simhash的01有多少个不同吗？对的，其实也就是这样，我们通过海明距离（Hamming distance）就可以计算出两个simhash到底相似不相似。两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。

SimHash 的存储和索引

经过simhash映射以后，我们得到了每个文本内容对应的simhash签名，而且也确定了利用汉明距离来进行相似度的衡量。那剩下的工作就是两两计算我们得到的simhash签名的汉明距离了，这在理论上是完全没问题的，但是考虑到我们的数据是海量的这一特点，我们是否应该考虑使用一些更具效率的存储呢？其实SimHash算法输出的simhash签名可以为我们很好建立索引，从而大大减少索引的时间，那到底怎么实现呢？

这时候大家有没有想到hashmap呢，一种理论上具有O(1)复杂度的查找数据结构。我们要查找一个key值时，通过传入一个key就可以很快的返回一个value，这个号称查找速度最快的数据结构是如何实现的呢？看下hashmap的内部结构：

如果我们需要得到key对应的value，需要经过这些计算，传入key，计算key的hashcode，得到7的位置；发现7位置对应的value还有好几个，就通过链表查找，直到找到v72。其实通过这么分析，如果我们的hashcode设置的不够好，hashmap的效率也不见得高。借鉴这个算法，来设计我们的simhash查找。通过顺序查找肯定是不行的，能否像hashmap一样先通过键值对的方式减少顺序比较的次数。看下图：

存储：

将一个64位的simhash签名拆分成4个16位的二进制码。（图上红色的16位）
分别拿着4个16位二进制码查找当前对应位置上是否有元素。（放大后的16位）
对应位置没有元素，直接追加到链表上；对应位置有则直接追加到链表尾端。（图上的 S1 — SN）

查找：

将需要比较的simhash签名拆分成4个16位的二进制码。
分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。
如果有元素，则把链表拿出来顺序查找比较，直到simhash小于一定大小的值，整个过程完成。

原理：
借鉴hashmap算法找出可以hash的key值，因为我们使用的simhash是局部敏感哈希，这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本，至少有16位的simhash是一样的。具体选择16位、8位、4位，大家根据自己的数据测试选择，虽然比较的位数越小越精准，但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。之前算出5000w数据是 382 Mb，扩大4倍1.5G左右，还可以接受。

（注：这种存储方式可以看做是针对某个64位的签名拆成4个16位的数并建立 Inverted Index）

SimHash存储和索引

当文本内容较长时，使用SimHash准确率很高，SimHash处理短文本内容准确率往往不能得到保证；
文本内容中每个term对应的权重如何确定要根据实际的项目需求，一般是可以使用IDF权重来进行计算。

参考内容

严澜的博客《海量数据相似度计算之simhash短文本查找》
《Similarity estimation techniques from rounding algorithms》

LATERAL VIEW in HiveQL

背景

在写HiveQL来分析日志的时候，有时会出现这样一种场景：

记录日志的时候把结果作为一个列表存成一条记录，比如

1,2,3,4,5,6
2,3,4,5,6,6

同时分析日志时要统计每一个结果出现了多少次也就是这样的输出

1,1
2,2
3,2
4,2
5,2
6,3

当然在这种情况下写一个UDAF + UDTF 是可以的。不过通过 LATERAL VIEW 可以更快速地解决。

SELECT result, count(0)
FROM <table_name>
LATERAL VIEW EXPLODE(split(results, ',')) t AS result
GROUP BY result

LATERAL VIEW Syntax

lateralView: LATERAL VIEW udtf(expression) tableAlias AS columnAlias (',' columnAlias)*
fromClause: FROM baseTable (lateralView)*

LATERAL VIEW Explain

Lateral view is used in conjunction with user-defined table generating functions such as explode(). As mentioned in Built-in Table-Generating Functions, a UDTF generates zero or more output rows for each input row. A lateral view first applies the UDTF to each row of base table and then joins resulting output rows to the input rows to form a virtual table having the supplied table alias.

LATERAL VIEW 是和UDTF共同工作的。它对每一行去执行UDTF，再把UDTF输出的n行结果和输入的一行连起来组成一个 virtual table。

注意：UDTF是可以生成0行结果的，那么如果想把产生0行结果对应的输入也包含进最终结果里要怎么办呢？

OUTER LATERAL VIEW

答案是使用 OUTER 关键字。

The user can specify the optional OUTER keyword to generate rows even when a LATERAL VIEW usually would not generate a row. This happens when the UDTF used does not generate any rows which happens easily with explode when the column to explode is empty. In this case the source row would never appear in the results. OUTER can be used to prevent that and rows will be generated with NULL values in the columns coming from the UDTF.

OUTER LATERAL VIEW 会把零结果的UDTF 对应的输入也显示出来，对应的无结果字段会显示为NULL。与OUTER JOIN还是有些类似的。

Reference

https://cwiki.apache.org/confluence/display/Hive/LanguageManual+LateralView

Loading, Linking and Initializing in Java - Initialization

这篇试着介绍一下 Java 类的初始化阶段。一个类/接口的初始化就是执行这个类/接口的初始化方法。

一个类/接口的初始化仅在以下的情况下发生

执行以下的JVM 指令，这些指令会直接地或间接地通过字段或方法引用来指向某个类/接口。
- new,
- getstatic,
- putstatic,
- invokestatic that references C (§new, §getstatic, §putstatic, §invokestatic)
The first invocation of a java.lang.invoke.MethodHandle instance which was the result of method handle resolution (§5.4.3.5) for a method handle of kind 2 (REF_getStatic), 4 (REF_putStatic), 6 (REF_invokeStatic), or 8 (REF_newInvokeSpecial). （这个没看懂，看到字节码的时候再回来看看吧）
执行相应的反射方法
如果c是一个类，那么初始化c的子类时
如果c是一个接口并且实现了非抽象非静态方法，那么在初始化实现了c的某个类时
c作为JVM启动的入口时

初始化时要满足的条件

在执行初始化之前，类/接口必须被 linked，也就是必须 verified，必须 prepared，可选 resolved。

多线程环境中进行类的初始化

因为JVM是一个多线程的环境，所以说在进行类的初始化时也会遇到多线程的问题。比如说当一个线程想要初始化某个类时，另一个线程正在初始化这个类。或者是对于某个类的初始化会被初始化这个类时多次请求（比如这个类包含对自己的static引用）。所以JVM的实现就要解决同步（Synchronization）和递归（Recursive Initialization）的问题。通常我们都假设 Class 对象都已经被 verified 和 prepared 了，而且 Class 对象里都包含一个 state 字段来表示这个对象处在以下的几种状态之一

已被 verified 和 prepared 但是没有被 initialized。
正在被某个线程 initializing
已经被 initialized，并且 ready for use
处在错误状态，可能是尝试 initialization 时出现了错误。

此外，为了解决同步的问题，每一个类/接口还要有一个 unique initialization lock （LC）。LC的实现依赖于JVM的具体实现。可以作为 Class 对象的一部分，也可以是一个 Class 的 Monitor。Anyway，对 Class C 的初始化主要是以下的步骤：

线程等待至获取 LC
获取 LC 之后
- 如果 C 正在被别的类进行初始化，那么就释放 LC 并阻塞当前线程，知道被通知 C 的初始化已经完成。之后重新等待获取LC
- 如果 C 正在被当前线程初始化，那么意味着出现了 Recursive Initialization。这时释放 LC 并继续初始化
- 如果 C 已经被初始化完成并且 ready for use，那么就释放 LC 并正常完成
- 如果 C 的初始化处在错误状态，那么初始化已经不可能了，释放 LC 并抛出 NoClassDefFoundError
- 否则（也就是 C 还没有被任何线程初始化），记录下 C 正在被当前线程初始化并释放锁 LC，然后按照 ClassFile 里出现的顺序将 C 的 final static field 赋值
然后，如果 C 是一个类而不是一个接口的话，找到 C 的 SuperClass SC 和所有的至少有一个 non-static non-abstract 方法的 SuperInterfaces。并对它们重复初始化的步骤，必要的时候也对父类和父接口执行 verification 和 preparation。如果在执行时出现 thrown exception，那么就要获取锁 LC，将 C 的状态标记为错误，通知所有等待的线程。之后释放锁，以抛出同样的异常结束
然后，咨询 C 的 ClassLoader 来决定是否允许 Assertion
然后，执行 C 的 initialization method
如果 initialization method 正常结束，那么就获取锁 LC，标记 C 为正常初始化完毕，通知所有等待的线程。然后释放锁，并正常退出。
否则，也就是执行 initialization method 出现问题，那么说明 initialization method 抛出了一个异常 E。如果 E 不是 Error 或 Error 的子类的话，就创建一个 ExceptionInInitializerError 的实例作为抛出的异常。如果在创建实例时出现 OOM，那么就将 OOM 的实例作为抛出的异常。
然后，获取 LC，将 C 标记为错误状态，通知所有的等待的线程。释放 LC，以抛出上一步骤的异常结束当前线程。

初始化过程中的优化

A Java Virtual Machine implementation may optimize this procedure by eliding the lock acquisition in step 1 (and release in step 4/5) when it can determine that the initialization of the class has already completed, provided that, in terms of the Java memory model, all happens-before orderings (JLS §17.4.5) that would exist if the lock were acquired, still exist when the optimization is performed.

在线程已经知道某个 Class C 已经成功创建的时候，可以不去获取 LC。这需要 Java Memory Model 里的 happens-before 原则在需要获取锁和优化存在（不需要获取锁）时都适用。

Java 里的单例模式

今天来讨论一下 Java 里的单例模式。

首先单例模式分为 eager-load 和 lazy-load。

class EagerSingelton {
    private static EagerSingleton instance = new EagerSingelton();
    private EagerSingleton(){}
    public static EagerSingleton getInstance() {return instance;}
}

class LazySingleton {
    private static LazySingleton instance;
    private LazySingleton() {}
    public static LazySingleton getInstance() {
        if (instance == null) instance = new LazySingleton();
        return instance;
    }
}

上面的实现都是把 Constructor 给设置成 private，然后将单例作为一个 static 的 field，使用 getInstance() 这个工厂方法来获取 instance。

So far so good，但是在多线程的环境里执行语句 Singleton.getInstance() 会出现问题。

首先是在 lazy-load 的情况下，如果有两个线程 a 和 b 同时执行语句 LazySingleton.getInstance() 可能会出现下面的这种顺序：

a - if (instance == null)
b - if (instance == null)
a - instance = new LazySingleton();
b - instance = new LazySingleton();

也就是说会出现 LazySingleton 被 new 了两遍。所以要考虑到给 getInstance() 方法加锁。

class LazySingleton {
    private static LazySingleton instance;
    private LazySingleton() {}
    public static synchronized LazySingleton getInstance() {
        if (instance == null) instance = new LazySingleton();
        return instance;
    }
}

当然这样每次去调用 getInstance() 方法都会尝试获取锁，这样会降低吞吐量。所以就出现了 Double Checked Lock

class LazySingleton {
    private static LazySingleton instance;
    private LazySingleton() {}
    public static LazySingleton getInstance() {
        if (instance == null) {
            synchronized(LazySingleton.class){
                if (instance == null) {
                    instance = new LazySingleton();
                }
            }
        }
        return instance;
    }
}

看上去问题是解决了，但是实际上并没有。因为还会出现一种指令重排序的问题。这个问题会发生在 new LazySingleton() 的时候。

对于执行构造方法 instance = new LazySingleton() 来说，其实是分为三个步骤的。

为新的 LazySingleton 对象分配内存空间
初始化这个 LazySingleton 对象
将这个 LazySingleton 对象的地址 assign 给 instance

其中 2 和 3 没有严格的 happens-before 的关系，也就是可以进行重排序的。换言之，当 instance 被赋值为 LazySingleton 对象的地址时，可能实际的对象还没有被初始化。所以当两个线程 a、b 同时执行 getInstance() 方法时，可能 b 线程得到的 instance 是非 null 并且未初始化的。这样就会出现隐含的问题。

改正的方法，就是将 instance 设置为 volatile。这个关键字会在一定程度上禁止指令重排序。这个在 JMM 中会介绍到。

class LazySingleton {
    private volatile static LazySingleton instance;
    private LazySingleton() {}
    public static LazySingleton getInstance() {
        if (instance == null) {
            synchronized(LazySingleton.class){
                if (instance == null) {
                    instance = new LazySingleton();
                }
            }
        }
        return instance;
    }
}

当然在 Effective Java 里介绍了一个 “Best Practice”，就是使用 enum 来实现单例。

JCIP Notes

Loading, Linking and Initializing in Java - Verifying, Preparation and Resolution, or, Linking

"Link" 一个类/接口包括验证（Verify）和准备（Preparing）相应的类/接口与它的直接父类、父接口和 element type（对于数组类来说）。Resolution 则是一个可选项。

Linking 的过程需要满足以下两点

一个类/接口必须在 link 之前被完全地 load 了。
一个类/接口必须在初始化之前被完全地 verify 和 prepare 。
Errors detected during linkage are thrown at a point in the program where some action is taken by the program that might, directly or indirectly, require linkage to the class or interface involved in the error. （这一条主要是针对 Resolution 来说的，因为存在 “lazy resolution”，所以resolution可能在 class Initialization 之后执行。而如果resolution出了错，错误就要在程序使用某个类的 symbolic reference 时抛出）

Linking 可能会抛出 OOM。

Verification

Verification 是为了保证类的二进制表示是 Structurally Correct的。这个过程可能会load别的类。但那些类不是必须被 verify 和 prepare 的。

Structurally Correct 是指什么呢？这个有点复杂要单独说了。

如果验证不通过会抛出 VerifyError。

Preparation

Preparation 是指创建类的static field 并赋予 默认值。这个过程不需要执行JVM代码。因为 默认值 并不是 class 文件里指定的 初始值。比如 static final int i = 5;，在这个阶段i 只会被赋值为0。赋值为5的操作在initialization 里而不是在 preparation。

这一阶段也会执行 loading constraints。是一种确保 overriding method 时 type-safe的约束。目前我也不太懂。。。

Resolution

Resolution 在之前的 Runtime Constant Pool 里也有提到过。也就是动态确定运行时常量池里的 Symbolic Reference 的实际值的过程。执行以下这些JVM指令都需要Resolution：

anewarray
checkcast
getfield
getstatic
instanceof
invokedynamic
invokeinterface
invokespecial
invokestatic
invokevirtual
ldc
ldc_w
multianewarray
new
putfield
putstatic

JVM Specification 接下来讲的都是初始化class、interface、field等的方法。

Access Control

在 link 的阶段会执行 Access Control，就是 public private package access 之类的。但是并不会检查 protected 。

That (protected access checking) requirement is checked as part of the verification process (§4.10.1.8); it is not part of link-time access control.

Overriding

An instance method mC declared in class C overrides another instance method mA declared in class A iff either mC is the same as mA, or all of the following are true:

C is a subclass of A.
mC has the same name and descriptor as mA.
mC is not marked ACC_PRIVATE.
One of the following is true:
- mA is marked ACC_PUBLIC; or is marked ACC_PROTECTED; or is marked neither ACC_PUBLIC nor ACC_PROTECTED nor ACC_PRIVATE and A belongs to the same run-time package as C.
- mC overrides a method m'(m'distinct from mC and mA) such that m' overrides mA.

这一段是在说 Overriding 的规则。
必须满足的条件是 C 是 A 的子类 && 方法的描述符相同 && 方法不是 ACC_PRIVATE 的。
二选一满足的条件分别是
父类的方法必须对子类可见
子类C的方法 override了一个 override 了 A的方法的方法。。。（传递性）

最后

mC is the same as mA

是什么意思啊没懂。。。

Loading, Linking and Initializing in Java - Verifying, Preparation and Resolution, or, Linking

Linking 的过程需要满足以下两点

一个类/接口必须在 link 之前被完全地 load 了。
一个类/接口必须在初始化之前被完全地 verify 和 prepare 。
Errors detected during linkage are thrown at a point in the program where some action is taken by the program that might, directly or indirectly, require linkage to the class or interface involved in the error. （这一条主要是针对 Resolution 来说的，因为存在 “lazy resolution”，所以resolution可能在 class Initialization 之后执行。而如果resolution出了错，错误就要在程序使用某个类的 symbolic reference 时抛出）

Linking 可能会抛出 OOM。

Verification

Verification 是为了保证类的二进制表示是 Structurally Correct的。这个过程可能会load别的类。但那些类不是必须被 verify 和 prepare 的。

Structurally Correct 是指什么呢？这个有点复杂要单独说了。

如果验证不通过会抛出 VerifyError。

Preparation

这一阶段也会执行 loading constraints。是一种确保 overriding method 时 type-safe的约束。目前我也不太懂。。。

Resolution

anewarray
checkcast
getfield
getstatic
instanceof
invokedynamic
invokeinterface
invokespecial
invokestatic
invokevirtual
ldc
ldc_w
multianewarray
new
putfield
putstatic

JVM Specification 接下来讲的都是初始化class、interface、field等的方法。

Access Control

在 link 的阶段会执行 Access Control，就是 public private package access 之类的。但是并不会检查 protected 。

That (protected access checking) requirement is checked as part of the verification process (§4.10.1.8); it is not part of link-time access control.

Overriding

An instance method mC declared in class C overrides another instance method mA declared in class A iff either mC is the same as mA, or all of the following are true:
• C is a subclass of A.
• mC has the same name and descriptor as mA.
• mC is not marked ACC_PRIVATE.
• One of the following is true:
– mA is marked ACC_PUBLIC; or is marked ACC_PROTECTED; or is marked neither ACC_PUBLIC nor ACC_PROTECTED nor ACC_PRIVATE and A belongs to the same run-time package as C.
– mC overrides a method m' (m' distinct from mC and mA) such that m' overrides mA.

怎么理解Condition

from http://www.importnew.com/19666.html

在java.util.concurrent包中，有两个很特殊的工具类，Condition和ReentrantLock,使用过的人都知道，ReentrantLock（重入锁）是jdk的concurrent包提供的一种独占锁的实现。它继承自Dong Lea的 AbstractQueuedSynchronizer（同步器），确切的说是ReentrantLock
的一个内部类继承了AbstractQueuedSynchronizer，ReentrantLock只不过是代理了该类的一些方法，可能有人会问为什么要使用内部类在包装一层？我想是安全的关系，因为AbstractQueuedSynchronizer中有很多方法，还实现了共享锁，Condition(稍候再细说)等功能，如果直接使ReentrantLock`继承它，则很容易出现AbstractQueuedSynchronizer中的API被误用的情况。

言归正传，今天，我们讨论下Condition工具类的实现。

ReentrantLock和Condition的使用方式通常是这样的：

运行后，结果如下：

可以看到，

Condition的执行方式，是当在线程1中调用await方法后，线程1将释放锁，并且将自己沉睡，等待唤醒，

线程2获取到锁后，开始做事，完毕后，调用Condition的signal方法，唤醒线程1，线程1恢复执行。

以上说明Condition是一个多线程间协调通信的工具类，使得某个，或者某些线程一起等待某个条件（Condition）,只有当该条件具备( signal 或者 signalAll方法被带调用)时，这些等待线程才会被唤醒，从而重新争夺锁。

那，它是怎么实现的呢？

首先还是要明白，reentrantLock.newCondition() 返回的是Condition的一个实现，该类在AbstractQueuedSynchronizer中被实现，叫做newCondition()

它可以访问AbstractQueuedSynchronizer中的方法和其余内部类（ AbstractQueuedSynchronizer是个抽象类，至于他怎么能访问，这里有个很奇妙的点，后面我专门用demo说明）

现在，我们一起来看下Condition类的实现，还是从上面的demo入手，

为了方便书写，我将AbstractQueuedSynchronizer缩写为AQS

当await被调用时，代码如下：

public final void await() throws InterruptedException {
if (Thread.interrupted())
 throw new InterruptedException();
 Node node = addConditionWaiter(); //将当前线程包装下后，
                                   //添加到Condition自己维护的一个链表中。
int savedState = fullyRelease(node);//释放当前线程占有的锁，从demo中看到，
                                       //调用await前，当前线程是占有锁的

int interruptMode = 0;
 while (!isOnSyncQueue(node)) {//释放完毕后，遍历AQS的队列，看当前节点是否在队列中，
                           //不在 说明它还没有竞争锁的资格，所以继续将自己沉睡。
                             //直到它被加入到队列中，聪明的你可能猜到了，
                            //没有错，在singal的时候加入不就可以了？
 LockSupport.park(this);
 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
 break;
 }
//被唤醒后，重新开始正式竞争锁，同样，如果竞争不到还是会将自己沉睡，等待唤醒重新开始竞争。
if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
 interruptMode = REINTERRUPT;
 if (node.nextWaiter != null)
 unlinkCancelledWaiters();
 if (interruptMode != 0)
 reportInterruptAfterWait(interruptMode);
 }

回到上面的demo，锁被释放后，线程1开始沉睡，这个时候线程因为线程1沉睡时，会唤醒AQS队列中的头结点，所所以线程2会开始竞争锁，并获取到，等待3秒后，线程2会调用signal方法，“发出”signal信号，signal方法如下：

    public final void signal() {
     if (!isHeldExclusively()) throw new IllegalMonitorStateException();
     Node first = firstWaiter; //firstWaiter为condition自己维护的一个链表的头结点，
                              //取出第一个节点后开始唤醒操作
     if (first != null)
     doSignal(first);
     }

说明下，其实Condition内部维护了等待队列的头结点和尾节点，该队列的作用是存放等待signal信号的线程，该线程被封装为Node节点后存放于此。

关键的就在于此，我们知道AQS自己维护的队列是当前等待资源的队列，AQS会在资源被释放后，依次唤醒队列中从前到后的所有节点，使他们对应的线程恢复执行。直到队列为空。

而Condition自己也维护了一个队列，该队列的作用是维护一个等待signal信号的队列，两个队列的作用是不同，事实上，每个线程也仅仅会同时存在以上两个队列中的一个，流程是这样的：

线程1调用reentrantLock.lock时，线程被加入到AQS的等待队列中。
线程1调用await方法被调用时，该线程从AQS中移除，对应操作是锁的释放。
接着马上被加入到Condition的等待队列中，以为着该线程需要signal信号。
线程2，因为线程1释放锁的关系，被唤醒，并判断可以获取锁，于是线程2获取锁，并被加入到AQS的等待队列中。
线程2调用signal方法，这个时候Condition的等待队列中只有线程1一个节点，于是它被取出来，并被加入到AQS的等待队列中。注意，这个时候，线程1 并没有被唤醒。
signal方法执行完毕，线程2调用reentrantLock.unLock()方法，释放锁。这个时候因为AQS中只有线程1，于是，AQS释放锁后按从头到尾的顺序唤醒线程时，线程1被唤醒，于是线程1回复执行。
直到释放所整个过程执行完毕。

可以看到，整个协作过程是靠结点在AQS的等待队列和Condition的等待队列中来回移动实现的，Condition作为一个条件类，很好的自己维护了一个等待信号的队列，并在适时的时候将结点加入到AQS的等待队列中来实现的唤醒操作。

看到这里，signal方法的代码应该不难理解了。

取出头结点，然后doSignal

private void doSignal(Node first) {
 do {
 if ( (firstWaiter = first.nextWaiter) == null) //修改头结点，完成旧头结点的移出工作
 lastWaiter = null;
 first.nextWaiter = null;
 } while (!transferForSignal(first) &&//将老的头结点，加入到AQS的等待队列中
 (first = firstWaiter) != null);
 }

final boolean transferForSignal(Node node) {
 /*
 * If cannot change waitStatus, the node has been cancelled.
 */
 if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
 return false;

/*
 * Splice onto queue and try to set waitStatus of predecessor to
 * indicate that thread is (probably) waiting. If cancelled or
 * attempt to set waitStatus fails, wake up to resync (in which
 * case the waitStatus can be transiently and harmlessly wrong).
 */
 Node p = enq(node);
 int ws = p.waitStatus;
//如果该结点的状态为cancel 或者修改waitStatus失败，则直接唤醒。
 if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
 LockSupport.unpark(node.thread);
 return true;
 }

可以看到，正常情况 ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL) 这个判断是不会为true的，所以，不会在这个时候唤醒该线程。

只有到发送signal信号的线程调用reentrantLock.unlock()后因为它已经被加到AQS的等待队列中，所以才会被唤醒。

总结：

本文从代码的角度说明了Condition的实现方式，其中，涉及到了AQS的很多操作，比如AQS的等待队列实现独占锁功能，不过，这不是本文讨论的重点，等有机会再将AQS的实现单独分享出来。

Notes on The java.util.concurrent Synchronizer Framework

Notes on The java.util.concurrent Synchronizer Framework

最近看了一篇 Doug Lea 写的论文 The java.util.concurrent Synchronizer Framework。在这里面他介绍了他写 juc 内部的同步器（事实上是 AQS）时的设计思路与实现方法。

摘要

在摘要里，Doug Lea 讲述了两件事：

大部分 juc 里的 synchronizer（同步器）都是基于 AbstractQueueSynchronizer（aka AQS）来实现的。
AQS 里提供了通用的机制来原子性地管理同步状态、阻塞/解阻塞线程和排队。

Introduction

JSR166 就是以 AQS 为核心的。

Requirements

功能需求

所有的同步器都要提供两类方法。一类是 acquire 操作，它会阻塞调用这个方法的线程直到同步状态允许它继续执行。另一类是 release 操作，会改变同步状态，允许一个或多个被阻塞的线程继续执行。

juc 并没有指定一个统一的接口来规范 synchronizer 的 api，所以 acquire 和 release 操作在各个类里有多种名称和形式。另一方面，这些 synchronizer 也都支持了一些通用的功能，比如说

非阻塞式的同步尝试，比如 tryLock
可选的超时机制
通过打断来取消

同步器可按照是 一定独占式 和 可以共享式 来分类。
独占式是指同时只可能有一个线程通过 blocking point。共享式是指同时可能有多个线程在执行。

juc 也定义了接口 Condition 来支持 monitor-style 的 await/signal 操作。Condition 可能与独占锁相关联，而且在实现上也是紧密连在一起的。

性能需求

Java 内置的锁（aka synchronized 关键字修饰的 method 和 block ）会产生性能问题，一方面会增加 Memory Overhead，另一方面在单线程环境下会产生 Time Overhead。这些对于 juc 的锁来说都不是问题。实际上，juc 的锁的性能问题在于 Scalability，也就是当同步器很contended的时候还能保证效率。当然系统资源的消耗也要考虑进来做 tradeoff。比如 spinlock 去 acquire 的时间比 blocking lock 要短，但是这时的CPU是在空转的。

保证高吞吐量时难免会对减小公平性（可能造成死锁），同理保证线程执行的公平也会降低吞吐量。所以不同的目的采取不同的公平策略。

提供方法帮助用户定位到瓶颈（多少个线程被阻塞了），因为不管设计得怎么好都难免会出现性能瓶颈。

Design and Implementation

synchronizer 的设计**是很直观的，对于 acquire 操作来说代码如下：

while(synchronization state does not allow acquire){  // sync state 不允许线程 acquire 时

    enqueue current thread if not already queued;  // 将当前线程放入队列

    possibly block current thread;                 // （可能）阻塞当前线程

}

dequeue current thread if it was queued;           // （sync state 允许 acquire 时，）将当前线程出列

对于 release 的操作如下：

update synchronization state;                      // 更新 sync state

if(state may permit a blocked thread to acquire)   // 如果 sync state 允许一个被阻塞的线程去 acquire，就 unlock 一个或多个排队的线程

    unlock one or more queued threads;

为了支持上面的两个操作，我们要实现下面的三个基本组件

可以原子性地操作 sync state
阻塞和结阻塞线程
维护一个队列

sync state

AQS 使用一个32位的 int 来存放 sync state，使用 volatile 关键字来保证可见性，使用 CAS 来保证更新的原子性。

AQS 的实现类必须要实现方法 tryAcquire 和 tryRelease 并在其中使用相关方法来操作 sync state，用来控制 acquire 和 release 的操作。如果 synchronization 被 acquire 的话 tryAcquire 一定要返回 true；如果 sync state 允许 future acquires 的话 tryRelease 方法就一定要返回 true。

Blocking

JSR166 以前对于线程的 block 和 unblock 并没有很好的支持。但是 juc 的 LockSupport 解决了这个问题。LockSupport.park() 和 LockSupport.unpark() 方法可以分别阻塞当前线程和释放某个被 park 住的线程。

Queues

AQS 的核心就在于维护 FIFO Queues of Blocked Threads。这个 Queue 最好是一个不使用 low-level 的锁的非阻塞数据结构。MCS locks 和 CLH locks 都支持这种特性。 CLH 因为更容易实现“取消”和“超时”而被选为 AQS 的 queue。

Java 位运算汇总

最近在看 Java 的 ThreadpoolExector 的实现，里面有用到位运算。所以就先总结一下 Java 里的位运算吧。

JDK 里提供的位运算符有以下7种

左移<<
右移>>
无符号右移>>>
位与&
位或|
位非~
位异或^

这回先看看前三个移位运算。

移位运算

<< >> >>> 是移位运算符。

<< 是左移很好理解。就是向左移位，右侧补0。

3 << 4 相当于 3 * Math.pow(2, 4)

>> 是算数右移，也就是向右移位，低位舍去，高位补充原来的最高位。换言之带符号的右移。

>>> 是逻辑右移，最左边补0。

换言之，对于正数来说，>> 和 >>> 是没有区别的。但是对于负数来说，这两个运算符产生的效果就截然不同了。

所以对于程序

int a = -32000;
a
a << 5
a >> 5
a >>> 5

表示为2进制就是

11111111111111111000001100000000
11111111111100000110000000000000
11111111111111111111110000011000
00000111111111111111110000011000

表示为10进制是

可见算数右移运算 a >> n，不管 a 是正数还是负数，都相当于 a / Math.pow(2, n)。而对于逻辑右移来说， a >>> n 仅在 a 为正数时相当于 a >> n，a为负数时看起来没有算数意义。

之前的例子都是假定 a 是 32 位有符号整数。当 a 是 long、float、double 时使用这些运算符是会使编译器报错的。但是当 a 为 short、byte、char 时使用这些运算符是不会报错的，只是返回结果是 int 型而且进行位操作时也是把 a 当做 32 位（左边空位补0）来处理的。

数据库的一些知识

数据库事务的隔离级别

uncommitted read: 一个事务可能读到另一个事务尚未提交的修改，会导致 dirty read
unrepeatable read: 为了解决脏读，规定一个事物执行过程中的修改在提交前对其他事务不可见。但是这时一个事务在执行中读取某个数据两次。在这两次之间另一个事务将这个数据进行修改导致两次读的结果不一样。会导致 unrepeatable read。
repeatable read: 为了解决不可重复读，可以让事务锁定在读的行，这样其它事务不能修改。但是其它事务可以插入新的行并且这些行包含在事务接下来的读取中。这样会导致 phantom read。在InnoDB里因为行锁的 “GAP” 的存在，可以解决幻读的问题。
serializable: 最高的隔离级别，串行化并发的事务。解决了幻读的问题但是性能不好。

ACID

A atomic 事务里的所有操作要么都执行成功，要么都执行失败。
C consistency 事务前和事务后数据库的完整性约束没有发生变化
I isolation 数据库的隔离性（也就是不同的隔离级别）
D duration 事务一旦提交了结果就是永久性的，即使发生了宕机也不会消失掉。

行锁和表锁

InnoDB支持了行锁。只有走索引的时候才会去锁住行，否则会锁住表。锁住行准确的说是锁住了对应的索引。可能会导致死锁。
行锁包括读锁和写锁，也叫共享锁和排它锁。
InnoDB还提供了两种意向锁，都是表锁。在获取读（写）锁是必须先获得读（写）意向锁。

UPDATE INSERT DELETE 都会加排它锁。
SELECT * FOR UPDATE 会加排它锁
SELECT * LOCK IN SHARE MODE 会加共享锁。

两段锁协议

MySQL 加锁和释放锁是遵循两段式的协议的。也就是加锁阶段和释放锁阶段。加锁阶段就是逐步加锁，释放锁阶段就是一起释放。同时释放锁的阶段不能再加锁。

乐观锁、悲观锁和MVCC

悲观锁是数据库的锁机制（读锁和写锁）。总是假定数据会被别的事务修改所以加锁来保证。
乐观锁的加锁机制更轻松。一般是通过增加版本号来实现的。在读出数据的时候连版本号一起读出来。更新数据时将版本号加一。提交时会将新数据的版本号和数据库的版本号进行比对。只有新数据的版本号更大时才会更新成功。好处就是读不加锁。

MVCC的实现
MVCC会对数据的每一行增加一个版本号。这个版本号是事务的版本号。每开启一个新的事务。版本号都会加一。
在 repeatable read 的隔离级别下：
select 时会取出版本号小于等于这个事务版本号的值并删掉版本号为空或版本号大于事务版本号的数据。
INSERT 和 DELETE 时会将当前版本号写入
UPDATE 实质上是一次 INSERT 和一次 DELETE。
所以读是快照读。也就是读的是snapshot 历史数据。可以不用加锁。但是去处理当前（最新）数据时还是要加锁的。

ACID 的实现

实现ACID的关键技术就是锁和日志。

A redo 和 undo 日志。
C 通过类型检查、唯一索引、外键约束和级联更新保护数据的完整性
I 加锁
D 磁盘持久化

Understanding "Query Then Fetch" vs "DFS Query Then Fetch"

From https://www.elastic.co/blog/understanding-query-then-fetch-vs-dfs-query-then-fetch

The Problem

如下的 Query 和查询结果

$ curl -XGET localhost:9200/startswith/test/_search?pretty -d '{
        "query": {
        "match_phrase_prefix": {
           "title": {
             "query": "d",
             "max_expansions": 5
           }
         }
       }
     }' | grep title

      "_score" : 1.0, "_source" : {"title":"drunk"}
      "_score" : 0.30685282, "_source" : {"title":"dzone"}
      "_score" : 0.30685282, "_source" : {"title":"data"}
      "_score" : 0.30685282, "_source" : {"title":"drive"}

可以看到 drunk 的 _score 是1 而其它的title的得分只有 0.3。难道这些单词都匹配了d，得分不应该是一样的吗？按理来说应该是一样的但是下面是对出现“得分不一样”的情况的解释

ES Search Types

之前的那个问题的答案是既是也不是。这跟ES使用的 Search Type 有关。这里先讨论 Query Then Fetch 和 DFS Query Then Fetch。

Query Then Fetch

ES 默认的 Search Type 是 Query Then Fetch，工作过程如下：

Send the query to each shard
Find all matching documents and calculate scores using local Term/Document Frequencies
Build a priority queue of results (sort, pagination with from/to, etc)
Return metadata about the results to requesting node. Note, the actual document is not sent yet, just the scores
Scores from all the shards are merged and sorted on the requesting node, docs are selected according to query criteria
Finally, the actual docs are retrieved from individual shards where they reside.
Results are returned to the client

简单来说就是

对每个shard发送query ->
shard 找到匹配的文档并计算local的TF-IDF ->
根据 sort 或分页等信息建立 results 的优先队列 ->
只向 requesting node 返回文档的metadata，比如_score ->
在 requesting node 上，根据 query 和 docs 的 _score 选择适合的docs ->
现在才向对应的 shard 请求文档内容 ->
requesting node 将结果返回客户端

大多数情况下，index上有足够多的文档的话，每个shard上的tf-idf是差不多的。当然个别情况下会出现最开始的那个问题。

DFS Query Then Fetch

出现那种问题时可以使用 DFS Query Then Fetch 来解决，它的工作过程如下

Prequery each shard asking about Term and Document frequencies
Send the query to each shard
Find all matching documents and calculate scores using global Term/Document Frequencies calculated from the prequery.
Build a priority queue of results (sort, pagination with from/to, etc)
Return metadata about the results to requesting node. Note, the actual document is not sent yet, just the scores
Scores from all the shards are merged and sorted on the requesting node, docs are selected according to query criteria
Finally, the actual docs are retrieved from individual shards where they reside.
Results are returned to the client

所以用这种方法的话，一开始的query和结果就变成

$ curl -XGET 'localhost:9200/startswith/test/_search?pretty=true&search_type=dfs_query_then_fetch' -d '{
        "query": {
        "match_phrase_prefix": {
           "title": {
             "query": "d",
             "max_expansions": 5
           }
         }
       }
     }' | grep title

      "_score" : 1.9162908, "_source" : {"title":"dzone"}
      "_score" : 1.9162908, "_source" : {"title":"data"}
      "_score" : 1.9162908, "_source" : {"title":"drunk"}
      "_score" : 1.9162908, "_source" : {"title":"drive"}

结论

显然要在准确性和效率上做一个 tradeoff。prequery 会在所有shard之间产生一个 round-trip，从而降低效率（跟索引大小、shard数量、query rate 有关）。大多数情况下 DFS Query Then Fetch 都是不必要的。当然在对打分很严格的情形之下还是要使用 DFS Query Then Fetch的。

[转]Java 理论与实践: 非阻塞算法简介

在不只一个线程访问一个互斥的变量时，所有线程都必须使用同步，否则就可能会发生一些非常糟糕的事情。Java 语言中主要的同步手段就是 synchronized 关键字（也称为内在锁），它强制实行互斥，确保执行 synchronized 块的线程的动作，能够被后来执行受相同锁保护的 synchronized 块的其他线程看到。在使用得当的时候，内在锁可以让程序做到线程安全，但是在使用锁定保护短的代码路径，而且线程频繁地争用锁的时候，锁定可能成为相当繁重的操作。

在 “流行的原子” 一文中，我们研究了原子变量，原子变量提供了原子性的读-写-修改操作，可以在不使用锁的情况下安全地更新共享变量。原子变量的内存语义与 volatile 变量类似，但是因为它们也可以被原子性地修改，所以可以把它们用作不使用锁的并发算法的基础。

非阻塞的计数器

清单 1 中的 Counter 是线程安全的，但是使用锁的需求带来的性能成本困扰了一些开发人员。但是锁是必需的，因为虽然增加看起来是单一操作，但实际是三个独立操作的简化：检索值，给值加 1，再写回值。（在 getValue 方法上也需要同步，以保证调用 getValue 的线程看到的是最新的值。虽然许多开发人员勉强地使自己相信忽略锁定需求是可以接受的，但忽略锁定需求并不是好策略。）

在多个线程同时请求同一个锁时，会有一个线程获胜并得到锁，而其他线程被阻塞。JVM 实现阻塞的方式通常是挂起阻塞的线程，过一会儿再重新调度它。由此造成的上下文切换相对于锁保护的少数几条指令来说，会造成相当大的延迟。

清单 1. 使用同步的线程安全的计数器

public final class Counter {
    private long value = 0;
    public synchronized long getValue() {
        return value;
    }
    public synchronized long increment() {
        return ++value;
    }
}

清单 2 中的 NonblockingCounter 显示了一种最简单的非阻塞算法：使用 AtomicInteger 的 compareAndSet() （CAS）方法的计数器。compareAndSet() 方法规定 “将这个变量更新为新值，但是如果从我上次看到这个变量之后其他线程修改了它的值，那么更新就失败”（请参阅 “流行的原子” 获得关于原子变量以及 “比较和设置” 的更多解释。）

清单 2. 使用 CAS 的非阻塞算法

public class NonblockingCounter {
    private AtomicInteger value;
    public int getValue() {
        return value.get();
    }
    public int increment() {
        int v;
        do {
            v = value.get();
        while (!value.compareAndSet(v, v + 1));
        return v + 1;
    }
}

原子变量类之所以被称为原子的，是因为它们提供了对数字和对象引用的细粒度的原子更新，但是在作为非阻塞算法的基本构造块的意义上，它们也是原子的。非阻塞算法作为科研的主题，已经有 20 多年了，但是直到 Java 5.0 出现，在 Java 语言中才成为可能。

现代的处理器提供了特殊的指令，可以自动更新共享数据，而且能够检测到其他线程的干扰，而 compareAndSet() 就用这些代替了锁定。（如果要做的只是递增计数器，那么 AtomicInteger 提供了进行递增的方法，但是这些方法基于 compareAndSet()，例如NonblockingCounter.increment()）。

非阻塞版本相对于基于锁的版本有几个性能优势。首先，它用硬件的原生形态代替 JVM 的锁定代码路径，从而在更细的粒度层次上（独立的内存位置）进行同步，失败的线程也可以立即重试，而不会被挂起后重新调度。更细的粒度降低了争用的机会，不用重新调度就能重试的能力也降低了争用的成本。即使有少量失败的 CAS 操作，这种方法仍然会比由于锁争用造成的重新调度快得多。

NonblockingCounter 这个示例可能简单了些，但是它演示了所有非阻塞算法的一个基本特征 —— 有些算法步骤的执行是要冒险的，因为知道如果 CAS 不成功可能不得不重做。非阻塞算法通常叫作乐观算法，因为它们继续操作的假设是不会有干扰。如果发现干扰，就会回退并重试。在计数器的示例中，冒险的步骤是递增 —— 它检索旧值并在旧值上加一，希望在计算更新期间值不会变化。如果它的希望落空，就会再次检索值，并重做递增计算。

非阻塞堆栈

非阻塞算法稍微复杂一些的示例是清单 3 中的 ConcurrentStack。ConcurrentStack 中的 push()和 pop() 操作在结构上与NonblockingCounter 上相似，只是做的工作有些冒险，希望在 “提交” 工作的时候，底层假设没有失效。push()方法观察当前最顶的节点，构建一个新节点放在堆栈上，然后，如果最顶端的节点在初始观察之后没有变化，那么就安装新节点。如果 CAS 失败，意味着另一个线程已经修改了堆栈，那么过程就会重新开始。

清单 3. 使用 Treiber 算法的非阻塞堆栈

public class ConcurrentStack<E> {
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }
    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) 
                return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead,newHead));
        return oldHead.item;
    }
    static class Node<E> {
        final E item;
        Node<E> next;
        public Node(E item) { this.item = item; }
    }
}

性能考虑

在轻度到中度的争用情况下，非阻塞算法的性能会超越阻塞算法，因为 CAS 的多数时间都在第一次尝试时就成功，而发生争用时的开销也不涉及线程挂起和上下文切换，只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多（这句话肯定是真的，因为没有争用的锁涉及 CAS 加上额外的处理），而争用的 CAS 比争用的锁获取涉及更短的延迟。

在高度争用的情况下（即有多个线程不断争用一个内存位置的时候），基于锁的算法开始提供比非阻塞算法更好的吞吐率，因为当线程阻塞时，它就会停止争用，耐心地等候轮到自己，从而避免了进一步争用。但是，这么高的争用程度并不常见，因为多数时候，线程会把线程本地的计算与争用共享数据的操作分开，从而给其他线程使用共享数据的机会。（这么高的争用程度也表明需要重新检查算法，朝着更少共享数据的方向努力。）“流行的原子” 中的图在这方面就有点儿让人困惑，因为被测量的程序中发生的争用极其密集，看起来即使对数量很少的线程，锁定也是更好的解决方案。

非阻塞的链表

目前为止的示例（计数器和堆栈）都是非常简单的非阻塞算法，一旦掌握了在循环中使用 CAS，就可以容易地模仿它们。对于更复杂的数据结构，非阻塞算法要比这些简单示例复杂得多，因为修改链表、树或哈希表可能涉及对多个指针的更新。CAS 支持对单一指针的原子性条件更新，但是不支持两个以上的指针。所以，要构建一个非阻塞的链表、树或哈希表，需要找到一种方式，可以用 CAS 更新多个指针，同时不会让数据结构处于不一致的状态。

在链表的尾部插入元素，通常涉及对两个指针的更新：“尾” 指针总是指向列表中的最后一个元素，“下一个” 指针从过去的最后一个元素指向新插入的元素。因为需要更新两个指针，所以需要两个 CAS。在独立的 CAS 中更新两个指针带来了两个需要考虑的潜在问题：如果第一个 CAS 成功，而第二个 CAS 失败，会发生什么？如果其他线程在第一个和第二个 CAS 之间企图访问链表，会发生什么？

对于非复杂数据结构，构建非阻塞算法的 “技巧” 是确保数据结构总处于一致的状态（甚至包括在线程开始修改数据结构和它完成修改之间），还要确保其他线程不仅能够判断出第一个线程已经完成了更新还是处在更新的中途，还能够判断出如果第一个线程走向 AWOL，完成更新还需要什么操作。如果线程发现了处在更新中途的数据结构，它就可以 “帮助” 正在执行更新的线程完成更新，然后再进行自己的操作。当第一个线程回来试图完成自己的更新时，会发现不再需要了，返回即可，因为 CAS 会检测到帮助线程的干预（在这种情况下，是建设性的干预）。

这种 “帮助邻居” 的要求，对于让数据结构免受单个线程失败的影响，是必需的。如果线程发现数据结构正处在被其他线程更新的中途，然后就等候其他线程完成更新，那么如果其他线程在操作中途失败，这个线程就可能永远等候下去。即使不出现故障，这种方式也会提供糟糕的性能，因为新到达的线程必须放弃处理器，导致上下文切换，或者等到自己的时间片过期（而这更糟）。

清单 4 的 LinkedQueue 显示了 Michael-Scott 非阻塞队列算法的插入操作，它是由 ConcurrentLinkedQueue 实现的：

清单 4. Michael-Scott 非阻塞队列算法中的插入

public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }
    private AtomicReference<Node<E>> head
        = new AtomicReference<Node<E>>(new Node<E>(null, null));
    private AtomicReference<Node<E>> tail = head;
    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
            if (curTail == tail.get()) {
                if (residue == null) /* A */ {
                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                        tail.compareAndSet(curTail, newNode) /* D */ ;
                        return true;
                    }
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }
    }
}

像许多队列算法一样，空队列只包含一个假节点。头指针总是指向假节点；尾指针总指向最后一个节点或倒数第二个节点。图 1 演示了正常情况下有两个元素的队列：

图1. 有两个元素，处在静止状态的队列

如清单 4 所示，插入一个元素涉及两个指针更新，这两个更新都是通过 CAS 进行的：从队列当前的最后节点（C）链接到新节点，并把尾指针移动到新的最后一个节点（D）。如果第一步失败，那么队列的状态不变，插入线程会继续重试，直到成功。一旦操作成功，插入被当成生效，其他线程就可以看到修改。还需要把尾指针移动到新节点的位置上，但是这项工作可以看成是 “清理工作”，因为任何处在这种情况下的线程都可以判断出是否需要这种清理，也知道如何进行清理。

队列总是处于两种状态之一：正常状态（或称静止状态，图 1 和图 3）或中间状态（图 2）。在插入操作之前和第二个 CAS（D）成功之后，队列处在静止状态；在第一个 CAS（C）成功之后，队列处在中间状态。在静止状态时，尾指针指向的链接节点的 next 字段总为 null，而在中间状态时，这个字段为非 null。任何线程通过比较 tail.next 是否为 null，就可以判断出队列的状态，这是让线程可以帮助其他线程 “完成” 操作的关键。

图 2. 处在插入中间状态的队列，在新元素插入之后，尾指针更新之前

插入操作在插入新元素（A）之前，先检查队列是否处在中间状态，如清单 4 所示。如果是在中间状态，那么肯定有其他线程已经处在元素插入的中途，在步骤（C）和（D）之间。不必等候其他线程完成，当前线程就可以 “帮助” 它完成操作，把尾指针向前移动（B）。如果有必要，它还会继续检查尾指针并向前移动指针，直到队列处于静止状态，这时它就可以开始自己的插入了。

第一个 CAS（C）可能因为两个线程竞争访问队列当前的最后一个元素而失败；在这种情况下，没有发生修改，失去 CAS 的线程会重新装入尾指针并再次尝试。如果第二个 CAS（D）失败，插入线程不需要重试 —— 因为其他线程已经在步骤（B）中替它完成了这个操作！

图 3. 在尾指针更新后，队列重新处在静止状态

幕后的非阻塞算法

如果深入 JVM 和操作系统，会发现非阻塞算法无处不在。垃圾收集器使用非阻塞算法加快并发和平行的垃圾搜集；调度器使用非阻塞算法有效地调度线程和进程，实现内在锁。在 Mustang（Java 6.0）中，基于锁的 SynchronousQueue 算法被新的非阻塞版本代替。很少有开发人员会直接使用 SynchronousQueue，但是通过 Executors.newCachedThreadPool()工厂构建的线程池用它作为工作队列。比较缓存线程池性能的对比测试显示，新的非阻塞同步队列实现提供了几乎是当前实现 3 倍的速度。在 Mustang 的后续版本（代码名称为 Dolphin）中，已经规划了进一步的改进。

结束语

非阻塞算法要比基于锁的算法复杂得多。开发非阻塞算法是相当专业的训练，而且要证明算法的正确也极为困难。但是在 Java 版本之间并发性能上的众多改进来自对非阻塞算法的采用，而且随着并发性能变得越来越重要，可以预见在 Java 平台的未来发行版中，会使用更多的非阻塞算法。

Loading, Linking and Initializing in Java - JVM Startup

JVM Specification 里提到的关于 JVM startup 的话很短

The Java Virtual Machine starts up by creating an initial class, which is specified in an implementation-dependent manner, using the bootstrap class loader (§5.3.1). The Java Virtual Machine then links the initial class, initializes it, and invokes the public class method void main(String[]). The invocation of this method drives all further execution. Execution of the Java Virtual Machine instructions constituting the main method may cause linking (and consequently creation) of additional classes and interfaces, as well as invocation of additional methods.
In an implementation of the Java Virtual Machine, the initial class could be provided as a command line argument. Alternatively, the implementation could provide an initial class that sets up a class loader which in turn loads an application. Other choices of the initial class are possible so long as they are consistent with the specification given in the previous paragraph.

第一段是说 JVM的启动是通过创建 initial class。而这个 initial class 是在实现里指定的，会使用 bootstrap classloader。JVM之后会 link 和 initialize 这个 class 并调用里面的 public static void main(String[] args) 方法。

第二段是说不同的实现可以怎么指定 initial class

通过命令行传入 init class 的名字
提供一个 init class 用来设置一个可以加载应用的class loader
其它满足之前提到的specification的方法

An Issue Named “minimum_master_nodes does not prevent split-brain if splits are intersecting”

之前有一篇大概翻译了一下 ES 为什么会出现 Split Brain 以及通过设置参数minimum_master_nodes来预防。那篇文章的结尾提到了有一个 Issue 指出即使设置了这个参数依然会有 Split Brain 的问题出现。这篇文章就试着解释一下这个 Issue 所提到的问题和一些与之相关的问题。

Why Still Split Brain?

假设有三个节点组成一个集群，其中 Node2 是 Master，如下图所示。

之后 Node2 和 Node3 之间的网络连接断了，但是它们和 Node1 之间还可以互相 Ping 到。这时，Node2 以为集群里只剩下 Node1 和 Node2 了。同时 Node3 也以为集群只剩下 Node1 和 Node3 了。Node2 还是小集群里的 Master。而这个时候如果 Node3 也将自己选举为 Master 的话，这个集群里就出现了两个 Master 并且会出现 Split Brain。

这个 Split Brain 的问题即使是将 minimum_master_nodes 设置为2 也就是 3/2 +1 时也会出现。

Follow-up

目前这个 Issue 已经被关闭，也就是问题被解决了。

可以看到在一个 PR 上进行了 Zen Discovery 的优化来解决了这个问题。具体怎么解决的还没看懂。。。先来介绍一下 ES 使用的 Zen Discovery 吧。

Zen Discovery

（这一部分要去看相关代码才能明白但是有点看跪了。。。所以就借鉴了这篇文章里的内容）

ES 在集群内部是使用的是一种叫做 Zen Discovery 的方法。它提供的是一种叫做 Unicast Discovery，也就是“单播发现”的机制来维护集群的状态。Zen DIscovery 主要包含以下几个模块：

Ping
Unicast
Master Election
Fault Detection
Cluster State Updates
No Master Block

Ping

ES instance 通过 Ping 来找到其它节点。具体在 Ping 里做了什么要看代码了。。

Unicast

Unicast 是一个点对点的传播。在这里为了提高效率可以指定某些 host 作为 Gossip Router。也就是会采用 Gossip Protocol 的方式进行 unicast。

Unicast 采用的是 Transport 模块来 perform discovery。

Master Election

Master Election 就是用来选举 Master 的。这部分也要先看代码了。。。

As part of the ping process a master of the cluster is either elected or joined to. This is done automatically. The discovery.zen.ping_timeout (which defaults to 3s) allows for the tweaking of election time to handle cases of slow or congested networks (higher values assure less chance of failure). Once a node joins, it will send a join request to the master (discovery.zen.join_timeout) with a timeout defaulting at 20 times the ping timeout.

When the master node stops or has encountered a problem, the cluster nodes start pinging again and will elect a new master. This pinging round also serves as a protection against (partial) network failures where a node may unjustly think that the master has failed. In this case the node will simply hear from other nodes about the currently active master.

If discovery.zen.master_election.filter_client is true, pings from client nodes (nodes where node.client is true, or both node.data and node.master are false) are ignored during master election; the default value is true. If discovery.zen.master_election.filter_data is true, pings from non-master-eligible data nodes (nodes where node.data is true and node.master is false) are ignored during master election; the default value is false. Pings from master-eligible nodes are always observed during master election.

Nodes can be excluded from becoming a master by setting node.master to false. Note, once a node is a client node (node.client set to true), it will not be allowed to become a master (node.master is automatically set to false).

The discovery.zen.minimum_master_nodes sets the minimum number of master eligible nodes that need to join a newly elected master in order for an election to complete and for the elected node to accept it’s mastership. The same setting controls the minimum number of active master eligible nodes that should be a part of any active cluster. If this requirement is not met the active master node will step down and a new master election will be begin.

This setting must be set to a quorum of your master eligible nodes. It is recommended to avoid having only two master eligible nodes, since a quorum of two is two. Therefore, a loss of either master node will result in an inoperable cluster.

Fault Detection

用 Ping 的方式来确认别的 node 是否还在集群里面。Detection 分为

MasterFaultDetection 在所有 node 上运行。
NodesFaultDetection 只在 Master 上运行。

There are two fault detection processes running. The first is by the master, to ping all the other nodes in the cluster and verify that they are alive. And on the other end, each node pings to master to verify if its still alive or an election process needs to be initiated.

The following settings control the fault detection process using the discovery.zen.fd prefix:

ping_interval How often a node gets pinged. Defaults to 1s.
ping_timeout How long to wait for a ping response, defaults to 30s.
ping_retries How many ping failures / timeouts cause a node to be considered failed. Defaults to 3.

Java 线程的状态

网上有很多讲 Java 的线程的状态和他们之间的互相转换的文章，其中的内容也是五花八门。这篇文章尝试以源代码为标准来总结一下 Java 的线程的状态。

Java 的线程状态在 java.lang.Thread$State 里，一共有以下的六种

NEW
RUNNABLE
BLOCKED
WAITING
TIMED_WAITING
TERMINATED

各自的含义

NEW 是指一个线程被创建但是还没有开始执行

RUNNABLE 是指一个线程正在 JVM 里执行，也可能是在 OS 里的资源，比如说 CPU。

BLOCKED 的线程是在等待 monitor lock。也就是等待获取锁。

WAITING 的线程是在等待其它的线程做出相应。比如执行 LockSupport.park() 后的线程在等待其它线程调用 LockSupport.unpark()。调用 thread1.join() 方法的线程在等待 thread1 执行完毕。调用 object1.wait() 方法在等待某个线程调用 object1.notify() 或 object1.notifyAll() 方法。

TIMED_WAITING 是指某个线程执行的了带超时的等待方法。

TERMINATED 是说某个线程正确或异常地完成了执行。

状态间的互相转换

线程的状态转换直接看这个图就好了。

Blocked 和 Waiting 的区别

Blocked 是指 JVM 认为线程不能进入某个临界区，也就是还没获得相应的锁。
Waiting 是指线程已经进入了临界区（也就是已经拿到了锁）但是还需要等待别的资源准备完毕。（所以会将锁释放掉）

Conclusion

这篇文章简要地介绍了线程的6种不同的状态，用一张图来记录了它们间互相转换的条件。最后提及了一下
Blocked 状态和 Waiting 状态的区别。

JVM

When a class is loaded and initialized in JVM

from http://javarevisited.blogspot.com/2012/07/when-class-loading-initialization-java-example.html

这篇主要介绍一下在JVM里，一个class什么时候被加载（load），又是什么时候被初始化（initialize）的。

When a class is loaded

一个class既可以在有一个class引用它的时候加载也可以在这个class需要被初始化的时候来加载。这个在JVM Specification 里没有明确规定，根据JVM的实现不同而不同。但是可以保证的是一旦有 static initialization，相应的类会被加载。

When a class is initialized
仅当以下情况出现时 class initialization 会执行。（from jvm8 specification）

翻译过来就是

class的instance被创建
class的非final的 static field被 get put invoke
class 的静态方法被调用
反射
子类的初始化会调用父类初始化
声明了non-static non-abstract方法的 interface 会在实现这个interface的某个类被初始化时初始化
JVM startup的初始类（public static void main(String[] args)）

How class is initialized in Java

这一部分主要关注初始化的顺序

先声明的field（在上面的）先初始化。
Super class 先于 sub class 初始化。
如果class initialization 是被 static field access 所触发的话，那么只有声明这个field的class才被初始化。如果在Father里声明而通过Child.field 调用的话只会初始化Father。
interface Initialization 不会触发 super interface initialization。
static field 先于 non-static field 被初始化。
父类的 non-static field 先于子类的 non-static field 被初始化。

下面有几个例子

/**
 * Java program to demonstrate class loading and initialization in Java.
 */
public class ClassInitializationTest {

    public static void main(String args[]) throws InterruptedException {

        NotUsed o = null; //this class is not used, should not be initialized
        Child t = new Child(); //initializing sub class, should trigger super class initialization
        System.out.println((Object)o == (Object)t);
    }
}

/**
 * Super class to demonstrate that Super class is loaded and initialized before Subclass.
 */
class Parent {
    static { System.out.println("static block of Super class is initialized"); }
    {System.out.println("non static blocks in super class is initialized");}
}

/**
 * Java class which is not used in this program, consequently not loaded by JVM
 */
class NotUsed {
    static { System.out.println("NotUsed Class is initialized "); }
}

/**
 * Sub class of Parent, demonstrate when exactly sub class loading and initialization occurs.
 */
class Child extends Parent {
    static { System.out.println("static block of Sub class is initialized in Java "); }
    {System.out.println("non static blocks in sub class is initialized");}
}

Output:
static block of Super class is initialized
static block of Sub class is initialized in Java
non static blocks in super class is initialized
non static blocks in sub class is initialized
false

/**
 * Another Java program example to demonstrate class initialization and loading in Java.
 */

public class ClassInitializationTest {

    public static void main(String args[]) throws InterruptedException {

       //accessing static field of Parent through child, should only initialize Parent
       System.out.println(Child.familyName);
    }
}

class Parent {
    //compile time constant, accessing this will not trigger class initialization
    //protected static final String familyName = "Lawson";

    protected static String familyName = "Lawson";

    static { System.out.println("static block of Super class is initialized"); }
    {System.out.println("non static blocks in super class is initialized");}
}

Output:
static block of Super class is initialized
Lawson

Default Apache Lucene Scoring

In order to calculate the score for a doc, multiple factors are taken into account.

The conceptual formula is a combination of Boolean Model and Vector Space Model.

norm() is the length of the word

Loading, Linking and Initializing in Java - Creation and Loading

这一篇试着介绍一下 Java class 的 creation 和 loading 吧。分成两个部分 Creation 和 Loading

类创建的时机

Creation of a class or interface C denoted by the name N consists of the construction in the method area of the Java Virtual Machine (§2.5.4) of an implementation-specific internal representation of C. Class or interface creation is triggered by another class or interface D, which references C through its run-time constant pool. Class or interface creation may also be triggered by D invoking methods in certain Java SE platform class libraries (§2.12) such as reflection.

类和接口的创建实质上就是在方法区生成一个对应的类/接口的表示（representation）。

类/接口 C 的创建可以通过两个行为触发（第二个没太懂）

另一个类 D 在它自己的 run-time constant pool 里引用了 C
使用反射等Java类库

如果 C 不是一个 array class 的话，创建 C 是通过 load C 的class 文件。如果 C 是一个 array class 的话，它并没有显式的二进制表示，事实上它是通过JVM而不是ClassLoader来创建的。

关于 ClassLoader

ClassLoader 的介绍在之前的一篇文章里。

但是要注意 Specification 里的一段话

If the Java Virtual Machine ever attempts to load a class C during verification (§5.4.1) or resolution (§5.4.3) (but not initialization (§5.5)), and the class loader that is used to initiate loading of C throws an instance of ClassNotFoundException, then the Java Virtual Machine must throw an instance of NoClassDefFoundError whose cause is the instance of ClassNotFoundException.

大概是说如果在 verification 和 resolution 阶段去 load class C。这时 C 的 ClassLoader 抛出 ClassNotFoundException，JVM要抛出NoClassDefFoundError作为wrapper。这个也不知道为啥。。。下面加了一段这个

(A subtlety here is that recursive class loading to load superclasses is performed as part of resolution (§5.3.5, step 3). Therefore, a ClassNotFoundException that results from a class loader failing to load a superclass must be wrapped in a NoClassDefFoundError.)

创建数组类

The following steps are used to create the array class C denoted by N using class loader L. Class loader L may be either the bootstrap class loader or a user-defined class loader.
If L has already been recorded as an initiating loader of an array class with the same component type as N, that class is C, and no array class creation is necessary.
Otherwise, the following steps are performed to create C:

If the component type is a reference type, the algorithm of this section (§5.3) is applied recursively using class loader L in order to load and thereby create the component type of C.

The Java Virtual Machine creates a new array class with the indicated component type and number of dimensions.

If the component type is a reference type, C is marked as having been defined by the defining class loader of the component type. Otherwise, C is marked as having been defined by the bootstrap class loader.
In any case, the Java Virtual Machine then records that L is an initiating loader for C (§5.3.4).
If the component type is a reference type, the accessibility of the array class is determined by the accessibility of its component type. Otherwise, the accessibility of the array class is public.

[转]使用scroll实现Elasticsearch数据遍历和深度分页

from http://lxwei.github.io/posts/%E4%BD%BF%E7%94%A8scroll%E5%AE%9E%E7%8E%B0Elasticsearch%E6%95%B0%E6%8D%AE%E9%81%8D%E5%8E%86%E5%92%8C%E6%B7%B1%E5%BA%A6%E5%88%86%E9%A1%B5.html?f=tt&hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
作者：lxWei

背景

Elasticsearch 是一个实时的分布式搜索与分析引擎，被广泛用来做全文搜索、结构化搜索、分析。在使用过程中，有一些典型的使用场景，比如分页、遍历等。在使用关系型数据库中，我们被告知要注意甚至被明确禁止使用深度分页，同理，在 Elasticsearch 中，也应该尽量避免使用深度分页。这篇文章主要介绍 Elasticsearch 中使用分页的方式、Elasticsearch 搜索执行过程以及为什么深度分页应该被禁止，最后再介绍使用 scroll 的方式遍历数据。

Elasticsearch 搜索内部执行原理

一个最基本的 Elasticsearch 查询语句是这样的：

POST /my_index/my_type/_search
{
    "query": { "match_all": {}},
    "from": 100,
    "size":  10
}

上面的查询表示从搜索结果中取第100条开始的10条数据。下面讲解搜索过程时也以这个请求为例。

那么，这个查询语句在 Elasticsearch 集群内部是怎么执行的呢？为了方便描述，我们假设该 index 只有primary shards，没有 replica shards。

在 Elasticsearch 中，搜索一般包括两个阶段，query 和 fetch 阶段，可以简单的理解，query 阶段确定要取哪些doc，fetch 阶段取出具体的 doc。

Query 阶段

如上图所示，描述了一次搜索请求的 query 阶段。

Client 发送一次搜索请求，node1 接收到请求，然后，node1 创建一个大小为 from + size 的优先级队列用来存结果，我们管 node1 叫 coordinating node。
coordinating node将请求广播到涉及到的 shards，每个 shard 在内部执行搜索请求，然后，将结果存到内部的大小同样为 from + size 的优先级队列里，可以把优先级队列理解为一个包含 top N 结果的列表。
每个 shard 把暂存在自身优先级队列里的数据返回给 coordinating node，coordinating node 拿到各个 shards 返回的结果后对结果进行一次合并，产生一个全局的优先级队列，存到自身的优先级队列里。

在上面的例子中，coordinating node 拿到 (from + size) * 6 条数据，然后合并并排序后选择前面的 from + size 条数据存到优先级队列，以便 fetch 阶段使用。另外，各个分片返回给 coordinating node 的数据用于选出前 from + size 条数据，所以，只需要返回唯一标记 doc 的 _id 以及用于排序的 _score 即可，这样也可以保证返回的数据量足够小。

coordinating node 计算好自己的优先级队列后，query 阶段结束，进入 fetch 阶段。

Fetch 阶段

query 阶段知道了要取哪些数据，但是并没有取具体的数据，这就是 fetch 阶段要做的。

上图展示了 fetch 过程：

coordinating node 发送 GET 请求到相关shards。
shard 根据 doc 的 _id 取到数据详情，然后返回给 coordinating node。
coordinating node 返回数据给 Client。

coordinating node 的优先级队列里有 from + size 个 _doc _id，但是，在 fetch 阶段，并不需要取回所有数据，在上面的例子中，前100条数据是不需要取的，只需要取优先级队列里的第101到110条数据即可。

需要取的数据可能在不同分片，也可能在同一分片，coordinating node 使用 multi-get 来避免多次去同一分片取数据，从而提高性能。

深度分页的问题

Elasticsearch 的这种方式提供了分页的功能，同时，也有相应的限制。举个例子，一个索引，有10亿数据，分10个 shards，然后，一个搜索请求，from=1,000,000，size=100，这时候，会带来严重的性能问题：

CPU
内存
IO
网络带宽

CPU、内存和IO消耗容易理解，网络带宽问题稍难理解一点。在 query 阶段，每个shards需要返回 1,000,100 条数据给 coordinating node，而 coordinating node 需要接收 10 * 1,000,100 条数据，即使每条数据只有 _doc _id 和 _score，这数据量也很大了，而且，这才一个查询请求，那如果再乘以100呢？

在另一方面，我们意识到，这种深度分页的请求并不合理，因为我们是很少人为的看很后面的请求的，在很多的业务场景中，都直接限制分页，比如只能看前100页。

不过，这种深度分页确实存在，比如，被爬虫了，这个时候，直接干掉深度分页就好；又或者，业务上有遍历数据的需要，比如，有1千万粉丝的微信大V，要给所有粉丝群发消息，或者给某省粉丝群发，这时候就需要取得所有符合条件的粉丝，而最容易想到的就是利用 from + size 来实现，不过，这个是不现实的，这时，可以采用 Elasticsearch 提供的 scroll 方式来实现遍历。

利用 scroll 遍历数据

可以把 scroll 理解为关系型数据库里的 cursor，因此，scroll 并不适合用来做实时搜索，而更适用于后台批处理任务，比如群发。

可以把 scroll 分为初始化和遍历两步，初始化时将所有符合搜索条件的搜索结果缓存起来，可以想象成快照，在遍历时，从这个快照里取数据，也就是说，在初始化后对索引插入、删除、更新数据都不会影响遍历结果。

使用介绍

下面介绍下scroll的使用，可以通过 Elasticsearch 的 HTTP 接口做试验下，包括初始化和遍历两个部分。

初始化

POST ip:port/my_index/my_type/_search?scroll=1m
{
        "query": { "match_all": {}}
}

初始化时需要像普通 search 一样，指明 index 和 type (当然，search 是可以不指明 index 和 type 的)，然后，加上参数 scroll，表示暂存搜索结果的时间，其它就像一个普通的search请求一样。

初始化返回一个 _scroll_id，_scroll_id 用来下次取数据用。

遍历

POST /_search?scroll=1m
{
    "scroll_id":"XXXXXXXXXXXXXXXXXXXXXXX I am scroll id XXXXXXXXXXXXXXX"
}

这里的 scroll_id 即上一次遍历取回的 _scroll_id 或者是初始化返回的 _scroll_id，同样的，需要带 scroll 参数。重复这一步骤，直到返回的数据为空，即遍历完成。注意，每次都要传参数 scroll，刷新搜索结果的缓存时间。另外，不需要指定 index 和 type。

设置scroll的时候，需要使搜索结果缓存到下一次遍历完成，同时，也不能太长，毕竟空间有限。

Scroll-Scan

Elasticsearch 提供了 Scroll-Scan 方式进一步提高遍历性能。还是上面的例子，微信大V要给粉丝群发这种后台任务，是不需要关注顺序的，只要能遍历所有数据即可，这时候，就可以用Scroll-Scan。

Scroll-Scan 的遍历与普通 Scroll 一样，初始化存在一点差别。

POST ip:port/my_index/my_type/_search?search_type=scan&scroll=1m&size=50
{
        "query": { "match_all": {}}
}

需要指明参数：

search_type。赋值为scan，表示采用 Scroll-Scan 的方式遍历，同时告诉 Elasticsearch 搜索结果不需要排序。
scroll。同上，传时间。
size。与普通的 size 不同，这个 size 表示的是每个 shard 返回的 size 数，最终结果最大为 number_of_shards * size。

Scroll-Scan 方式与普通 scroll 有几点不同：

Scroll-Scan 结果没有排序，按 index 顺序返回，没有排序，可以提高取数据性能。
初始化时只返回 _scroll_id，没有具体的 hits 结果。
size 控制的是每个分片的返回的数据量而不是整个请求返回的数据量。

Java 实现

用 Java 举个例子。

初始化

try {
    response = esClient.prepareSearch(index)
            .setTypes(type)
            .setSearchType(SearchType.SCAN)
            .setQuery(query)
            .setScroll(new TimeValue(timeout))
            .setSize(size)
            .execute()
            .actionGet();
} catch (ElasticsearchException e) {
    // handle Exception
}

初始化返回 _scroll_id，然后，用 _scroll_id 去遍历，注意，上面的query是一个JSONObject，不过这里很多种实现方式，我这儿只是个例子。

遍历

    try {
        response = esClient.prepareSearchScroll(scrollId)
            .setScroll(new TimeValue(timeout))
            .execute()
            .actionGet();
    } catch (ElasticsearchException e) {
        // handle Exception
    }

总结

深度分页不管是关系型数据库还是Elasticsearch还是其他搜索引擎，都会带来巨大性能开销，特别是在分布式情况下。
有些问题可以考业务解决而不是靠技术解决，比如很多业务都对页码有限制，google 搜索，往后翻到一定页码就不行了。
Elasticsearch 提供的 Scroll 接口专门用来获取大量数据甚至全部数据，在顺序无关情况下，首推Scroll-Scan。
描述搜索过程时，为了简化描述，假设 index 没有备份，实际上，index 肯定会有备份，这时候，就涉及到选择 shard。

PS：Elasticsearch 各个版本可能有区别，但原理基本相同，本文包括文末的代码都基于Elasticsearch 1.3。

NIO of Java

[转] 深入理解 Spring 事务原理

from http://www.codeceo.com/article/spring-transactions.html

事务的基本原理

Spring事务的本质其实就是数据库对事务的支持，没有数据库的事务支持，spring是无法提供事务功能的。对于纯JDBC操作数据库，想要用到事务，可以按照以下步骤进行：

获取连接 Connection con = DriverManager.getConnection()
开启事务 con.setAutoCommit(true/false);
执行CRUD
提交事务/回滚事务 con.commit() / con.rollback();
关闭连接 conn.close();

使用Spring的事务管理功能后，我们可以不再写步骤 2 和 4 的代码，而是由Spirng 自动完成。 那么Spring是如何在我们书写的 CRUD 之前和之后开启事务和关闭事务的呢？解决这个问题，也就可以从整体上理解Spring的事务管理实现原理了。下面简单地介绍下，注解方式为例子

配置文件开启注解驱动，在相关的类和方法上通过注解@transactional标识。
spring 在启动的时候会去解析生成相关的bean，这时候会查看拥有相关注解的类和方法，并且为这些类和方法生成代理，并根据@transaction的相关参数进行相关配置注入，这样就在代理中为我们把相关的事务处理掉了（开启正常提交事务，异常回滚事务）。
真正的数据库层的事务提交和回滚是通过binlog或者redo log实现的。

Spring 事务的传播属性

所谓spring事务的传播属性，就是定义在存在多个事务同时存在的时候，spring应该如何处理这些事务的行为。这些属性在TransactionDefinition中定义，具体常量的解释见下表：

PROPAGATION_REQUIRED 支持当前事务，如果当前没有事务，就新建一个事务。这是最常见的选择，也是 Spring 默认的事务的传播。
PROPAGATION_REQUIRES_NEW 新建事务，如果当前存在事务，把当前事务挂起。新建的事务将和被挂起的事务没有任何关系，是两个独立的事务，外层事务失败回滚之后，不能回滚内层事务执行的结果，内层事务失败抛出异常，外层事务捕获，也可以不处理回滚操作
PROPAGATION_SUPPORTS 支持当前事务，如果当前没有事务，就以非事务方式执行。
PROPAGATION_MANDATORY 支持当前事务，如果当前没有事务，就抛出异常。
PROPAGATION_NOT_SUPPORTED 以非事务方式执行操作，如果当前存在事务，就把当前事务挂起。
PROPAGATION_NEVER 以非事务方式执行，如果当前存在事务，则抛出异常。
PROPAGATION_NESTED
如果一个活动的事务存在，则运行在一个嵌套的事务中。如果没有活动事务，则按REQUIRED属性执行。它使用了一个单独的事务，这个事务拥有多个可以回滚的保存点。内部事务的回滚不会对外部事务造成影响。它只对DataSourceTransactionManager事务管理器起效。

数据库隔离级别

隔离级别	隔离级别的值	导致的问题
Read-Uncommitted	0	导致脏读
Read-Committed	1	避免脏读，允许不可重复读和幻读
Repeatable-Read	2	避免脏读，不可重复读，允许幻读
Serializable	3	串行化读，事务只能一个一个执行，避免了脏读、不可重复读、幻读。执行效率慢，使用时慎重。

脏读：一事务对数据进行了增删改，但未提交，另一事务可以读取到未提交的数据。如果第一个事务这时候回滚了，那么第二个事务就读到了脏数据。
不可重复读：一个事务中发生了两次读操作，第一次读操作和第二次操作之间，另外一个事务对数据进行了修改，这时候两次读取的数据是不一致的。
幻读：第一个事务对一定范围的数据进行批量修改，第二个事务在这个范围增加一条数据，这时候第一个事务就会丢失对新增数据的修改。

总结：

隔离级别越高，越能保证数据的完整性和一致性，但是对并发性能的影响也越大。

大多数的数据库默认隔离级别为 Read Commited，比如 SqlServer、Oracle

少数数据库默认隔离级别为：Repeatable Read 比如： MySQL InnoDB

Spring中的隔离级别

ISOLATION_DEFAULT 这是个 PlatfromTransactionManager 默认的隔离级别，使用数据库默认的事务隔离级别。另外四个与 JDBC 的隔离级别相对应。
ISOLATION_READ_UNCOMMITTED 这是事务最低的隔离级别，它充许另外一个事务可以看到这个事务未提交的数据。这种隔离级别会产生脏读，不可重复读和幻像读。
ISOLATION_READ_COMMITTED 保证一个事务修改的数据提交后才能被另外一个事务读取。另外一个事务不能读取该事务未提交的数据。
ISOLATION_REPEATABLE_READ 这种事务隔离级别可以防止脏读，不可重复读。但是可能出现幻像读。
ISOLATION_SERIALIZABLE 这是花费最高代价但是最可靠的事务隔离级别。事务被处理为顺序执行。

事务的嵌套

通过上面的理论知识的铺垫，我们大致知道了数据库事务和spring事务的一些属性和特点，接下来我们通过分析一些嵌套事务的场景，来深入理解spring事务传播的机制。

假设外层事务 Service A 的 Method A() 调用内层Service B 的 Method B()

PROPAGATION_REQUIRED(spring 默认)

如果ServiceB.methodB() 的事务级别定义为 PROPAGATION_REQUIRED，那么执行 ServiceA.methodA() 的时候spring已经起了事务，这时调用 ServiceB.methodB()，ServiceB.methodB() 看到自己已经运行在 ServiceA.methodA() 的事务内部，就不再起新的事务。

假如 ServiceB.methodB() 运行的时候发现自己没有在事务中，他就会为自己分配一个事务。

这样，在 ServiceA.methodA() 或者在 ServiceB.methodB() 内的任何地方出现异常，事务都会被回滚。

PROPAGATION_REQUIRES_NEW

比如我们设计 ServiceA.methodA() 的事务级别为 PROPAGATION_REQUIRED，ServiceB.methodB() 的事务级别为 PROPAGATION_REQUIRES_NEW。

那么当执行到 ServiceB.methodB() 的时候，ServiceA.methodA() 所在的事务就会挂起，ServiceB.methodB() 会起一个新的事务，等待 ServiceB.methodB() 的事务完成以后，它才继续执行。

他与 PROPAGATION_REQUIRED 的事务区别在于事务的回滚程度了。因为 ServiceB.methodB() 是新起一个事务，那么就是存在两个不同的事务。如果 ServiceB.methodB() 已经提交，那么 ServiceA.methodA() 失败回滚，ServiceB.methodB() 是不会回滚的。如果 ServiceB.methodB() 失败回滚，如果他抛出的异常被 ServiceA.methodA() 捕获，ServiceA.methodA() 事务仍然可能提交(主要看B抛出的异常是不是A会回滚的异常)。

PROPAGATION_SUPPORTS

假设ServiceB.methodB() 的事务级别为 PROPAGATION_SUPPORTS，那么当执行到ServiceB.methodB()时，如果发现ServiceA.methodA()已经开启了一个事务，则加入当前的事务，如果发现ServiceA.methodA()没有开启事务，则自己也不开启事务。这种时候，内部方法的事务性完全依赖于最外层的事务。

PROPAGATION_NESTED

现在的情况就变得比较复杂了, ServiceB.methodB() 的事务属性被配置为 PROPAGATION_NESTED, 此时两者之间又将如何协作呢?  ServiceB#methodB 如果 rollback, 那么内部事务(即 ServiceB#methodB) 将回滚到它执行前的 SavePoint 而外部事务(即 ServiceA#methodA) 可以有以下两种处理方式:

a、捕获异常，执行异常分支逻辑


void methodA() { 
        try { 
            ServiceB.methodB(); 
        } catch (SomeException) { 
            // 执行其他业务, 如 ServiceC.methodC(); 
        } 
    }

这种方式也是嵌套事务最有价值的地方, 它起到了分支执行的效果, 如果 ServiceB.methodB 失败, 那么执行 ServiceC.methodC(), 而 ServiceB.methodB 已经回滚到它执行之前的 SavePoint, 所以不会产生脏数据(相当于此方法从未执行过), 这种特性可以用在某些特殊的业务中, 而 PROPAGATION_REQUIRED 和 PROPAGATION_REQUIRES_NEW 都没有办法做到这一点。

b、外部事务回滚/提交代码不做任何修改, 那么如果内部事务(ServiceB#methodB) rollback, 那么首先 ServiceB.methodB 回滚到它执行之前的 SavePoint(在任何情况下都会如此), 外部事务(即 ServiceA#methodA) 将根据具体的配置决定自己是 commit 还是 rollback

另外三种事务传播属性基本用不到，在此不做分析。

总结

对于项目中需要使用到事务的地方，我建议开发者还是使用spring的TransactionCallback接口来实现事务，不要盲目使用spring事务注解，如果一定要使用注解，那么一定要对spring事务的传播机制和隔离级别有个详细的了解，否则很可能发生意想不到的效果。

[译]PostFilter in Elasticsearch

PostFilter 也是 Elasticsearch 的一个很实用的功能。具体看看这篇文章是怎么写的吧。

post_filter 是在一个 search request 的最后面起作用的，也就是在 aggregation 的结果出来以后。那它有啥用呢？这个就要看下面的例子了。

假设你在卖衣服（shirts），然后有个顾客想买 color:red并且 brand:gucci 的。那么就有这样一段 query。

curl -XGET localhost:9200/shirts/_search -d '
{
  "query": {
    "bool": {
      "filter": [
        { "term": { "color": "red"   }},
        { "term": { "brand": "gucci" }}
      ]
    }
  }
}
'

然而，你又想给顾客展示不同的款式（model）的衣服都有多少，来作为一个展示入口。那么你会这么写：

curl -XGET localhost:9200/shirts/_search -d '
{
  "query": {
    "bool": {
      "filter": [
        { "term": { "color": "red"   }},
        { "term": { "brand": "gucci" }}
      ]
    }
  },
  "aggs": {
    "models": {
      "terms": { "field": "model" } 
    }
  }
}
'

但是如果想告诉用户别的颜色的衣服还有多少呢？之前的 query 显然不行，因为 filter 已经把别的颜色的衣服给滤掉了。这时就是 post_filter 发挥作用的时候了。

curl -XGET localhost:9200/shirts/_search -d '
{
  "query": {
    "bool": {
      "filter": {
        { "term": { "brand": "gucci" }} 
      }
    }
  },
  "aggs": {
    "colors": {
      "terms": { "field": "color" } 
    },
    "color_red": {
      "filter": {
        "term": { "color": "red" } 
      },
      "aggs": {
        "models": {
          "terms": { "field": "model" } 
        }
      }
    }
  },
  "post_filter": { 
    "term": { "color": "red" }
  }
}
'

Conclusion

这篇文章介绍了 post_filter 的用法，也就是当我们在 aggregation 里获得更宽泛的结果而在 search result 里需要展现更细致的结果时，可以使用 post_filter 来实现这种效果。

How to Avoid Brain-Split for Elasticsearch Cluster

这一篇算是 HOW TO AVOID THE SPLIT-BRAIN PROBLEM IN ELASTICSEARCH 这篇文章的笔记吧。试着介绍一下 ES 的 Brain-Split 和怎么来预防这个问题。

What is Brain Split?

首先考虑一下只有两个 ES Instance 的 Cluster。

Node1 是 Master，拥有 Primary Shard 0P。Node2 则是一个 Replica，拥有一个 Replica Shard 0R。

这个时候如果 Node1 和 Node2 之间没有了相应，（可能是因为网络异常，也可能是因为某个节点正在 Full-GC 而使得连接超时）。

那么两个节点的连接中断，但是它们都还活着，所以 Node1 是 Master 而 Node2 也认为自己是 Master（因为它相信只剩它自己了）。

这样的话集群就变成了两个节点都是 Master，而这就导致了 Inconsistency。比如一个 Index Request 发送给了 Node1，Node1 并不会把这个 request 发送给 Node2 而这就引起了两个节点的数据不一致。反之亦然。更为严重的是，这个错误对于 Client 来说是不可见的。因为 Index Request 和 Search Request 都不会出现错误。

How to Avoid Brain Split Problem

出现 Split Brain 问题的关键在于两个 Node 自己就可以将自己选举为 Master。因此我们需要规定只有集群里相应的节点大于一个阈值的时候才能进行选举。在config/elasticsearch.yml 文件里有一个参数 discovery.zen.minimum_master_nodes 可以用来设置那个阈值。通常这个值都设置为 N/2 + 1。N自然是集群里 ES 实例的个数。

另一个可以设置的参数是 discovery.zen.ping.timeout。也就是一个节点等待另一个无响应的节点多长时间才认为它是挂掉的。默认值是 3s。

Two Nodes Cluster?

设置 discovery.zen.minimum_master_nodes 就可以解决 Brain Split 的问题了，但是对于两个节点的 Cluster 来说意味着这个值要设为 2。在这个情形下当两个节点互相的连接中断时，Node1 和 Node2 都不会选举自己为 Master 而这就意味着 ES 的服务中断了。换言之，这可以解决 Brain Split 的问题但是却牺牲了可用性。因为当一个节点挂了时整个集群就停止工作了。

在这种情况之下，一个建议就是在集群里加入一个不存放数据的节点（By setting node.data to false ）。这个节点默认会被选举为 Master。此时就可以将 discovery.zen.minimum_master_nodes 设置为 2了。

Conclusion

这篇文章先介绍了为什么 ES 会出现 Brain Split，然后给出了一种解决方案，就是只有多数派存活时才会进行选举。最后讨论了当集群里只有两个节点时的解决方案。

原文还提到了即使是设置了那个阈值，也会有 Brain Split 存在。具体看这个 Issue。但是现在这个 Issue 已经被关掉了。我还要具体看看为什么。

liangshang / liangshang.github.com Goto Github PK

liangshang.github.com's People

Contributors

Stargazers

Watchers

Forkers

liangshang.github.com's Issues

"Run-time" Constant Pool vs Constant Pool

Run-time Constant Pool and Resolution

An Example

Multi-Rescores

Conclusion

Binding Native Method Implementations

Java Virtual Machine Exists

What is ClassLoader

How ClassLoader works in Java

Delegation Principle

Visibility Principle

Uniqueness Principle

ClassLoader 能用来做啥？

SimHash 和传统 Hash 函数的区别

SimHash 算法**

SimHash 流程实现

SimHash 签名距离计算

SimHash 的存储和索引

SimHash存储和索引

参考内容

背景

LATERAL VIEW Syntax

LATERAL VIEW Explain

OUTER LATERAL VIEW

Reference

一个 类/接口 的初始化仅在以下的情况下发生

初始化时要满足的条件

多线程环境中进行类的初始化

初始化过程中的优化

Verification

Preparation

Resolution

Access Control

Overriding

Verification

Preparation

Resolution

Access Control

Overriding

摘要

Introduction

Requirements

功能需求

性能需求

Design and Implementation

sync state

Blocking

Queues

移位运算

数据库事务的隔离级别

ACID

行锁和表锁

两段锁协议

乐观锁、悲观锁和MVCC

ACID 的实现

The Problem

相关性打分

ES Search Types

Query Then Fetch

DFS Query Then Fetch

结论

非阻塞的计数器

非阻塞堆栈

性能考虑

非阻塞的链表

幕后的非阻塞算法

结束语

Why Still Split Brain?

Follow-up

Zen Discovery

Ping

Unicast

Master Election

一个类/接口的初始化仅在以下的情况下发生

创建数组类