Posted on | In

第二章主要讲了三个问题

  • 40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数
  • 将一个n元一维向量向左旋转i个位置
  • 给定一个英文字典，找出其中的所有的变位词集合。例如”pots”, “stop”, “tops”。

Posted on | Edited on | In

直接从习题开始吧

1 表1.1中若只包含编号为1和4的两个样例，试给出相应的版本空间.

假设空间指的是问题所有假设组成的空间，我们可以把学习过程看作是在假设空间中搜索的过程，搜索目标是寻找与训练集“匹配”的假设。

假设数据集有n种属性，第i个属性可能的取值有

Posted on | Edited on | In

好久没写博客了，最近拉出来，准备写点学习的内容和总结。

本地启动不了，来是theme没有下载，需要去next单独把theme下载到themes目录下，并且保证文件名和config中配置的一致。

然后现在发现about，category等都消失了，待会看看什么原因。应该是theme中的config需要配置一下，就可以了，语言就默认为英文吧。

最近准备学一点机器学习的内容，从张志华博士的《机器学习》开始吧。

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Posted on | Edited on | In

Sentinel是Redis的高可用性解决方案：由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器以及这些主服务器属下的所有从服务器，并在被监视的主服务器进去下线状态时，自动将下线主服务器属下的某个从服务器升级为新的主服务器，然后由新的主服务器代替已下线的主服务器继续处理命令请求。

Read more »

Posted on | Edited on | In

今天讲一下多机数据库的实现。

假设现在有两个Redis服务器，地址分别为127.0.0.1:6379和127.0.0.1:12345，如果我们向服务器127.0.0.1:12345发送以下命令127.0.0.1:12345: SLAVEOF 127.0.0.1 6379，那么12345将成为6379的从服务器。

旧版复制功能的实现

Redis的复制功能分为同步sync和命令传播command propagate两个操作：

同步

从服务器对主服务器的同步操作需要通过向主服务器发送SYNC命令来完成，以下是SYNC命令的执行步骤：

  1. 从服务器向主服务器发送SYNC命令
  2. 收到SYNC命令的主服务器执行BGSAVE命令，在后台生成一个RDB文件，并使用一个缓冲区记录从现在开始执行的所有写命令。
  3. 当主服务器的BGSAVE命令执行完毕时，主服务器会将BGSAVE命令生成的RDB文件发送给从服务器，从服务器接收并载入这个RDB文件，将自己的数据库状态更新至主服务器执行BGSAVE命令时的数据库状态。
  4. 主服务器将记录在缓冲区里面的所有写命令发送给从服务器，从服务器执行这些写命令，将自己的数据库状态更新至主服务器数据库当前所处的状态。

命令传播

主服务器会将自己执行的写命令发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态。

旧版复制功能的缺陷

旧版复制功能对于断线后重复制，采用的是跟初次复制一样的策略，导致断线重复制成本非常高。

新版复制功能的实现

Redis从2.8版本开始，使用PSYNC命令代替SYNC命令来执行复制时的同步操作。

PSYNC命令具有完整重同步和部分重同步两种模式：

  • 完整重同步和初次复制一样，让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓冲区里面的写命令来进行同步。
  • 部分重同步则用于处理断线后重复制情况。

部分重同步的实现

部分重同步功能由以下三个部分构成

  • 主服务器的复制偏移量和从服务器的复制偏移量
  • 主服务器的复制积压缓冲区
  • 服务器的运行ID

复制偏移量

执行复制的双方-主服务器和从服务器会分别维护一个复制偏移量

  • 主服务器每次向从服务器传播N个字节的数据时，就将字节的复制偏移量的值加上N
  • 从服务器每次收到主服务器传播来的N个字节的数据时，就将字节的复制偏移量的值加上N
  • 对比主从服务器的复制偏移量，程序可以很容易地知道主从服务器是否处于一致状态。

复制积压缓冲区

复制积压缓冲区是由主服务器维护的一个固定长度先进先出队列，默认大小为1MB。

当从服务器重新连上主服务器时，从服务器会通过PSYNC命令将自己的复制偏移量offset发送给主服务器，主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作。要么是完全重同步，要么是部分重同步

