Laboratory structure

• Every instance is a watcher, when event be triggered
  process method will be callback.

  public class SyncPrimitive implements Watcher

• Properties

  1 2 3 4 5 6

  // share zk client static ZooKeeper zk = null; // share lock mointor static Integer mutex; // instance zk path String root;

• Constructor

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  SyncPrimitive(String address) { if(zk == null){ try { System.out.println("Starting ZK:"); zk = new ZooKeeper(address, 3000, this); mutex = new Integer(-1); System.out.println("Finished starting ZK: " + zk); } catch (IOException e) { System.out.println(e.toString()); zk = null; } } // else mutex = new Integer(-1); }

  1. if the common zk client not exists, create one
  2. create the lock monitor by the way
  3. if not init the propertiy mutex is 0.

• Implements abstract method

1
2
3
4
5

synchronized public void process(WatchedEvent event) {
    synchronized (mutex) {
        mutex.notify();
    }
}

If the thread have monitor, call one another.
If not, wait for monitor mutex unlock.

1
2
3
4
5

public class HelloWorld {
   public static void main(String[] args) {
     System.out.println("hello world");
   }
}

invokevirtual
$ javap -c HelloWorld

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Compiled from "HelloWorld.java"
public class HelloWorld {
  public HelloWorld();
    Code:
       0: aload_0
       // Method java/lang/Object."<init>":()V
       1: invokespecial #1
       4: return

  public static void main(java.lang.String[]);
    Code:
       // Field java/lang/System.out:Ljava/io/PrintStream;
       0: getstatic     #2
       // String hello world
       3: ldc           #3
       // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       5: invokevirtual #4
       8: return
}

The property out in System is a packaged type PrintStream.
There is a BufferedOutputStream inside PrintStream.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public final class System {
    ...
    public final static PrintStream out = null;
    ...
    private static native void setOut0(PrintStream out);
    ...
    private static void initializeSystemClass() {
      ...
      FileOutputStream fdOut = new FileOutputStream(FileDescriptor.out);
      ...
      setOut0(newPrintStream(fdOut, props.getProperty("sun.stdout.encoding")));
      ...
    }
}

The init method called after thread initialization, initialize the system class.

1
2
3
4
5
6
7
8

private static PrintStream newPrintStream(FileOutputStream fos, String enc) {
   if (enc != null) {
        try {
            return new PrintStream(new BufferedOutputStream(fos, 128), true, enc);
        } catch (UnsupportedEncodingException uee) {}
    }
    return new PrintStream(new BufferedOutputStream(fos, 128), true);
}

package buffer function into out. base on encoding, create output stream object.

1
2
3
4
5
6
7
8
9

JNIEXPORT void JNICALL
Java_java_lang_System_setOut0(JNIEnv *env, jclass cla, jobject stream)
{
    jfieldID fid =
        (*env)->GetStaticFieldID(env,cla,"out","Ljava/io/PrintStream;");
    if (fid == 0)
        return;
    (*env)->SetStaticObjectField(env,cla,fid,stream);
}

• The native method setOut0 will call this c function.

• fid the member of System the out‘s id.

• "Ljava/io/PrintStream;" mean java.io.PrintStream object

SetStaticObjectField define here.

1
2

void (JNICALL *SetStaticObjectField)
      (JNIEnv *env, jclass clazz, jfieldID fieldID, jobject value);

Frames

Local Variables

Each frame contains an array of variables known as its local variables.

• one can hold
  >
  boolean, byte, char, short, int,
  float, reference, returnAddress

• a pair can hold long or double

JVM uses local variables to pass parameters on method invocation.

On instance method invocation, local variable 0 is always used to pass
a reference to instance it’self(this).

Operand Stacks

Each frame contains a last-in-first-out (LIFO) stack known as its operand stack.

Used to push or pop constant or values from variable or method.

Values from the operand stack must be operated upon in ways appropriate to their types.

These restrictions on operand stack manipulation are enforced through class file verification.

Dynamic Linking

Each frame contains a reference to the run-time constant pool for
the type of the current method to support dynamic linking of the method code.

invoke InvocationHandler in java ?

Used to reduce the invasive of the code linked code,
keep current code shape and solid.

Dynamic linking translates these symbolic method references into concrete method references.

Normal Method Invocation Completion

A method invocation completes normally if
that invocation does not cause an exception to be thrown.

The current frame use break characteristic to restore the state of the invoker
for the program counter of the invoker appropriately incremented to skip past
the method invocation instruction(PC Register?).

Abrupt Method Invocation Completion

A method invocation completes abruptly if execution of a JVM
instruction within the method causes the JVM to throw an
exception, and that exception is not handled within the method.

Execution of an athrow instruction also causes an exception to
be explicitly thrown and, if the exception is not caught by the
current method, results in abrupt method invocation completion.

A method invocation that completes abruptly never returns a value to its invoker.

Run-Time Data Areas

The pc Register

JVM can support many thread run at once.
Each JVM thread has it’s own pc register.

At any point,thread executing the code of a single method ,
called the current method for that thread.

If the method is a native method, pc register is undefined,
else the pc register contains the address of JVM instruction current being executed.

It is wide enough to hold a returnAddress or a native pointer on the specific platform.

Java Virtual Machine Stacks

Each Java Virtual Machine thread has a private JVM stack

A JVM stack stores frames, frames may be heap allocated.

• Requires a larger JVM stack than is permitted
  StackOverflowError in infinite recursion this error happen.

• Stacks dynamically expanded, and expansion is attempted but
  insufficient memory can be made available to effect the expansion.
  OutOfMemoryError in fames too many? in stack this error may happen.

Heap

The heap is the run-time data area, it’s a ‘public area’.
GC be appointed to manage this area.

OutOfMemoryError when frame need memory size over the maximum heap size.

Method Area

Method Area is a ‘public area’ as well.

It stores

1. per-class structures such as the run-time constant pool
2. field and method data
3. the code for methods and constructors, including
   the special methods (§2.9) used in class and instance initialization
   and interface initialization.

Accturally it is the origin class library of all programes in JVM.

OutOfMemoryError expansion/initialization is attempted
but insufficient memory can be made available

Run-Time Constant Pool

Each run-time constant pool is allocated from the JVM’s method area.

The run-time constant pool serves a function similar to
that of a symbol table for a programming language

OutOfMemoryError expansion/initialization is attempted
but insufficient memory can be made available

Native Method Stacks

JVM may use conventional stacks,
colloquially called C stacks to support native method.

Also be used by the implementation of an interpreter for the JVM’s
instruction set in a language such as C.

If JVM rely on conventional stack, it need not supply native method stacks.

If supplied, native method stacks are
typically allocated per thread when each thread is created.

• StackOverflowError thread requires a larger native method stack than is permitted
• OutOfMemoryError expansion/initialization is attempted
  but insufficient memory can be made available

NoClassDefFoundError

When JavaEE load big quantity package in develop environment,
mantain dependency will become hard.
Especially JavaEE have alot of ClassLoader now.

When developing in IDE, package can be found, but can’t found class in deploy status.

1
2
3
4
5
6
7

@WebServlet(name = "NoClassDefFoundErrorServlet", urlPatterns = "/noClassDefFoundError.do")
public class NoClassDefFoundErrorServlet extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws IOException {
        resp.getWriter().println(TestCase.class.toString());
    }
}

