ConcurrentLinkedQueue的实现具体分析

发表于 2017-11-20

##引言## 在并发编程中我们有时候需要使用线程安全的队列。如果我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现，而非阻塞的实现方式则可以使用循环CAS的方式来实现，本文让我们一起来研究下Doug Lea是如何使用非阻塞的方式来实现线程安全队列ConcurrentLinkedQueue的，相信从大师身上我们能学到不少并发编程的技巧。 ##ConcurrentLinkedQueue的介绍##
ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。它采用了“wait－free”算法来实现，该算法在Michael & Scott算法上进行了一些修改。 ##ConcurrentLinkedQueue的结构## 我们通过ConcurrentLinkedQueue的类图来分析一下它的结构。在此输入图片描述 ConcurrentLinkedQueue由head节点和tair节点组成，每个节点（Node）由节点元素（item）和指向下一个节点的引用(next)组成，节点与节点之间就是通过这个next关联起来，从而组成一张链表结构的队列。默认情况下head节点存储的元素为空，tair节点等于head节点。

1	复制代码private transient volatile Node<e> tail = head;

##入队列## 入队列就是将入队节点添加到队列的尾部。为了方便理解入队时队列的变化，以及head节点和tair节点的变化，每添加一个节点我就做了一个队列的快照图。在此输入图片描述

第一步添加元素1：队列更新head节点的next节点为元素1节点。又因为tail节点默认情况下等于head节点，所以它们的next节点都指向元素1节点。 第二步添加元素2：队列首先设置元素1节点的next节点为元素2节点，然后更新tail节点指向元素2节点。 第三步添加元素3：设置tail节点的next节点为元素3节点。 第四步添加元素4：设置元素3的next节点为元素4节点，然后将tail节点指向元素4节点。

通过debug入队过程并观察head节点和tail节点的变化，发现入队主要做两件事情，第一是将入队节点设置成当前队列尾节点的下一个节点。第二是更新tail节点，如果tail节点的next节点不为空，则将入队节点设置成tail节点，如果tail节点的next节点为空，则将入队节点设置成tail的next节点，所以tail节点不总是尾节点，理解这一点对于我们研究源码会非常有帮助。

上面的分析让我们从单线程入队的角度来理解入队过程，但是多个线程同时进行入队情况就变得更加复杂，因为可能会出现其他线程插队的情况。如果有一个线程正在入队，那么它必须先获取尾节点，然后设置尾节点的下一个节点为入队节点，但这时可能有另外一个线程插队了，那么队列的尾节点就会发生变化，这时当前线程要暂停入队操作，然后重新获取尾节点。让我们再通过源码来详细分析下它是如何使用CAS算法来入队的。

复制代码public boolean offer(E e) {
    if (e == null) throw new NullPointerException();

    //入队前，创建一个入队节点
    Node<E> n = new Node<E>(e);

    retry:
        //死循环，入队不成功反复入队。
        for (;;) {
            //创建一个指向tail节点的引用
            Node<E> t = tail;
            //p用来表示队列的尾节点，默认情况下等于tail节点。
            Node<E> p = t;

            for (int hops = 0; ; hops++) {
                //获得p节点的下一个节点。
                Node<E> next = succ(p);
                //next节点不为空，说明p不是尾节点，需要更新p后在将它指向next节点
                if (next != null) {
                    //循环了两次及其以上，并且当前节点还是不等于尾节点
                    if (hops > HOPS && t != tail)
                        continue retry;
                    p = next;
                }

                //如果p是尾节点，则设置p节点的next节点为入队节点。
                else if (p.casNext(null, n)) {
                    //如果tail节点有大于等于1个next节点，则将入队节点设置成tair节点，更新失败了也没关系，因为失败了表示有其他线程成功更新了tair节点
                    if (hops >= HOPS)
                        casTail(t, n); // 更新tail节点，允许失败
                    return true;
                }

                // p有next节点,表示p的next节点是尾节点，则重新设置p节点
                else {
                    p = succ(p);
                }
            }
        }
}

从源代码角度来看整个入队过程主要做二件事情。第一是定位出尾节点，第二是使用CAS算法能将入队节点设置成尾节点的next节点，如不成功则重试。

第一步定位尾节点。tail节点并不总是尾节点，所以每次入队都必须先通过tail节点来找到尾节点，尾节点可能就是tail节点，也可能是tail节点的next节点。代码中循环体中的第一个if就是判断tail是否有next节点，有则表示next节点可能是尾节点。获取tail节点的next节点需要注意的是p节点等于p的next节点的情况，只有一种可能就是p节点和p的next节点都等于空，表示这个队列刚初始化，正准备添加第一次节点，所以需要返回head节点。获取p节点的next节点代码如下：

复制代码final Node<E> succ(Node<E> p) {
    Node<E> next = p.getNext();
    return (p == next) ? head : next;
}

第二步设置入队节点为尾节点。p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点，p如果是null表示p是当前队列的尾节点，如果不为null表示有其他线程更新了尾节点，则需要重新获取当前队列的尾节点。

hops的设计意图。上面分析过对于先进先出的队列入队所要做的事情就是将入队节点设置成尾节点，doug lea写的代码和逻辑还是稍微有点复杂。那么我用以下方式来实现行不行？

复制代码public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    Node</e><e> n = new Node</e><e>(e);
    for (;;) {
        Node</e><e> t = tail;
        if (t.casNext(null, n) && casTail(t, n)) {
            return true;
        }
    }
}

让tail节点永远作为队列的尾节点，这样实现代码量非常少，而且逻辑非常清楚和易懂。但是这么做有个缺点就是每次都需要使用循环CAS更新tail节点。如果能减少CAS更新tail节点的次数，就能提高入队的效率，所以doug lea使用hops变量来控制并减少tail节点的更新频率，并不是每次节点入队后都将 tail节点更新成尾节点，而是当 tail节点和尾节点的距离大于等于常量HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距离越长使用CAS更新tail节点的次数就会越少，但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长，因为循环体需要多循环一次来定位出尾节点，但是这样仍然能提高入队的效率，因为从本质上来看它通过增加对volatile变量的读操作来减少了对volatile变量的写操作，而对volatile变量的写操作开销要远远大于读操作，所以入队效率会有所提升。

1	复制代码private static final int HOPS = 1;

还有一点需要注意的是入队方法永远返回true，所以不要通过返回值判断入队是否成功。 ##出队列## 出队列的就是从队列里返回一个节点元素，并清空该节点对元素的引用。让我们通过每个节点出队的快照来观察下head节点的变化。在此输入图片描述

从上图可知，并不是每次出队时都更新head节点，当head节点里有元素时，直接弹出head节点里的元素，而不会更新head节点。只有当head节点里没有元素时，出队操作才会更新head节点。这种做法也是通过hops变量来减少使用CAS更新head节点的消耗，从而提高出队效率。让我们再通过源码来深入分析下出队过程。

复制代码public E poll() {
    Node<E> h = head;

    // p表示头节点，需要出队的节点
    Node<E> p = h;
    for (int hops = 0;; hops++) {
        // 获取p节点的元素
        E item = p.getItem();

        // 如果p节点的元素不为空，使用CAS设置p节点引用的元素为null,如果成功则返回p节点的元素。
        if (item != null && p.casItem(item, null)) {
            if (hops >= HOPS) {
                // 将p节点下一个节点设置成head节点
                Node<E> q = p.getNext();

                updateHead(h, (q != null) ? q : p);
            }
            return item;
        }

        // 如果头节点的元素为空或头节点发生了变化，这说明头节点已经被另外一个线程修改了。那么获取p节点的下一个节点
        Node<E> next = succ(p);

        // 如果p的下一个节点也为空，说明这个队列已经空了
        if (next == null) {
            // 更新头节点。
            updateHead(h, p);
            break;
        }

        // 如果下一个元素不为空，则将头节点的下一个节点设置成头节点
        p = next;
    }
    return null;
}

首先获取头节点的元素，然后判断头节点元素是否为空，如果为空，表示另外一个线程已经进行了一次出队操作将该节点的元素取走，如果不为空，则使用CAS的方式将头节点的引用设置成null，如果CAS成功，则直接返回头节点的元素，如果不成功，表示另外一个线程已经进行了一次出队操作更新了head节点，导致元素发生了变化，需要重新获取头节点。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

OpenResty 1136 发布

发表于 2017-11-20

upgraded the Nginx core to 1.13.6.
- see the changes here: nginx.org/en/CHANGES
bundled the new component, ngx_stream_lua_module 0.0.4, which is also enabled by default. One can disable this 3rd-party Nginx C module by passing --without-stream_lua_module to the ./configure script. We provide compatible Lua API with ngx_lua wherever it makes sense. Currently
we support content_by_lua*, preread_by_lua* (similar to ngx_lua‘s access_by_lua* ), log_by_lua*, and balancer_by_lua* in the stream subsystem. thanks Mashape Inc. for
sponsoring the OpenResty Inc. team to do the development work on rewriting ngx_stream_lua for recent nginx core version.
change: applied a patch to the nginx core to make sure the “server” header in HTTP/2 response shows “openresty” when the server_tokens diretive is turned off.
feature: added nginx core patches needed by ngx_stream_lua_module‘s balancer_by_lua*.
win32: upgraded PCRE to 8.41.
upgraded ngx_lua to 0.10.11.
- feature: shdict: added pure C API for getting free page size and total capacity for lua-resty-core. thanks Hiroaki Nakamura for the patch.
- feature: added pure C functions for shdict:ttl() and shdict:expire() API functions.
  thanks Thibault Charbonnier for the patch.
- bugfix: *_by_lua_block directives might break nginx config dump (-T switch). thanks Oleg A. Mamontov for the patch.
- bugfix: segmentation faults might happen when pipelined http requests are used in the downsteram connection. thanks Gao Yan for the report.
- bugfix: the ssl connections might be drained and reused prematurely when ssl_certificate_by_lua* or ssl_session_fetch_by_lua* were used. this might lead to segmentation faults under load. thanks guanglinlv for the report and the original patch.
- bugfix: tcpsock:connect(): when the nginx resolver’s send() immediately fails without yielding, we
  didn’t clean up the coroutine ctx state properly. This might lead to segmentation faults. thanks xiaocang for the report and root for the patch.
- bugfix: added fallthrough comment to silence GCC 7’s -Wimplicit-fallthrough. thanks Andriy Kornatskyy for the report and spacewander for the patch.
- bugfix: tcpsock:settimeout, tcpsock:settimeouts: throws an error when the timeout
  argument values overflow. Here we only support timeout values no greater than the max value of a 32 bits integer. thanks spacewander for the patch.
- doc: added “413 Request Entity Too Large” to the possible short circuit response list. thanks Datong Sun for the patch.
upgraded lua-resty-core to 0.1.13.
- feature: ngx.balancer now supports the ngx_stream_lua; also disabled
  all the other FFI APIs for the stream subsystem for now.
- feature: resty.core.shdict: added new methods shdict:free_space()
  and shdict:capacity(). thanks Hiroaki Nakamura for the patch.
- feature: implemented the ngx.re.gmatch function with FFI. thanks spacewander for the patch.
- bugfix: ngx.re: fix an edge-case where re.split() might
  not destroy compiled regexes. thanks Thibault Charbonnier for the patch.
- feature: implemented the shdict:ttl() and shdict:expire() API functions using
  FFI.
upgraded lua-resty-dns to 0.20.
- feature: allows RRTYPE values larger than 255. thanks Peter Wu for the patch.
upgraded lua-resty-limit-traffic to 0.05.
- feature: added new module resty.limit.count for GitHub API style request count limiting. thanks Ke Zhu for the original patch
  and Ming Wen for the followup tweaks.
- bugfix: resty.limit.traffic: we might not uncommit previous limiters if a limiter got rejected while committing a state. thanks
  Thibault Charbonnier for the patch.
