作者介绍：熊训德 腾讯云工程师

Hbase 的 WAL 机制是保证 hbase 使用 lsm 树存储模型把随机写转化成顺序写，并从内存 read 数据，从而提高大规模读写效率的关键一环。wal 的多生产者单消费者的线程模型让wal的写入变得安全而高效。

在文章《WAL在RegionServer调用过程》中从代码层面阐述了一个 client 的“写”操作是如何到达Hbase的RegionServer，又是如何真正地写入到 wal(FSHLog) 文件，再写入到 memstore 。但是 hbase 是支持 mvcc 机制的存储系统，本文档将说明
RegionServer 是如何把多个客户端的“写”操作安全有序地落地日志文件，又如何让 client 端优雅地感知到已经真正的落地。

wal 为了高效安全有序的写入，笔者认为最关键的两个机制是 wal 中使用的线程模型和多生产者单消费者模型。

线程模型

其线程模型主要实现实在FSHLog中，FSHLog是WAL接口的实现类，实现了最关键的apend()和sync()方法，其模型如图所示：

这个图主要描述了HRegion中调用append和sync后,hbase的wal线程流转模型。最左边是有多个client提交到HRegion的append和sync操作。

当调用append后WALEdit和WALKey会被封装成FSWALEntry类进而再封装成RinbBufferTruck类放入一个线程安全的Buffer(LMAX Disruptor RingBuffer)中。

当调用sync后会生成一个SyncFuture进而封装成RinbBufferTruck类同样放入这个Buffer中，然后工作线程此时会被阻塞等待被notify()唤醒。在最右边会有一个且只有一个线程专门去处理这些RinbBufferTruck，如果是FSWALEntry则写入hadoop sequence文件。因为文件缓存的存在，这时候很可能client数据并没有落盘。所以进一步如果是SyncFuture会被批量的放到一个线程池中，异步的批量去刷盘,刷盘成功后唤醒工作线程完成wal。

源码分析

下面将从源码角度分析其中具体实现过程和细节。

工作线程中当HRegion准备好一个行事务“写”操作的，WALEdit，WALKey后就会调用FSHLog的append方法：

FSHLog的append方法首先会从LAMX Disruptor RingbBuffer中拿到一个序号作为txid(sequence)，然后把WALEdit,WALKey和sequence等构建一个FSALEntry实例entry，并把entry放到ringbuffer中。而entry以truck(RingBufferTruck，ringbuffer实际存储类型)通过sequence和ringbuffer一一对应。

如果client设置的持久化等级是USER_DEFAULT，SYNC_WAL或FSYNC_WAL，那么工作线程的HRegion还将调用FSHLog的sync()方法：

追踪代码可以分析出Sync()方法会往ringbuffer中放入一个SyncFuture对象，并阻塞等待完成(唤醒)。

像模型图中所展示的多个工作线程封装后拿到由ringbuffer生成的sequence后作为生产者放入ringbuffer中。在FSHLog中有一个私有内部类RingBufferEventHandler类实现了LAMX Disruptor的EventHandler接口，也即是实现了OnEvent方法的ringbuffer的消费者。Disruptor通过 java.util.concurrent.ExecutorService 提供的线程来触发 Consumer 的事件处理，可以看到hbase的wal中只启了一个线程，从源码注释中也可以看到RingBufferEventHandler在运行中只有单个线程。由于消费者是按照sequence的顺序刷数据，这样就能保证WAL日志并发写入时只有一个线程在真正的写入日志文件的可感知的全局唯一顺序。

RingBufferEventHandler类的onEvent()(一个回调方法)是具体处理append和sync的方法。在前面说明过wal使用RingBufferTruck来封装WALEntry和SyncFuture(如下图源码)，在消费线程的实际执行方法onEvent()中就是被ringbuffer通知一个个的从ringbfer取出RingBufferTruck，如果是WALEntry则使用当前HadoopSequence文件writer写入文件（此时很可能写的是文件缓存），如果是SyncFuture则简单的轮询处理放入SyncRunner线程异步去把文件缓存中数据刷到磁盘。

这里再加一个异步操作去真正刷文件缓存的原因wal源码中有解释：刷磁盘是很费时的操作，如果每次都同步的去刷client的回应比较快，但是写效率不高，如果异步刷文件缓存，写效率提高但是友好性降低，在考虑了写吞吐率和对client友好回应平衡后，wal选择了后者，积累了一定量(通过ringbuffer的sequence)的缓存再刷磁盘以此提高写效率和吞吐率。这个决策从hbase存储机制最初采用lsm树把随机写转换成顺序写以提高写吞吐率，可以看出是目标一致的。

这部分源码可以看到RingBufferTruck类的结构，从注释可以看到选择SyncFuture和FSWALEntry一个放入ringbuffer中。

这部分源码可以看到append的最终归属就是根据sequence有序的把FSWALEntry实例entry写入HadoopSequence文件。这里有序的原因是多工作线程写之前通过ringbuffer线程安全的CAS得到一个递增的sequence，ringbuffer会根据sequence取出FSWALEntry并落盘。这样做其实只有在得到递增的sequence的时候需要保证线程安全，而java的CAS通过轮询并不用加锁，所以效率很高。具体有关ringbuffer说明和实现可以参考LMAX Disruptor文档。

这部分源码是说明sync操作的SyncFuture会被提交到SyncRunner中，这里可以注意SyncFuture实例其实并不是一个个提交到SyncRunner中执行的，而是以syncFutures(数组,多个SyncFuture实例)方式提交的。下面这部分源码是注释中说明批量刷盘的决策。

SyncRunner是一个线程，wal实际有一个SyncRunner的线程组，专门负责之前append到文件缓存的刷盘工作。

SyncRunner的线程方法（run()）负责具体的刷写文件缓存到磁盘的工作。首先去之前提交的synceFutues中拿到其中sequence最大的SyncFuture实例，并拿到它对应ringbuffer的sequence。再去比对当前最大的sequence，如果发现比当前最大的sequence则去调用releaseSyncFuture()方法释放synceFuture，实际就是notify通知正被阻塞的sync操作，让工作线程可以继续往下继续。

前面解释了sequence是根据提交顺序过来的，并且解释了append到文件缓存的时候也是全局有序的，所以这里取最大的去刷盘，只要最大sequence已经刷盘，那么比这个sequence的也就已经刷盘成功。最后调用当前HadoopSequence文件writer刷盘，并notify对应的syncFuture。这样整个wal写入也完成了。

小结

Hbase的WAL机制是保证hbase使用lsm树存储模型把随机写转化成顺序写，并从内存read数据，从而提高大规模读写效率的关键一环。wal的多生产者单消费者的线程模型让wal的写入变得安全而高效，本文档从源码入手分析了其线程模型为以后更好开发和研究hbase其他相关知识奠定基础。

相关推荐

Hbase的WAL在RegionServer基本调用过程
HBase跨版本数据迁移总结
Hbase写入hdfs源码分析

本文转载自: 掘金

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

一. 点睛

在前面的文章SpringMvc4.x高级配置(三):服务器端推送技术之SSE中已经介绍了服务器端推送技术的第一种方案，下面演示第二种服务器端推送技术，基于Servlet3.0+异步方法处理。

二. 示例

1.开启异步方法支持

在文件WebInitializer的方法onStartup末尾增加以下代码开启异步方法支持，代码如下：

1

复制代码servlet.setAsyncSupported(true);//①

添加完成之后的代码如下所示：

1
2
3
4
5

复制代码 
Dynamic servlet = servletContext.addServlet("dispatcher", new DispatcherServlet(ctx)); //③
     servlet.addMapping("/");
     servlet.setLoadOnStartup(1);
     servlet.setAsyncSupported(true);//①

代码解释：

① 此句开启异步方法支持。

2. 演示控制器

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

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

import org.light4j.springMvc4.service.PushService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.ResponseBody;
import org.springframework.web.context.request.async.DeferredResult;

@Controller
public class AysncController {
    @Autowired
    PushService pushService; //①

    @RequestMapping("/defer")
    @ResponseBody
    public DeferredResult<String> deferredCall() { //②
        return pushService.getAsyncUpdate();
    }
}

代码解释：

异步任务实现是通过控制器从另外一个线程返回一个DeferredResult，这里的DeferredResult是从pushService中获得的。
① 定时任务，定时更新DeferredResult。
② 返回给客户端DeferredResult。

3. 定时任务

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

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

import org.springframework.scheduling.annotation.Scheduled;
import org.springframework.stereotype.Service;
import org.springframework.web.context.request.async.DeferredResult;

@Service
public class PushService {
    private DeferredResult<String> deferredResult; //①

    public DeferredResult<String> getAsyncUpdate() {
        deferredResult = new DeferredResult<String>();
        return deferredResult;
    }

    @Scheduled(fixedDelay = 5000)
    public void refresh() {
        if (deferredResult != null) {
            deferredResult.setResult(new Long(System.currentTimeMillis()).toString());
        }
    }
}

代码解释：

① 在PushService里产生DeferredResult给控制器使用，通过@Scheduled注解的方法定时更新DeferredResult

4. 演示页面

在src/main/resources下新建async.jsp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

复制代码<%@ 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>servlet async support</title>

</head>
<body>

<script type="text/javascript" src="assets/js/jquery.js"></script>
<script type="text/javascript">

    deferred();//①

    function deferred(){
        $.get('defer',function(data){
            console.log(data); //②
            deferred(); //③
        });
    }

</script>
</body>
</html>

代码解释：

此处的代码使用的是JQuery的Ajax请求，所以没有浏览器兼容性问题。
① 页面打开就向后台发送请求。
② 在控制台输出服务端推送的数据。
③ 一次请求完成后再向后台推送数据。

5. 配置

在文件MyMvcConfig上使用注解@EnableScheduling开启计划任务的支持，代码如下：

1
2
3
4
5
6
7

复制代码@Configuration
@EnableWebMvc// ①
@EnableScheduling
@ComponentScan("org.light4j.springMvc4")
public class MyMvcConfig extends WebMvcConfigurerAdapter {

}

在文件MyMvcConfig的方法addViewControllers添加viewController映射访问演示页面async.jsp，代码如下：

1

复制代码registry.addViewController("/async").setViewName("/async");

添加完成之后的代码如下所示：

1
2
3
4
5
6
7
8
9

复制代码
@Override
public void addViewControllers(ViewControllerRegistry registry) {
    registry.addViewController("/index").setViewName("/index");
    registry.addViewController("/toUpload").setViewName("/upload");
    registry.addViewController("/converter").setViewName("/converter");
    registry.addViewController("/sse").setViewName("/sse");
    registry.addViewController("/async").setViewName("/async");
}

6. 运行

访问http://localhost/springMvc4.x-servlet3/async，可以看到网络不断的在获取服务器端推送的消息，如下图所示：

查看浏览器控制台可以看到不断的在打印消息,如下图所示：

三. 源代码示例：

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

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

本文转载自: 掘金

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

最近遇到Spring-boot的多个profile切换问题，需求是这样的：微服务中引入了Spring Cloud Config，服务启动的时候，从Config Server中读取该实例对应的配置信息。本地开发环境可能使用的profile是default，到了集成测试环境就需要切换到jenkins，到了预发布环境又变成了prod。多个profile需要之间可以切换。

这边设置的时候还走了点弯路，先是探索了一遍pom的profile，后来才到Spring-boot的配置文件。

这两部分实现的功能不太一样，本文将会具体讲下这两部分。

1. profile之Maven

maven切换profile的命令很简单，加上-P参数指定你的profile，如指定prod：

1

复制代码mvn clean package -P prod

maven使用名字为prod的profile来打包，即所有的配置文件都使用生产环境。
下面看下pom中的profiles：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

复制代码 <profiles>
   <profile>
      <id>dev</id>
      <activation>
         <activeByDefault>true</activeByDefault>
      </activation>
      <properties>
         <profileActive>dev</profileActive>
      </properties>
      <dependencies>
         <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-devtools</artifactId>
            <optional>true</optional>
         </dependency>
      </dependencies>
   </profile>
   <profile>
      <id>prod</id>
      <dependencies>
         <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-undertow</artifactId>
         </dependency>
      </dependencies>
      <properties>
         <profileActive>prod</profileActive>
      </properties>
   </profile>
</profiles>

对于resources的配置如下：

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

复制代码 
<build>
      <resources>
          <resource>
              <directory>src/main/resources</directory>
              <filtering>true</filtering>
              <!-- 过滤掉所有配置文件-->
              <excludes>
                  <exclude>application-dev.yml</exclude>
                  <exclude>application-prod.yml</exclude>
              </excludes>
          </resource>
          <resource>
              <filtering>true</filtering>
              <directory>src/main/resources</directory>
              <!--根据profile中的变量profileActive指定对应的配置文件-->
              <includes>
                  <include>application-${profileActive}.yml</include>
              </includes>
          </resource>
      </resources>
  </build>

上面的两段pom配置相结合，当指定profile为prod时，环境变量profileActive的属性值变为prod。指定打包时，包含application-prod.yml。

所以当你有多套配置文件，可以动态根据mvn命令的参数-P动态指定你所需要加载的配置文件。

2. profile之Spring boot

Profile是Spring boot用来针对不同环境对不同配置提供支持的,全局Profile配置使用。
application-{profile}.yml 如:application-yml。

spring通过配置spring.profiles.active指定激活某个具体的profile。除了spring.profiles.active来激活一个或者多个profile之外，还可以用spring.profiles.include来叠加profile。

1

复制代码spring.profiles.include: prod,dev

下面看一下我们的application.yml中包含的配置：

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

复制代码
spring:
  profiles:
    active: dev
---
#开发环境配置
spring:
  profiles: dev
server:
  port: 8080
---
#测试环境配置
spring:
  profiles: test
server:
  port: 8081
---
#生产环境配置
spring:
  profiles: prod
server:
  port: 8082

application.yml文件分为四部分，使用一组(—)来作为分隔符。第一部分，通用配置部分，表示三个环境都通用的属性，默认激活了dev的profile；后面三部分分别表示不同的环境，指定了不同的port。

部署到服务器的话，正常会打成jar包，加上参数
--spring.profiles.active=test指定加载哪个环境的配置。