服务器运行ID

  • 每个Redis服务器，不论主从，都会有自己的运行ID
  • 在服务器启动时自动生成，由40个随机的十六进制字符组成

当从服务器对主服务器进行初次复制时，主服务器会将自己的运行ID传送给从服务器，而从服务器则会将这个运行ID保存起来。

心跳检测

在命令传播节点，从误区默认会以每秒一次的频率才，向主服务器发送命令：REPLCONF ACK <replication_offset>，其中replication_offset是从服务器当前的复制偏移量，主要有三个作用：

  • 检测主从服务器的网络连接状态
  • 辅助实现min-slaves选项
  • 检测命令丢失

Posted on | Edited on | In

Redis服务器将所有数据库都保存在服务器状态redis.h/redisServer结构的db数组中，db数组的每个项都是一个redis.h/redisDb结构，每个redisDb结构代表一个数据库。

1
2
3
4
5
6
7
struct redisServer {
    // 一个数组，保存着服务器中的所有数据库
    redisDb *db;

    // 服务器的数据库数量，默认为16
    int dbNum;
}

Redis是一个键值对数据库服务器买服务器中的每个数据库都由一个redis.h/redisDb结构表示，其中，redisDb结构的dict字典保存了数据库中的所有键值对，我们将这个字典称为键空间。

1
2
3
4
5
6
7
struct redisDb {
    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict;

    // 过期字典，保存着键的过期时间
    dict *expires;
}

设置键的生存时间或过期时间

通过EXPIRE命令或者PEXPIRE命令，客户端可以以秒或者毫秒精度为数据库中的某个键设置生存时间，在经过指定的秒数或毫秒数之后，服务器就会自动删除生存时间为0的键。

EXPIREAT或PEXPIREAT，以秒或者毫秒精度给数据库中的某个键设置过期时间。

TTL 查看过期时间，time to live

过期键删除策略

  • 定时删除：在设定键的过期时间时，创建一个定时器，定时器定时删除
  • 惰性删除：每次从键空间获取键时，检查是否过期
  • 定期删除：每隔一段时间，程序对数据库检查，删除过期键

Redis服务器实际使用的是惰性删除和定期删除两种策略：通过配合使用这两种删除策略，服务器可以很好地在合理使用CPU时间和避免浪费内存空间之间取得平衡。

AOF、RDB和复制功能对过期键的处理

生成RDB文件

过期键不会被保存到RDB文件中

载入RDB文件

  • 以主服务器模式运行，在载入的时候会对过期键进行检查
  • 以从服务器模式运行，会载入全部的键，不过在主从同步的时候，会删除

AOF文件写入

过期键不会被保存到AOF文件中

复制

  • 主服务器在删除一个过期键之后，会显示地向所有从服务器发送一个DEL命令，告知从服务器删除这个过期键。
  • 从服务器在执行客户端发生的读命令时，即使碰到过期键也不会将过期键删除，而是继续像处理未过期的键一样来处理过期键。
  • 从服务器只有在接到主服务器发来的DEL命令之后，才会删除过期键。

Posted on | Edited on

网上搜一下idea+spring关键字出来的都是Spring MVC项目，我只是想学习Spring，根本不需要什么web项目啊。

废话不多说，直接上流程

  1. 左上角File-New-Project
  2. 选择Maven，勾选create from archetype，选择org.apache.maven.archetypes:maven-archetype-quickstart，Next输入GroupId “com.stefler” ArtifactId “spring-start”，Next，Finish.
  3. 稍等一段时间，建好工程。
  4. 打开pom文件，在dependencies中添加
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    <!-- https://mvnrepository.com/artifact/org.springframework/spring-core -->
            <dependency>
                <groupId>org.springframework</groupId>
                <artifactId>spring-core</artifactId>
                <version>4.2.5.RELEASE</version>
            </dependency>

            <!-- https://mvnrepository.com/artifact/org.springframework/spring-core -->
            <dependency>
                <groupId>org.springframework</groupId>
                <artifactId>spring-context</artifactId>
                <version>4.2.5.RELEASE</version>
            </dependency>