- bugfix: resty.limit.conn: we incorrectly specified the exceeded connection count as the initial value for the shdict key decrement
  which may lead to dead locks when the key has been evicted in very busy systems. thanks bug had appeared in v0.04.
upgraded resty-cli to 0.20.
- feature: resty: impelented the -j off option to turn off the JIT compiler.
- feature: resty: implemented the -j v and -j dump options similar to luajit’s.
- feature: resty: added new command-line option -l LIB to mimic lua and luajit -l parameter. thanks Michal Cichra for the patch.
- bugfix: resty: handle SIGPIPE ourselves by simply killing the process. thanks Ingy dot Net for the report.
- bugfix: resty: hot looping Lua scripts failed to respond to the INT signal.
upgraded opm to 0.0.4.
- bugfix: opm: when curl uses HTTP/2 by default opm would complain about “bad response status line received”. thanks Donal Byrne
  and Andrew Redden for the report.
- debug: opm: added more details in the “bad response status line received from server” error.
upgraded ngx_headers_more to 0.33.
- feature: add wildcard match support for more_clear_input_headers.
- doc: fixed more_clear_input_headers usage examples. thanks Daniel Paniagua for the patch.
upgraded ngx_encrypted_session to 0.07.
- bugfix: fixed one potential memory leak in an error condition. thanks dyu for the patch.
upgraded ngx_rds_json to 0.15.
- bugfix: fixed warnings with C compilers without variadic macro support.
- doc: added context info for all the config directives.
upgraded ngx_rds_csv to 0.08.
- tests: varous changes in the test suite.
upgraded LuaJIT to v2.1-20171103: github.com/openresty/l…
- optimize: use more appressive JIT compiler parameters as the default to help large OpenResty Lua apps. We now use the following jit.opt defaults: maxtrace=8000 maxrecord=16000 minstitch=3 maxmcode=40960 -- in KB.
- imported Mike Pall’s latest changes:
  - LJ_GC64: Make ASMREF_L references 64 bit.
  - LJ_GC64: Fix ir_khash for non-string GCobj.
  - DynASM/x86: Fix potential REL_A overflow. Thanks to Joshua Haberman.
  - MIPS64: Hide internal function.
  - x64/LJ_GC64: Fix type-check-only variant of SLOAD. Thanks to Peter Cawley.
  - PPC: Add soft-float support to JIT compiler backend. Contributed by Djordje Kovacevic and Stefan Pejic from RT-RK.com. Sponsored by Cisco Systems, Inc.
  - x64/LJ_GC64: Fix fallback case of asm_fuseloadk64(). Contributed by Peter Cawley.

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

AI 学习之路——轻松初探 Python 篇（三）

发表于 2017-11-20

喜欢小之的文章的可以关注公众号「WeaponZhi」持续关注动态

这是「AI 学习之路」的第 3 篇，「Python 学习」的第 3 篇

Python 字符串使用和 C 语言比较类似，但还有一些我们值得注意的地方需要关注，用这篇文章来帮助大家掌握 Python 的字符串吧！

编码

不论什么语言，我们都需要考虑一下这个语言的编码问题。「ASCII」编码是我们最熟悉的编码，但它只有 127 个字符被编码到计算机里面了，显然，像中日韩这类国家，语言文字比较特殊，就需要自己来指定编码格式。

比如，中国自己就制定了「GB2312」编码，韩文则是「EUC_KR」，俄语是「KOI8-R」，显然，如果每一个国家都需要制作一个适配的编码，那我们的计算机世界就要乱套了，不同国家之间信息的传输将变的寸步难行。如果电脑里没有某个语言的编码，那就会产生乱码冲突，这是相当麻烦的。

所以，大家商量了一下，就做出了「Unicode」这么个编码格式，它干脆把所有的编码都统一了，只要你用 Unicode 它就能保证没有乱码问题。

但 Unicode 也有缺点。比如如果一个文件是纯英文来写的，那所有的字符实际上都可以用过 ASCII 的 8 位二进制来表示。我们知道 Unicode 是通过补 0 来表示一些低位数的字符的，这样，为了保持兼容性，你实际上白白浪费了两倍的空间。

UTF-8 就是为了解决这样一个问题而出现的。它是一个**「可变长编码」**，你不是嫌空间浪费吗，那么现在只要你用了 UTF-8，从此以后英文字母咱就可以用 1 个字节来存储了，如果遇到像中文这种「高大上」但又比较复杂的字体，我们灵活对待，用三个字节来表示，实在有某些更加变态而复杂的字体，那最多可以拓展到用 6 个字节来存储。总之，这样下去，既解决了兼容性问题，又可以节约资源，资源问题迎刃而解了。

Python 中的字符串是用 Unicode 编码的，所以 Python 可以支持多语言，当我们保存的时候，我们需要把 Unicode 转换为 UTF-8，使用的时候，再从文件中转换 UTF-8 到 Unicode 到内存中。

通过编码的这种演进过程，我们是不是会有所启发呢？

**你会发现，一切技术的产生和发展，都是为了解决问题而出现的。**大家如果细细的思考一下，不论是语言、技术、设计模式、架构，实际上他们的发展过程并不是一个凭空的技术升级行为，而是为了解决某种问题而诞生的。

「GB2312」是为了解决 ASCII 没有中文而才创造出来的，「Unicode」是因为各国语言不兼容而创造出来的。而 Unicode 对于资源的浪费又促成了 UTF-8 的产生。最典型的问题驱动技术，就是设计模式了，设计模式的产生实际上就是各种为解决某些特定问题而总结出来的方案。

所以在技术上，遇到问题并不可怕，问题恰恰是最能帮助自己提升的，问题是创造力的源头之一。我们同时在平时看书的时候，也要抱着解决问题的角度来学习，如果你单纯的去读一本技术书，这本书又只有理论和代码，你会觉得很枯燥。如果书里可以结合一些案例和问题，从这里展开讲解，然后再介绍一些解决方案和代码，这种教学方式效果就会特别好。比如我之前看过的一本书「Android 源码设计模式」，它就是用这种方式来进行展开的说明设计模式的场景，看完了这本书后，以后面对某种场景，我就特别容易回想起之前书中写过的一些场景，从而产生记忆联想。

不仅如此，如果想的再深一点，你就会突然醒悟，实际上人类社会好像也是以这种形式来发展的…

是不是有点扯远了？我们还是来看看字符串吧。

字符串

Python 的字符串和 C 语言有些类似。我们简单的把常用的用法介绍一下即可，平时只要多写几次，就能比较熟练的掌握了(此节引用廖雪峰教程示例，作了简化)。

ord() 和 chr()

使用 ord() 获取字符的整数表示，chr() 则是把编码转化为字符：

复制代码>>> ord('A')
65
>>> ord('中')
20013
>>> chr(66)
'B'
>>> chr(25991)
'文'

bytes

用带「b」前缀的单引号或者双引号字符来表示「bytes」类型的数据，非常方便

1 2	复制代码x = b'ABC' encode() 和 decode()

开发的时候，经常要把 str 和 bytes 进行相互转换, str 通过 encode() 转化为 bytes，bytes 通过 decode() 转化为 str

复制代码>>> 'ABC'.encode('ascii')
b'ABC'

>>> '中文'.encode('utf-8')
b'\xe4\xb8\xad\xe6\x96\x87'

>>> '中文'.encode('ascii')
Trace back (most recent call last):
    File "<stdin>", line 1, in<module>
UnicodeEncodeError


>>> b'ABC'.decode('ascii')
'ABC'

>>> b'\xe4\xb8\xad\xe6\x96\x87'
'中文'

>>> b'\xe4\xb8\xad\xff'.decode('utf-8')
Tradeback(most recent call last):
    ...
UnicodeDecodeError

这里要注意容错，encode 不能转化超过参数编码范围的字符，而如果 bytes 中包含编码格式无法解析的字符，decode() 也会报错。

len()

通过 len 计算字符串的字符数或者 bytes 的字节数

复制代码>>> len('ABC')
3
>>> len('中文')
2
>>> len(b'ABC')
3
>>> len(b'\xe4\xb8\xad\xe6\x87')
6
>>> len('中文'.encode('utf-8'))
6

从输出结果发现，中文占 3 个字节，英文占 1 个字节

声明编码格式

如果希望 Python 解释器可以按 UTF-8 编码来读取 .py 文件，需要在文件中声明

1 2	复制代码#1 /usr/bin/env python3 # -- coding: utf-8 --

第一行只对 Linux/OS X 有效，它告诉系统这是一个 Python 可执行程序。第二行则告诉 Python 解释器，这个文件要按照 UTF-8 编码。如果不这样写，中文输出会有乱码。

字符串格式化

格式化和 C 有点像，用「%」实现

复制代码>>> 'Hello,%s' % 'world'
'Hello , world'

>>> '你好%s，你有 ￥%d 吗' % ('小之',50)
'你好小之，你有 ￥50 吗'

占位符中，%d 代表整数，%f 代表浮点数，%s 代表字符串，%x 代表十六进制整数，占位符要和 % 号后面的变量或者值一一对应，如果只有一个占位符，% 号后不需要括号。

占位符还可以控制空格、小数点和补 0 的位数。比如：

复制代码>>> print('%2d-%02d' % (5,1))
  5-01

>>> print('%.2f' % 3.1415)
3.14

注意，「5-01」中，5 的前面是有两个空格的。

如果你需要使用 % 这个字符显示在字符串中，那么就需要转义了，%% 表示一个 %

1 2	复制代码>>> '小之公众号的点赞率竟然超过了 %d%%' % 50 '小之公众号的点赞率竟然超过了 50%'

欢迎关注我的公众号

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

JDK不同操作系统的FileSystem（Windows）中

发表于 2017-11-20

前言

我们知道不同的操作系统有各自的文件系统，这些文件系统又存在很多差异，而Java 因为是跨平台的，所以它必须要统一处理这些不同平台文件系统之间的差异，才能往上提供统一的入口。

关于FileSystem类

JDK 里面抽象出了一个 FileSystem 来表示文件系统，不同的操作系统通过继承该类实现各自的文件系统，比如 Windows NT/2000 操作系统则为 WinNTFileSystem，而 unix-like 操作系统为 UnixFileSystem。

需要注意的一点是，WinNTFileSystem类和 UnixFileSystem类并不是在同一个 JDK 里面，也就是说它们是分开的，你只能在 Windows 版本的 JDK 中找到 WinNTFileSystem，而在 Linux 版本的 JDK 中找到 UnixFileSystem，同样地，其他操作系统也有自己的文件系统实现类。

这里分成两个系列分析 JDK 对两种（Windows 和Linux）操作系统的文件系统的实现类，先讲 Windows操作系统，对应为 WinNTFileSystem 类。由于篇幅较长，《JDK不同操作系统的FileSystem（Windows）》分为上中下篇，此为中篇。

继承结构

1
2
3

复制代码--java.lang.Object
  --java.io.FileSystem
    --java.io.WinNTFileSystem

getDefaultParent方法

返回默认的父路径，直接返回 slash 即\。

1
2
3

复制代码public String getDefaultParent() {
        return ("" + slash);
    }

fromURIPath方法

该方法主要是格式化路径。主要逻辑是完成类似以下的转换处理：

/c:/test –> c:/test。
c:/test/ –> c:/test，但要注意，c:/ –> c:/，这是通过长度来限制的，即当长度超过3时才会去掉尾部的 /。
/test/ –> /test。

复制代码public String fromURIPath(String path) {
        String p = path;
        if ((p.length() > 2) && (p.charAt(2) == ':')) {
            p = p.substring(1);
            if ((p.length() > 3) && p.endsWith("/"))
                p = p.substring(0, p.length() - 1);
        } else if ((p.length() > 1) && p.endsWith("/")) {
            p = p.substring(0, p.length() - 1);
        }
        return p;
    }