在IDE中也可以直接配置激活的profile。

idea配置

idea配置profile

3. config server的配置

这节讲下与Spring cloud config的结合使用。既然使用了config server，动态配置这块基本就由配置服务器完成了。配置服务器中对该服务指定多个profile。config Server中的配置优先于本地配置，当服务启动时，根据激活的profile，去配置服务器拉取其对应的配置。

既然知道了上面的主要流程，就可以明白我们的需求其实是要在服务启动时指定激活的profile。所以上面一节关于Spring boot的profile动态配置，我们的问题就能解决了。但上面讲到的是jar包启动时指定--spring.profiles.active，实际都是微服务的容器化部署，服务通过容器直接启动jar包，这样就需要容器启动的时候能够动态指定active profile，所以上面的配置改一下，如下：

1
2
3

复制代码spring:
  profiles:
    active: ${ACTIVE_PROFILE:dev}

容器启动截图

从容器的启动截图来看，指定了docker run -d -e ACTIVE_PROFILE=exp ...后，active profile 变味了exp，并且从config server中拉取对应的是gatewayserver的exp配置。

4. 总结

本文主要写了Spring-boot配置服务器切换profile。首先描述了需求背景，然后是对maven pom中profile进行了探索与讲解，其次是讲解了Spring-boot中的profile切换，最后结合config server实现容器部署微服务的profile。笔者最开始一直认为通过pom的profile切换就可以设置服务启动的profile，经过一番探索，发现与配置服务器结合好像并不需要pom的profile这么繁琐，结合配置服务器可以更方便的使用Spring boot的profile。

参考

1. 详解Spring Boot Profiles 配置和使用
2. [Spring Boot 系列] 集成maven和Spring boot的profile功能

本文转载自: 掘金

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

大数据是使用工具和技术处理大量和复杂数据集合的术语。能够处理大量数据的技术称为MapReduce。

何时使用MapReduce

MapReduce特别适合涉及大量数据的问题。它通过将工作分成更小的块，然后可以被多个系统处理。由于MapReduce将一个问题分片并行工作，与传统系统相比，解决方案会更快。

大概有如下场景会应用到MapReduce：

1 计数和统计
2 整理
3 过滤
4 排序

Apache Hadoop

在本文中，我们将使用Apache Hadoop。

开发MapReduce解决方案，推荐使用Hadoop，它已经是事实上的标准，同时也是开源免费的软件。
另外在Amazon，Google和Microsoft等云提供商租用或搭建Hadoop集群。

还有其他多个优点：

可扩展：可以轻松清加新的处理节点，而无需更改一行代码
成本效益：不需要任何专门和奇特的硬件，因为软件在正常的硬件都运行正常
灵活：无模式。可以处理任何数据结构 ，甚至可以组合多个数据源，而不会有很多问题。
容错：如果有节点出现问题，其它节点可以接收它的工作，整个集群继续处理。

另外，Hadoop容器还是支持一种称为“流”的应用程序，它为用户提供了选择用于开发映射器和还原器脚本语言的自由度。

本文中我们将使用PHP做为主开发语言。

Hadoop安装

Apache Hadoop的安装配置超出了本文范围。您可以根据自己的平台，在线轻松找到很多文章。为了保持简单，我们只讨论大数据相关的事。

映射器（Mapper）

映射器的任务是将输入转换成一系列的键值对。比如在字计数器的情况下，输入是一系列的行。我们按单词将它们分开，把它们变成键值对（如key:word,value:1）,看起来像这样：

the 1
water 1
on 1
on 1
water 1
on 1
… 1

然后，这些对然后被发送到reducer以进行下一步骤。

reducer

reducer的任务是检索（排序）对，迭代并转换为所需输出。 在单词计数器的例子中，取单词数（值），并将它们相加得到一个单词（键）及其最终计数。如下：

water 2
the 1
on 3

mapping和reducing的整个过程看起来有点像这样，请看下列之图表：

使用PHP做单词计数器

我们将从MapReduce世界的“Hello World”的例子开始，那就是一个简单的单词计数器的实现。 我们将需要一些数据来处理。我们用已经公开的书Moby Dick来做实验。

执行以下命令下载这本书：

1

复制代码wget http://www.gutenberg.org/cache ... 1.txt

在HDFS（Hadoop分布式文件系统）中创建一个工作目录

1

复制代码hadoop dfs -mkdir wordcount

我们的PHP代码从mapper开始

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

复制代码#!/usr/bin/php
<?php
    // iterate through lines
    while($line = fgets(STDIN)){
        // remove leading and trailing
        $line = ltrim($line);
        $line = rtrim($line);

        // split the line in words
        $words = preg_split('/\s/', $line, -1, PREG_SPLIT_NO_EMPTY);
        // iterate through words
        foreach( $words as $key ) {
            // print word (key) to standard output
            // the output will be used in the
            // reduce (reducer.php) step
            // word (key) tab-delimited wordcount (1)
            printf("%s\t%d\n", $key, 1);
        }
    }
?>

下面是 reducer 代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

复制代码#!/usr/bin/php
<?php
    $last_key = NULL;
    $running_total = 0;

    // iterate through lines
    while($line = fgets(STDIN)) {
        // remove leading and trailing
        $line = ltrim($line);
        $line = rtrim($line);
        // split line into key and count
        list($key,$count) = explode("\t", $line);
        // this if else structure works because
        // hadoop sorts the mapper output by it keys
        // before sending it to the reducer
        // if the last key retrieved is the same
        // as the current key that have been received
        if ($last_key === $key) {
            // increase running total of the key
            $running_total += $count;
        } else {
            if ($last_key != NULL)
                // output previous key and its running total
                printf("%s\t%d\n", $last_key, $running_total);
            // reset last key and running total
            // by assigning the new key and its value
            $last_key = $key;
            $running_total = $count;
        }
    }
?>

你可以通过使用某些命令和管道的组合来在本地轻松测试脚本。

1

复制代码head -n1000 pg2701.txt | ./mapper.php | sort | ./reducer.php

我们在Apache Hadoop集群上运行它：

1
2
3
4
5

复制代码hadoop jar /usr/hadoop/2.5.1/libexec/lib/hadoop-streaming-2.5.1.jar \
 -mapper "./mapper.php"
 -reducer "./reducer.php"
 -input "hello/mobydick.txt"
 -output "hello/result"

输出将存储在文件夹hello / result中，可以通过执行以下命令查看

1

复制代码hdfs dfs -cat hello/result/part-00000

计算年均黄金价格

下一个例子是一个更实际的例子，虽然数据集相对较小，但是相同的逻辑可以很容易地应用于具有数百个数据点的集合上。 我们将尝试计算过去五十年的黄金年平均价格。

我们下载数据集：

1

复制代码wget https://raw.githubusercontent. ... a.csv

在HDFS（Hadoop分布式文件系统）中创建一个工作目录

1

复制代码hadoop dfs -mkdir goldprice

将已下载的数据集复制到HDFS

1

复制代码hadoop dfs -copyFromLocal ./data.csv goldprice/data.csv

我的reducer看起来像这样

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

复制代码#!/usr/bin/php
<?php
    // iterate through lines
    while($line = fgets(STDIN)){
        // remove leading and trailing
        $line = ltrim($line);
        $line = rtrim($line);

        // regular expression to capture year and gold value
        preg_match("/^(.*?)\-(?:.*),(.*)$/", $line, $matches);

        if ($matches) {
            // key: year, value: gold price
            printf("%s\t%.3f\n", $matches[1], $matches[2]);
        }
    }
?>

reducer也略有修改，因为我们需要计算项目数量和平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

复制代码#!/usr/bin/php
<?php
    $last_key = NULL;
    $running_total = 0;
    $running_average = 0;
    $number_of_items = 0;

    // iterate through lines
    while($line = fgets(STDIN)) {
        // remove leading and trailing
        $line = ltrim($line);
        $line = rtrim($line);

        // split line into key and count
        list($key,$count) = explode("\t", $line);

        // if the last key retrieved is the same
        // as the current key that have been received
        if ($last_key === $key) {
            // increase number of items
            $number_of_items++;
            // increase running total of the key
            $running_total += $count;
            // (re)calculate average for that key
            $running_average = $running_total / $number_of_items;
        } else {
            if ($last_key != NULL)
                // output previous key and its running average
                printf("%s\t%.4f\n", $last_key, $running_average);
            // reset key, running total, running average
            // and number of items
            $last_key = $key;
            $number_of_items = 1;
            $running_total   = $count;
            $running_average = $count;
        }
    }

    if ($last_key != NULL)
        // output previous key and its running average
        printf("%s\t%.3f\n", $last_key, $running_average);
?>

像单词统计样例一样，我们也可以在本地测试

1

复制代码head -n1000 data.csv | ./mapper.php | sort | ./reducer.php

最终在hadoop集群上运行它

1
2
3
4
5

复制代码hadoop jar /usr/hadoop/2.5.1/libexec/lib/hadoop-streaming-2.5.1.jar \
 -mapper "./mapper.php"
 -reducer "./reducer.php"
 -input "goldprice/data.csv"
 -output "goldprice/result"

查看平均值

1

复制代码hdfs dfs -cat goldprice/result/part-00000

小奖励：生成图表

我们经常会将结果转换成图表。 对于这个演示，我将使用gnuplot，你可以使用其它任何有趣的东西。

首先在本地返回结果：

1

复制代码hdfs dfs -get goldprice/result/part-00000 gold.dat

创建一个gnu plot配置文件（gold.plot）并复制以下内容

1
2
3
4
5
6
7
8
9
10

复制代码# Gnuplot script file for generating gold prices
set terminal png
set output "chart.jpg"
set style data lines
set nokey
set grid
set title "Gold prices"
set xlabel "Year"
set ylabel "Price"
plot "gold.dat"

生成图表：

1

复制代码gnuplot gold.plot

这会生成一个名为chart.jpg的文件。看起来像这样：

译者：杜江
作者：Glenn De Backer
原文：www.simplicity.be/article/big…

本文转载自: 掘金

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

最近遇到Spring-boot的多个profile切换问题，需求是这样的：微服务中引入了Spring Cloud Config，服务启动的时候，从Config Server中读取该实例对应的配置信息。本地开发环境可能使用的profile是default，到了集成测试环境就需要切换到jenkins，到了预发布环境又变成了prod。多个profile需要之间可以切换。

这边设置的时候还走了点弯路，先是探索了一遍pom的profile，后来才到Spring-boot的配置文件。

这两部分实现的功能不太一样，本文将会具体讲下这两部分。

1. profile之Maven

maven切换profile的命令很简单，加上-P参数指定你的profile，如指定prod：

1

复制代码 mvn clean package -P prod

maven使用名字为prod的profile来打包，即所有的配置文件都使用生产环境。
下面看下pom中的profiles：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

复制代码 <profiles>
   <profile>
      <id>dev</id>
      <activation>
         <activeByDefault>true</activeByDefault>
      </activation>
      <properties>
         <profileActive>dev</profileActive>
      </properties>
      <dependencies>
         <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-devtools</artifactId>
            <optional>true</optional>
         </dependency>
      </dependencies>
   </profile>

   <profile>
      <id>prod</id>
      <dependencies>
         <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-undertow</artifactId>
         </dependency>
      </dependencies>
      <properties>
         <profileActive>prod</profileActive>
      </properties>
   </profile>
</profiles>

对于resources的配置如下：

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

复制代码
     <build>
        <resources>
            <resource>
                <directory>src/main/resources</directory>
                <filtering>true</filtering>
                <!-- 过滤掉所有配置文件-->
                <excludes>
                    <exclude>application-dev.yml</exclude>
                    <exclude>application-prod.yml</exclude>
                </excludes>
            </resource>
            <resource>
                <filtering>true</filtering>
                <directory>src/main/resources</directory>
                <!--根据profile中的变量profileActive指定对应的配置文件-->
                <includes>
                    <include>application-${profileActive}.yml</include>
                </includes>
            </resource>
        </resources>
    </build>

上面的两段pom配置相结合，当指定profile为prod时，环境变量profileActive的属性值变为prod。指定打包时，包含application-prod.yml。

所以当你有多套配置文件，可以动态根据mvn命令的参数-P动态指定你所需要加载的配置文件。

2. profile之Spring boot

Profile是Spring boot用来针对不同环境对不同配置提供支持的,全局Profile配置使用。
application-{profile}.yml 如:application-yml。

spring通过配置spring.profiles.active指定激活某个具体的profile。除了spring.profiles.active来激活一个或者多个profile之外，还可以用spring.profiles.include来叠加profile。

1

复制代码spring.profiles.include: prod,dev

下面看一下我们的application.yml中包含的配置：

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

复制代码
spring:
  profiles:
    active: dev
---
#开发环境配置
spring:
  profiles: dev
server:
  port: 8080
---
#测试环境配置
spring:
  profiles: test
server:
  port: 8081
---
#生产环境配置
spring:
  profiles: prod

server:
  port: 8082

application.yml文件分为四部分，使用一组(—)来作为分隔符。第一部分，通用配置部分，表示三个环境都通用的属性，默认激活了dev的profile；后面三部分分别表示不同的环境，指定了不同的port。

部署到服务器的话，正常会打成jar包，加上参数
--spring.profiles.active=test指定加载哪个环境的配置。

在IDE中也可以直接配置激活的profile。

entry

profile

3. config server的配置

这节讲下与Spring cloud config的结合使用。既然使用了config server，动态配置这块基本就由配置服务器完成了。配置服务器中对该服务指定多个profile。config Server中的配置优先于本地配置，当服务启动时，根据激活的profile，去配置服务器拉取其对应的配置。

既然知道了上面的主要流程，就可以明白我们的需求其实是要在服务启动时指定激活的profile。所以上面一节关于Spring boot的profile动态配置，我们的问题就能解决了。但上面讲到的是jar包启动时指定--spring.profiles.active，实际都是微服务的容器化部署，服务通过容器直接启动jar包，这样就需要容器启动的时候能够动态指定active profile，所以上面的配置改一下，如下：

1
2
3

复制代码spring:
  profiles:
    active: ${ACTIVE_PROFILE:dev}

startup