When TestCase.class from junit package, it’s scope is provider.
Junit package will not be depolyed,
so loader can’t find class in WEB-INF/lib.

NoSuchMethodError

This Error mean project included package version wrong.
The resource code use the high version package in IDE,
but package low level package in deploy environment.

Use -verbose:class to judge which version package jvm loaded.

ClassCastException

When more than one class loader loaded same class,
and use them to do operation, this problem may happen.
Because delegate model is different.

when in tradition delegate model this problem will not happen,
in JavaEE environment, module load it’s self resource first.
Although direct point outside resource, but use it’s parent loader’s resource first.

In JVM, how make sure a implement is the class’s implement?
JVM find a implement by ClassLoader + class full name.
class be define in a data structure named SystemDictionary.
This structure accept a ClassLoader and a name as parameters,
and return a class’s implement in call.

LinkageError

Different ClassLoader’s class, the method be overrided.
LinkageError is essentially same with LinkageError.

IllegalAccessError

The implement has no privilege to access method or field.
When class be loaded in a Unanticipated package, this problem happens

Summary

Inheritance system

When JVM start, bookstrap class loader will be loaded into java core.
like class in rt.jar.bookstrap is other ClassLoader’s parent,
it is the only loader has no parent.

Then the extension class loader, it’s parent is bookstrap,
it used to load class from java’s environment path java.ext.dir.