这是spring的两个核心依赖，稍等一段时间idea会auto import所有的依赖。

  1. 在src/main目录下新建文件夹resources，右击resources -> Mark Directory as -> Resources root。
  2. 在刚才新建的resources目录下新建文件applicationContext.xml，用来放置spring的配置信息。
  3. 在src/main/java/com/stefler目录下新建类InfoCollect，代码如下
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
package com.stefler;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;

/**
 * Created by Qinjiu on 5/12/2017.
 */
public class InfoCollect {
    private String name;
    private int age;
    private String address;
    private String passWord;


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getAddress() {
        return address;
    }

    public void setAddress(String address) {
        this.address = address;
    }

    public String getPassWord() {
        return passWord;
    }

    public void setPassWord(String passWord) {
        this.passWord = passWord;
    }

    public static void main(String[] args) {
        ApplicationContext context = new ClassPathXmlApplicationContext("applicationContext.xml");
        InfoCollect infoCollect = (InfoCollect) context.getBean("infoCollect");
        int i = 1;
    }

}

  1. 在applicationContext.xml中添加bean配置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    <?xml version="1.0" encoding="UTF-8"?>
    <beans xmlns="http://www.springframework.org/schema/beans"
           xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
           xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-3.0.xsd">
        <bean id="infoCollect" class="com.stefler.InfoCollect">
            <property name="name" value="stefler"/>
            <property name="age" value="111"/>
            <property name="address" value="hangzhou"/>
            <property name="passWord" value="22}"/>
        </bean>
    </beans>

  2. 直接运行刚刚InfoCollect中的main函数即可。

Posted on | Edited on | In

自从转了Java开发之后，就一直会面对各种XML和JSON，XML多了之后看起来就特别难看，每次都需要去一个网站的在线XML格式化工具，反正很麻烦就是了。

然后在chrome的插件里也没有找到好用的，今天终于找到一个好用的插件了，sublime text中安装一个插件indent XML，安装好之后，点击菜单栏中的selection->format->选择indent或者auto indent都行，或者快捷键CTRL + F。

nice job~

Posted on | Edited on | In

初识ZooKeeper

ZooKeeper介绍

ZooKeeper是一个开放源代码的分布式协调服务，由雅虎创建，是Google Chubby的开源实现。ZooKeeper的设计目标是将那些复杂且容易出错的分布式一致性服务封装起来，构成一个高效可靠的原语集，并以一系列简单易用的接口提供给用户使用。

ZooKeeper是什么

ZooKeeper可以保证如下分布式一致性特性：

  • 顺序一致性
  • 原子性
  • 单一视图
  • 可靠性
  • 实时性

ZooKeeper的设计目标

ZooKeeper致力于提供一个高性能、高可用，且具有严格的顺序访问控制能力的分布式协调服务。

  • 简单的数据模型
  • 可以构建集群
  • 顺序访问
  • 高性能

ZooKeeper的基本概念

集群角色

ZooKeeper没有沿用船用的slave/master概念，而是引入了Leader、Follower和Observer三种角色。ZooKeeper集群中的所有机器通过一个Leader选举过程来选定一台被称为“Leader”的机器，Leader服务器为客户端提供读和写服务。Follower和Observer都能提供读服务，唯一的区别在于Observer机器不参与Leader选举过程，也不参与写操作的“过半写成功”策略。

会话 Session

客户端和服务器之间建立一个TCP长连接，通过心跳检测与服务器保持有效的会话，也能够向ZooKeeper服务器发生请求并接受响应，通过来能够通过该连接接收来自服务器的Watch时间通知。

数据节点 Znode

指数据模型中的数据单元。ZooKeeper将所有数据村粗在内存中，数据模型是一棵树，由斜杠进行分隔的路径就是一个Znode，例如/foo/path1.每个Znode上都会保存自己的数据内容，同事还会保存一系列属性信息。

  • 持久节点：需要主动进行Znode移除操作。
  • 临时结点：它的生命周期和客户端会话绑定。

版本