isAbsolute方法

判断文件是否是绝对路径，先获取文件路径头部长度，如果长度为3则为绝对路径，如果长度为2且路径第一个字符为\也为绝对路径。

复制代码    public boolean isAbsolute(File f) {
        int pl = f.getPrefixLength();
        return (((pl == 2) && (f.getPath().charAt(0) == slash))
                || (pl == 3));
    }

canonicalize方法

该方法用来标准化一个路径，标准路径不仅是一个绝对路径而且还是唯一的路径，而且标准的定义是依赖于操作系统的，一般在标准化路径时会先将路径转成绝对路径，然后才根据操作系统解析成唯一形式的路径。这个过程比较典型的就是处理包含”.”或”..”的路径，还有符号链接和驱动盘符号大小写等。

如果路径长度为2，且路径第一个字符为字母，且路径第二个字符为:，此时路径类似为c:，直接返回路径或加上:返回。
如果路径长度为3，且路径第一个字符为字母，且路径第二个字符为:，且路径第三个字符为\，此时路径类似为c:\，直接返回路径或加上:返回。
如果不使用缓存则直接调用 canonicalize0 本地方法获取标准化路径。
如果使用了缓存则在缓存中查找，存在则直接返回，否则先调用 canonicalize0 本地方法获取标准化路径，再将路径放进缓存中。
另外，还提供了前缀缓存可以使用，它缓存了标准路径的父目录，这样就可以节省了前缀部分的处理，前缀缓存的逻辑也是第一次标准化后将其缓存起来，下次则可从前缀缓存中查询。
使用前缀缓存来标准化路径时是调用 canonicalizeWithPrefix 方法的，该方法最终也是调一个本地方法 canonicalizeWithPrefix0，这里不再列出该方法代码，此本地方法与前面的 canonicalize0 方法的逻辑差不多，唯一不同的是它不用遍历整个路径从头开始检查路径的有效性，而只需要检查一次整个路径的有效性，这也是存在前缀缓存的原因，节省了一些工作。

复制代码    public String canonicalize(String path) throws IOException {
        int len = path.length();
        if ((len == 2) &&
            (isLetter(path.charAt(0))) &&
            (path.charAt(1) == ':')) {
            char c = path.charAt(0);
            if ((c >= 'A') && (c <= 'Z'))
                return path;
            return "" + ((char) (c-32)) + ':';
        } else if ((len == 3) &&
                   (isLetter(path.charAt(0))) &&
                   (path.charAt(1) == ':') &&
                   (path.charAt(2) == '\\')) {
            char c = path.charAt(0);
            if ((c >= 'A') && (c <= 'Z'))
                return path;
            return "" + ((char) (c-32)) + ':' + '\\';
        }
        if (!useCanonCaches) {
            return canonicalize0(path);
        } else {
            String res = cache.get(path);
            if (res == null) {
                String dir = null;
                String resDir = null;
                if (useCanonPrefixCache) {
                    dir = parentOrNull(path);
                    if (dir != null) {
                        resDir = prefixCache.get(dir);
                        if (resDir != null) {
                            String filename = path.substring(1 + dir.length());
                            res = canonicalizeWithPrefix(resDir, filename);
                            cache.put(dir + File.separatorChar + filename, res);
                        }
                    }
                }
                if (res == null) {
                    res = canonicalize0(path);
                    cache.put(path, res);
                    if (useCanonPrefixCache && dir != null) {
                        resDir = parentOrNull(res);
                        if (resDir != null) {
                            File f = new File(res);
                            if (f.exists() && !f.isDirectory()) {
                                prefixCache.put(dir, resDir);
                            }
                        }
                    }
                }
            }
            return res;
        }
    }

private native String canonicalize0(String path)
            throws IOException;

private String canonicalizeWithPrefix(String canonicalPrefix,
            String filename) throws IOException
    {
        return canonicalizeWithPrefix0(canonicalPrefix,
                canonicalPrefix + File.separatorChar + filename);
    }


private native String canonicalizeWithPrefix0(String canonicalPrefix,
            String pathWithCanonicalPrefix)
            throws IOException;

因为标准化的具体实现是依赖于操作系统的，所以这部分工作交由本地方法去做，主要逻辑如下，

标准路径最大长度是 MAX_PATH_LENGTH 即1024个字符。
获取路径长度并且通过 currentDirLength 函数获取当前工作目录长度，该函数代码不再贴出来，主要逻辑是判断是否为驱动盘相对路径，如果是的话则根据驱动盘符号获取对应驱动盘的工作目录并返回该目录长度。否则就根据C的API函数 _wgetcwd 获取工作目录并返回长度。路径长度加上工作目录长度则为总长度。
通过 malloc 分配空间，注意这里是宽字符。
最后通过 wcanonicalize 函数标准化路径。代码较长，不再贴出，主要逻辑是，

检查路径是否包含通配符，是则标准化失败。
通过 _wfullpath 函数获取绝对路径，这个函数他会处理 \和..等符号，比如 “test”、”\test” 和”..\test”，则会处理成”C:\Documents and Settings\user\My Documents\test”、”C:\test”和”C:\Documents and Settings\user\test”。
检查路径中是否包含了非法的 .。
获取标准化驱动盘符号，将其大写，保存到结果字符数组中。
如果是 UNC 路径的话，UNC路径格式如\\server\share\file_path，则此时分别获取 server 和 share，将其保存到结果字符数组中。
通过循环检测剩余路径的有效性，主要是使用 FindFirstFileW 函数获取路径对应文件的属性信息，根据返回值可判断其有效性，有效地路径则保存到结果字符数组中。
最终结果字符数组则为标准化后的路径。

复制代码JNIEXPORT jstring JNICALL
Java_java_io_WinNTFileSystem_canonicalize0(JNIEnv *env, jobject this,
                                           jstring pathname)
{
    jstring rv = NULL;
    WCHAR canonicalPath[MAX_PATH_LENGTH];

    WITH_UNICODE_STRING(env, pathname, path) {
        int len = (int)wcslen(path);
        len += currentDirLength(path, len);
        if (len  > MAX_PATH_LENGTH - 1) {
            WCHAR *cp = (WCHAR*)malloc(len * sizeof(WCHAR));
            if (cp != NULL) {
                if (wcanonicalize(path, cp, len) >= 0) {
                    rv = (*env)->NewString(env, cp, (jsize)wcslen(cp));
                }
                free(cp);
            }
        } else
        if (wcanonicalize(path, canonicalPath, MAX_PATH_LENGTH) >= 0) {
            rv = (*env)->NewString(env, canonicalPath, (jsize)wcslen(canonicalPath));
        }
    } END_UNICODE_STRING(env, path);
    if (rv == NULL) {
        JNU_ThrowIOExceptionWithLastError(env, "Bad pathname");
    }
    return rv;
}

getBooleanAttributes方法

这是一个本地方法，它主要的作用是可以用来判断 File 对象对应的文件或目录是否存在，判断 File 对象对应的是不是文件，判断 File 对象对应的是不是目录，判断 File 对象是不是隐藏文件或目录。

但这里为什么返回的是一个 int 类型呢？因为这里为了高效利用数据，用位作为不同属性的标识，分别为
0x01、0x02、0x04、0x08，分别代表是否存在、是否为文件、是否为目录和是否为隐藏文件或目录。

1	复制代码public native int getBooleanAttributes(File f);

本地方法的主要逻辑是先得到文件的路径，再判断路径是否为 windows 保留设备名称，它包括以下这些，

复制代码static WCHAR* ReservedDEviceNames[] = {
    L"CON", L"PRN", L"AUX", L"NUL",
    L"COM1", L"COM2", L"COM3", L"COM4", L"COM5", L"COM6", L"COM7", L"COM8", L"COM9",
    L"LPT1", L"LPT2", L"LPT3", L"LPT4", L"LPT5", L"LPT6", L"LPT7", L"LPT8", L"LPT9",
    L"CLOCK$"
};

接着通过 GetFileAttributesExW 函数获取文件属性，如果文件属于超链接或者快捷方式，则需要再通过 CreateFileW 函数与 GetFileInformationByHandle 函数组合获取文件信息，其中 CreateFileW 函数要使用 OPEN_EXISTING 表示仅仅打开文件而不是创建。得到文件属性后通过位的或操作来标识是否存在、是否文件、是否目录、是否隐藏。

此外有一个特例也需要处理，就是 pagefile.sys 文件，它比较特殊，主要用于虚拟内存，它是文件而不是目录。

复制代码JNIEXPORT jint JNICALL
Java_java_io_WinNTFileSystem_getBooleanAttributes(JNIEnv *env, jobject this,
                                                  jobject file)
{

    jint rv = 0;
    jint pathlen;

#define SPECIALFILE_NAMELEN 12

    WCHAR *pathbuf = fileToNTPath(env, file, ids.path);
    WIN32_FILE_ATTRIBUTE_DATA wfad;
    if (pathbuf == NULL)
        return rv;
    if (!isReservedDeviceNameW(pathbuf)) {
        if (GetFileAttributesExW(pathbuf, GetFileExInfoStandard, &wfad)) {
            DWORD a = getFinalAttributesIfReparsePoint(pathbuf, wfad.dwFileAttributes);
            if (a != INVALID_FILE_ATTRIBUTES) {
                rv = (java_io_FileSystem_BA_EXISTS
                    | ((a & FILE_ATTRIBUTE_DIRECTORY)
                        ? java_io_FileSystem_BA_DIRECTORY
                        : java_io_FileSystem_BA_REGULAR)
                    | ((a & FILE_ATTRIBUTE_HIDDEN)
                        ? java_io_FileSystem_BA_HIDDEN : 0));
            }
        } else { 
            if (GetLastError() == ERROR_SHARING_VIOLATION) {
                rv = java_io_FileSystem_BA_EXISTS;
                if ((pathlen = (jint)wcslen(pathbuf)) >= SPECIALFILE_NAMELEN &&
                    (_wcsicmp(pathbuf + pathlen - SPECIALFILE_NAMELEN,
                              L"pagefile.sys") == 0) ||
                    (_wcsicmp(pathbuf + pathlen - SPECIALFILE_NAMELEN,
                              L"hiberfil.sys") == 0))
                  rv |= java_io_FileSystem_BA_REGULAR;
            }
        }
    }
    free(pathbuf);
    return rv;
}

checkAccess方法

这是一个本地方法，它主要的作用是判断某个文件或目录是否可读、是否可写、是否可执行。这里同样用位标识这些属性，分别用0x01、0x02、0x04表示可执行、可写、可读。

1	复制代码public native boolean checkAccess(File f, int access);

本地方法的逻辑是先获取文件或目录路径，接着通过 GetFileAttributesW 函数获取文件属性，如果文件属于超链接或者快捷方式，则需要再通过 CreateFileW 函数与 GetFileInformationByHandle 函数组合获取文件信息，其中 CreateFileW 函数要使用 OPEN_EXISTING 表示仅仅打开文件而不是创建。可以看到如果为 INVALID_FILE_ATTRIBUTES 则是获取失败了，此时任何权限都是没有的。获取成功则当判断可读性和可执行性时都返回true，但检查可写时则还要判断是否为目录（目录直接可写），而且还要看文件属性是否为 FILE_ATTRIBUTE_READONLY，只读的话则不可写。