从容器的启动截图来看，指定了docker run -d -e ACTIVE_PROFILE=exp ...后，active profile 变味了exp，并且从config server中拉取对应的是gatewayserver的exp配置。

4. 总结

本文主要写了Spring-boot配置服务器切换profile。首先描述了需求背景，然后是对maven pom中profile进行了探索与讲解，其次是讲解了Spring-boot中的profile切换，最后结合config server实现容器部署微服务的profile。笔者最开始一直认为通过pom的profile切换就可以设置服务启动的profile，经过一番探索，发现与配置服务器结合好像并不需要pom的profile这么繁琐，结合配置服务器可以更方便的使用Spring boot的profile。

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

xq

参考

1. 详解Spring Boot Profiles 配置和使用
2. [Spring Boot 系列] 集成maven和Spring boot的profile功能

本文转载自: 掘金

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

LSTM，全称为「长短期记忆」，是一种「时间递归神经网络」(RNN)。LSTM 适合于处理和预测时间序列中间隔和延迟非常长的重要事件。

通俗来讲，LSTM 非常适合用来预测与时间相关的数据，在文本处理方面更是应用广泛 (可以理解为某个词在 t 时间点出现，预测 t+1 时间点最有可能出现哪个词)；往专业上讲，呃，我完全不懂。

但这不妨碍我们去使用 LSTM 去做点有趣的事情，好比你不知道电饭煲是怎么做出来的，但你总会煮饭是吧。接下来我们使用 Keras 这个强大的「电饭煲」来煮几煲好吃的饭。

自动写代码

这有点标题党，但其实还是个人工智障。比如你在写代码的时候，写下了这么一段：

1
2
3

cpp复制代码def afunc(i):
    i = i + 1
    retur

下一个字符很自然应该是「n」对不对。将一个个字符转化为数字序列作为输入，这些字符组成的序列的下一个字符作为输出，比如，序列长度为 3 的话，return 这个字符序列，可以转化为：

1
2
3

xl复制代码r,e,t -> u
e,t,u -> r
t,u,r -> n

然后将这些单个字符分别映射为数字：

1
2
3
4
5

xl复制代码r -> 1
e -> 2
t -> 3
u -> 4
n -> 5

变成这种形式：

1
2
3

ini复制代码x1 = [1,2,3], y1 = 4
x2 = [2,3,4], y2 = 1
x3 = [3,4,1], y3 = 5

这样，我们就可以用 Keras 来训练了。

我使用的是「python requests」去掉了空行和注释的代码作为训练样本。

脚本具体可以参考

https://machinelearningmastery.com/text-generation-lstm-recurrent-neural-networks-python-keras/

训练 40 个 epoch 后的成绩：

1
2

apache复制代码Epoch 40/40
217004/217004 [==============================] - 270s - loss: 0.9860

效果：

可以看到部分输出确实有点像代码的样子，但是重复的地方也比较多，这是因为过拟合了。

「GRU」是 LSTM 的一个变种，据说结构上比 LSTM 简单，参数少，比 LSTM 在过拟合方面好点：

1
2
3
4
5