Third the most important class loader, the system classpath
class loader, developer’s self define class.
It’s parent is extension, it load class from
java’s environment path java.class.path.
Path can be set in -classpath parameter in command.

Tips

The system is not Inheritance but Delegation
Most loader will find resource in it’s parents, if not find in local.
Actually it ensure the high level loader’s class
can be assign with lower level loader’s type.

The motivation of Delegation is avoid load same class multi times.
When in 1995, java be used in Applet.
At that time the network bandwidth has priority, so program load class
when class be used then load it. Model is load parent first.

But in this time java show it’s power in server part.
Server need loader follow reverse delegation priciple,
to load local class first, if can’t load class in parent.

JavaEE Delegation model

Tomcat class load sequence(delegation model)

1. Bookstrap @rt.jar
2. Extension @lib/ext
3. System @%catalina_home%/bin/bootstrap.jar
4. Common @%catalina_home%/lib
5. Webapp @WEB-INF/lib

In tomcat default model,
try to load class in Bootstrap and Extension first.
If can’t load, try to load class in Webapp
If still can’t load, load in Common.

In Ali’s tomcat, it is in delegate model, so parent has priority.
So use Common loader first, then Webapp loader.

ip2region - 最自由的ip地址查询库，ip到地区的映射库，提供Binary,B树和纯内存三种查询算法，妈妈再也不用担心我的ip地址定位。

1. 99.9%准确率，定时更新：

数据聚合了一些知名ip到地名查询提供商的数据，这些是他们官方的的准确率，经测试着实比纯真啥的准确多了。

每次聚合一下数据需要1-2天，会不定时更新。

2. 标准化的数据格式：

每条ip数据段都固定了格式：城市Id|国家|区域|省份|城市|ISP

只有中国的数据精确到了城市，其他国家只能定位到国家，后前的选项全部是0，已经包含了全部你能查到的大大小小的国家。
（请忽略前面的城市Id，个人项目需求）

3. 体积小：

生成的数据库文件ip2region.db只有1.5M（1.2版本前是3.5M）

4. 多查询客户端的支持，0.0x毫秒级别的查询

已经集成的客户端有：java, php, c, python，nodejs，php扩展(支持linux, php5, php7版本已支持)，golang。

提供了两种查询算法，响应时间如下：
客户端/binary算法/b-tree算法/Memory算法：
java/0.x毫秒/0.x毫秒/0.1x毫秒 (使用RandomAccessFile)
php/0.x毫秒/0.1x毫秒/0.1x毫秒
c/0.0x毫秒/0.0x毫秒/0.00x毫秒(b-tree算法基本稳定在0.02x毫秒级别)
python/0.x毫秒/0.1x毫秒/未知

任何客户端b-tree都比binary算法快，当然Memory算法固然是最快的！

5. 测试程序：
java:

cd binding/java
ant all
java -jar ip2region-{version}.jar ./data/ip2region.db

php:

php binding/php/testSearcher ./data/ip2region.db

c:

cd binding/c/
gcc -g -O2 testSearcher.c ip2region.c
./a.out ../../data/ip2region.db

python:

python binding/python/testSearcher ./data/ip2region.db

均会看到如下界面：

initializing  B-tree ...
+----------------------------------+
| ip2region test script            |
| Author: chenxin619315@gmail.com  |
| Type 'quit' to exit program      |
+----------------------------------+
p2region>> 101.105.35.57
2163|中国|华南|广东省|深圳市|鹏博士 in 0.02295 millseconds

输入ip地址开始测试，第一次会稍微有点慢，在运行命令后面接入binary,memory来尝试其他算法，建议使用b-tree算法，速度和并发需求的可以使用memory算法。

具体集成请参考不同客户端的测试源码。

6. 如何生成ip2region.db文件

从ip2region 1.2.2版本开始里面提交了一个dbMaker-{version}.jar的可以执行jar文件，用它来完成这个工作：