复制代码JNIEXPORT jboolean
JNICALL Java_java_io_WinNTFileSystem_checkAccess(JNIEnv *env, jobject this,
                                                 jobject file, jint access)
{
    DWORD attr;
    WCHAR *pathbuf = fileToNTPath(env, file, ids.path);
    if (pathbuf == NULL)
        return JNI_FALSE;
    attr = GetFileAttributesW(pathbuf);
    attr = getFinalAttributesIfReparsePoint(pathbuf, attr);
    free(pathbuf);
    if (attr == INVALID_FILE_ATTRIBUTES)
        return JNI_FALSE;
    switch (access) {
    case java_io_FileSystem_ACCESS_READ:
    case java_io_FileSystem_ACCESS_EXECUTE:
        return JNI_TRUE;
    case java_io_FileSystem_ACCESS_WRITE:
        if ((attr & FILE_ATTRIBUTE_DIRECTORY) ||
            (attr & FILE_ATTRIBUTE_READONLY) == 0)
            return JNI_TRUE;
        else
            return JNI_FALSE;
    default:
        assert(0);
        return JNI_FALSE;
    }
}

getLastModifiedTime方法

该方法用于获取文件或目录的最后修改时间，本地方法先获取 File 对象的路径，再通过 CreateFileW 函数和 GetFileTime 函数获取最后修改时间，其中 CreateFileW 函数要使用 OPEN_EXISTING 表示仅仅打开文件而不是创建。

复制代码public native long getLastModifiedTime(File f);

JNIEXPORT jlong JNICALL
Java_java_io_WinNTFileSystem_getLastModifiedTime(JNIEnv *env, jobject this,
                                                 jobject file)
{
    jlong rv = 0;
    LARGE_INTEGER modTime;
    FILETIME t;
    HANDLE h;
    WCHAR *pathbuf = fileToNTPath(env, file, ids.path);
    if (pathbuf == NULL)
        return rv;
    h = CreateFileW(pathbuf,
                    0,
                    FILE_SHARE_DELETE | FILE_SHARE_READ | FILE_SHARE_WRITE,
                    NULL,
                    OPEN_EXISTING,
                    FILE_FLAG_BACKUP_SEMANTICS,
                    NULL);
    if (h != INVALID_HANDLE_VALUE) {
        if (GetFileTime(h, NULL, NULL, &t)) {
            modTime.LowPart = (DWORD) t.dwLowDateTime;
            modTime.HighPart = (LONG) t.dwHighDateTime;
            rv = modTime.QuadPart / 10000;
            rv -= 11644473600000;
        }
        CloseHandle(h);
    }
    free(pathbuf);
    return rv;
}

getLength方法

该方法御用获取文件或目录的长度。逻辑为，

获取 File 对象的路径。
通过 GetFileAttributesExW 函数获取文件属性，然后通过 nFileSizeHigh 和 nFileSizeLow 得到文件的长度。
如果文件属于超链接或者快捷方式，则需要再通过 CreateFileW 函数与 GetFileInformationByHandle 函数组合获取文件信息，其中 CreateFileW 函数要使用 OPEN_EXISTING 表示仅仅打开文件而不是创建，然后通过 nFileSizeHigh 和 nFileSizeLow 得到文件的长度。
如果另一个进程在使用文件，则不能访问该文件，并报错 ERROR_SHARING_VIOLATION，此时尝试用 _wstati64 函数获取文件的长度。

复制代码 public native long getLength(File f);

JNIEXPORT jlong JNICALL
Java_java_io_WinNTFileSystem_getLength(JNIEnv *env, jobject this, jobject file)
{
    jlong rv = 0;
    WIN32_FILE_ATTRIBUTE_DATA wfad;
    WCHAR *pathbuf = fileToNTPath(env, file, ids.path);
    if (pathbuf == NULL)
        return rv;
    if (GetFileAttributesExW(pathbuf,
                             GetFileExInfoStandard,
                             &wfad)) {
        if ((wfad.dwFileAttributes & FILE_ATTRIBUTE_REPARSE_POINT) == 0) {
            rv = wfad.nFileSizeHigh * ((jlong)MAXDWORD + 1) + wfad.nFileSizeLow;
        } else {
            BY_HANDLE_FILE_INFORMATION finfo;
            if (getFileInformation(pathbuf, &finfo)) {
                rv = finfo.nFileSizeHigh * ((jlong)MAXDWORD + 1) +
                    finfo.nFileSizeLow;
            }
        }
    } else {
        if (GetLastError() == ERROR_SHARING_VIOLATION) {
            struct _stati64 sb;
            if (_wstati64(pathbuf, &sb) == 0) {
                rv = sb.st_size;
            }
        }
    }
    free(pathbuf);
    return rv;
}

setPermission方法

该方法主要用于设置 File 对象的访问权限。逻辑如下，

如果设置额权限为 ACCESS_READ 或 ACCESS_EXECUTE，则直接返回传入的参数enable。
获取 File 对象的路径。
通过 GetFileAttributesW 函数获取文件属性。
如果文件属于超链接或者快捷方式，则先获取对应的最终路径，然后再用 GetFileAttributesW 函数获取文件属性。
判断如果不是目录的话则根据传入的参数enable设置属性，并且通过 SetFileAttributesW 函数设置文件的读写权限。

复制代码public native boolean setPermission(File f, int access, boolean enable,
            boolean owneronly);

JNIEXPORT jboolean JNICALL
Java_java_io_WinNTFileSystem_setPermission(JNIEnv *env, jobject this,
                                           jobject file,
                                           jint access,
                                           jboolean enable,
                                           jboolean owneronly)
{
    jboolean rv = JNI_FALSE;
    WCHAR *pathbuf;
    DWORD a;
    if (access == java_io_FileSystem_ACCESS_READ ||
        access == java_io_FileSystem_ACCESS_EXECUTE) {
        return enable;
    }
    pathbuf = fileToNTPath(env, file, ids.path);
    if (pathbuf == NULL)
        return JNI_FALSE;
    a = GetFileAttributesW(pathbuf);

    if ((a != INVALID_FILE_ATTRIBUTES) &&
        ((a & FILE_ATTRIBUTE_REPARSE_POINT) != 0))
    {
        WCHAR *fp = getFinalPath(env, pathbuf);
        if (fp == NULL) {
            a = INVALID_FILE_ATTRIBUTES;
        } else {
            free(pathbuf);
            pathbuf = fp;
            a = GetFileAttributesW(pathbuf);
        }
    }
    if ((a != INVALID_FILE_ATTRIBUTES) &&
        ((a & FILE_ATTRIBUTE_DIRECTORY) == 0))
    {
        if (enable)
            a =  a & ~FILE_ATTRIBUTE_READONLY;
        else
            a =  a | FILE_ATTRIBUTE_READONLY;
        if (SetFileAttributesW(pathbuf, a))
            rv = JNI_TRUE;
    }
    free(pathbuf);
    return rv;
}

以下是广告和相关阅读

========广告时间========

鄙人的新书《Tomcat内核设计剖析》已经在京东销售了，有需要的朋友可以到 item.jd.com/12185360.ht… 进行预定。感谢各位朋友。

为什么写《Tomcat内核设计剖析》

=========================

SpringMvc4x高级配置(五) Spring MVC

发表于 2017-11-20

一. 点睛

测试是保证软件质量的关键，在之前的讲解中只是介绍了简单的测试，下面要进行一些和Spring MVC相关的测试，主要涉及控制器的测试。

为了测试Web项目通常不需要启动项目，我们需要一些Servlet相关的模拟对象，比如：MockMVC，MockHttpServletRequest，MockHttpServletResponse，MockHttpSession等。

在Spring里，我们使用@WebAppConfiguration指定加载的ApplicationContext是一个WebAppConfiguration。

在下面的示例里面借助JUnit和Spring TestContext framework，分别演示对普通页面转向形控制器和RestController进行测试。

二. 示例：

测试依赖

复制代码        <!-- spring-test -->
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-test</artifactId>
            <version>${spring-framework.version}</version>
            <scope>test</scope>
        </dependency>

        <!-- junit -->
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.11</version>
            <scope>test</scope>
        </dependency>

代码解释：

这里<scope>test</scope>说明这些包的存活是在test周期，也就是意味着发布时我们将不包含这些jar包。

演示服务：

在src/main/java下新增DemoService 类，代码如下所示：

复制代码package org.light4j.springMvc4.service;

import org.springframework.stereotype.Service;

@Service
public class DemoService {

    public String saySomething(){
        return "hello";
    }
}

测试用例

在src/test/java下新建TestControllerIntegrationTests类，代码如下：

复制代码package org.light4j.springMvc4.web;


import static org.springframework.test.web.servlet.request.MockMvcRequestBuilders.get;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.content;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.forwardedUrl;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.model;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.status;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.view;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.light4j.springMvc4.MyMvcConfig;
import org.light4j.springMvc4.service.DemoService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.mock.web.MockHttpServletRequest;
import org.springframework.mock.web.MockHttpSession;
import org.springframework.test.context.ContextConfiguration;
import org.springframework.test.context.junit4.SpringJUnit4ClassRunner;
import org.springframework.test.context.web.WebAppConfiguration;
import org.springframework.test.web.servlet.MockMvc;
import org.springframework.test.web.servlet.setup.MockMvcBuilders;
import org.springframework.web.context.WebApplicationContext;

@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(classes = {MyMvcConfig.class})
@WebAppConfiguration("src/main/resources") //①
public class TestControllerIntegrationTests {
    private MockMvc mockMvc; //②

   @Autowired
   private DemoService demoService;//③

   @Autowired 
   WebApplicationContext wac; //④

    @Autowired 
    MockHttpSession session; //⑤

    @Autowired 
    MockHttpServletRequest request; //⑥

    @Before //7
    public void setup() {
        mockMvc =
                MockMvcBuilders.webAppContextSetup(this.wac).build(); //②
        }

    @Test
    public void testNormalController() throws Exception{
        mockMvc.perform(get("/normal")) //⑧
                .andExpect(status().isOk())//⑨
                .andExpect(view().name("page"))//⑩
                .andExpect(forwardedUrl("/WEB-INF/classes/views/page.jsp"))//11
                .andExpect(model().attribute("msg", demoService.saySomething()));//12

    }

    @Test
    public void testRestController() throws Exception{
        mockMvc.perform(get("/testRest")) //13
        .andExpect(status().isOk())
         .andExpect(content().contentType("text/plain;charset=UTF-8"))//14
        .andExpect(content().string(demoService.saySomething()));//15
    }
}

代码解释：

① @WebAppConfiguration注解在类上，用来声明加载的ApplicationContext是一个WebApplicationContext。它的属性指定的是Web资源的位置，默认为src/main/webapp,本例修改为src/main/resource。
② MockMvc模拟MVC对象，通过MockMvcBuilders.webAppContextSetup(this.wac).build()进行初始化。
③ 可以在测试用例中注入Spring的Bean。
④ 可注入WebApplicationContext。
⑤ 可注入模拟的http session，此处仅作演示，没有使用。
⑥ 可注入模拟的http request，此处仅作演示，没有使用。
⑦ @Before 在测试开始前进行的初始化工作。
⑧ 模拟向/normal进行get请求。
⑨ 预期控制返回状态为200.
⑩ 预期view的名称为page。
11 预期页面转向的真正路径为/WEB-INF/classes/views/page.jsp。
12 预期model里面的值是demoService.saySomething()返回值hello。
13.模拟向/testRest进行get请求。
14 预期返回值的媒体类型是text/plain;charset=UTF-8。
15 预期返回值的内容为demoService.saySomething()返回值hello。

此时，运行该测试，效果如下图所示：
xxx

编写普通控制器

在src/main/java下新增NormalController 类，代码如下所示：

复制代码package org.light4j.springMvc4.web;

import org.light4j.springMvc4.service.DemoService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.RequestMapping;

@Controller
public class NormalController {

    @Autowired
    DemoService demoService;

    @RequestMapping("/normal")
    public  String testPage(Model model){
        model.addAttribute("msg", demoService.saySomething());
        return "page";
    }
}

编写普通控制器的演示页面