routeros复制代码model = Sequential()
model.add(GRU(256, input_shape=(X.shape[1], X.shape[2]), return_sequences=True))
model.add(GRU(256))
model.add(Dense(y.shape[1], activation='softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam')

训练 20 个 epoch 的效果：

1
2

apache复制代码Epoch 20/20
217004/217004 [==============================] - 224s - loss: 0.8398

可以看到重复性方面解决得比 LSTM 要好，有时间再训练多些看下是否能得到更好的效果。

作诗机器人

其实就是把上面例子里的英文字母，换成汉字。

文本格式如下，冒号分隔诗名和诗，一行一首诗，一共一千首诗。

1

makefile复制代码山阁晚秋:山亭秋色满，岩牖凉风度。疏兰尚染烟，残菊犹承露。古石衣新苔，新巢封古树。历览情无极，咫尺轮光暮。

数据处理：

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

stylus复制代码with open('poetry.txt') as f:
    raw_text = f.read()
lines = raw_text.split("\n")[:-1]
poem_text = [i.split(':')[1] for i in lines]
char_list = [re.findall('[\x80-\xff]{3}|[\w\W]', s) for s in poem_text]
all_words = []
for i in char_list:
    all_words.extend(i)
word_dataframe = pd.DataFrame(pd.Series(all_words).value_counts())
word_dataframe['id']=list(range(1,len(word_dataframe)+1))
word_index_dict = word_dataframe['id'].to_dict()
index_dict = {}
for k in word_index_dict:
    index_dict.update({word_index_dict[k]:k})
seq_len = 2
dataX = []
dataY = []
for i in range(0, len(all_words) - seq_len, 1):
    seq_in = all_words[i : i + seq_len]
    seq_out = all_words[i + seq_len]
    dataX.append([word_index_dict[x] for x in seq_in])
    dataY.append(word_index_dict[seq_out])
X = np.array(dataX)
y = np_utils.to_categorical(np.array(dataY))

序列长度我设置为 2，即用前面两个字来预测下一个字，一共 217687 条数据。

汉字的体量比英文字母高了几个级别，共 4620 个。我们得用 word embedding 来处理，将 one-hot 编码的词，映射为低维向量表达，以降低特征维度。

1
2
3
4
5
6

stylus复制代码model = Sequential()
model.add(Embedding(len(word_dataframe)+1, 512))
model.add(GRU(512))
model.add(Dense(y.shape[1]))
model.add(Activation('softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam')

定义一个生成诗的函数：

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

apache复制代码def gen_poem(seed_text):
    rows = 4
    cols = 6
    chars = re.findall('[\x80-\xff]{3}|[\w\W]', seed_text)
    if len(chars) != seq_len:
        return ""
    arr = [word_index_dict[k] for k in chars]
    for i in range(seq_len, rows * cols):
        if (i+1) % cols == 0:
            if (i+1) / cols == 2 or (i+1) / cols == 4:
                arr.append(2)
            else:
                arr.append(1)
        else:
            proba = model.predict(np.array(arr[-seq_len:]), verbose=0)
            predicted = np.argsort(proba[1])[-5:]
            index = random.randint(0,len(predicted)-1)
            new_char = predicted[index]
            while new_char == 1 or new_char == 2:
                index = random.randint(0,len(predicted)-1)
                new_char = predicted[index]
            arr.append(new_char)
    poem = [index_dict[i] for i in arr]
    return "".join(poem)

为了不会每次都生成一样的句子，我设置了随机从最有可能的 5 个结果里面取。

训练了 25 个 epoch 看下效果：

还不错吧！起码语句还是比较通顺的！

该诗描述了，在一个月明的夜里传来了阵阵的猿声，猿猴才不可惜眼前的这座空城呢，它发现了一面崭新的梳妆铜镜，然而它四处张望，三千里内杳无人烟，找不到镜子的主人。表达了诗人的一种孤寂虚无的情怀。( 原谅我的强行解释 … )

以下是生成的部分诗句：

1. 清泉落花开，何处不见花。玉门前山水，不得无限情。

2. 二月出长生，何为谁知音。礼容备乐钟，天地气调弦。

3. 小荷恩重重，天涯不相见。一别有事征，云际会春花。

4. 残菊还畏风，金石咸来此。礼容暗通三，天下朝斑竹。

5. 悠然影曲与，云浮黄云际。风何处处在，一杯酒熟金。

训练了 75 个 epoch 的效果：

1. 清泉鸣天不，一杯酒若游。此时月悬舞，一何不归去。

2. 二月明月悬，何不知天涯。今宵似生长，金香玉春色。

3. 小荷休征衣，天不相顾非。今宵光如可，何日更畏凉。

4. 残菊杯色摇，金甲云盖极。风花落日月，云愁思君子。

5. 悠然知天地，何年光彩云。君不可怜故，天涯天地无。

来个七言：

1. 清泉凝愁夜长思，一何处欲待我行。君王道远烟雾里，天地来不相见无。

2. 二月悬舞凤凰天，何年光如可荐严。风动四时得无声，云愁不相如此生。

3. 小荷休气齐复来，金香金屋夹流水。今已枕在何须尽，金香风吹落花开。

4. 残菊杯色犹倚望，云愁夜月悬舞红。今奉君之何须一，云中绣衣襟艳芳。

5. 悠然身自有时人，一生百年无声至。君不可见少别有，一人行晚朝云浮。

文本情感分析

上面都是玩票的性质，接下来用 LSTM 做下比较实用的文本情感分析。

文本情感分析一般是指给出一段文本，然后给机器判断该文本表达的情绪是正面的还是负面的。

比如说：

「太喜欢这个产品了，我会推荐给朋友用。」是正面的，

「垃圾，不推荐，要求退货。」是负面的。

文本情感分析在网上做舆论分析时特别有用。

所用的语料，我爬了下京东的产品评论，url 类似下面这个例子：

1

apache复制代码https://club.jd.com/comment/productPageComments.action?callback=fetchJSON_comment98vv3006&productId=2695276&score=1&sortType=5&page=0&pageSize=10&isShadowSku=0

参数 productId 为商品的 id；score=1 为一星评论 (负面)，score=5 为五星评论 (正面)。

抓好后，整理成 csv 文件，如：

1
2
3
4
5

erlang复制代码0,"很山寨！根本读不出来，换了两台电脑winXP和win10都读不出来！"
0,"刚买完就降价，必须差评。"
...
1,"很好的移动硬盘，价格合理，不比其它品牌差，很满意。"
1,"办公室必备之物，非常不错"

0 表示负面；1 表示正面。差评和好评数量要均衡点。

在这个例子中，跟上面的诗词又不一样了，我们需要分词处理，否则输入序列就太长了。

数据预处理：

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

python复制代码import pandas as pd
import numpy as np
import jieba
from keras.preprocessing import sequence

comments = pd.read_csv('jd_comments.csv', encoding='utf-8')
comments['words'] = comments['content'].apply(lambda x: list(jieba.cut(x)))
all_words = []
for w in comments['words']:
    all_words.extend(w)
word_dict = pd.DataFrame(pd.Series(all_words).value_counts())
word_dict['id'] = list(range(1, len(word_dict)+1))
comments['w2v'] = comments['words'].apply(lambda x: list(word_dict['id'][x]))
# 规整为 50 个词
comments['w2v'] = list(sequence.pad_sequences(comments['w2v'], maxlen=50))

训练和测试数据：

1
2
3
4

stylus复制代码x_train = np.array(list(comments['w2v']))[::2]
y_train = np.array(list(comments['score']))[::2]
x_test = np.array(list(comments['w2v']))[1::2]
y_test = np.array(list(comments['score']))[1::2]

模型：

1
2
3
4
5
6
7

routeros复制代码model = Sequential()
model.add(Embedding(len(word_dict)+1, 256))
model.add(LSTM(256))
model.add(Dropout(0.5))
model.add(Dense(1))
model.add(Activation('sigmoid'))
model.compile(loss='binary_crossentropy', optimizer='adam', metrics=['accuracy'])

输出只有 1 维，所以激活函数要用 sigmoid，损失函数用 binary_crossentropy。

训练：

我只用了 14255 条数据，所以训练起来非常快，准确率也达到了 96.38% 。

看下测试数据集的准确率：

1
2

cli复制代码model.evaluate(x=x_test,y=y_test,verbose=0)
[0.37807498600423312, 0.87680651045320612]

也有 87.68% 的准确率，总体来说还算过得去了。

定义一个函数用来看下效果：

1
2
3
4
5

haxe复制代码def new_data(new_comment):
    words = list(jieba.cut(new_comment))
    w2v = [word_dict['id'][x] for x in words]
    xn = sequence.pad_sequences([w2v], maxlen=50)
    return xn

准确率还是不错的：

「他们都说好用，我就呵呵了。」 都能判断正确，神奇了哎。

本文转载自: 掘金

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

【编者的话】本文为大家带来了Prometheus 2.0中新存储层需求的由来，主要的挑战，实现的简要介绍，以及相关的基准测试结果，相关领域人员可以参考一下。

Kubernetes使得复杂环境的管理变得容易，但是为了确保可用性，对Kubernetes组件以及群集上运行的所有应用程序进行操作深入分析至关重要。在CoreOS，我们相信监控是良好生产环境的基石，这也是我们投入开发Prometheus监控系统的原因。作为一个由Cloud
Native Computing Foundation（CNCF）支持的项目，Prometheus迅速获得了基础设施及应用监控方面的热度，今天是它更进一步的时候。

CoreOS将Prometheus作为我们企业级Kubernetes平台Tectonic的集成组件，并且我们也一直在努力提升其对Kubernetes用户的价值。今年早些时候，我们分享了关于下一代Prometheus（version 2.0）的新存储层方面的工作。为了稳固这项工作，我们和Prometheus团队以及我们的用户进行了更加密切的合作。在3个alpha版本，6个beta版本以及3个RC版本之后，今天Prometheus
2.0正式宣布稳定版本。感谢Brian Brazil和Goutham Veeramachaneni，他们在这项工作中付出巨大。在我们探索该发行版的优点之前，让我们回过头来，先探讨一下我们为何需要一个新的存储层。

时间序列和动态环境

Prometheus关于监控的理念鼓励在堆栈的每一层都采用高度详细的度量工具。容器的状态，通过的请求流，甚至是运行于其中的应用的深层信息都通过度量工具对外可见。Prometheus带来了一款强力的查询语言帮助将度量数据汇总转换成行动方案。

Prometheus通过时间序列的方式收集和存储数据，它是通过固定间隔收集到的带有时间戳数据的序列。这种设计可以使运行中的容器轻松产生成千的时间序列。随着容器的规模从成百扩展到成千，在集群中很可能产生数百万被跟踪的时间序列。

为上百万的时间序列持续写入数据显然是一项技术难题。更糟糕的是，Kubernetes使得持续销毁和创建容器变得十分容易。该项模型对于持续部署，自动扩容以及批处理作业调度而言是极为强大的，因此只会随着时间的推移而变得越来越普遍。

每个容器都有一个独一无二的标识符，所有其时间序列均包含该标识符，以达到最佳的视角。因此当被跟踪的活跃时间序列总数大致固定时，Prometheus中可以对外访问的所有历史时间序列数据是持续增长的。允许查询十亿级的时间序列是一项全新的挑战，但我们决定让Prometheus很好地支持该特性。

新的存储引擎就是用来解决这项挑战的。受到全文搜索的启发，它使用倒排索引以提供对于Prometheus时间序列可能拥有的任意纬度进行快速检索。新的磁盘格式确保相关的时间序列数据良好分布，另外write-ahead日志也使得Prometheus 2.0n能够从崩溃中恢复。

Prometheus同样变得更易操作了。Prometheus 1.x的用户应该对调整期望负载的存储配置十分熟悉。然而，有了新的存储层之后，这些控制就不再需要了。

基准测

这项工作的真实结果是令人印象深刻的。Prometheus 2.0的资源消耗得到了显著降低，使用率更加稳定，并且新的索引方式带来了更低且一致的查询延迟。

下方的图是一个基准测试集的结果，它来自一个运行着成百个应用Pod并被监控的Kubernetes集群。Pod按照高频率替换以产生时间序列的扰动。各有2个Prometheus 1.5和Prometheus 2.0实例运行采集新数据。不同版本中，各有1个实例对外服务，以产生适中性的高查询负载。

从前2个图中，我们可以看到Prometheus
2.0的内存和CPU消耗均明显更低，并且自启动后，它们很快到达稳定状态。Prometheus 1.5则需要更多的资源，并且其资源使用率难以预测。


Prometheus
2.0中最大的改进是其每秒写入磁盘的数据量，可以查看下图。新版本的写入量较之前低了近2个数量级。很明显，这能增加SSD的寿命（译者：SSD寿命由PE次数决定，与写入数据量密切相关），进而降低成本。在高序列扰动的情况下，即使使用相同的序列压缩算法，依旧可以观察到显著的磁盘空间节省。

在Prometheus 1.5中，随着更多的时间序列被创建，查询的延迟是线性增长的。Prometheus 2.0则从一开始就维持了稳定的性能，它使得查询的反馈更加敏捷，正如下图所示。

其余新特性

Prometheus 2.0的大多数工作都聚焦于提升性能并使其更加易于操作。但是新的存储层同样被设计以更好地和Prometheus的外部交互，这使得围绕收集到的时间序列数据进行广泛的定制处理成为可能。

快照备份是一项被频繁要求的特性。当使用flag --web.enable-admin-api时，只需要通过简单的API调用，Prometheus 2.0便可原生支持它们。

1
2
3

复制代码bash
$ curl -XPOST http://<prometheus>/api/v2/admin/tsdb/snapshot
{"name":"2017-10-18T13:44:35Z-3f6a679bb001e65d"}

快照存放于名为返回值的目录中，且可以被上传到归档存储中，它们几乎不会占用额外的磁盘空间。最棒的是，新的Prometheus服务器可以从备份的数据启动，你只需将数据移动到新的服务器数据目录中即可。

关于完整的变更列表以及如何从Prometheus 1.x迁移，请查看官方声明以及迁移指南。

敬请尝试

有关Prometheus 2.0增强的最佳部分是，Prometheus当前不但可以比以往更好地支持Kubernetes的工作负载，更在于当Kubernetes在基础设施中活力倍增时，它预留了足够的空间来支撑届时的工作负载。

想要了解Prometheus，请关注11月16日上午8时webinar上关于新特性的PT（来自Prometheus开发者Frederic
Branczyk）。

如果你想要亲自了解集成Prometheus支持是如何使得CoreOS Tectonic成为真正的企业级Kubernetes平台的，你可以免费部署一个不多于10个节点的Tectonic集群。你将能够使用最新的Prometheus操作器不费吹灰之力地在集群中部署Prometheus
2.0，而无需额外的配置。

声明：本文中的基准测试通过prombench生成。为了复现它们，你需要一个配置好的AWS账户，并且你必须指定想要执行的基准测试spec。spec.example.yaml正是生成本文所用图的spec。

相关文章

• Prometheus 2.0: New storage layer dramatically increases monitoring scalability for Kubernetes and other distributed systems
• The Prometheus Operator: Managed Prometheus setups for Kubernetes
• Monitoring Kubernetes with Prometheus | Prometheus Docker Monitoring
• CoreOS and Prometheus: Building monitoring for the next generation of cluster infrastructure

原文链接：Prometheus, the backbone of container monitoring, hits 2.0（翻译：孙科）

本文转载自: 掘金

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

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

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

我将分两篇讲解下 Python 的基础语法，这是第一篇。大家也可以在很多地方看到入门的学习资料，我就简单的根据自己理解和学习，用尽量简单和好理解的方式，再来小入门一下，文中可能会用到一些 Java 上的理解。

总而言之，我不希望是一种阅读文档的方式，而是用一种思考和共鸣的方式去理解各个知识点。

一些建议

今天在群里，有的小伙伴建议我使用一些类似 PyCharm 这样的智能编译器来入门 Python，实际上我何尝不想用编译器呢，我也是老早就下载了 PyCharm，但我还是决定在学习的过程中不使用任何智能编译器，使用命令行和纯文本编辑器来一个字符一个字符的写代码，我也建议大家这样做，先暂时放放手里的编译器。

为什么一再强调这样做呢，在上大学的时候，每次学一门新的语言，老师都会强调让我们用命令行来编译代码，这样做不仅能帮助我们更好的理解一门语言的编译过程，而且一行一行敲出来可以更好的培养我们对这门语言的「语感」，是不是真的和学英语感觉差不多，实际上确实是差不多的，写代码也是要一个「语感」。

我们在控制台或者终端中输入「python3」将进入 Python 的交互式环境，在交互式环境中，我们可以直接输入代码，回车后，每一行代码的结果都会被打印输出出来。你也可以通过执行「python test.py」来运行一个 .py 文件。但这两种输出方式有一定区别，举个例子。

在交互式环境下输入以下代码并回车

1
2

复制代码>>> 'Python is the best language. '
'Python is the best language. '

‘Python is the best language’是一个字符串，我们下篇文章会说到。这里我们发现，输入我们输入了一个字符串并回车后，交互式环境直接帮我们把这个字符串打印出来了。我们试试在 test.py 文件中输入这段代码吧

1

复制代码'Python is the best language. '

通过「python test.py」执行文件发现没有任何输出，它不会像交互式环境下输出每一行。提醒大家一点的是，在交互式环境中，我们可以省略「.py」，直接通过「 python test」来执行 Python 文件。

我们把「test.py」稍作修改，添加 print 语句，就能打印出来了

1

复制代码print('Python is the best language. ')

这里推荐大家使用「Sublime Text」配合交互式环境来进行学习，在 Sublime Text 中进行代码编写，在 Tools –> Build System 中选择 Python 后，通过「Command+B」(Mac) 来编译，如果有需要验证某一行代码，就复制到交互式环境中去验证，使用这种方式来学习 Python 语法，别提有多来劲了。

输入输出

1. print

我们看到了好几次「print()」了，Python 的输出语句，2.x 和 3.x 是有所区别的：
这是 2.x 的语法

1

复制代码>>> print 'Hello, Python'

这是 3.x 的语法

1

复制代码>>> print('Hello, Python')

print() 也可以带多参数，用「,」相隔，每次遇到逗号会出处一个空格，就像这样：

1
2

复制代码>>> print('小之','正在','帅气的','学 Python')
小之 正在 帅气的 学 Python

不止是字符串，print() 还可以打印出整数：

1
2

复制代码>>> print(2017-1994)
23

然后配合刚刚的多参数函数就可以组合出一些有意思的输出：

1
2

复制代码>>> print('小之今年',2017-1994,'岁。')
小之今年 23 岁。

我还在青春期呢。

2. input

我们可以通过 input() 来进行等待输入，然后把输入结果放到一个变量中，3.x可以支持中文变量名！

1
2
3
4

复制代码>>> 姓名 = input()
小之
>>> 姓名
`小之`

我们通过键盘输入，将「小之」这个字符串存放在了「姓名」这个变量中，输出「姓名」会直接把存放的字符串给打印出来。

我们搭配一下上面的知识，来综合应用下：

1
2
3
4
5
6

复制代码>>> 姓名 = input()
小之
>>> 性别 = input()
男
>>> print('姓名:',姓名,'性别:',性别)
姓名:  小之 性别:  男

Python 的缩进

Python 不像 Java，它没有大括号和分号这样明显的代码块控制符号，一切的代码块都是通过缩进来区分，这样做的好处是，它强制你写出语法严格的缩进模式，不会像 Java 一样，只要你符号使用的对，你甚至可以极端的把所有代码写在一行里。

但这样做又会有一些问题，如果逻辑比较复杂，可能你的代码就会有非常冗长的「迷之缩进」，看的你怀疑人生。用 Java 写客户端的同学可能会有一个体会，在写一些嵌套请求或者涉及到匿名内部类的时候应该深有体会，环环相扣的大括号在你眼前像麻花一般晃动，酸爽自知，不过好在有了「Lambda」和一些链式结构，这种情况才有所缓解，这里就不深谈了。

在 Python 里，这种情况可能会更严重，但实际上这种缩进语法也有一种反向指引作用，他会促使你去想尽一切办法写一些缩进比较少的代码，为了达到这个目的，首先你就得保证你的代码拥有良好的设计性，每个函数遵守「单一原则」。

这让我想到了「单元测试」，测试驱动开发就是这样，如果你想让你的代码具有可测性，那你不得不在开发阶段就让代码具有良好的设计性，每一个函数都尽量只做一个事，这样才能把每一段逻辑「可命名化」。

好比做菜可以分好多步骤，比如洗菜、切菜、炒菜、放调料等，你得把每个步骤都拎出来一个函数，这个函数名就叫洗菜，然后它只干洗菜的事。如果你把这些步骤都放在一个函数里，函数名叫做菜，这实际上不是一个很好的做法，因为它干的事太多了，而你的命名不能很好的让阅读你代码的人细化的理解到它到底做了啥。

所以，缩进里面的门道可多了呢。

数据类型

1. 整数与浮点数

Python 的数据类型和其他语言比较类似，整数运算始终是精确的，而浮点数可能会有精度的丢失。

没错，即便是整数的除法，结果也是精确的：我们使用 5/3 来看看结果

1
2

复制代码>>> 5/3
1.6666666666666667

「/」计算的结果是浮点数，5/3 你无论试几次，它都是这个结果。即便整除，最后还是浮点数。

1
2

复制代码>>> 6/3
2.0

还有一个取整除法「//」，这是一种割尾取值：

1
2

复制代码>>> 5//3
1

当然，还有我们熟悉的「%」，余数计算：

1
2

复制代码>>> 5%3
2

2. 布尔值

布尔值只有两种值：True 和 False，不是 True 就是 False，经常用在判断语句中，他们可以搭配 and、or、not 来运算，也可以直接输出或者通过布尔运算计算出来：

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

复制代码>>> True
True
>>> False
False
>>> 2>1
True
>>> 2<1
False

if age >= 23:
    print('比小之成熟')
else:
    print('比小之年轻')

3. 空值

Python 中的空值用「None」表示，和 Java 中的 null 有点像。

4. 变量

Python 中的变量是可以被任何数据类型赋值的，这是动态语言的特性，而像 Java 这样的静态语言，在给变量赋值的时候，是需要指定类型的。

1
2

复制代码int a = 10; //指定 a 为整型
a = "Test";  // 编译期报错，类型不匹配

但 Python 没有这种问题，同样的变量可以被赋予不同类型的值。

1
2

复制代码a = 10;     // a 为整数类型
a = 'Test' // a 现在是字符串类型

不过 Python 和 Java 变量的内存语义是类似的。变量都是指向一个引用。

1
2
3
4

复制代码a = 'ABC'
b = a
a = "XYZ"
print(b)

这里的 b 打印出来是 ‘ABC’，a 和 b 存储的是引用指针，b = a 的时候，b 存储了 a 的引用，当 a 的引用变化的时候，b 的引用当然不会变化，而字符串又是一种常量池的实现方式，所以 b 就会打印出来 ‘ABC’，大家是不是觉得和 Java 非常类似呢

常量在 Python 中用大写字母表示：

1

复制代码PI = 3.141592653

不过实际上它也是个变量，也可以被修改。只是约定俗成用这种方式来表示常量罢了。

欢迎关注我的公众号

本文转载自: 掘金

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

在Go社区中, 包管理和泛型看上去被当做一个很大的问题, 但有另一个很少被提及的问题——项目结构。

每一个我参与的Go程序都看似对这个问题有自己的答案, 那我应该如何组织我的Go代码? 有些人把所有代码放到一个包中, 有些人用类型或者模块归组代码.如果你们的团队没有使用一个好的策略, 你会发现代码混乱分散在不同的包中。 所以我们需要一个更加标准的Go程序设计。

我提倡一种更好的方法. 通过以下的几种简单的规则, 我们解耦我们的代码, 并便于测试, 同时给我们的项目带来一种始终如一的结构。

常见但有瑕疵的方式

方法一: 整块的包布局

把所有代码丢到一个包下确实可以在小程序中工作的很好. 避免了出现循环依赖的问题, 因为在你的应用程序中, 没有互相依赖的情况。

我目睹过这种方式在一万行代码内良好的工作, 但只要超过这个级别, 它将变得非常难于定位和分离代码。

方法二: Rails 风格

另一种方式是将代码按照功能类型来归组。比如, 把所有Handlers 放在同一个包, 所有Controller放在另外一个包, 所有Models也放到单独的包中。 我见过很多之前做Rails的开发者使用这种方式(包括我自己)。

但这种方式有两个问题。 第一, 你的命名格则会是糟糕的。 你的type命名会像controller.UserController 这样重复你的包名。 我倾向于保持良好的命名规范。我坚信当你在修改老代码时命名是最好的文档。 同时命名也是代码质量的一种表现——这是其他人阅读代码时首先知觉的事

但最大的问题是循环依赖。 不同的功能类型可能需要互相引用。 这种方式只适合单向依赖但大多数程序没那么简单。

方法三: 根据模块归组

这种方式与Rails风格结构类似除了是按照模块归组而不是按照功能. 比如, 你可能有一个user包和一个account 包。

我们会发现这种方式有一样的问题。 最终我们的命名又变得像users.User一样糟糕。 如果accounts.Controller和users.Controller需要相互调用,我们同样也有循环依赖的问题。

一种更好的方式

我用在项目中的包策略包含四个信条:

1. Root package is for domain types (根包作为领域类型)
2. Group subpackages by dependency (根据依赖将子包归组)
3. Use a shared mock subpackage (使用共享的模拟子包)
4. Main package ties together dependencies (main包将所有依赖关联起来)

这些规则有助于我们的包解耦, 它定义一个清晰的领域语言。 让我们看一下这几个规则的实践。

1. Root package is for domain types (根包作为领域类型)

你的程序有一个有逻辑且高层级语言描述数据和进程是如何交互的, 这是你的领域模型。如果你有一个电子商务应用, 那么你的领域包含一些像客户,账户,收费信用卡, 和库存处理。如果你是Facebook 那么你的领域是用户,赞和各种关联. 这是一些不依赖你的技术的东西。

我把领域类型放在我的根目录。 这个包只包含简单的数据类型, 如一个User struct 用户放用户数据或者一个UserService interface 来获取保存用户数据。

1
2
3
4
5
6
7
8
9
10
11

复制代码type User struct {
    ID      int
    Name    string
    Address Address
}
type UserService interface {
    User(id int) (*User, error)
    Users() ([]*User, error)
    CreateUser(u *User) error
    DeleteUser(id int) error
}

这使你的根包非常简单。 你还可以把具体的执行操作放在里面, 但仅当它们仅依赖于其他域类型的时候。 比如, 你可以有个定时轮训你的User Service的类型。 但是, 它不应该调用外部服务或者数据。这是一个操作细节。

在你的程序中根包不应该依赖于任何其他包

2. Group subpackages by dependency (根据依赖将子包归组)

如果你的根包不允许有外部依赖, 那么我们必须把这些依赖放到子包里面。 用这种包布局方式, 子包以一个桥接你的领域模型和实现的适配器而存在。

比如, 你的UserService可能依赖PostgreSQL。 你可以在你的程序中创建一个postgres 子包来提供一个postgres.UserService 实现:

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

复制代码package postgres

import (
    "database/sql"

    "github.com/benbjohnson/myapp"
    _ "github.com/lib/pq"
)

// UserService 代表一个myapp.UserService的PostgreSQL实现 
type UserService struct {
    DB *sql.DB
}

// User方法 根据一个给定的id返回一个用户
func (s *UserService) User(id int) (*myapp.User, error) {
    var u myapp.User
    row := db.QueryRow(`SELECT id, name FROM users WHERE id = $1`, id)
    if row.Scan(&u.ID, &u.Name); err != nil {
        return nil, err
    }
    return &u, nil
}
// 实现myapp.UserService剩余的接口

这种方式解耦了我们的PostgreSQL依赖, 简化了测试,同时提供了一种简单的方式以便未来迁移到另一种数据库。 它可以作为一个可插拔的架构如果你决定支持其他数据库实现比如BoltDB

这种方式还给了你一种方式来实现分层。可能你想要把数据贮存在内存中, 将LRU cache 前置于PostgreSQL。你可以增加一个实现UserService接口的UserCache, 来包装你的PostgreSQL实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

复制代码package myapp

// UserCache 封装了UserService, 提供了内存缓存功能
type UserCache struct {
        cache   map[int]*User
        service UserService
}

// NewUserCache returns a new read-through cache for service.
func NewUserCache(service UserService) *UserCache {
        return &UserCache{
                cache: make(map[int]*User),
                service: service,
        }
}
// User returns a user for a given id.
// Returns the cached instance if available.
func (c *UserCache) User(id int) (*User, error) {
// Check the local cache first.
        if u := c.cache[id]]; u != nil {
                return u, nil
        }

// Otherwise fetch from the underlying service.
        u, err := c.service.User(id)
        if err != nil {
            return nil, err
        } else if u != nil {
            c.cache[id] = u
        }
        return u, err
}

在标准库中也使用了这种方式. io.Reader 是一个用来读取bytes的领域类型, 它的实现是按照依赖分组——tar.Reader, gzip.Reader,
multipart.Reader. 这些也可以被分层. 另外常见的还有os.File 被bufio.Reader封装, bufio.Reader 又被gzip.Reader封装,
gzip.Reader 又被tar.Reader封装.

相互依赖处理

你的依赖不会孤立存在. 你可能把User 数据存储在PostgreSQL中, 但你的财务交易数据存储在像Stripe之类的第三方. 在这种情况下, 我们用一个逻辑上的领域类型来封装我们的Stripe依赖—我们叫它TransactionService.

通过增加TransactionService到UserService来解耦了我们的两个依赖:

1
2
3
4

复制代码type UserService struct{
        DB *sql.DB
        TransactionService   myapp.TransactionService
}

现在我们的依赖通过通用的领域语言来交流. 这意味着我们可以在不影响其他依赖的情况下, 替换PostgreSQL到MySQL或者替换Stripe到其他支付平台

这个规则不仅限于第三方依赖

这个听上去很奇怪, 但我也使用了以上同样方式解耦了对标准库的依赖. 比如, net/http 包是一个依赖项. 我们也可以使用一个包含http实现的子包将它解耦.

你可能会觉得很奇怪, 如果存在一个名字和它的依赖一样的包, 但是这是有意义的. 这种方式并不会让你的程序中存在命名冲突, 除非你允许 net/http被直接使用于其他地方.

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

复制代码package http

import (
    "net/http"

    "github.com/benbjohnson/myapp"
)

type Handler struct {
    UserService myapp.UserService
}

func (h *Handler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    // 处理请求
}

现在你的http.Handler 在连接了你的领域模型和HTTP协议.

3. Use a shared mock subpackage (使用共享的模拟子包)

因为我们的依赖通过领域接口互相独立, 所以我们可以用这些连接点来注入mock实现.

市面上有一些mock库比如GoMock, 它会为你生成mocks, 但我个人更加倾向于自己写. 因为我发现很多mocking工具都过于复杂.

我使用的mock方式很简单. 比如, 一个UserService mock 如下:

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

复制代码package mock

import "github.com/benbjohnson/myapp"

// UserService 代表一个myapp.UserService.的 mock实现 
type UserService struct {
    UserFn      func(id int) (*myapp.User, error)
    UserInvoked bool

    UsersFn     func() ([]*myapp.User, error)
    UsersInvoked bool

    // additional function implementations...
}

// User调用mock实现, 并标记这个方法为已调用
func (s *UserService) User(id int) (*myapp.User, error) {
    s.UserInvoked = true
    return s.UserFn(id)
}

// 其他函数Users(), CreateUser(), DeleteUser()

这个mock把函数注入任何使用了myapp.UserService接口来验证参数, 输出期望的数据或者注入错误.

我们测试下我们刚才使用的http.Handler:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

复制代码package http_test

import (
    "testing"
    "net/http"
    "net/http/httptest"

    "github.com/benbjohnson/myapp/mock"
)

func TestHandler(t *testing.T) {
    // 将Mock注入其他Handler
    var us mock.UserService
    var h Handler
    h.UserService = &us

    // Mock我们的User()调用
    us.UserFn = func(id int) (*myapp.User, error) {
        if id != 100 {
            t.Fatalf("unexpected id: %d", id)
        }
        return &myapp.User{ID: 100, Name: "susy"}, nil
    }

    //调用其他Handler
    w := httptest.NewRecorder()
    r, _ := http.NewRequest("GET", "/users/100", nil)
    h.ServeHTTP(w, r)

    // 验证Mock
    if !us.UserInvoked {
        t.Fatal("expected User() to be invoked")
    }
}

我们的Mock让我们完全解耦了我们的单元测试, 只处理HTTP协议

4. Main package ties together dependencies (main包将所有依赖关联起来)

由于所有这些依赖包都是在独立的, 你可能想知道它们是如何聚集在一起的。这就是Main包的工作.

Main包布局

一个应用程序可能产生多个二进制文件, 所以我们将使用 Go 约定将我们的主包作为 cmd 包的子目录. 比如, 我们的项目可能有一个myapp服务的二进制文件和一个myappctl 客户端二进制文件从终端管理服务. 我们会像这样布局我们的Main包:

1
2
3
4
5
6

复制代码myapp/
    cmd/
         myapp/
              main.go
         myappctl/
              main.go

在编译时注入依赖

“依赖注入” 这个词受到不好的斥责. 它唤起了冗长的 Spring XML 文件的思想. 但是, 所有的这些实际上都意味着我们要将依赖项传递给对象, 而不是引用对象或查找依赖项本身.

主程序包是要选择将哪些依赖项注入到哪些对象中. 因为主包只是简单地将片段连接起来, 所以它往往是相当小且琐碎的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

复制代码package main

import (
    "log"
    "os"

    "github.com/benbjohnson/myapp"
    "github.com/benbjohnson/myapp/postgres"
    "github.com/benbjohnson/myapp/http"
)

func main() {
    // 连接数据库
    db, err := postgres.Open(os.Getenv("DB"))
    if err != nil {
        log.Fatal(err)
    }

    defer db.Close()

    // 创建Services
    us := &postgres.UserService{DB: db}

    // 关联Http Handler
    var h http.Handler
    h.UserService = us

    // 启动服务
}

同样重要的是要注意, 你的Main包也是一个适配器。它将终端连接到您的领域模型.

总结

应用程序设计是一个难题。有这么多的设计决策, 但如果没有Solid原则来指导你的问题的话会做得更糟。我们已经研究了几种当前 Go 应用程序设计的方法, 我们已经看到了他们的许多缺点。

我相信从依赖关系的角度来看, 设计使代码组织更简单, 更容易理解。首先, 我们设计我们的领域语言。然后我们解耦我们的依赖。接下来, 我们引入 mock 来隔离我们的测试。最后, 我们用Main包连接所有的东西。

原文连接 : medium.com/@benbjohnso…

本文转载自: 掘金

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

引子

每天我们晚上加班回家，可能都会用到滴滴或者共享单车。打开 app 会看到如下的界面：

app 界面上会显示出自己附近一个范围内可用的出租车或者共享单车。假设地图上会显示以自己为圆心，5公里为半径，这个范围内的车。如何实现呢？最直观的想法就是去数据库里面查表，计算并查询车距离用户小于等于5公里的，筛选出来，把数据返回给客户端。

这种做法比较笨，一般也不会这么做。为什么呢？因为这种做法需要对整个表里面的每一项都计算一次相对距离。太耗时了。既然数据量太大，我们就需要分而治之。那么就会想到把地图分块。这样即使每一块里面的每条数据都计算一次相对距离，也比之前全表都计算一次要快很多。

我们也都知道，现在用的比较多的数据库 MySQL、PostgreSQL 都原生支持 B+ 树。这种数据结构能高效的查询。地图分块的过程其实就是一种添加索引的过程，如果能想到一个办法，把地图上的点添加一个合适的索引，并且能够排序，那么就可以利用类似二分查找的方法进行快速查询。

问题就来了，地图上的点是二维的，有经度和纬度，这如何索引呢？如果只针对其中的一个维度，经度或者纬度进行搜索，那搜出来一遍以后还要进行二次搜索。那要是更高维度呢？三维。可能有人会说可以设置维度的优先级，比如拼接一个联合键，那在三维空间中，x，y，z 谁的优先级高呢？设置优先级好像并不是很合理。

本篇文章就来介绍2种比较通用的空间点索引算法。

一. GeoHash 算法

1. Genhash 算法简介

Genhash 是一种地理编码，由 Gustavo Niemeyer 发明的。它是一种分级的数据结构，把空间划分为网格。Genhash 属于空间填充曲线中的 Z 阶曲线（Z-order curve）的实际应用。

何为 Z 阶曲线？

上图就是 Z 阶曲线。这个曲线比较简单，生成它也比较容易，只需要把每个 Z 首尾相连即可。

Z 阶曲线同样可以扩展到三维空间。只要 Z 形状足够小并且足够密，也能填满整个三维空间。

说到这里可能读者依旧一头雾水，不知道 Geohash 和 Z 曲线究竟有啥关系？其实 Geohash算法 的理论基础就是基于 Z 曲线的生成原理。继续说回 Geohash。

Geohash 能够提供任意精度的分段级别。一般分级从 1-12 级。

还记得引语里面提到的问题么？这里我们就可以用 Geohash 来解决这个问题。

我们可以利用 Geohash 的字符串长短来决定要划分区域的大小。这个对应关系可以参考上面表格里面 cell 的宽和高。一旦选定 cell 的宽和高，那么 Geohash 字符串的长度就确定下来了。这样我们就把地图分成了一个个的矩形区域了。

地图上虽然把区域划分好了，但是还有一个问题没有解决，那就是如何快速的查找一个点附近邻近的点和区域呢？

Geohash 有一个和 Z 阶曲线相关的性质，那就是一个点附近的地方(但不绝对) hash 字符串总是有公共前缀，并且公共前缀的长度越长，这两个点距离越近。

由于这个特性，Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长（但是这不一定，也有特殊情况，下面举例会说明）

Geohash 也有几种编码形式，常见的有2种，base 32 和 base 36。

base 36 的版本对大小写敏感，用了36个字符，“23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX”。

2. Geohash 实际应用举例

接下来的举例以 base-32 为例。举个例子。

上图是一个地图，地图中间有一个美罗城，假设需要查询距离美罗城最近的餐馆，该如何查询？

第一步我们需要把地图网格化，利用 geohash。通过查表，我们选取字符串长度为6的矩形来网格化这张地图。

经过查询，美罗城的经纬度是[31.1932993, 121.43960190000007]。

先处理纬度。地球的纬度区间是[-90,90]。把这个区间分为2部分，即[-90,0)，[0,90]。31.1932993位于(0,90]区间，即右区间，标记为1。然后继续把(0,90]区间二分，分为[0,45)，[45,90]，31.1932993位于[0,45)区间，即左区间，标记为0。一直划分下去。

再处理经度，一样的处理方式。地球经度区间是[-180,180]

纬度产生的二进制是101011000101110，经度产生的二进制是110101100101101，按照“偶数位放经度，奇数位放纬度”的规则，重新组合经度和纬度的二进制串，生成新的：111001100111100000110011110110，最后一步就是把这个最终的字符串转换成字符，对应需要查找 base-32 的表。11100 11001 11100 00011 00111 10110转换成十进制是 28 25 28 3 7 22，查表编码得到最终结果，wtw37q。

我们还可以把这个网格周围8个各自都计算出来。

从地图上可以看出，这邻近的9个格子，前缀都完全一致。都是wtw37。

如果我们把字符串再增加一位，会有什么样的结果呢？Geohash 增加到7位。

当Geohash 增加到7位的时候，网格更小了，美罗城的 Geohash 变成了 wtw37qt。

看到这里，读者应该已经清楚了 Geohash 的算法原理了。咱们把6位和7位都组合到一张图上面来看。

可以看到中间大格子的 Geohash 的值是 wtw37q，那么它里面的所有小格子前缀都是 wtw37q。可以想象，当 Geohash 字符串长度为5的时候，Geohash 肯定就为 wtw37 了。

接下来解释之前说的 Geohash 和 Z 阶曲线的关系。回顾最后一步合并经纬度字符串的规则，“偶数位放经度，奇数位放纬度”。读者一定有点好奇，这个规则哪里来的？凭空瞎想的？其实并不是，这个规则就是 Z 阶曲线。看下图：

x 轴就是纬度，y轴就是经度。经度放偶数位，纬度放奇数位就是这样而来的。

最后有一个精度的问题，下面的表格数据一部分来自 Wikipedia。

3. Geohash 具体实现

到此，读者应该对 Geohash 的算法都很明了了。接下来用 Go 实现一下 Geohash 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

复制代码
package geohash

import (
    "bytes"
)

const (
    BASE32                = "0123456789bcdefghjkmnpqrstuvwxyz"
    MAX_LATITUDE  float64 = 90
    MIN_LATITUDE  float64 = -90
    MAX_LONGITUDE float64 = 180
    MIN_LONGITUDE float64 = -180
)

var (
    bits   = []int{16, 8, 4, 2, 1}
    base32 = []byte(BASE32)
)

type Box struct {
    MinLat, MaxLat float64 // 纬度
    MinLng, MaxLng float64 // 经度
}

func (this *Box) Width() float64 {
    return this.MaxLng - this.MinLng
}

func (this *Box) Height() float64 {
    return this.MaxLat - this.MinLat
}

// 输入值：纬度，经度，精度(geohash的长度)
// 返回geohash, 以及该点所在的区域
func Encode(latitude, longitude float64, precision int) (string, *Box) {
    var geohash bytes.Buffer
    var minLat, maxLat float64 = MIN_LATITUDE, MAX_LATITUDE
    var minLng, maxLng float64 = MIN_LONGITUDE, MAX_LONGITUDE
    var mid float64 = 0

    bit, ch, length, isEven := 0, 0, 0, true
    for length < precision {
        if isEven {
            if mid = (minLng + maxLng) / 2; mid < longitude {
                ch |= bits[bit]
                minLng = mid
            } else {
                maxLng = mid
            }
        } else {
            if mid = (minLat + maxLat) / 2; mid < latitude {
                ch |= bits[bit]
                minLat = mid
            } else {
                maxLat = mid
            }
        }

        isEven = !isEven
        if bit < 4 {
            bit++
        } else {
            geohash.WriteByte(base32[ch])
            length, bit, ch = length+1, 0, 0
        }
    }

    b := &Box{
        MinLat: minLat,
        MaxLat: maxLat,
        MinLng: minLng,
        MaxLng: maxLng,
    }

    return geohash.String(), b
}

4. Geohash 的优缺点

Geohash 的优点很明显，它利用 Z 阶曲线进行编码。而 Z 阶曲线可以将二维或者多维空间里的所有点都转换成一维曲线。在数学上成为分形维。并且 Z 阶曲线还具有局部保序性。

Z 阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。一旦将数据被加到该排序中，任何一维数据结构，例如二叉搜索树，B树，跳跃表或（具有低有效位被截断）哈希表 都可以用来处理数据。通过 Z 阶曲线所得到的顺序可以等同地被描述为从四叉树的深度优先遍历得到的顺序。

这也是 Geohash 的另外一个优点，搜索查找邻近点比较快。

Geohash 的缺点之一也来自 Z 阶曲线。

Z 阶曲线有一个比较严重的问题，虽然有局部保序性，但是它也有突变性。在每个 Z 字母的拐角，都有可能出现顺序的突变。

看上图中标注出来的蓝色的点点。每两个点虽然是相邻的，但是距离相隔很远。看右下角的图，两个数值邻近红色的点两者距离几乎达到了整个正方形的边长。两个数值邻近绿色的点也达到了正方形的一半的长度。

Geohash 的另外一个缺点是，如果选择不好合适的网格大小，判断邻近点可能会比较麻烦。

看上图，如果选择 Geohash 字符串为6的话，就是蓝色的大格子。红星是美罗城，紫色的圆点是搜索出来的目标点。如果用 Geohash 算法查询的话，距离比较近的可能是 wtw37p，wtw37r，wtw37w，wtw37m。但是其实距离最近的点就在 wtw37q。如果选择这么大的网格，就需要再查找周围的8个格子。

如果选择 Geohash 字符串为7的话，那变成黄色的小格子。这样距离红星星最近的点就只有一个了。就是 wtw37qw。

如果网格大小，精度选择的不好，那么查询最近点还需要再次查询周围8个点。

二. 空间填充曲线 和 分形

在介绍第二种多维空间点索引算法之前，要先谈谈空间填充曲线(Space-filling curve)和分形。

解决多维空间点索引需要解决2个问题，第一，如何把多维降为低维或者一维？第二，一维的曲线如何分形？

1. 空间填充曲线

在数学分析中，有这样一个难题：能否用一条无限长的线，穿过任意维度空间里面的所有点？

在1890年，Giuseppe Peano 发现了一条连续曲线，现在称为 Peano 曲线，它可以穿过单位正方形上的每个点。他的目的是构建一个可以从单位区间到单位正方形的连续映射。 Peano 受到 Georg Cantor 早期违反直觉的研究结果的启发，即单位区间中无限数量的点与任何有限维度流型（manifold）中无限数量的点，基数相同。 Peano 解决的问题实质就是，是否存在这样一个连续的映射，一条能填充满平面的曲线。上图就是他找到的一条曲线。

一般来说，一维的东西是不可能填满2维的方格的。但是皮亚诺曲线恰恰给出了反例。皮亚诺曲线是一条连续的但处处不可导的曲线。

皮亚诺曲线的构造方法如下：取一个正方形并且把它分出九个相等的小正方形，然后从左下角的正方形开始至右上角的正方形结束，依次把小正方形的中心用线段连接起来；下一步把每个小正方形分成九个相等的正方形，然后上述方式把其中中心连接起来……将这种操作手续无限进行下去，最终得到的极限情况的曲线就被称作皮亚诺曲线。

皮亚诺对区间[0，1]上的点和正方形上的点的映射作了详细的数学描述。实际上，正方形的这些点对于[图片上传失败…(image-a5643e-1510187476679)]，可找到两个连续函数 x = f(t) 和 y = g(t)，使得 x 和 y 取属于单位正方形的每一个值。

一年后，即1891年，希尔伯特就作出了这条曲线，叫希尔伯特曲线（Hilbert curve）。

上图就是1-6阶的希尔伯特曲线。具体构造方式在下一章再说。

上图是希尔伯特曲线填充满3维空间。

之后还有很多变种的空间填充曲线，龙曲线(Dragon curve)、 高斯帕曲线(Gosper curve)、Koch曲线(Koch curve)、摩尔定律曲线(Moore curve)、谢尔宾斯基曲线(Sierpiński curve)、奥斯古德曲线(Osgood curve)。这些曲线和本文无关，就不详细介绍了。

在数学分析中，空间填充曲线是一个参数化的注入函数，它将单位区间映射到单位正方形，立方体，更广义的，n维超立方体等中的连续曲线，随着参数的增加，它可以任意接近单位立方体中的给定点。除了数学重要性之外，空间填充曲线也可用于降维，数学规划，稀疏多维数据库索引，电子学和生物学。空间填充曲线的现在被用在互联网地图中。

2. 分形

皮亚诺曲线的出现，说明了人们对维数的认识是有缺陷的，有必要重新考察维数的定义。这就是分形几何考虑的问题。在分形几何中，维数可以是分数叫做分维。

多维空间降维以后，如何分形，也是一个问题。分形的方式有很多种，这里有一个列表，可以查看如何分形，以及每个分形的分形维数，即豪斯多夫分形维(Hausdorff fractals dimension)和拓扑维数。这里就不细说分形的问题了，感兴趣的可以仔细阅读链接里面的内容。

接下来继续来说多维空间点索引算法，下面一个算法的理论基础来自希尔伯特曲线，先来仔细说说希尔伯特曲线。

三. Hilbert Curve 希尔伯特曲线

1. 希尔伯特曲线的定义

希尔伯特曲线一种能填充满一个平面正方形的分形曲线（空间填充曲线），由大卫·希尔伯特在1891年提出。

由于它能填满平面，它的豪斯多夫维是2。取它填充的正方形的边长为1，第n步的希尔伯特曲线的长度是2^n - 2^(-n)。

2. 希尔伯特曲线的构造方法

一阶的希尔伯特曲线，生成方法就是把正方形四等分，从其中一个子正方形的中心开始，依次穿线，穿过其余3个正方形的中心。

二阶的希尔伯特曲线，生成方法就是把之前每个子正方形继续四等分，每4个小的正方形先生成一阶希尔伯特曲线。然后把4个一阶的希尔伯特曲线首尾相连。

三阶的希尔伯特曲线，生成方法就是与二阶类似，先生成二阶希尔伯特曲线。然后把4个二阶的希尔伯特曲线首尾相连。

n阶的希尔伯特曲线的生成方法也是递归的，先生成n-1阶的希尔伯特曲线，然后把4个n-1阶的希尔伯特曲线首尾相连。

3. 为何要选希尔伯特曲线

看到这里可能就有读者有疑问了，这么多空间填充曲线，为何要选希尔伯特曲线？

因为希尔伯特曲线有非常好的特性。

(1) 降维

首先，作为空间填充曲线，希尔伯特曲线可以对多维空间有效的降维。

上图就是希尔伯特曲线在填满一个平面以后，把平面上的点都展开成一维的线了。

可能有人会有疑问，上图里面的希尔伯特曲线只穿了16个点，怎么能代表一个平面呢？

当然，当n趋近于无穷大的时候，n阶希尔伯特曲线就可以近似填满整个平面了。

(2) 稳定

当n阶希尔伯特曲线，n趋于无穷大的时候，曲线上的点的位置基本上趋于稳定。举个例子：

上图左边是希尔伯特曲线，右边是蛇形的曲线。当n趋于无穷大的时候，两者理论上都可以填满平面。但是为何希尔伯特曲线更加优秀呢？

在蛇形曲线上给定一个点，当n趋于无穷大的过程中，这个点在蛇形曲线上的位置是时刻变化的。

这就造成了点的相对位置始终不定。

再看看希尔伯特曲线，同样是一个点，在n趋于无穷大的情况下：

从上图可以看到，点的位置几乎没有怎么变化。所以希尔伯特曲线更加优秀。

(3) 连续

希尔伯特曲线是连续的，所以能保证一定可以填满空间。连续性是需要数学证明的。具体证明方法这里就不细说了，感兴趣的可以点文章末尾一篇关于希尔伯特曲线的论文，那里有连续性的证明。

接下来要介绍的谷歌的 S2 算法就是基于希尔伯特曲线的。现在读者应该明白选择希尔伯特曲线的原因了吧。

四. S² 算法

Google’s S2 library is a real treasure, not only due to its capabilities for spatial indexing but also because it is a library that was released more than 4 years ago and it didn’t get
the attention it deserved

上面这段话来自2015年一位谷歌工程师的博文。他由衷的感叹 S2 算法发布4年没有得到它应有的赞赏。不过现在 S2 已经被各大公司使用了。

在介绍这个重量级算法之前，先解释一些这个算法的名字由来。S2其实是来自几何数学中的一个数学符号 S²，它表示的是单位球。S2 这个库其实是被设计用来解决球面上各种几何问题的。值得提的一点是，除去 golang 官方 repo 里面的 geo/s2 完成度目前只有40%，其他语言，Java，C++，Python 的 S2 实现都完成100%了。本篇文章讲解以 Go 的这个版本为主。

接下来就看看怎么用 S2 来解决多维空间点索引的问题的。

1. 球面坐标转换

按照之前我们处理多维空间的思路，先考虑如何降维，再考虑如何分形。

众所周知，地球是近似一个球体。球体是一个三维的，如何把三维降成一维呢？

球面上的一个点，在直角坐标系中，可以这样表示：

1
2
3
4

复制代码
x = r * sin θ * cos φ
y = r * sin θ * sin φ 
z = r * cos θ

通常地球上的点我们会用经纬度来表示。

再进一步，我们可以和球面上的经纬度联系起来。不过这里需要注意的是，纬度的角度 α 和直角坐标系下的球面坐标 θ 加起来等于 90°。所以三角函数要注意转换。

于是地球上任意的一个经纬度的点，就可以转换成 f(x,y,z)。

在 S2 中，地球半径被当成单位 1 了。所以半径不用考虑。x，y，z的值域都被限定在了[-1,1] x [-1,1] x [-1,1]这个区间之内了。

2. 球面变平面

接下来一步 S2 把球面碾成平面。怎么做的呢？

首先在地球外面套了一个外切的正方体，如下图。

从球心向外切正方体6个面分别投影。S2 是把球面上所有的点都投影到外切正方体的6个面上。

这里简单的画了一个投影图，上图左边的是投影到正方体一个面的示意图，实际上影响到的球面是右边那张图。

从侧面看，其中一个球面投影到正方体其中一个面上，边缘与圆心的连线相互之间的夹角为90°，但是和x，y，z轴的角度是45°。我们可以在球的6个方向上，把45°的辅助圆画出来，见下图左边。

上图左边的图画了6个辅助线，蓝线是前后一对，红线是左右一对，绿线是上下一对。分别都是45°的地方和圆心连线与球面相交的点的轨迹。这样我们就可以把投影到外切正方体6个面上的球面画出来，见上图右边。

投影到正方体以后，我们就可以把这个正方体展开了。

一个正方体的展开方式有很多种。不管怎么展开，最小单元都是一个正方形。

以上就是 S2 的投影方案。接下来讲讲其他的投影方案。

首先有下面一种方式，三角形和正方形组合。

这种方式展开图如下图。

这种方式其实很复杂，构成子图形由两种图形构成。坐标转换稍微复杂一点。

再还有一种方式是全部用三角形组成，这种方式三角形个数越多，就能越切近于球体。

上图最左边的图，由20个三角形构成，可以看的出来，菱角非常多，与球体相差比较大，当三角形个数越来越多，就越来越贴近球体。

20个三角形展开以后就可能变成这样。

最后一种方式可能是目前最好的方式，不过也可能是最复杂的方式。按照六边形来投影。

六边形的菱角比较少，六个边也能相互衔接其他的六边形。看上图最后边的图可以看出来，六边形足够多以后，非常近似球体。

六边形展开以后就是上面这样。当然这里只有12个六边形。六边形个数越多越好，粒度越细，就越贴近球体。

Uber 在一个公开分享上提到了他们用的是六边形的网格，把城市划分为很多六边形。这块应该是他们自己开发的。也许滴滴也是划分六边形，也许滴滴有更好的划分方案也说不定。

回到 S2 上面来，S2是用的正方形。这样第一步的球面坐标进一步的被转换成 f(x,y,z) -> g(face,u,v)，face是正方形的六个面，u，v对应的是六个面中的一个面上的x，y坐标。

3. 球面矩形投影修正

上一步我们把球面上的球面矩形投影到正方形的某个面上，形成的形状类似于矩形，但是由于球面上角度的不同，最终会导致即使是投影到同一个面上，每个矩形的面积也不大相同。

上图就表示出了球面上个一个球面矩形投影到正方形一个面上的情况。

经过实际计算发现，最大的面积和最小的面积相差5.2倍。见上图左边。相同的弧度区间，在不同的纬度上投影到正方形上的面积不同。

现在就需要修正各个投影出来形状的面积。如何选取合适的映射修正函数就成了关键。目标是能达到上图右边的样子，让各个矩形的面积尽量相同。

这块转换的代码在 C++ 的版本里面才有详细的解释，在 Go 的版本里面只一笔带过了。害笔者懵逼了好久。

线性变换是最快的变换，但是变换比最小。tan() 变换可以使每个投影以后的矩形的面积更加一致，最大和最小的矩形比例仅仅只差0.414。可以说非常接近了。但是 tan() 函数的调用时间非常长。如果把所有点都按照这种方式计算的话，性能将会降低3倍。

最后谷歌选择的是二次变换，这是一个近似切线的投影曲线。它的计算速度远远快于 tan() ，大概是 tan() 计算的3倍速度。生成的投影以后的矩形大小也类似。不过最大的矩形和最小的矩形相比依旧有2.082的比率。

上表中，ToPoint 和 FromPoint 分别是把单位向量转换到 Cell ID 所需要的毫秒数、把 Cell ID 转换回单位向量所需的毫秒数（Cell ID 就是投影到正方体六个面，某个面上矩形的 ID，矩形称为 Cell，它对应的 ID 称为 Cell ID）。ToPointRaw 是某种目的下，把 Cell ID 转换为非单位向量所需的毫秒数。

在 S2 中默认的转换是二次转换。

1
2

复制代码
#define S2_PROJECTION S2_QUADRATIC_PROJECTION

详细看看这三种转换到底是怎么转换的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

复制代码
#if S2_PROJECTION == S2_LINEAR_PROJECTION

inline double S2::STtoUV(double s) {
  return 2 * s - 1;
}

inline double S2::UVtoST(double u) {
  return 0.5 * (u + 1);
}

#elif S2_PROJECTION == S2_TAN_PROJECTION

inline double S2::STtoUV(double s) {
  // Unfortunately, tan(M_PI_4) is slightly less than 1.0.  This isn't due to
  // a flaw in the implementation of tan(), it's because the derivative of
  // tan(x) at x=pi/4 is 2, and it happens that the two adjacent floating
  // point numbers on either side of the infinite-precision value of pi/4 have
  // tangents that are slightly below and slightly above 1.0 when rounded to
  // the nearest double-precision result.

  s = tan(M_PI_2 * s - M_PI_4);
  return s + (1.0 / (GG_LONGLONG(1) << 53)) * s;
}

inline double S2::UVtoST(double u) {
  volatile double a = atan(u);
  return (2 * M_1_PI) * (a + M_PI_4);
}

#elif S2_PROJECTION == S2_QUADRATIC_PROJECTION

inline double S2::STtoUV(double s) {
  if (s >= 0.5) return (1/3.) * (4*s*s - 1);
  else          return (1/3.) * (1 - 4*(1-s)*(1-s));
}

inline double S2::UVtoST(double u) {
  if (u >= 0) return 0.5 * sqrt(1 + 3*u);
  else        return 1 - 0.5 * sqrt(1 - 3*u);
}

#else

#error Unknown value for S2_PROJECTION

#endif

上面有一处对 tan(M_PI_4) 的处理，是因为精度的原因，导致略小于1.0 。

所以投影之后的修正函数三种变换应该如下：

1
2
3
4
5
6
7
8
9
10

复制代码
// 线性转换
u = 0.5 * ( u + 1)

// tan() 变换
u = 2 / pi * (atan(u) + pi / 4) = 2 * atan(u) / pi + 0.5

// 二次变换
u >= 0，u = 0.5 * sqrt(1 + 3*u)
u < 0,    u = 1 - 0.5 * sqrt(1 - 3*u)

注意上面虽然变换公式只写了u，不代表只变换u。实际使用过程中，u，v都分别当做入参，都会进行变换。

这块修正函数在 Go 的版本里面就直接只实现了二次变换，其他两种变换方式找遍整个库，根本没有提及。

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

复制代码
// stToUV converts an s or t value to the corresponding u or v value.
// This is a non-linear transformation from [-1,1] to [-1,1] that
// attempts to make the cell sizes more uniform.
// This uses what the C++ version calls 'the quadratic transform'.
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))
}