每个Znode都会维护一个叫做Stat的数据结构，Stat中记录了这个Znode的三个数据版本，分别是version-当前Znode的版本，cversion-当前Znode子节点的版本，aversion-当前Znode的acl版本。

Watcher

事件监听器。ZooKeeper允许用户在指定节点上注册一些Watcher，并且在一些特定事件触发的时候，ZooKeeper服务端会将时间通知到感兴趣的客户端上去，该机制是ZooKeeper实现分布式协调服务的重要特性。

ACL

access control lists来进行权限控制。ZooKeeper定义了如下5种权限：

  • CREATE 创建子节点的权限
  • READ 获取节点数据和子节点列表的权限
  • WRITE 更新节点数据的权限0
  • DELETE 删除子节点的权限
  • ADMIN 设置节点ACL的权限

ZooKeeper的ZAB协议

ZooKeeper Atomic Broadcast， ZooKeeper原子消息广播协议。ZooKeeper使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用ZAB的原子广播协议，将服务器数据的状态变更以书屋Proposal的形式广播到所有的副本进程上去。

ZAB协议的核心是定义了对于那些会改变ZooKeeper服务器数据状态的事务请求的处理方式，即：

所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器则称为Follower服务器。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal(提议)，并将该Proposal分发给集群中所有的Follower服务器。之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其将前一个Proposal进行提交。

协议介绍

消息广播

针对客户端的事务请求，Leader服务器会为其生成对应的事务Proposal，并将其发送给集群中其余所有的机器，然后再分别收集各自的选票，最后进行事务提交。

崩溃恢复

核心：能够确保提交已经被Leader提交的事务Proposal，同时丢弃已经被跳过的事务Proposal。

算法描述

  • 发现 discovery 选取最大的epoch
  • 同步 synchronization prepare commit
  • 广播 broadcast

Zookeeper安装

在windows上部署伪集群模式的链接，注意需要给每个机器的data目录下添加一个myid文件。
http://blog.csdn.net/morning99/article/details/40426133

启动zkCli.cmd -server ip:host

Java客户端API使用

创建会话

Zookeeper zk = new Zookeeper();

节点类型共有四种

  • 持久 PERSITENT
  • 持久顺序 PERSITENT_SEQUENTIAL
  • 临时 EPHEMERAL
  • 临时顺序 EPHEMERAL

创建节点

zkClient.create()

Zookeeper不支持递归创建，即无法在父节点不存在的情况下创建一个子节点。

删除节点

zkClient.delete()

在Zookeeper中，只允许删除叶子节点。也就是说如果一个节点存在至少一个子节点的话，那么该节点将无法被直接删除，必须先删除掉其所有子节点。

读取数据

zkClient.getChildren()

调用getChildren()获取到的节点列表，都是数据节点的相对节点路径。

Zookeeper服务端在向客户端发送Watcher”NodeChildrenChanged”事件通知的时候，仅仅只会发出一个通知，而不会把节点的变化情况发送给客户端，需要客户端自己重新获取。另外，由于Watcher通知是一次性的，即一旦触发一次通知后，该Watcher就失效了，因此客户端需要反复注册Watcher。

zkClient.getData()

节点的数据内容或是节点的数据版本编号，都被看作是Zookeeper节点的编号。

更新数据

setData(final String path, byte date[], int version)

CAS理论，对于值V，每次更新前都会比对其值是否是预期值A，只有符合预期，才会将V原子化地更新到新值B。

如果传入的version为-1，就是告诉Zookeeper服务器，客户端需要基于数据的最新版本进行更新操作，没有原子性要求。

检测节点是否存在

zkClient.exists()

  • 无论指定节点是否存在，通过调用exists接口都可以注册Watcher。
  • exists接口中注册的Watcher，能够对节点创建、节点删除和节点数据更新事件进行监听
  • 对于指定节点的子节点的各种变化，都不会通知客户端。

权限控制

当客户端对一个数据节点添加了权限信息后，对于删除操作而言，其作用范围是其子节点。也就是说，当我们对一个数据节点添加权限信息后，依然可以自由地删除这个节点，但是对于这个节点的子节点，就必须使用相应的权限信息才能够删除掉它。