在src/main/resources/view下新建page.jsp

复制代码<%@ page language="java" contentType="text/html; charset=UTF-8"
    pageEncoding="UTF-8"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Test page</title>
</head>
<body>
    <pre>
        Welcome to Spring MVC world
    </pre>
</body>
</html>

编写RestController控制器

在src/main/java下新增RestController类，代码如下所示：

复制代码package org.light4j.springMvc4.web;

import org.light4j.springMvc4.service.DemoService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.ResponseBody;

@RestController
public class MyRestController {

    @Autowired
    DemoService demoService;

    @RequestMapping(value = "/testRest" ,produces="text/plain;charset=UTF-8")
    public @ResponseBody String testRest(){
        return demoService.saySomething();
    }
}

运行测试

效果如下图所示：
xxx

三. 源代码示例：

github地址：点击查看
码云地址：点击查看

打赏 欢迎关注人生设计师的微信公众账号
公众号ID：longjiazuoA

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

Docker的那点事儿

发表于 2017-11-19

Docker是什么？

Docker是一个基于轻量级虚拟化技术的容器，整个项目基于Go语言开发，并采用了Apache 2.0协议。Docker可以将我们的应用程序打包封装到一个容器中，该容器包含了应用程序的代码、运行环境、依赖库、配置文件等必需的资源，通过容器就可以实现方便快速并且与平台解耦的自动化部署方式，无论你部署时的环境如何，容器中的应用程序都会运行在同一种环境下。

举个栗子，小明写了一个CMS系统，该系统的技术栈非常广，需要依赖于各种开源库和中间件。如果按照纯手动的部署方式，小明需要安装各种开源软件，还需要写好每个开源软件的配置文件。如果只是部署一次，这点时间开销还是可以接受的，但如果小明每隔几天就需要换个服务器去部署他的程序，那么这些繁琐的重复工作无疑是会令人发狂的。这时候，Docker的用处就派上场了，小明只需要根据应用程序的部署步骤编写一份Dockerfile文件（将安装、配置等操作交由Docker自动化处理），然后构建并发布他的镜像，这样，不管在什么机器上，小明都只需要拉取他需要的镜像，然后就可以直接部署运行了，这正是Docker的魅力所在。

那么镜像又是什么呢？镜像是Docker中的一个重要概念：

Image（镜像）：它类似于虚拟机中使用到的镜像，由于任何应用程序都需要有它自己的运行环境，Image就是用来提供所需运行环境的一个模板。
Container（容器）：Container是Docker提供的一个抽象层，它就像一个轻量级的沙盒，其中包含了一个极简的Linux系统环境与运行在其中的应用程序。Container是Image的运行实例（Image本身是只读的，Container启动时，Docker会在Image的上层创建一个可写层，任何在Container中的修改都不会影响到Image，如果想要在Image保存Container中的修改，Docker采用了基于Container生成新的Image层的策略），Docker引擎利用Container来操作并隔离每个应用（也就是说，每个容器中的应用都是互相独立的）。

其实从Docker与Container的英文单词原意中就可以体会出Docker的思想。Container可以释义为集装箱，集装箱是一个可以便于机械设备装卸的封装货物的通用标准规格，它的发明简化了物流运输的机械化过程，使其建立起了一套标准化的物流运输体系。而Docker的意思为码头工人，可以认为，Docker就像是在码头上辛勤工作的工人，把应用打包成一个个具有某种标准化规格的”集装箱”（其实这里指出的集装箱对应的是Image，在Docker中Container更像是一个运行中的沙盒），当货物运输到目的地后，码头工人们（Docker）就可以把集装箱拆开取出其中的货物（基于Image来创建Container并运行）。这种标准化与隔离性可以很方便地组合使用多个Image来构建你的应用环境（Docker也提倡每个Image都遵循单一职责原则，也就是只做好一件事），或者与其他人共享你的Image。

本文作者为SylvanasSun(sylvanas.sun@gmail.com)，首发于SylvanasSun’s Blog。
原文链接：sylvanassun.github.io/2017/11/19/…
（转载请务必保留本段声明，并且保留超链接。）

Docker VS 虚拟机

在上文中我们提到了Docker是基于轻量级虚拟化技术的，所以它与我们平常使用的虚拟机是不一样的。虚拟机技术可以分成以下两类：

系统虚拟机

系统虚拟机：通过软件对计算机系统的模拟来提供一个真实计算机的替代品。它是物理硬件的抽象并提供了运行完整操作系统所需的功能。虚拟机通过物理机器来管理和共享硬件，这样实现了多个虚拟机环境彼此之间的隔离，一台机器上可以运行多个虚拟机，每个虚拟机包括一个操作系统的完整副本。在系统虚拟机中，所运行的所有软件或操作都只会影响到该虚拟机的环境。我们经常使用的VMWare就是系统虚拟机的实现。
程序虚拟机：允许程序独立运行在平台之外。比较典型的例子就是JVM，Java通过JVM这一抽象层使得Java程序与操作系统和硬件平台解耦（因为每个Java程序都是运行在JVM中的），因此实现了所谓的compile once, run everywhere。

Docker所用到的技术与上述两种都不相同，它使用了更轻量级的虚拟化技术，多个Container共享了同一个操作系统内核，并且就像运行在本地上一样。Container技术相对于虚拟机来说，只是一个应用程序层的抽象，它将代码与依赖关系打包到一起，多个Container可以在同一台机器上运行（意味着一个虚拟机上也可以运行多个Container），并与其它Container共享操作系统内核，每一个Container都在用户空间中作为一个独立的进程运行，这些特性都证明了Container要比虚拟机更加灵活与轻量（一般都是结合虚拟机与Docker一起使用）。

Container技术其实并不是个新鲜事物，最早可以追溯到UNIX中的chroot（在1979年的V7 Unix中引入），它可以改变当前正在运行的进程及其子目录的根目录，在这种修改过的环境下运行的程序不能在指定的目录树之外访问文件，从而限制用户的活动范围，为进程提供了隔离空间。

之后各种Unix版本涌现出很多Container技术，在2006年，Google提出了”Process Containers”期望在Linux内核中实现进程资源隔离的相关特性，由于Container在Linux内核中的定义过于宽泛混乱，后来该项目改名为CGroups（Control Groups），实现了对进程的资源限制。

2008年，LXC（Linux Containers）发布，它是一种在操作系统层级上的虚拟化方法，用于在Linux系统上通过共享一个内核来运行多个互相隔离的程序（Container）。LXC正是结合了Linux内核中的CGroups和对分离的名称空间的支持来为应用程序提供了一个隔离的环境。而Docker也是基于LXC实现的（Docker的前身是dotClound公司中的内部项目，它是一家提供PaaS服务的公司。），并作出了许多改进。

使用Docker

在使用Docker之前你需要先安装Docker（这好像是一句废话。。。），根据不同的平台安装方法都不相同，可以去参考Install Docker | Docker Documentation或者自行Google。

安装完毕之后，输入docker --version来确认是否安装成功。

1 2	复制代码$ docker --version Docker version 17.05.0-ce-rc1, build 2878a85

从Docker Hub中可以pull到其他人发布的Image，我们也可以注册一个账号去发布自己的Image与他人共享。

复制代码[root@Jack ~]# docker search redis # 查看redis镜像是否存在
[root@Jack ~]# docker pull redis # 拉取redis镜像到本机
Using default tag: latest
Trying to pull repository docker.io/library/redis ... 
latest: Pulling from docker.io/library/redis
Digest: sha256:cd277716dbff2c0211c8366687d275d2b53112fecbf9d6c86e9853edb0900956
[root@Jack ~]# docker images # 查看镜像信息
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
docker.io/python    3.6-onbuild         7195f9298ffb        2 weeks ago         691.1 MB
docker.io/mongo     latest              d22888af0ce0        2 weeks ago         360.9 MB
docker.io/redis     latest              8f2e175b3bd1        2 weeks ago         106.6 MB

有了Image，之后就可以在其之上运行一个Container了，命令如下。

复制代码[root@Jack ~]# docker run -d -p 6379:6379 redis # 运行redis，-p代表将本机上6379端口映射到Container的6379端口 -d代表在后台启动
[root@Jack ~]# docker ps -a # 查看容器信息，如果不加-a只会显示当前运行中的容器
# 如果想要进入容器中，那么需要执行以下命令
[root@Jack ~]# docker ps # 先获得容器的id
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS              PORTS                    NAMES
1f928073b7eb        redis               "docker-entrypoint.sh"   45 seconds ago      Up 44 seconds       0.0.0.0:6379->6379/tcp   desperate_khorana
[root@Jack ~]# docker exec -it 1f928073b7eb /bin/bash # 然后再执行该命令进入到容器中
root@1f928073b7eb:/data# touch hello_docker.txt # 在容器中创建一个文件
root@1f928073b7eb:/data# exit # 退出
exit
[root@Jack ~]# 
# 也可以在启动时直接进入 命令如下
[root@Jack ~]# docker run -d -it -p 6379:6379 redis /bin/bash

我们对Container做出了修改，如果想要保留这个修改，可以通过commit命令来生成一个新的Image。

复制代码# -m为描述信息 -a为作者 1f9是你要保存的容器id 取前3个字符 docker可以自行识别
# sylvanassun/redis为镜像名 :test 为一个tag 一般用于标识版本
[root@Jack ~]# docker commit -m "test" -a "SylvanasSun" 1f9 sylvanassun/redis:test
sha256:e7073e8e5bd70b8d58092fd6bd8c2551e65dd29241c235eddf2a7f4b4b25cbbd
[root@Jack ~]# docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
sylvanassun/redis   test                e7073e8e5bd7        2 seconds ago       106.6 MB
docker.io/python    3.6-onbuild         7195f9298ffb        2 weeks ago         691.1 MB
docker.io/mongo     latest              d22888af0ce0        2 weeks ago         360.9 MB
docker.io/redis     latest              8f2e175b3bd1        2 weeks ago         106.6 MB

想删除一个容器或镜像也很简单，但在删除镜像前需要先删除依赖于它的容器。

复制代码[root@Jack ~]# docker stop 1f9 # 关闭运行中的容器，相应的也有docker start id命令来启动一个容器
1f9
[root@Jack ~]# docker rm 1f9 # 删除容器
1f9
[root@Jack ~]# docker rmi e70 # 删除上面保存的镜像
Untagged: sylvanassun/redis:test
Deleted: sha256:e7073e8e5bd70b8d58092fd6bd8c2551e65dd29241c235eddf2a7f4b4b25cbbd
Deleted: sha256:751db4a870e5f703082b31c1614a19c86e0c967334a61f5d22b2511072aef56d

如果想要自己构建一个镜像，那么需要编写Dockerfile文件，该文件描述了镜像的依赖环境以及如何配置你的应用环境。

复制代码# 使用python:2.7-slim 作为父镜像
FROM python:2.7-slim

# 跳转到/app 其实就是cd命令
WORKDIR /app

# 将当前目录的内容(.)复制到镜像的/app目录下
ADD . /app

# RUN代表运行的shell命令，下面这条命令是根据requirements.txt安装python应用的依赖包
RUN pip install --trusted-host pypi.python.org -r requirements.txt

# 暴露80端口让外界访问
EXPOSE 80

# 定义环境变量
ENV NAME World

# 当容器启动时执行的命令，它与RUN不同，只在容器启动时执行一次
CMD ["python", "app.py"]

然后就可以通过docker build -t xxx/xxxx .命令来构建镜像，-t后面是镜像名与tag等信息，注意.表示在当前目录下寻找Dockerfile文件。

学会如何构建自己的镜像之后，你是否也想将它发布到Docker Hub上与他人分享呢？要想做到这一点，需要先注册一个Docker Hub账号，之后通过docker login命令登录，然后再docker push image name，就像在使用Git一样简单。