// uvToST is the inverse of the stToUV transformation. Note that it
// is not always true that uvToST(stToUV(x)) == x due to numerical
// errors.
func uvToST(u float64) float64 {
    if u >= 0 {
        return 0.5 * math.Sqrt(1+3*u)
    }
    return 1 - 0.5*math.Sqrt(1-3*u)
}

经过修正变换以后，u，v都变换成了s，t。值域也发生了变化。u，v的值域是[-1,1]，变换以后，是s，t的值域是[0,1]。

至此，小结一下，球面上的点S(lat,lng) -> f(x,y,z) -> g(face,u,v) -> h(face,s,t)。目前总共转换了4步，球面经纬度坐标转换成球面xyz坐标，再转换成外切正方体投影面上的坐标，最后变换成修正后的坐标。

到目前为止，S2 可以优化的点有两处，一是投影的形状能否换成六边形？二是修正的变换函数能否找到一个效果和 tan() 类似的函数，但是计算速度远远高于 tan()，以致于不会影响计算性能？

4. 点与坐标轴点相互转换

在 S2 算法中，默认划分 Cell 的等级是30，也就是说把一个正方形划分为 2^30 * 2^30个小的正方形。

那么上一步的s，t映射到这个正方形上面来，对应该如何转换呢？

s，t的值域是[0,1]，现在值域要扩大到[0,230-1]。