• 1, 确保你安装好了java环境（不玩Java的童鞋就自己谷歌找找拉，临时用一用，几分钟的事情）
• 2, cd到ip2region的根目录，然后运行如下命令：

1
2
3
4
5

java -jar dbMaker-{version}.jar -src 文本数据文件 -region 地域csv文件 [-dst 生成的ip2region.db文件的目录]

# 文本数据文件：db文件的原始文本数据文件路径，自带的ip2region.db文件就是/data/ip.merge.txt生成而来的，你可以换成自己的或者更改/data/ip.merge.txt重新生成
# 地域csv文件：该文件目的是方便配置ip2region进行数据关系的存储，得到的数据包含一个city_id，这个直接使用/data/origin/global_region.csv文件即可
# ip2region.db文件的目录：是可选参数，没有指定的话会在当前目录生成一份./data/ip2region.db文件

• 3, 获取生成的ip2region.db文件覆盖原来的ip2region.db文件即可
• 4, 默认的ip2region.db文件生成命令:

1
2
3
4

cd ip2region项目根目录
java -jar dbMaker-1.2.2.jar -src ./data/ip.merge.txt ./data/global_region.csv

# 会看到一大片的输出

• 5, 数据库文件的结构和原理请阅读 @冬芽 的blog：“ip2region数据库文件的结构和原理”

一. 源数据如何存储到ip2region.db

1. 源数据来源与结构

ip2region 的ip数据来自纯真和淘宝的ip数据库，每次抓取完成之后会生成 ip.merge.txt， 再通过程序根据这个源文件生成ip2region.db 文件。

ip.merge.txt 中每一行对应一条完整记录，每一条记录由ip段和数据组成，格式如下：

0.0.0.0|0.255.255.255|未分配或者内网IP|0|0|0|0
1.0.0.0|1.0.0.255|澳大利亚|0|0|0|0
1.0.1.0|1.0.3.255|中国|华东|福建省|福州市|电信
1.0.4.0|1.0.7.255|澳大利亚|0|0|0|0
1.0.8.0|1.0.15.255|中国|华南|广东省|广州市|电信
1.0.16.0|1.0.31.255|日本|0|0|0|0
1.0.32.0|1.0.63.255|中国|华南|广东省|广州市|电信
1.0.64.0|1.0.127.255|日本|0|0|0|0
1.0.128.0|1.0.255.255|泰国|0|0|0|0
1.1.0.0|1.1.0.255|中国|华东|福建省|福州市|电信
从左到右分别表示： 起始ip,结束ip,国家，区域，省份，市，运营商。无数据区域默认为0。

最新的ip.merge.txt 有122474条记录，并且根据开始ip地址升序排列。

2. 如何生成ip2region.db

给定一个ip，如何快速从ip.merge.txt中找到该ip所属记录？最简单的办法就是顺序遍历，当该ip在某条记录起始和结束ip之间时，即命中。

这是低效的做法，如何提高查询性能？用过mysql和其他数据库的的都知道，使用索引。所以ip2region.db使用了内建索引，直接将性能提升到0.0x毫秒级别。

根据ip.merge.txt，为所有数据生成一份索引，并和数据地址组成一个索引项(index block), 然后按起始ip升序排列组成索引，并存储到数据文件的末尾，最终生成的ip2region.db文件大小只有3.5M。

此时的数据库文件中的每一条索引都指向一条对应的数据，也就是说如

|中国|华南|广东省|广州市|电信
这样的数据在文件中被重复存储了很多次，再经过去重优化之后，ip2region.db只有1.5M了，此时把数据库文件全部读取到内存再查找都是非常可行的。

二. ip2region.db 结构

生成 ip2region.db 的时候，首先会在首部预留 8 bytes 的SUPER BLOCK 和 8k 的 HEADER INDEX。

再根据ip.merge.txt，依据每一条记录的起始ip, 结束ip和数据，生成一个index block， 前四个字节存储起始ip, 中间四个字节存储结束ip, 后四个字节存储已经计算出的数据地址，并暂存到INDEX区。