关于Docker的更多命令与使用方法，请参考Docker Documentation | Docker Documentation，另外我还推荐使用Docker Compose来构建镜像，它可以很方便地组合管理多个镜像。

结语

Docker提供了非常强大的自动化部署方式与灵活性，对多个应用程序之间做到了解耦，提供了开发上的敏捷性、可控性以及可移植性。同时，Docker也在不断地帮助越来越多的企业实现了向云端迁移、向微服务转型以及向DevOps模式的实践。

如今，微服务与DevOps火爆程度日益渐高，你又有何理由选择拒绝Docker呢？让我们一起选择拥抱Docker，拥抱未来！

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

四叉树上如何求希尔伯特曲线的邻居？

发表于 2017-11-19

关于邻居的定义，相邻即为邻居，那么邻居分为2种，边相邻和点相邻。边相邻的有4个方向，上下左右。点相邻的也有4个方向，即4个顶点相邻的。

如上图，绿色的区域是一颗四叉树表示的范围，四叉树上面有一个点，图中黄色区域标明的点。现在想求四叉树上黄色的点的希尔伯特曲线邻居。图中黑色的线就是一颗穿过四叉树的希尔伯特曲线。希尔伯特曲线的起点0在左上角的方格中，终点63在右上角的方格中。

红色的四个格子是黄色格子边相邻邻居，蓝色的四个格子是黄色格子的顶点相邻的邻居，所以黄色格子的邻居为8个格子，分别表示的点是8，9，54，11，53，30，31，32 。可以看出来这些邻居在表示的点上面并不是相邻的。

那么怎么求四叉树上任意一点的希尔伯特曲线邻居呢？

一. 边邻居

边邻居最直接的想法就是先拿到中心点的坐标 (i，j) ，然后通过坐标系的关系，拿到与它边相邻的 Cell 的坐标 (i + 1，j) ， (i - 1，j) ， (i，j - 1) ， (i，j + 1) 。

实际做法也是如此。不过这里涉及到需要转换的地方。这里需要把希尔伯特曲线上的点转换成坐标以后才能按照上面的思路来计算边邻居。

关于 CellID 的生成与数据结构，见笔者这篇《Google S2 中的 CellID 是如何生成的？》

按照上述的思路，实现出来的代码如下：

复制代码

func (ci CellID) EdgeNeighbors() [4]CellID {
    level := ci.Level()
    size := sizeIJ(level)
    f, i, j, _ := ci.faceIJOrientation()
    return [4]CellID{
        cellIDFromFaceIJWrap(f, i, j-size).Parent(level),
        cellIDFromFaceIJWrap(f, i+size, j).Parent(level),
        cellIDFromFaceIJWrap(f, i, j+size).Parent(level),
        cellIDFromFaceIJWrap(f, i-size, j).Parent(level),
    }
}

边按照，下边，右边，上边，左边，逆时针的方向依次编号0，1，2，3 。

接下来具体分析一下里面的实现。

复制代码
func sizeIJ(level int) int {
    return 1 << uint(maxLevel-level)
}

sizeIJ 保存的是当前 Level 的格子边长大小。这个大小是相对于 Level 30 来说的。比如 level = 29，那么它的 sizeIJ 就是2，代表 Level 29 的一个格子边长是由2个 Level 30 的格子组成的，那么也就是2^2^=4个小格子组成的。如果是 level = 28，那么边长就是4，由16个小格子组成。其他都以此类推。

复制代码
func (ci CellID) faceIJOrientation() (f, i, j, orientation int) {

    f = ci.Face()
    orientation = f & swapMask
    nbits := maxLevel - 7*lookupBits // first iteration

    for k := 7; k >= 0; k-- {
        orientation += (int(uint64(ci)>>uint64(k*2*lookupBits+1)) & ((1 << uint((2 * nbits))) - 1)) << 2
        orientation = lookupIJ[orientation]
        i += (orientation >> (lookupBits + 2)) << uint(k*lookupBits)
        j += ((orientation >> 2) & ((1 << lookupBits) - 1)) << uint(k*lookupBits)
        orientation &= (swapMask | invertMask)
        nbits = lookupBits // following iterations
    }
    // 下面这个判断详细解释
    if ci.lsb()&0x1111111111111110 != 0 {
        orientation ^= swapMask
    }
    return
}

这个方法就是把 CellID 再分解回原来的 i 和 j。这里具体的过程在笔者这篇《Google S2 中的 CellID 是如何生成的？》里面的 cellIDFromFaceIJ 方法里面有详细的叙述，这里就不再赘述了。cellIDFromFaceIJ 方法和 faceIJOrientation 方法是互为逆方法。
cellIDFromFaceIJ 是把 face，i，j 这个当入参传进去，返回值是 CellID，faceIJOrientation 是把 CellID 分解成 face，i，j，orientation。faceIJOrientation 比 cellIDFromFaceIJ 分解出来多一个 orientation。

这里需要重点解释的是 orientation 怎么计算出来的。

我们知道 CellID 的数据结构是 3位 face + 60位 position + 1位标志位。那么对于 Level - n 的非叶子节点，3位 face 之后，一定是有 2 n 位二进制位，然后紧接着 2(maxLevel - n) + 1 位以1开头的，末尾都是0的二进制位。maxLevel = 30 。

例如 Level - 16，中间一定是有32位二进制位，然后紧接着 2*(30 - 16) + 1 = 29位。这29位是首位为1，末尾为0组成的。3 + 32 + 29 = 64 位。64位 CellID 就这样组成的。

当 n = 30，3 + 60 + 1 = 64，所以末尾的1并没有起任何作用。当 n = 29，3 + 58 + 3 = 64，于是末尾一定是 100 组成的。10对方向并不起任何作用，最后多的一个0也对方向不起任何作用。关键就是看10和0之间有多少个00 。当 n = 28，3 + 56 + 5 = 64，末尾5位是 10000，在10和0之间有一个“00”。“00”是会对方向产生影响，初始的方向应该再异或 01 才能得到。

关于 “00” 会对原始的方向产生影响，这点其实比较好理解。CellID 从最先开始的方向进行四分，每次四分都将带来一次方向的变换。直到变换到最后一个4个小格子的时候，方向就不会变化了，因为在4个小格子之间就可以唯一确定是哪一个 Cell 被选中。所以这也是上面看到了， Level - 30 和 Level - 29 的方向是不变的，除此以外的 Level 是需要再异或一次 01 ，变换以后得到原始的 orientation。

最后进行转换，具体代码实现如下：

复制代码
func cellIDFromFaceIJWrap(f, i, j int) CellID {
    // 1.
    i = clamp(i, -1, maxSize)
    j = clamp(j, -1, maxSize)

    // 2.
    const scale = 1.0 / maxSize
    limit := math.Nextafter(1, 2)
    u := math.Max(-limit, math.Min(limit, scale*float64((i<<1)+1-maxSize)))
    v := math.Max(-limit, math.Min(limit, scale*float64((j<<1)+1-maxSize)))
    // 3.
    f, u, v = xyzToFaceUV(faceUVToXYZ(f, u, v))
    return cellIDFromFaceIJ(f, stToIJ(0.5*(u+1)), stToIJ(0.5*(v+1)))
}

转换过程总共分为三步。第一步先处理 i，j 边界的问题。第二步，将 i，j 转换成 u，v 。第三步，u，v 转 xyz，再转回 u，v，最后转回 CellID 。

第一步：

复制代码
func clamp(x, min, max int) int {
    if x < min {
        return min
    }
    if x > max {
        return max
    }
    return x
}

clamp 函数就是用来限定 i ， j 的范围的。i，j 的范围始终限定在 [-1，maxSize] 之间。

第二步：

最简单的想法是将（i，j）坐标转换为（x，y，z）（这个点不在边界上），然后调用 xyzToFaceUV 方法投影到对应的 face 上。

我们知道在生成 CellID 的时候，stToUV 的时候，用的是一个二次变换：

复制代码
func stToUV(s float64) float64 {
    if s >= 0.5 {
        return (1 / 3.) * (4*s*s - 1)
    }
    return (1 / 3.) * (1 - 4*(1-s)*(1-s))
}

但是此处，我们用的变换就简单一点，用的是线性变换。

1
2
3

复制代码
u = 2 * s - 1
v = 2 * t - 1

u，v 的取值范围都被限定在 [-1，1] 之间。具体代码实现：

复制代码
const scale = 1.0 / maxSize
limit := math.Nextafter(1, 2)
u := math.Max(-limit, math.Min(limit, scale*float64((i<<1)+1-maxSize)))
v := math.Max(-limit, math.Min(limit, scale*float64((j<<1)+1-maxSize)))

第三步：找到叶子节点，把 u，v 转成对应 Level 的 CellID。

1
2
3

复制代码
f, u, v = xyzToFaceUV(faceUVToXYZ(f, u, v))
return cellIDFromFaceIJ(f, stToIJ(0.5*(u+1)), stToIJ(0.5*(v+1)))

这样就求得了一个 CellID 。

由于边有4条边，所以边邻居有4个。

复制代码
    return [4]CellID{
        cellIDFromFaceIJWrap(f, i, j-size).Parent(level),
        cellIDFromFaceIJWrap(f, i+size, j).Parent(level),
        cellIDFromFaceIJWrap(f, i, j+size).Parent(level),
        cellIDFromFaceIJWrap(f, i-size, j).Parent(level),
    }

上面数组里面分别会装入当前 CellID 的下边邻居，右边邻居，上边邻居，左边邻居。

如果在地图上显示出来的话，就是下图的这样子。

中间方格的 CellID = 3958610196388904960 , Level 10 。按照上面的方法求出来的边邻居，分别是：

复制代码

3958603599319138304 // 下边邻居
3958607997365649408 // 右边邻居
3958612395412160512 // 上边邻居
3958599201272627200 // 左边邻居

在地图上展示出来：

二. 共顶点邻居

这里的共顶点邻居和文章开始讲的顶点邻居有点区别。并且下面还会有一些看似奇怪的例子，也是笔者在实际编码中踩过的坑，分享一下。

这里先说明一种特殊情况，即 Cell 正好在地球的外切立方体的8个顶点上。那么这个点的顶点邻居只有3个，而不是4个。因为这8个顶点每个点只有3个面与其连接，所以每个面上有且只有一个 Cell 是它们的顶点邻居。除去这8个点以外的 Cell 的顶点邻居都有4个！

复制代码
j
|
|  (0,1)  (1,1)
|  (0,0)  (1,0)
|
---------------> i

在上述的坐标轴中，i 轴方向如果为1，就落在4个象限的右边一列上。如果 j 轴方向如果为，就落在4个象限的上面一行上。

假设 Cell Level 不等于 30，即末尾标志位1后面还有0，那么这种 Cell 转换成 i，j 以后，i，j 的末尾就都是1 。

上面的结论可以证明的，因为在 faceIJOrientation 函数拆分 Cell 的时候，如果遇到了都是0的情况，比如 orientation = 11，Cell 末尾都是0，那么取出末尾8位加上orientation，00000000 11，经过 lookupIJ 转换以后得到 1111111111 ，于是 i = 1111，j = 1111 ，方向还是 11。Cell 末尾的00还是继续循环上述的过程，于是 i，j 末尾全是1111 了。

所以我们只需要根据 i，j 判断入参给的 Level 在哪个象限，就可以把共顶点的邻居都找到。

假设入参给定的 Level 小，即 Cell 的面积大，那么就需要判断当前 Cell (函数调用者) 的共顶点是位于入参 Cell 的4个顶点的哪个顶点上。Cell 是一个矩形，有4个顶点。当前 Cell (函数调用者) 离哪个顶点近，就选那个顶点为公共顶点。再依次求出以公共顶点周围的4个 Cell 即可。