1
2
3
4
5

复制代码
// stToIJ converts value in ST coordinates to a value in IJ coordinates.
func stToIJ(s float64) int {
    return clamp(int(math.Floor(maxSize*s)), 0, maxSize-1)
}

C ++ 的实现版本也一样

1
2
3
4
5
6
7
8

复制代码
inline int S2CellId::STtoIJ(double s) {
  // Converting from floating-point to integers via static_cast is very slow
  // on Intel processors because it requires changing the rounding mode.
  // Rounding to the nearest integer using FastIntRound() is much faster.
  // 这里减去0.5是为了四舍五入
  return max(0, min(kMaxSize - 1, MathUtil::FastIntRound(kMaxSize * s - 0.5)));
}

到这一步，是h(face,s,t) -> H(face,i,j)。

5. 坐标轴点与希尔伯特曲线 Cell ID 相互转换

最后一步，如何把 i，j 和希尔伯特曲线上的点关联起来呢？

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

复制代码
const (
    lookupBits = 4
    swapMask   = 0x01
    invertMask = 0x02
)

var (
    ijToPos = [4][4]int{
        {0, 1, 3, 2}, // canonical order
        {0, 3, 1, 2}, // axes swapped
        {2, 3, 1, 0}, // bits inverted
        {2, 1, 3, 0}, // swapped & inverted
    }
    posToIJ = [4][4]int{
        {0, 1, 3, 2}, // canonical order:    (0,0), (0,1), (1,1), (1,0)
        {0, 2, 3, 1}, // axes swapped:       (0,0), (1,0), (1,1), (0,1)
        {3, 2, 0, 1}, // bits inverted:      (1,1), (1,0), (0,0), (0,1)
        {3, 1, 0, 2}, // swapped & inverted: (1,1), (0,1), (0,0), (1,0)
    }
    posToOrientation = [4]int{swapMask, 0, 0, invertMask | swapMask}
    lookupIJ         [1 << (2*lookupBits + 2)]int
    lookupPos        [1 << (2*lookupBits + 2)]int
)