当 INDEX 索引区和 DATA 数据区确定下来之后，再把 INDEX 的起始位置存储到 SUPER BLOCK 的前四个字节，结束位置存储到 SUPER BLOCK 的后四个字节。

再把 INDEX 分成大小为 4K 的索引分区，把每个分区起始位置的索引的起始ip和该索引的位置存入一个 header index block, 组成 HEADER INDEX 区域, 最后写入ip2region.db。

• SUPER BLOCK

用来保存 INDEX 的起始地址和结束地址，first index ptr 指向INDEX起始位置的index block， last index ptr 指向最后一个index block的地址。这样查询的时候直接读取superblock 8个字节，就能快速获取 INDEX 索引区域的地址。

• HEADER INDEX

HEADER INDEX 区是对 INDEX 区的二级索引， INDEX总长度除以 4K 就是 HEADER INDEX 的实际索引数。

该区域长度为8k, 由 8 bytes 的 header index block 组成。

header index block 前四个字节存储每个4K分区起始位置的index block 的起始ip值，后四个字节指向该index block的地址。

把HEADER INDEX 区定义为8k，可以通过一次磁盘读取读取整个HEADER INDEX 区，然后在内存中进行查询，查询的结果可以确定该ip在INDEX区的某个4k分区内，然后再根据地址一次读取4k index 到内存，再在内存中查询，从而减少磁盘读取的次数。

• DATA

保存的数据，数据格式如下：

2163|中国|华南|广东省|深圳市|鹏博士
分别表示 城市ip,国家，区域，省份，城市，运营商

• INDEX

索引区域，索引元素为 index block (12 字节)， 分成三个部分，起始ip, 结束ip, 数据信息, 每一条 index block 对应 ip.merge.txt 中的一条记录。

数据信息：前一个字节保存数据长度， 后三个字节保存数据地址（DATA中）。

每个index block 表示一个ip段的索引。当指定ip 在某个 index block 的起始ip和结束ip中间，即表示命中索引。

再通过 index block 中的数据地址和数据长度，就能从ip2region.db读取对应的地址。

三. 搜索方法

binary搜索

• 把ip值通过ip2long方法转为长整型
• 通过 SUPER BLOCK 拿到INDEX的起始位置和结束位置
• 相减+1得出index block 总数
• 采用二分法直接求解，比较 index block 和当前ip的大小，即可找到该ip属于的 index block
• 拿到该 index block 的后面四个字节， 分别得到数据长度和数据地址
• 从数据地址读取拿到的所得长度的字节，即是搜索结果

b-tree 搜索

• 把ip值通过ip2long 转为长整型
• 使用二分法在 HEADER INDEX 中搜索，比较得到对应的 header index block
• header index block 指向 INDEX 中的一个 4K 分区，所以直接把搜索范围降低到 4K
• 采用二分法在获取到的 4K 分区搜索，得到对应的 index block
• 拿到该 index block 的后面四个字节， 分别得到数据长度和数据地址
• 从数据地址读取拿到的所得长度的字节，即是搜索结果

Class

1
2
3
4
5
6
7
8
9
10
11
12
13

public abstract class ClassLoader {
  ...
  protected final Class<?> defineClass(String name, byte[] b, int off, int len)
  ...
  public Class<?> loadClass(String name) {...}
  ...
  public final ClassLoader getParent() {...}
  ...
  public URL getResource(String name) {...}
  ...
  public Enumeration<URL> getResources(String name) {...}
  ...
}

• Most important method is loadClass(arg) ,
  it accept a class’s full name, and return it’s instance.

• defineClass(arg) accept a byte array, turn it into instance.
  Usually, it load a file from disk, then pass file byte into JVM.
  Instantiate Class into a instance through JVM’s(native method) define to Class.

• getResource() and getResources search URL from repository.
  They have agent mechanism as well as loadClass, like:
  defineClass(getResource(name).getBytes())

Code

Because Java late binding and explain character,
Classes’ will be load when it needed like
static method/ construct method or direct allocate in field.

1
2
3
4
5
6

public class A {
  public void xxx() {
    B b = new B();
    b.xxoo();
  }
}

They are same when B have default constructor.

1
2
3
4

B b = new B();

B b = Class.forName("B", false,
    A.class.getClassLoader()).newInstance();

Control port in linux