假设入参给定的 Level 大，即 Cell 的面积小，那么也需要判断入参 Cell 的共顶点是位于当前 Cell (函数调用者)的4个顶点的哪个顶点上。Cell 是一个矩形，有4个顶点。入参 Cell 离哪个顶点近，就选那个顶点为公共顶点。再依次求出以公共顶点周围的4个 Cell 即可。

由于需要判断位于一个 Cell 的四等分的哪一个，所以需要判断它的4个孩子的位置情况。即判断 Level - 1 的孩子的相对位置情况。

复制代码
    halfSize := sizeIJ(level + 1)
    size := halfSize << 1
    f, i, j, _ := ci.faceIJOrientation()

    var isame, jsame bool
    var ioffset, joffset int

这里需要拿到 halfSize ，halfSize 其实就是入参 Cell 的孩子的格子的 size 。

复制代码
    if i&halfSize != 0 {
        // 位于后边一列，所以偏移量要加上一个格子
        ioffset = size
        isame = (i + size) < maxSize
    } else {
        // 位于左边一列，所以偏移量要减去一个格子
        ioffset = -size
        isame = (i - size) >= 0
    }

这里我们根据 halfSize 那一位是否为1来判断距离矩形的4个顶点哪个顶点近。这里还需要注意的是，如果 i + size 不能超过 maxSize，如果超过了，就不在同一个 face 上了。同理， i - size 也不能小于 0，小于0页不在同一个 face 上了。

j 轴判断原理和 i 完全一致。

复制代码
    if j&halfSize != 0 {
        // 位于上边一行，所以偏移量要加上一个格子
        joffset = size
        jsame = (j + size) < maxSize
    } else {
        // 位于下边一行，所以偏移量要减去一个格子
        joffset = -size
        jsame = (j - size) >= 0
    }

最后计算结果，先把入参的 Cell 先计算出来，然后在把它周围2个轴上的 Cell 计算出来。

复制代码

    results := []CellID{
        ci.Parent(level),
        cellIDFromFaceIJSame(f, i+ioffset, j, isame).Parent(level),
        cellIDFromFaceIJSame(f, i, j+joffset, jsame).Parent(level),
    }

如果 i，j 都在同一个 face 上，那么共顶点就肯定不是位于外切立方体的8个顶点上了。那么就可以再把第四个共顶点的 Cell 计算出来。

复制代码
    if isame || jsame {
        results = append(results, cellIDFromFaceIJSame(f, i+ioffset, j+joffset, isame && jsame).Parent(level))
    }

综上，完整的计算共顶点邻居的代码实现如下：

复制代码
func (ci CellID) VertexNeighbors(level int) []CellID {
    halfSize := sizeIJ(level + 1)
    size := halfSize << 1
    f, i, j, _ := ci.faceIJOrientation()

    fmt.Printf("halfsize 原始的值 = %v-%b\n", halfSize, halfSize)
    var isame, jsame bool
    var ioffset, joffset int

    if i&halfSize != 0 {
        // 位于后边一列，所以偏移量要加上一个格子
        ioffset = size
        isame = (i + size) < maxSize
    } else {
        // 位于左边一列，所以偏移量要减去一个格子
        ioffset = -size
        isame = (i - size) >= 0
    }
    if j&halfSize != 0 {
        // 位于上边一行，所以偏移量要加上一个格子
        joffset = size
        jsame = (j + size) < maxSize
    } else {
        // 位于下边一行，所以偏移量要减去一个格子
        joffset = -size
        jsame = (j - size) >= 0
    }

    results := []CellID{
        ci.Parent(level),
        cellIDFromFaceIJSame(f, i+ioffset, j, isame).Parent(level),
        cellIDFromFaceIJSame(f, i, j+joffset, jsame).Parent(level),
    }

    if isame || jsame {
        results = append(results, cellIDFromFaceIJSame(f, i+ioffset, j+joffset, isame && jsame).Parent(level))
    }

    return results
}

下面来举几个例子。

第一个例子是相同大小 Cell 。入参和调用者 Cell 都是相同 Level - 10 的。

复制代码
VertexNeighbors := cellID.Parent(10).VertexNeighbors(10)

// 11011011101111110011110000000000000000000000000000000000000000
3958610196388904960 // 右上角 
3958599201272627200 // 左上角
3958603599319138304 // 右下角
3958601400295882752 // 左下角

第二个例子是不是大小的 Cell 。调用者 Cell 是默认 Level - 30 的。

复制代码
VertexNeighbors := cellID.VertexNeighbors(10)

// 11011011101111110011110000000000000000000000000000000000000000
3958610196388904960 // 右下角
3958599201272627200 // 左下角
3958612395412160512 // 右上角
3958623390528438272 // 左上角

上面两个例子可以说明一个问题，同样是调用 VertexNeighbors(10) 得到的 Cell 都是 Level - 10 的，但是方向和位置是不同的。本质在它们共的顶点是不同的，所以生成出来的4个Cell生成方向也就不同。

在 C++ 的版本中，查找顶点邻居有一个限制：

1 2	复制代码 DCHECK_LT(level, this->level());

入参的 Level 必须严格的比要找的 Cell 的 Level 小才行。也就是说入参的 Cell 的格子面积大小要比 Cell 格子大小更小才行。但是在 Go 的版本实现中并没有这个要求，入参或大或小都可以。

下面这个举例，入参比 Cell 的 Level 小。（可以看到成都市已经小成一个点了）

复制代码
VertexNeighbors := cellID.Parent(10).VertexNeighbors(5)

3957538172551823360 // 右下角
3955286372738138112 // 左下角
3959789972365508608 // 右上角
3962041772179193856 // 左上角

下面这个举例，入参比 Cell 的 Level 大。（可以看到 Level 15 的面积已经很小了）

复制代码
VertexNeighbors := cellID.Parent(10).VertexNeighbors(15)


3958610197462646784 // 左下角
3958610195315163136 // 右下角
3958610929754570752 // 左上角
3958609463023239168 // 右上角

三. 全邻居

最后回来文章开头问的那个问题中。如何在四叉树上如何求希尔伯特曲线的邻居？经过前文的一些铺垫，再来看这个问题，也许读者心里已经明白该怎么做了。

查找全邻居有一个要求，就是入参的 Level 的面积必须要比调用者 Cell 的小或者相等。即入参 Level 值不能比调用者的 Level 小。因为一旦小了以后，邻居的 Cell 的面积变得巨大，很可能一个邻居的 Cell 里面就装满了原来 Cell 的所有邻居，那这样的查找并没有任何意义。

举个例子，如果入参的 Level 比调用者 Cell 的 Level 小。那么查找它的全邻居的时候，查出来会出现如下的情况：

1 2	复制代码 AllNeighbors := cellID.Parent(10).AllNeighbors(5)

这个时候是可以查找到全邻居的，但是可能会出现重叠 Cell 的情况，为何会出现这样的现象，下面再分析。

如果入参和调用者 Cell 的 Level 是相同的，那么查找到的全邻居就是文章开头说到的问题了。理想状态如下：

具体实现如下：

复制代码
func (ci CellID) AllNeighbors(level int) []CellID {
    var neighbors []CellID

    face, i, j, _ := ci.faceIJOrientation()

    // 寻找最左下角的叶子节点的坐标。我们需要规范 i，j 的坐标。因为入参 Level 有可能比调用者 Cell 的 Level 要大。
    size := sizeIJ(ci.Level())
    i &= -size
    j &= -size

    nbrSize := sizeIJ(level)

    for k := -nbrSize; ; k += nbrSize {
        var sameFace bool
        if k < 0 {
            sameFace = (j+k >= 0)
        } else if k >= size {
            sameFace = (j+k < maxSize)
        } else {
            sameFace = true
            // 上边邻居 和 下边邻居
            neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+k, j-nbrSize,
                j-size >= 0).Parent(level))
            neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+k, j+size,
                j+size < maxSize).Parent(level))
        }

        // 左边邻居，右边邻居，以及2个对角线上的顶点邻居
        neighbors = append(neighbors, cellIDFromFaceIJSame(face, i-nbrSize, j+k,
            sameFace && i-size >= 0).Parent(level))
        neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+size, j+k,
            sameFace && i+size < maxSize).Parent(level))

        // 这里的判断条件有2个用途，一是防止32-bit溢出，二是循环的退出条件，大于size以后也就不用再找了
        if k >= size {
            break
        }
    }

    return neighbors
}

上述代码简单的思路用注释写了。需要讲解的部分现在来讲解。

首先需要理解的是 nbrSize 和 size 的关系。为何会有 nbrSize ？因为入参 Level 是可以和调用者 Cell 的 Level 不一样的。入参的 Level 代表的 Cell 可大可小也可能相等。最终结果是以 nbrSize 格子大小来表示的，所以循环中需要用 nbrSize 来控制格子的大小。而 size 只是原来调用者 Cell 的格子大小。

循环中 K 的变化，当 K = -nbrSize 的时候，这个时候循环只会计算左边和右边的邻居。对角线上的顶点邻居其实也是左边邻居和右边邻居的一种特殊情况。接下来 K = 0，就会开始计算上边邻居和下边邻居了。K 不断增加，直到最后 K >= size ，最后一次循环内，会先计算一次左边和右边邻居，再 break 退出。

调用者的 Cell 在中间位置，所以想要跳过这个 Cell 到达另外一边(上下，或者左右)，那么就需要跳过 size 的大小。具体代码实现是 i + size 和 j + size 。

先看左右邻居的循环扫描方式。

左邻居是 i - nbrSize，j + k，k 在循环。这表示的就是左邻居的生成方式。它生成了左邻居一列。从左下角开始生成，一直往上生成到左上角。

右邻居是 i + size，j + k，k 在循环。这表示的就是右邻居的生成方式。它生成了右邻居一列。从右下角开始生成，一直往上生成到右上角。

再看上下邻居的循环扫描方式。

下邻居是 i + k，j - nbrSize，k 在循环。这表示的就是下邻居的生成方式。它生成了下邻居一行。从下邻居最左边开始生成，一直往上生成到下邻居最右边。

上邻居是 i + k，j + size，k 在循环。这表示的就是上邻居的生成方式。它生成了上邻居一行。从上邻居最左边开始生成，一直往上生成到上邻居最右边。

举例：

中间 Cell 的周围的全邻居是上图的 8 的相同 Level 的 Cell。

生成顺序用需要标识出来了。1，2，5，6，7，8 都是左右邻居生成出来的。3，4 是上下邻居生成出来的。

上面这个例子是都是 Level - 10 的 Cell 生成出来的。全邻居正好是8个。

复制代码
AllNeighbors := cellID.Parent(10).AllNeighbors(10)

3958601400295882752,
3958605798342393856,
3958603599319138304,
3958612395412160512,
3958599201272627200,
3958607997365649408,
3958623390528438272,
3958614594435416064

再举一个 Level 比调用者 Cell 的 Level 大的例子。

复制代码
AllNeighbors := cellID.Parent(10).AllNeighbors(11)

3958600575662161920,
3958606622976114688,
3958603324441231360,
3958611570778439680,
3958600025906348032,
3958607172731928576,
3958603874197045248,
3958613220045881344,
3958599476150534144,
3958608821999370240,
3958623115650531328,
3958613769801695232

它的全邻居生成顺序如下：

1，2，5，6，9，10，11，12 都是左右邻居，3，4，7，8 是上下邻居。我们可以看到左右邻居是从下往上生成的。上下邻居是从左往右生成的。

如果 Level 更大，比如 Level - 15 ，就会生成更多的邻居：

现在在解释一下如果入参 Level 比调用者 Cell 的 Level 小的情况。

举例，入参 Level = 9 。

复制代码
AllNeighbors := cellID.Parent(10).AllNeighbors(9)