在变换之前，先来解释一下定义的一些变量。

posToIJ 代表的是一个矩阵，里面记录了一些单元希尔伯特曲线的位置信息。

把 posToIJ 数组里面的信息用图表示出来，如下图：

同理，把 ijToPos 数组里面的信息用图表示出来，如下图：

posToOrientation 数组里面装了4个数字，分别是1,0,0,3。 lookupIJ 和 lookupPos 分别是两个容量为1024的数组。这里面分别对应的就是希尔伯特曲线 ID 转换成坐标轴 IJ 的转换表，和坐标轴 IJ 转换成希尔伯特曲线 ID 的转换表。

1
2
3
4
5
6
7
8

复制代码

func init() {
    initLookupCell(0, 0, 0, 0, 0, 0)
    initLookupCell(0, 0, 0, swapMask, 0, swapMask)
    initLookupCell(0, 0, 0, invertMask, 0, invertMask)
    initLookupCell(0, 0, 0, swapMask|invertMask, 0, swapMask|invertMask)
}

这里是初始化的递归函数，在希尔伯特曲线的标准顺序中可以看到是有4个格子，并且格子都有顺序的，所以初始化要遍历满所有顺序。入参的第4个参数，就是从0 - 3 。

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

复制代码
// initLookupCell initializes the lookupIJ table at init time.
func initLookupCell(level, i, j, origOrientation, pos, orientation int) {

    if level == lookupBits {
        ij := (i << lookupBits) + j
        lookupPos[(ij<<2)+origOrientation] = (pos << 2) + orientation
        lookupIJ[(pos<<2)+origOrientation] = (ij << 2) + orientation
    
        return
    }

    level++
    i <<= 1
    j <<= 1
    pos <<= 2
    
    r := posToIJ[orientation]
    
    initLookupCell(level, i+(r[0]>>1), j+(r[0]&1), origOrientation, pos, orientation^posToOrientation[0])
    initLookupCell(level, i+(r[1]>>1), j+(r[1]&1), origOrientation, pos+1, orientation^posToOrientation[1])
    initLookupCell(level, i+(r[2]>>1), j+(r[2]&1), origOrientation, pos+2, orientation^posToOrientation[2])
    initLookupCell(level, i+(r[3]>>1), j+(r[3]&1), origOrientation, pos+3, orientation^posToOrientation[3])
}

上面这个函数是生成希尔伯特曲线的。我们可以看到有一处对pos << 2的操作，这里是把位置变换到第一个4个小格子中，所以位置乘以了4。

由于初始设置的lookupBits = 4，所以i，j的变化范围是从[0,15]，总共有16*16=256个，然后i，j坐标是表示的4个格子，再细分，lookupBits = 4这种情况下能表示的点的个数就是256*4=1024个。这也正好是 lookupIJ 和 lookupPos 的总容量。

画一个局部的图，i，j从0-7变化。

上图是一个4阶希尔伯特曲线。初始化的实际过程就是初始化4阶希尔伯特上的1024个点的坐标与坐标轴上的x，y轴的对应关系表。

举个例子，下表是i，j在递归过程中产生的中间过程。下表是 lookupPos 表计算过程。

取出一行详细分析一下计算过程。

假设当前(i,j)=(0,2)，ij 的计算过程是把 i 左移4位再加上 j，整体结果再左移2位。目的是为了留出2位的方向位置。ij的前4位是i，接着4位是j，最后2位是方向。这样计算出ij的值就是8 。

接着计算lookupPos[i j]的值。从上图中可以看到(0,2)代表的单元格的4个数字是16，17，18，19 。计算到这一步，pos的值为4（pos是专门记录生成格子到第几个了，总共pos的值会循环0-255）。pos代表的是当前是第几个格子(4个小格子组成)，当前是第4个，每个格子里面有4个小格子。所以4*4就可以偏移到当前格子的第一个数字，也就是16 。posToIJ 数组里面会记录下当前格子的形状。从这里我们从中取出 orientation 。

看上图，16，17，18，19对应的是 posToIJ 数组轴旋转的情况，所以17是位于轴旋转图的数字1代表的格子中。这时 orientation = 1 。

这样 lookupPos[i j] 表示的数字就计算出来了，4*4+1=17 。这里就完成了i，j与希尔伯特曲线上数字的对应。

那如何由希尔伯特曲线上的数字对应到实际的坐标呢？

lookupIJ 数组里面记录了反向的信息。lookupIJ 数组 和 lookupPos 数组存储的信息正好是反向的。lookupIJ 数组 下表存的值是 lookupPos 数组 的下表。我们查 lookupIJ 数组 ，lookupIJ[17]的值就是8，对应算出来(i,j)=(0,2)。这个时候的i，j还是大格子。还是需要借助 posToIJ 数组 里面描述的形状信息。当前形状是轴旋转，之前也知道 orientation = 1，由于每个坐标里面有4个小格子，所以一个i，j代表的是2个小格子，所以需要乘以2，再加上形状信息里面的方向，可以计算出实际的坐标
(0 * 2 + 1 , 2 * 2 + 0) = ( 1，4) 。