1
2
3
4
5
6
7
8
9

# status
netstat -anp

# close
iptables -A INPUT -p tcp --drop 8080 -j DROP
iptables -A OUTPUT -p tcp --dport 8080 -j DROP

# open
iptables -A INPUT -ptcp --dport 8080 -j ACCEPT

Control port in windows

1
2
3
4
5
6
7
8

# status
netstat -ano

# find program name
tasklist|findstr "3624"

# kill it
taskkill /f /t /im Dandelion.exe

1. open control-panel -> manage-tool open local safety policy
   choose Ip safety policy to create a new ip policy.

2. remove use add guide, click add new rule, then add a new filter.

3. edit filter properties, src is any ip address, target is my id address.
   in protocol tab, protocol type choose TCP, to this port input 135.

4. repeat UDP port in [135, 139, 445]
   TCP port in [135, 137, 139, 445, 593, 1025, 2745, 3127, 6129, 3389]
5. in new rule dialog, the filter operation choose forbidden.
6. confirm new rule, in ip policy right click rule choose dispatch.
7. restart computer.

https://zookeeper.apache.org/doc/r3.5.2-alpha/javaExample.html

Executor

1
2
3

public class Executor
    implements Watcher, Runnable,
        DataMonitor.DataMonitorListener

Declare class first, implements Zookeeper Watcher
, thread Runnable and DataMonitor’s inner interface Listener.

1
2
3
4
5

try {
    new Executor(hostPort, znode, filename, exec).run();
} catch (Exception e) {
    e.printStackTrace();
}

Arguments sequence is

1. host:port
2. znode path
3. process output file path
4. process command array

1
2
3
4
5
6
7

public Executor(String hostPort, String znode, String filename,
            String exec[]) throws KeeperException, IOException {
    this.filename = filename;
    this.exec = exec;
    zk = new ZooKeeper(hostPort, 3000, this);
    dm = new DataMonitor(zk, znode, null, this);
}

In constuctor, Executor use it’s Object self as a parameter.
ZooKeeper need a Watch in third parameter, it triger
Executor’s implements to triger Monitor again.

DataMonitor need a DataMonitorListener to know what
operation need to notify when event happen.

1
2
3
4
5
6
7
8
9
10

public void run() {
    try {
        synchronized (this) {
            while (!dm.dead) {
                wait();
            }
        }
    } catch (InterruptedException e) {
    }
}

It’s Runnable implements.
When Executor be created and run in main, it check monitor’s status.
When first initiated, monitor dead should in false, main thread will wait for zookeeper client to wake it up.

1
2
3
4
5
6
7
8

try {
    System.out.println("Starting child");
    child = Runtime.getRuntime().exec(exec);
    new StreamWriter(child.getInputStream(), System.out);
    new StreamWriter(child.getErrorStream(), System.err);
} catch (IOException e) {
    e.printStackTrace();
}

local process executed here, it’s output will be write into file path.

feedbackTarget.sh

1
2
3
4
5
6
7
8

#!/bin/bash
while true
do
	echo "hello zookeeper" >&1
	echo "hello error" >&2
	sleep 3s
done
exit 0

192.168.3.11:2181 /key ./example/leon sh ./example/feedbackTarget.sh

DataMonitor

1

public class DataMonitor implements Watcher, StatCallback

implements Watcher as a watcher, but not use as watcher.
implements StatCallback, zookeeper client should callback this monitor when node status changed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public void process(WatchedEvent event) {
    String path = event.getPath();
    if (event.getType() == Event.EventType.None) {
        switch (event.getState()) {
        case SyncConnected:
            break;
        case Expired:
            dead = true;
            listener.closing(KeeperException.Code.SessionExpired);
            break;
        }
    } else {
        if (path != null && path.equals(znode)) {
            zk.exists(znode, true, this, null);
        }
    }
    if (chainedWatcher != null) {
        chainedWatcher.process(event);
    }
}

Monitor feedback what it seen to the listener,
and register the next chainedWatcher if exitst.

1
2
3
4
5
6

public void processResult(int rc, String path, Object ctx, Stat stat) {
  ...
  b = zk.getData(znode, false, null);
  ...
  listener.exists(b);
}

Put zookeeper client’s callback to executor.