3958589305667977216,
3958580509574955008,
3958580509574955008,
3958615693947043840,
3958598101760999424,
3958606897854021632,
3958624490040066048,
3958615693947043840

生成的全邻居如下：

可以看到本来有8个邻居的，现在只有6个了。其实生成出来的还是8个，只不过有2个重复了。重复的见图中深红色的两个 Cell。

为何会重叠？

中间调用者的 Level - 10 的 Cell 先画出来。

因为是 Level - 9 的，所以它是中间那个 Cell 的四分之一。

我们把 Level - 10 的两个上邻居也画出来。

可以看到上邻居 Up 和顶点邻居 up-right 都位于同一个 Level - 9 的 Cell 内了。所以上邻居和右上角的顶点邻居就都是同一个 Level - 9 的 Cell 。所以重叠了。同理，下邻居和右下的顶点邻居也重叠了。所以就会出现2个 Cell 重叠的情况。

而且中间也没有空出调用者 Cell 的位置。因为 i + size 以后，范围还在同一个 Level - 9 的 Cell 内。

如果 Level 更小，重叠情况又会发生变化。比如 Level - 5 。

复制代码
AllNeighbors := cellID.Parent(10).AllNeighbors(5)

3953034572924452864,
3946279173483397120,
3946279173483397120,
3957538172551823360,
3955286372738138112,
3957538172551823360,
3962041772179193856,
3959789972365508608

画在地图上就是

重叠的位置也发生了变化。

至此，查找邻居相关的算法都介绍完了。

空间搜索系列文章：

如何理解 n 维空间和 n 维时空
 高效的多维空间点索引算法 — Geohash 和 Google S2
Google S2 中的 CellID 是如何生成的？
Google S2 中的四叉树求 LCA 最近公共祖先
 神奇的德布鲁因序列
 四叉树上如何求希尔伯特曲线的邻居？

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: halfrost.com/go_s2_Hilbe…

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

Spring Cloud 服务第一次请求超时的优化

发表于 2017-11-19

问题背景

使用Spring Cloud组件构建的服务集群，在第一次请求时经常会出现timeout的情况，然而第二次就正常了。Spring Cloud版本为Dalston.SR4。

启动涉及到的相关服务：

gateway(zuul网关)
auth-Service（鉴权服务）
user-Service（用户服务）

测试的端点接口为：http:/login/oauth/token。服务之间的调用顺序为：gateway->auth-Service->user-Service。网关收到客户端的请求，转发请求到鉴权服务，鉴权服务对用户身份的核验是通过调用用户服，用户服务给鉴权服务返回身份校验的结果，鉴权服务将身份授权信息返回给gateway，gateway将最终的结果response返回给客户端。三个服务启动后，通过zipkin监控调用链路信息，可以看到第一次和第二次调用情况如下图所示：

首次调用端点

第二次调用信息

通过上面两次的链路监控信息截图，可以看到第一次的耗时是第二次的10多倍。遇到某些情况，很可能会出现第一次请求的超时。去官网看了下，主要原因是zuul网关和各个调用服务之间的Ribbon进行客户端负载均衡的Client懒加载，导致第一次的请求调用包括了创建Ribbon Client的时间。通过启动日志信息就可以发现：

Ribbon 客户端懒加载

下面分两部分解决这个问题，一是服务之间调用Ribbon的饥饿加载，对应上面的测试为auth-Service调用user-Service；二是zuul网关的饥饿加载。

ribbon的饥饿加载

经过调查发现，造成第一次auth-Service调用user-Service耗时长的原因主要是，Ribbon进行客户端负载均衡的服务实例并不是在服务启动的时候就初始化好的，而是在调用的时候才会去创建相应的服务实例。所以第一次调用user-Service耗时不仅仅包含发送HTTP请求的时间，还包含了创建Ribbon Client的时间，这样一来如果创建时间速度较慢，同时设置的请求超时又比较短的话，很容易就会出现耗时很长甚至超时的情况。在官网可以看到如下的配置说明：

Each Ribbon named client has a corresponding child Application Context that Spring Cloud maintains, this application context is lazily loaded up on the first request to the named client. This lazy loading behavior can be changed to instead
eagerly load up these child Application contexts at startup by specifying the names of the Ribbon clients.

意为Spring Cloud为每个Ribbon客户端维护了一个相对的子应用环境的上下文，应用的上下文在第一次请求到指定客户端的时候懒加载。不过可以通过如下配置进行修改：

yaml复制代码ribbon:
  eager-load:
    enabled: true
    clients: client1, client2, client3

按照如上的配置之后，发现鉴权服务启动时就将user服务的Ribbon客户端进行了加载。

user服务eager load

zuul网关的饥饿加载

上面小节解决了auth-Service调用user-Service的Ribbon客户端启动时饥饿加载。网关作为对外请求的入口，zuul内部使用Ribbon调用其他服务，Spring Cloud默认在第一次调用时懒加载Ribbon客户端。zuul同样需要维护一个相对的子应用环境的上下文，所以也需要启动时饥饿加载。

Zuul internally uses Ribbon for calling the remote url’s and Ribbon clients are by default lazily loaded up by Spring Cloud on first call. This behavior can be changed for Zuul using the following configuration and will result in the child
Ribbon related Application contexts being eagerly loaded up at application startup time.

具体配置如下：

yaml复制代码zuul:
  ribbon:
    eager-load:
      enabled: true

至此，优化完成，再次重启服务进行第一次请求，发现情况已经好多了，大家可以自己动手尝试改进一下。

总结

本文主要介绍了Spring Cloud的服务第一次请求超时的优化方法。首先介绍了问题的背景，并排查了问题造成的原因，主要是Ribbon客户端的懒加载；然后分别针对zuul网关和服务之间调用的Ribbon客户端进行配置，使其启动时便加载Ribbon客户端的相关上下文信息。最后想说的是，http调用毕竟还是性能远低于RPC。。🙂

参考

spring-cloud Dalston.SR4
Spring Cloud实战小贴士：Ribbon的饥饿加载(eager-load)模式

欢迎您扫一扫上面的微信公众号，aoho求索，订阅我的博客! 坚持原创技术分享，您的支持将鼓励我继续创作！

赏

微信打赏

支付宝打赏

本文作者： aoho
本文链接： blueskykong.com/2017/11/18/…
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

Spring Cloud 服务第一次请求超时的优化

发表于 2017-11-19

问题背景

使用Spring Cloud组件构建的服务集群，在第一次请求时经常会出现timeout的情况，然而第二次就正常了。Spring Cloud版本为Dalston.SR4。

启动涉及到的相关服务：

gateway(zuul网关)
auth-Service（鉴权服务）
user-Service（用户服务）

测试的端点接口为：http:/login/oauth/token。服务之间的调用顺序为：gateway->auth-Service->user-Service。网关收到客户端的请求，转发请求到鉴权服务，鉴权服务对用户身份的核验是通过调用用户服，用户服务给鉴权服务返回身份校验的结果，鉴权服务将身份授权信息返回给gateway，gateway将最终的结果response返回给客户端。
三个服务启动后，通过zipkin监控调用链路信息，可以看到第一次和第二次调用情况如下图所示：

not-eager-1st

second

lazy-load

下面分两部分解决这个问题，一是服务之间调用Ribbon的饥饿加载，对应上面的测试为auth-Service调用user-Service；二是zuul网关的饥饿加载。

ribbon的饥饿加载

Each Ribbon named client has a corresponding child Application Context that Spring Cloud maintains, this application context is lazily loaded up on the first request to the named client. This lazy loading behavior can be changed to instead eagerly load up these child Application contexts at startup by specifying the names of the Ribbon clients.

复制代码ribbon:
  eager-load:
    enabled: true
    clients: client1, client2, client3

按照如上的配置之后，发现鉴权服务启动时就将user服务的Ribbon客户端进行了加载。

zuul网关的饥饿加载

Zuul internally uses Ribbon for calling the remote url’s and Ribbon clients are by default lazily loaded up by Spring Cloud on first call. This behavior can be changed for Zuul using the following configuration and will result in the child Ribbon related Application contexts being eagerly loaded up at application startup time.

具体配置如下：

复制代码zuul:
  ribbon:
    eager-load:
      enabled: true

至此，优化完成，再次重启服务进行第一次请求，发现情况已经好多了，大家可以自己动手尝试改进一下。

总结

订阅最新消息，关注公众号，加入我的星球。

参考

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

基于maven构建多模块化的SSM框架构建多模块化项目

发表于 2017-11-19

之前写过一篇SSM的框架整合；项目开发框架-SSM；对SSM中的一些点进行了学习记录,那篇文章也是基于maven来创建的，那么为什么又要搞一篇呢？以我当前公司项目A来说，A项目包括前台、后台子项目【前台用于对外，后台用于管理】，如果按照前一篇文章的那种方式来进行，我们就需要建立两个单独的框架来进行开发，一样的拥有一套从dmo实体类包，util包，dao包，service包以及controller包，这种结构非常的紧凑和独立，但是问题在于，我们前后台使用的是同一个库，dmo、util、dao以及service中都会存在大量重复的代码，很多基础方法无法公用；另外一个原因是，我们还需要包装一些接口向外提供服务【不局限于我们自己的这两个系统】，这样一来，我们又需要再去抽离一次service，非常不方便。因此就使用maven来构建多模块项目，对于util、dao、rpc服务接口以及service进行模块化分离，这样一来，这些模块就可以对我们自己的前后台以及外部提供一些公关的服务，避免了大量的代码重复，也方便管理。

Maven多模块项目，通过合理的模块拆分，实现代码的复用，便于维护和管理。尤其是一些开源框架，也是采用多模块的方式，提供插件集成，用户可以根据需要配置指定的模块。

构建多模块化项目

基于maven构建多模块化项目主要依赖于maven可以实现父子项目的关系，子项目可以父项目的依赖Jar包，这样也方便我们去共同管理jar依赖，但是由于一个项目中毕竟会有很多人进行协同开发，在此过程中如果没有很好的约束，对于这种多模块化来说，解决jar包的冲突也很繁琐。

新建一个父工程

1.创建maven项目

step1:(新建maven项目)
step2:(勾选创建一个简单工程)
step3:(填写工程配置：主要是打包方式要选择pom方式)

点击finish，父项目就创建成功了！
2.创建子项目

step1:(右击父项目->maven->New Maven Model Project)
step2:
step3:(一般情况下，我们项目中的util、dao、service都是可以直接分出来的，这里我们选择quickstart来构建,用于生产后面的jar包提供服务。我们的web子项目选择webapp来构建，用于配置文件、jsp文件/ftl/html/js/css等界面资源文件维护)

点击finish，完成子模块的构建！构建之后的项目结构为：

此时，我们的父模块中已经有了子模块的项目标识，新建的dao模块中不包括webapp此类的文件夹。那么这时就可以将我们的数据访问相关的类和接口都放在这个子模块中，如果其他项目需要使用，我们直接引入就行，引入方式如下（下面截图是从service模块引入dao模块的，这里的groupId，artifactId，version我们可以在dao的pom文件中直接复制使用）：

（上面新建的过程只作为演示而用，下面的引入和上面的新建项目并非一个项目）
其他的模块构建和dao的构建过程是一样的，这里就不一一构建了。源码地址在下面，解压之后，以maven项目方式导入，修改下数据库配置文件应该就可以直接运行了（当前项目基于jdk1.7写的，有的小伙伴如果用1.8的话，应该会出现jsp无法编译的一个错误）；源码附件中还有一个setting文件,阿里的，个人觉得用起来很不错，也推荐给大家!

源码地址：download.csdn.net/download/si…
【这个是csdn的地址，现在资源上传还必需要选择C币，小伙伴如果没有csdn账户或者C币不足，可以在文章留言区留言，留下邮箱，我发给你们】

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有