至此，整个球面坐标的坐标映射就已经完成了。

球面上的点S(lat,lng) -> f(x,y,z) -> g(face,u,v) -> h(face,s,t) -> H(face,i,j) -> CellID。目前总共转换了6步，球面经纬度坐标转换成球面xyz坐标，再转换成外切正方体投影面上的坐标，最后变换成修正后的坐标，再坐标系变换，映射到 [0,230-1]区间，最后一步就是把坐标系上的点都映射到希尔伯特曲线上。

6. S2 Cell ID 数据结构

最后需要来谈谈 S2 Cell ID 数据结构，这个数据结构直接关系到不同 Level 对应精度的问题。

上图左图中对应的是 Level 30 的情况，右图对应的是 Level 24 的情况。(2的多少次方，角标对应的也就是 Level 的值)

在 S2 中，每个 CellID 是由64位的组成的。可以用一个 uint64 存储。开头的3位表示正方体6个面中的一个，取值范围[0,5]。3位可以表示0-7，但是6，7是无效值。

64位的最后一位是1，这一位是特意留出来的。用来快速查找中间有多少位。从末尾最后一位向前查找，找到第一个不为0的位置，即找到第一个1。这一位的前一位到开头的第4位（因为前3位被占用）都是可用数字。

绿色格子有多少个就能表示划分多少格。上图左图，绿色的有60个格子，于是可以表示[0,230 -1] * [0,230 -1]这么多个格子。上图右图中，绿色格子只有48个，那么就只能表示[0,224 -1]*[0,224 -1]这么多个格子。

那么不同 level 可以代表的网格的面积究竟是多大呢？

由上一章我们知道，由于投影的原因，所以导致投影之后的面积依旧有大小差别。

这里推算的公式比较复杂，就不证明了，具体的可以看文档。

1
2
3
4

复制代码
MinAreaMetric = Metric{2, 8 * math.Sqrt2 / 9} 
AvgAreaMetric = Metric{2, 4 * math.Pi / 6} 
MaxAreaMetric = Metric{2, 2.635799256963161491}

这就是最大最小面积和平均面积的倍数关系。

(下图单位是km2，平方公里)

level 0 就是正方体的六个面之一。地球表面积约等于510,100,000 km2。level 0 的面积就是地球表面积的六分之一。level 30 能表示的最小的面积0.48cm2，最大也就0.93cm2 。

7. S2 与 Geohash 对比

Geohash 有12级，从5000km 到 3.7cm。中间每一级的变化比较大。有时候可能选择上一级会大很多，选择下一级又会小一些。比如选择字符串长度为4，它对应的 cell 宽度是39.1km，需求可能是50km，那么选择字符串长度为5，对应的 cell 宽度就变成了156km，瞬间又大了3倍了。这种情况选择多长的 Geohash 字符串就比较难选。选择不好，每次判断可能就还需要取出周围的8个格子再次进行判断。Geohash 需要 12 bytes 存储。

S2 有30级，从 0.7cm² 到 85,000,000km² 。中间每一级的变化都比较平缓，接近于4次方的曲线。所以选择精度不会出现 Geohash 选择困难的问题。S2 的存储只需要一个 uint64 即可存下。

S2 库里面不仅仅有地理编码，还有其他很多几何计算相关的库。地理编码只是其中的一小部分。本文没有介绍到的 S2 的实现还有很多很多，各种向量计算，面积计算，多边形覆盖，距离问题，球面球体上的问题，它都有实现。

S2 还能解决多边形覆盖的问题。比如给定一个城市，求一个多边形刚刚好覆盖住这个城市。

如上图，生成的多边形刚刚好覆盖住下面蓝色的区域。这里生成的多边形可以有大有小。不管怎么样，最终的结果也是刚刚覆盖住目标物。

用相同的 Cell 也可以达到相同的目的，上图就是用相同 Level 的 Cell 覆盖了整个圣保罗城市。

这些都是 Geohash 做不到的。

多边形覆盖利用的是近似的算法，虽然不是严格意义上的最优解，但是实践中效果特别好。

额外值得说明的一点是，Google 文档上强调了，这种多边形覆盖的算法虽然对搜索和预处理操作非常有用，但是“不可依赖”的。理由也是因为是近似算法，并不是唯一最优算法，所以得到的解会依据库的不同版本而产生变化。

8. S2 Cell 举例

先来看看经纬度和 CellID 的转换，以及矩形面积的计算。

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

复制代码
    latlng := s2.LatLngFromDegrees(31.232135, 121.41321700000003)
    cellID := s2.CellIDFromLatLng(latlng)
    cell := s2.CellFromCellID(cellID) //9279882742634381312

    // cell.Level()
    fmt.Println("latlng = ", latlng)
    fmt.Println("cell level = ", cellID.Level())
    fmt.Printf("cell = %d\n", cellID)
    smallCell := s2.CellFromCellID(cellID.Parent(10))
    fmt.Printf("smallCell level = %d\n", smallCell.Level())
    fmt.Printf("smallCell id = %b\n", smallCell.ID())
    fmt.Printf("smallCell ApproxArea = %v\n", smallCell.ApproxArea())
    fmt.Printf("smallCell AverageArea = %v\n", smallCell.AverageArea())
    fmt.Printf("smallCell ExactArea = %v\n", smallCell.ExactArea())

这里 Parent 方法参数可以直接指定返回改点的对应 level 的 CellID。

上面那些方法打印出来的结果如下：

1
2
3
4
5
6
7
8
9
10
11

复制代码
latlng =  [31.2321350, 121.4132170]
cell level =  30
cell = 3869277663051577529

****Parent **** 10000000000000000000000000000000000000000
smallCell level = 10
smallCell id = 11010110110010011011110000000000000000000000000000000000000000
smallCell ApproxArea = 1.9611002454714756e-06
smallCell AverageArea = 1.997370817559429e-06
smallCell ExactArea = 1.9611009480261058e-06

再举一个覆盖多边形的例子。我们先随便创建一个区域。

1
2
3
4
5
6
7

复制代码
    rect = s2.RectFromLatLng(s2.LatLngFromDegrees(48.99, 1.852))
    rect = rect.AddPoint(s2.LatLngFromDegrees(48.68, 2.75))

    rc := &s2.RegionCoverer{MaxLevel: 20, MaxCells: 10, MinLevel: 2}
    r := s2.Region(rect.CapBound())
    covering := rc.Covering(r)

覆盖参数设置成 level 2 - 20，最多的 Cell 的个数是10个。

接着我们把 Cell 至多改成20个。

最后再改成30个。

可以看到相同的 level 的范围，cell 个数越多越精确目标范围。

这里是匹配矩形区域，匹配圆形区域也同理。

代码就不贴了，与矩形类似。这种功能 Geohash 就做不到，需要自己手动实现了。

最后举一个多边形匹配的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

复制代码

func testLoop() {

    ll1 := s2.LatLngFromDegrees(31.803269, 113.421145)
    ll2 := s2.LatLngFromDegrees(31.461846, 113.695803)
    ll3 := s2.LatLngFromDegrees(31.250756, 113.756228)
    ll4 := s2.LatLngFromDegrees(30.902604, 113.997927)
    ll5 := s2.LatLngFromDegrees(30.817726, 114.464846)
    ll6 := s2.LatLngFromDegrees(30.850743, 114.76697)
    ll7 := s2.LatLngFromDegrees(30.713884, 114.997683)
    ll8 := s2.LatLngFromDegrees(30.430111, 115.42615)
    ll9 := s2.LatLngFromDegrees(30.088491, 115.640384)
    ll10 := s2.LatLngFromDegrees(29.907713, 115.656863)
    ll11 := s2.LatLngFromDegrees(29.783833, 115.135012)
    ll12 := s2.LatLngFromDegrees(29.712295, 114.728518)
    ll13 := s2.LatLngFromDegrees(29.55473, 114.24512)
    ll14 := s2.LatLngFromDegrees(29.530835, 113.717776)
    ll15 := s2.LatLngFromDegrees(29.55473, 113.3772)
    ll16 := s2.LatLngFromDegrees(29.678892, 112.998172)
    ll17 := s2.LatLngFromDegrees(29.941039, 112.349978)
    ll18 := s2.LatLngFromDegrees(30.040949, 112.025882)
    ll19 := s2.LatLngFromDegrees(31.803269, 113.421145)

    point1 := s2.PointFromLatLng(ll1)
    point2 := s2.PointFromLatLng(ll2)
    point3 := s2.PointFromLatLng(ll3)
    point4 := s2.PointFromLatLng(ll4)
    point5 := s2.PointFromLatLng(ll5)
    point6 := s2.PointFromLatLng(ll6)
    point7 := s2.PointFromLatLng(ll7)
    point8 := s2.PointFromLatLng(ll8)
    point9 := s2.PointFromLatLng(ll9)
    point10 := s2.PointFromLatLng(ll10)
    point11 := s2.PointFromLatLng(ll11)
    point12 := s2.PointFromLatLng(ll12)
    point13 := s2.PointFromLatLng(ll13)
    point14 := s2.PointFromLatLng(ll14)
    point15 := s2.PointFromLatLng(ll15)
    point16 := s2.PointFromLatLng(ll16)
    point17 := s2.PointFromLatLng(ll17)
    point18 := s2.PointFromLatLng(ll18)
    point19 := s2.PointFromLatLng(ll19)

    points := []s2.Point{}
    points = append(points, point19)
    points = append(points, point18)
    points = append(points, point17)
    points = append(points, point16)
    points = append(points, point15)
    points = append(points, point14)
    points = append(points, point13)
    points = append(points, point12)
    points = append(points, point11)
    points = append(points, point10)
    points = append(points, point9)
    points = append(points, point8)
    points = append(points, point7)
    points = append(points, point6)
    points = append(points, point5)
    points = append(points, point4)
    points = append(points, point3)
    points = append(points, point2)
    points = append(points, point1)

    loop := s2.LoopFromPoints(points)

    fmt.Println("----  loop search (gets too much) -----")
    // fmt.Printf("Some loop status items: empty:%t   full:%t \n", loop.IsEmpty(), loop.IsFull())

    // ref: https://github.com/golang/geo/issues/14#issuecomment-257064823
    defaultCoverer := &s2.RegionCoverer{MaxLevel: 20, MaxCells: 1000, MinLevel: 1}
    // rg := s2.Region(loop.CapBound())
    // cvr := defaultCoverer.Covering(rg)
    cvr := defaultCoverer.Covering(loop)

    // fmt.Println(poly.CapBound())
    for _, c3 := range cvr {
        fmt.Printf("%d,\n", c3)
    }
}

这里用到了 Loop 类，这个类的初始化的最小单元是 Point，Point 是由经纬度产生的。最重要的一点需要注意的是，多边形是按照逆时针方向，左手边区域确定的。

如果一不小心点是按照顺时针排列的话，那么多边形确定的是外层更大的面，意味着球面除去画的这个多边形以外的都是你想要的多边形。

举个具体的例子，假如我们想要画的多边形是下图这个样子的：

如果我们用顺时针的方式依次存储 Point 的话，并用顺时针的这个数组去初始化 Loop，那么就会出现“奇怪”的现象。如下图：

这张图左上角的顶点和右下角的顶点在地球上是重合的。如果把这个地图重新还原成球面，那么就是整个球面中间挖空了一个多边形。

把上图放大，如下图：

这样就可以很清晰的看到了，中间被挖空了一个多边形。造成这种现象的原因就是按照顺时针的方向存储了每个点，那么初始化一个 Loop 的时候就会选择多边形外圈的更大的多边形。

使用 Loop 一定要切记，顺时针表示的是外圈多边形，逆时针表示的是内圈多边形。

多边形覆盖的问题同之前举的例子一样：

相同的 MaxLevel = 20，MinLevel = 1，MaxCells 不同，覆盖的精度就不同，下图是 MaxCells = 100 的情况：

下图是 MaxCells = 1000 的情况：

从这个例子也可以看出来 相同的 Level 范围，MaxCells 越精度，覆盖的精度越高。

9. S2 的应用

S2 目前应用比较多，用在和地图相关业务上更多。Google Map 就直接大量使用了 S2 ，速度有多快读者可以自己体验体验。Uber 在搜寻最近的出租车也是用的 S2 算法进行计算的。场景的例子就是本篇文章引语里面提到的场景。滴滴应该也有相关的应用，也许有更加优秀的解法。现在很火的共享单车也会用到这些空间索引算法。

最后就是外卖行业和地图关联也很密切。美团和饿了么相信也在这方面有很多应用，具体哪里用到了，就请读者自己想象吧。

五. 最后

本篇文章里面着重介绍了谷歌的 S2 算法的基础实现。虽然 Geohash 也是空间点索引算法，但是性能方面比谷歌的 S2 略逊一筹。并且大公司的数据库也基本上开始采用谷歌的 S2 算法进行索引。

关于空间搜索其实还有一大类问题，如何搜索多维空间线，多维空间面，多维空间多边形呢？他们都是由无数个空间点组成的。实际的例子，比如街道，高楼，铁路，河流。要搜索这些东西，数据库表如何设计？如何做到高效的搜索呢？还能用 B+ 树来做么？

答案当然是也可以实现高效率的搜索，那就需要用到 R 树，或者 R 树 和 B+树。

这部分就不在本文的范畴内了，下次有空可以再分享一篇《多维空间多边形索引算法》

最后，请大家多多指点。

Reference：
Z-order curve
Geohash wikipedia
Geohash-36
Geohash 在线演示
Geohash 查询
Geohash Converter
Space-filling curve
List of fractals by Hausdorff dimension
介绍希尔伯特曲线的Youtube视频
希尔伯特曲线在线演示
希尔伯特曲线论文
Mapping the Hilbert curve
S2 谷歌官方PPT
Go 版 S2 源码 github.com/golang/geo
Java 版 S2 源码 github.com/google/s2-geometry-library-java
L’Huilier’s Theorem

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: halfrost.com/go_spatial_…

本文转载自: 掘金

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