leetcode-二叉树

发表于 2018-01-18 | 分类于 leetcode

1. Maximum Depth of Binary Tree(104)

二叉树的最大深度

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        return Math.max( maxDepth(root.left), maxDepth(root.right) ) + 1;
    }
}

2. Invert Binary Tree(226)

翻转二叉树

Invert a binary tree.
     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if( root == null ){
            return null;
        }
        
        TreeNode tmp = root.left;
        root.left = invertTree( root.right );
        root.right = invertTree( tmp );
        
        return root;
    }
    
}

3. Same Tree(100)

相同二叉树

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true

Example 2:

Input:     1         1
          /           \
         2             2
        [1,2],     [1,null,2]
Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
Output: false

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        else if( p != null && q != null){
            return p.val == q.val && isSameTree( p.left, q.left ) && isSameTree( p.right, q.right );
        }
        else{
            return false;
        }
    }
}

4. Symmetric Tree(101)

对称二叉树

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

递归版

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root.left, root.right);
    }
    
    private boolean helper(TreeNode l, TreeNode r){
        if(l == null && r == null){
            return true;
        }
        else if(l == null || r == null){
            return false;
        }
        return l.val == r.val && helper(l.left, r.right) && helper(l.right, r.left);
    }
}

迭代版

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
    	//Q1和Q2以root为中心
    	//将二叉树一分为二,
    	//root以左的节点左至右顺序入队
    	//root以右的节点右至左顺序入队
    	//相当于对称方向的层序遍历二叉树
        Queue<TreeNode> Q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> Q2 = new LinkedList<TreeNode>();
        
        if(root == null){
            return true;
        }
        Q1.add(root.left);
        Q2.add(root.right);
        while(!Q1.isEmpty() && !Q2.isEmpty()){
            int size1 = Q1.size();
            int size2 = Q2.size();
            if(size1 != size2){
                return false;
            }
            for(int i = 0; i < size1; ++i){
                TreeNode n1 = Q1.remove();
                TreeNode n2 = Q2.remove();
                if(n1 == null && n2 == null){
                    continue;
                }
                if(n1 == null || n2 == null || n1.val != n2.val){
                    return false;
                }
                Q1.add(n1.left);
                Q1.add(n1.right);
                Q2.add(n2.right);
                Q2.add(n2.left);
            }
        }
        return Q1.isEmpty() && Q2.isEmpty();
    }
}

5. Count Complete Tree Nodes(222)

完全二叉树

Given a complete binary tree, count the number of nodes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight == rightHeight){
            return (1 << leftHeight) + countNodes(root.right);
        }
        else{
            return (1 << rightHeight) + countNodes(root.left);
        }
    }
    
    private int height(TreeNode node){
        if(node == null){
            return 0;
        }
        return 1 + height(node.left);
    }
}

6. Balanced Binary Tree(110)

平衡二叉树

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root, 0) >= 0;
    }
    
    //自底往上进行判断
    private int helper(TreeNode root, int height){
        if(root == null){
            return height;
        }
        int leftHeight = helper(root.left, height+1);
        int rightHeight = helper(root.right, height+1);
        if(Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        return Math.max(leftHeight, rightHeight);
    }
}

7. Path Sum(112)

根节点到叶节点的路径和

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

eturn true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return sum == root.val;
        }
        
        int remain = sum - root.val;
        
        return hasPathSum(root.left, remain)
                || hasPathSum(root.right, remain);
    }
}

8. Sum of Left Leaves(404)

二叉树左叶节点的和

Find the sum of all left leaves in a given binary tree.

Example:

3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        int ret = 0;
        if(root.left != null){
            if(root.left.left == null && root.left.right == null){
                ret = root.left.val;
            }
            else{
                ret = sumOfLeftLeaves(root.left);
            }
        }
        ret += sumOfLeftLeaves(root.right);
        
        return ret;
    }
}

9. Binary Tree Paths(257)

返回二叉树的路径

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

1	["1->2->5", "1->3"]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new ArrayList<String>();
        
        if(root == null){
            return ret;
        }
        
        if(root.left == null && root.right == null){
            ret.add( String.valueOf(root.val));
        }
        //把当前节点，接到每条路径上
        List<String> LList = binaryTreePaths(root.left);
        for(int i = 0 ; i < LList.size(); ++i){
            ret.add(root.val + "->" + LList.get(i));
        }
            
        List<String> RList = binaryTreePaths(root.right);
        for(int i = 0; i < RList.size(); ++i){
            ret.add(root.val + "->" + RList.get(i));
        }
        
        return ret;
    }
}

10. Path Sum II(113)

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

数据库笔记-查询处理

发表于 2018-01-15 | 分类于数据库

逻辑查询处理

(8) SELECT (9) DISTINCT <select_list>
(1) FROM <left_table>
(3) <join_type> JOIN <right_table>
(2) 			ON <join_condition>
(4) WHERE <where_condition>
(5) GROUP BY <group_by_list>
(6) WITH {CUBE|ROLLUP}
(7)HAVING <having_condition>
(10) ORDER BY <order_by_list>
(11) LIMIT <limit_number>

1.执行笛卡尔积

FROM子句前后的两张表进行笛卡尔积操作，也叫交叉连接(Cross Join)。

2.ON过滤器

NULL值：UNKNOWN，即表示未知的。即，NULL和NULL是不相等的，NULL与任何值也不相等。

在以下连个特殊条件下，两个NULL值比较是相等的：

GROUP BY 子句把所有NULL值分到同一组；
ORDER BY 子句把所有NULL值排列在一起。

3.添加外部行

只在连接类型为OUTER JOIN时才发生，如LEFT OUT JOIN、RIGHT OUTER JOIN和FULL OUTER JOIN。通常省略了OUTER关键字。

4.WHERE过滤器

有两种过滤不被允许：

由于数据还没有分组，因此现在还不能在WHERE过滤器中使用where_condition=MIN(col)这类对统计的过滤；
由于没有进行列的选取操作，因此在SELECT中使用列的别名不被允许。

eg.

mysql> SELECT custom_id, COUNT(custom_id)
	-> FROM orders
	-> WHERE COUNT(custom_id) < 2;
ERROR 1111(HY000)：Invalid use of group function

SELECT 操作的执行顺序排在WHERE条件之后

mysql> SELECT order_id AS o, custom_id AS c
	-> FROM orders
	-> WHERE c = '163';	
ERROR 1054(42S22)：Unknown colum 'c' in 'where clause'
//修改为：WHERE c.company = '163'

ON过滤器和WHERE过滤器的差别

类型	ON过滤器	WHERE过滤器
OUTER JOIN	会保留表中被ON条件过滤掉的数据	不保留

对于INNER JOIN两者无差别，因为没有添加外部行操作

5.分组

6.ROLLUP或CUBE

指定ROLLUP选项会添加额外的记录到虚拟表；
MYSQL并不支持CUBE。

7.HAVING过滤器

HVAING子查询不能做分组的聚合函数，如下错误示范

1	HAVING COUNT(SELECT ...) < 2

8.SELECT

列的别名不能在SELECT中的其他别名表达式中使用，如下错误示范

1 2	mysql> SELECT order_id AS o, o+1 AS n FROM orders; ERROR 1054(42S22)：Unknown column 'o' in 'field list'

9.DISTINCT

对进行DISTINCT操作的列增加了唯一的索引，以此来去除重复的数据。

对于使用了 GROUP BY 的查询，再使用DISTINCT是多余的，因为已经分组了，不会移除任何行。

10.ORDER BY

无论是InnoDB存储引擎还是MyISAM存储引擎，对于没有使用ORDER BY子句的选择查询，其结果永远不会是按照主键顺序进行排序的。因为没有ORDER BY子句的查询只代表从集合中查询数据，而集合是没有顺序概念的。

NULL值在ORDER BY中被视为最小值。

11.LIMIT

表示从第n条记录开始选择m条记录

1	LIMIT n, m

子查询

概述

子查询是指一个SELECT语句中嵌套另一个SELECT语句。如：

1	SELECT * FROM t1 WHERE column1 = (SELECET column2 FROM t2 );

子查询的限制：

外部语句必须是以下语句之一：SELECT、INSERT、UPDATE、DELETE、SET或DO。
目前用户不能既在一个子查询中修改一个表，又在同一个表中进行选择，虽然这样的操作可用于DELETE、INSERT、REPLACE和UPDATE语句中，但是对于子查询不可以同时进行操作。

常见的子查询

可以使用如下的操作符：

=
>
<
>=
<=
<>

不能使用JOIN来完成的操作，常用子查询进行，例如表t1中有些值与表t2中的最大值相等。

1 2	SELECT col1 FROM t1 WHERE col1 = (SELECT MAX(col2) FROM t2);

又如涉及表的统计时候，也不能用JOIN来得到结果。表t1中的有些行含有的值会在给定的列中出现两次，该例子可以查找出所有的这些行。

1 2	SELECT * FROM t1 AS t WHERE 2 = (SELEECT COUNT(*) FROM t WHERE t1.id = t.id);

使用ANY、IN和SOME进行子查询

ANY关键字必须与一个比较操作符一起使用，SOME是ANY的别名。
ANY关键字的意思：“对于子查询返回的列中任一数值，如果比较结果为TRUE, 则返回TRUE”。如：

1	SELECT col FROM t WHERE col > ANY(SELECT col FROM t2)

关键字IN是“=ANY”的别名。

使用ALL进行子查询

MySQL笔记-数据类型

发表于 2018-01-07

SQL编程

OLTP与OLAP的比较

OLTP（面向交易的处理系统）：

实时性要求高
查询的数据量不是很大
交易一般是确定的，所以OLTP是对确定性数据进行存取
并发性要求高，而且严格要求事务的完整性、安全性

OLAP（数据仓库系统的主要应用），典型应用就是复杂动态报表系统：

实时性要求不是很高
数据量大。因为OLAP支持的是动态查询，用户要通过对很多数据的统计才能得到想要知道的信息
重点在于决策支持，所以查询一般是动态的，也就是说允许用户随时提出查询的要求

数据库引擎

InnoDB存储引擎：
支持事务，其设计目标主要是面向联机事务处理（OLTP）的应用。其特点是行锁设计、支持外键，并支持类似Oracle的非锁定读，即默认读取操作不会产生锁。从MySQL5.5.8开始是默认的存储引擎。
InnoDB通过使用多版本的并发控制（MVCC）来获得高并发性，并且实现了SQL标准的4种隔离级别，默认为REPREATABLE级别

Netty-引导

发表于 2017-12-29

引导类

点击加载

服务器致力于使用一个父Channel来接受来自客户端的连接，并创建子Channel以用于它们之间的通信；而客户端将最可能只需要一个单独的、没有父Channel的来用于它们所有的网络交互。（如UDP，基于无连接的传输协议，因为它们并不是每个连接都需要一个单独的Channel）

为什么引导类是Cloneable的?

有时可能需要创建多个具有类似配置或者完全相同配置的Channel。为了支持这种模式而又需要为每个Channel都创建并配置一个新的引导类实例。在一个已经配置完成的引导类实例上调用clone()方法将返回另一个可以立即使用的引导类实例。
这种方式只会创建引导类实例的EventLoopGroup的一个浅拷贝，所以EventLoopGroup将在所有克隆的Channel实例之间共享。

Channel和EventLoopGroup的兼容性

事件池(阻塞/非阻塞)要对应相应类型的管道。

点击加载

引导服务器

ServerChannel的实现负责创建子Channels，这些子Channel代表已经被接受的连接。

点击加载

//线程池的类型要和管道的类型兼容
NioEventLoopGroup group = new NioEventLoopGroup();
ServerBootstrap serverBootstrap = new ServerBootstrap();
//设置EventLoop, 其提供了用于处理Channel事件的EventLoop
serverBootstrap.group(group)
        .channel(NioServerSocketChannel.class)  //指定要实现的Channel
        .childHandler(new SimpleChannelInboundHandler<ByteBuf>() {
            //设置用于处理已被接受的子Channel的I/O及数据的ChannelInboundHandler
            @Override
            public void channelRead0(ChannelHandlerContext ctx, ByteBuf byteBuf)
                    throws Exception{
                System.out.println("received data");
            }
        });
//通过配置好的ServerBootstrap的实例绑定该Channel
ChannelFuture future = serverBootstrap.bind(new InetSocketAddress(8080));
future.addListener(new ChannelFutureListener() {
    public void operationComplete(ChannelFuture channelFuture) throws Exception {
        if(channelFuture.isSuccess()) {
            System.out.println("Server bound");
        }
        else{
            System.err.println("Bound attempt failed");
            channelFuture.cause().printStackTrace();
        }
    }
});

引导客户端

Boostrap类负责为客户端和使用无连接协议的应用程序创建Channel。

点击加载

下面的代码，引导了一个使用NIO TCP传输的客户端。

EventLoopGroup group = new NioEventLoopGroup();
Bootstrap bootstrap = new Bootstrap();
bootstrap.group(group)
        .channel(NioServerSocketChannel.class)
        .handler(new SimpleChannelInboundHandler<ByteBuf>() {
            @Override
            protected void channelRead0(ChannelHandlerContext ctx, ByteBuf buf)
                throws Exception{
                System.out.println("Received data");
            }
        });
final ChannelFuture future = bootstrap.connect(     //连接到远程主机
        new InetSocketAddress("127.0.0.1", 80));
future.addListener(new ChannelFutureListener() {
    public void operationComplete(ChannelFuture channelFuture) throws Exception {
        if(future.isSuccess()){
            System.out.println("Connection established");
        }
        else{
            System.err.println("Connection attempt failed");
            future.cause().printStackTrace();
        }
    }
});

从Channel引导客户端

假设服务器正在处理一个客户端的请求，这个请求需要它充当第三方系统的客户端。当一个应用程序（如一个代理服务器）必须要和组织现有的系统（如Web服务或者服务数据库）集时，就可能发送这种情况。在这样情况下，将需要从已经被接受的子Channel中引导一个客户端Channel。

一个不创建额外的线程方法：通过将已被接受的子Channel的EventLoop传递给Bootstrap的group方法来共享该EventLoop。因为分配给EventLoop的所有的Channel都是使用同一个线程，所以这避免了额外的线程创建，这个共享的解决方案如下：

点击加载

Netty-EventLoop和线程模型

发表于 2017-12-29 | 分类于 Netty

任务调度

偶尔，需要调度一个任务以便稍后（延迟）执行或者周期性地执行。例如，你可能想要注册一个在客户端已经连接了5分钟之后才触发的任务。一个常见的用例，发送心跳消息到远程节点，以检查连接是否仍然还活着。如果没有响应，你便知道可以关闭该Channel了。

使用ScheduledExecutorService调度任务

class Task implements Runnable{
    public void run(){
        System.out.println("60 seconds later");
    }
}

//创建一个具有10个线程的ScheduledExecutorService
ScheduledExecutorService executor = Executors.newScheduledThreadPool(10);
//调度任务在从现在开始的60秒之后执行
ScheduledFuture<?> future = executor.schedule(new Task(), 60, TimeUnit.SECONDS);
//一旦调度任务执行完毕, 就关闭ScheduledExecutorService以释放资源
executor.shutdown();

使用EventLoop调度任务

Netty使用Channel的EventLoop实现任务调度解决以下问题：ScheduledExecutorService的实现具有局限性，例如，作为线程池管理的一部分，将会有额外的线程创建。如果有大量的任务被紧凑地调度，那么这将会成为一个瓶颈。

使用EventLoop调度周期性的任务和取消任务

Channel ch = ...;
//调度在60秒之后,并且以后每间隔60秒运行
ScheduledFuture<?> future = ch.eventLoop().
        scheduleAtFixedRate(new Task(), 60, 60, TimeUnit.SECONDS);
TimeUnit.SECONDS.sleep(10);
boolean mayInterruptIfRunning = false;
//取消该任务, 不让它再次运行, 并且设置运行中的任务不能被打断
future.cancel(mayInterruptIfRunning);

实现细节

线程管理

Netty线程模型的卓越性能取决于对当前执行的Thread的身份的确定，也就是，确定它是否分配给当前Channel以及它的EventLoop的那一个线程。每一个EventLoop将负责一个Channel的整个生命周期内的所有事件。

如果调用线程正是支撑EventLoop的线程，那么所提交的代码块将会被直接执行。否则，EventLoop将调度该任务以便稍后执行，并将它放入到内部队列中。当EventLoop下次处理它的事件时，它会执行队列中的那儿任务/事件。这也就解释了任何的Thread是如何与Channel直接交互而无需在ChannelHandler中进行额外同步的。

每个EventLoop都有它自己的任务队列，独立于任何其他的EventLoop。下图展示了EventLoop用于调度任务的执行逻辑。

点击加载

EventLoop/线程的分配

异步传输

异步传输实现只使用了少量的EventLoop（以及和它们相关联的Thread），而且在当前的线程模型中，它们可能会被多个Channel所共享。这使得可以通过尽量少的Thread的支撑大量的Channel，而不是每个Channel分配一个Thread。

点击加载

线程安全：一旦一个Channel被分配给一个EventLoop，它将会在它的整个生命周期都使用这个EventLoop（以及相关联的Thread）。

阻塞传输

点击加载

得到的保证，每个Channel的I/O事件都将会被一个Thread（用于支撑该Channel的EventLoop的那个Thread处理）。

Netty-事件及其流水线

发表于 2017-12-28 | 分类于 Netty

ChannelHandler家族

Channel的生命周期

状态	描述
ChannelUnregistered	Channel已经被创建，但还未注册到EventLoop
ChannelRegistered	Channel已经被注册到EventLoop
ChannelActive	Channel处于活动状态（已经连接到远程节点）。它现在可以接受或发送数据
ChannelInactive	Channel没有连接到远程节点

Channel的正常生命周期如下图

点击加载

ChannelHandler的生命周期

下表列出了interface ChannelHandler定义的生命周期操作，在ChannelHandler被添加到ChannelPipeline中或者被从ChanngelPipeline中移除时会调用这些操作。这些方法中的每一个都接受一个ChannelHandlerContext参数。

方法	描述
handlerAdded	当把ChannelHandler添加到ChannelPipeline中时被调用
handlerRemoved	当从ChannelPipeline中移除ChannelHandler时被调用
exceptionCaught	当处理过程中ChannelPipeline中有错误产生时被调用

ChannelInboundHandler接口

处理入站数据以及各种状态变化
下表列出了interface ChannelInboundHandler的生命周期方法。这些方法将会在数据被接收或者与其对应的Channel状态发生改变时调用，这些方法和Channel的生命周期密切相关。

方法名称	描述
channelRegistered	当Channel已经注册到它的EventLoop并且能够处理I/O时被调用
channelUnregistered	当Channel从它的EventLoop注销并且无法处理任何I/O时被调用
channelActive	当Channel处于活动状态时被调用；Channel已经连接/绑定并且已经就绪
channelInactive	当Channel离开活动状态并且不再连接它的远程节点时被调用
channelReadComplete	当所有可读的字节都已经被从Channel中读取之后
channelRead	当从Channel读取数据时被调用
ChannelWritablilityChanged	当Channel的可写状态发生改变时被调用。用户可以确保写操作不会完成得太快（避免发生OutOfMemoryError）或者可以在Channel变为再次写时恢复写入。可以通过调用Channel的isWritable()方法来检测Channel的可写性。
userEventTriggered	当ChannelInboundHandler.fireUserEventTriggered()调用时，调用userEventTriggered方法，因为一个POJO被传经了ChannelPipeline

@Sharable
public class DiscardHandler extends ChannelInboudHandlerAdapter{
	@Override
	public void ChannelRead(ChannelHandlerContext ctx, Object msg){
		ReferenceCountUtil.release(msg);	//丢弃已接收的消息
	}
}

使用SimpleChannelInboundHandler可以更加方便的管理资源。

@Sharable
public class SimpleDiscardHandler extends SimpleRead0(ChannelHandlerContext ctx, Object msg){
	@Override
	public void channelRead0(channelHandlerContext ctx, Object msg)
	//资源在被读取之后将被释放，所以不能存储
	///不需要任何显示的释放资源	
}

由于SimpleChannelInboundHandler的channelRead0()方法消费之后会自动释放资源，所以你不应该存储指向任何消息的引用供将来使用，因为这些引用都将失效。

在出站方向这边，如果你处理了write()操作并丢弃了一个消息，那么你也应该负责释放它。

//丢弃并释放出站消息
@Sharable
public class DiscardOutboundHandler extends ChannelOutboundHandlerAdapter{
	@Override
	public void write(ChannelHandlerContext ctx, Object msg, ChannelPromise promise){
		ReferenceCountUtil.release(msg);
		promise.setSuccess();	//通知ChannelPromise数据已经被处理了
	}
}

不仅要释放资源，还要通知ChannelPromise。否则可能会出现ChannelFutureListener收不到某个消息已经被处理了的通知的情况。
如果一个消息被消费或者丢弃了，并且没有传递给ChannelPipeline中的下一个ChannelOutboundHandler，那么用户就有责任调用ReferenceCountUtil.release()。如果消息到达了实际的传输层，那么当它被写入或者Channel关闭时，都将被自动释放。

ChannelOutboundHandler接口

处理出站数据并且允许拦截所有的操作

ChannelOutboundHandler的一个强大功能是可以按需推迟操作或者事件，这使得可以通过一些复杂的方法来处理请求。例如，如果到远程节点的写入被暂停了，那么你可以推迟冲刷操作并在稍后继续。

ChannelOutboundHandler的方法

ChannelHandlerContext ctx;
ScokAddress sa;
ChannelPromise cp;

类型	描述
bind(ctx, sa, cp)	当请求将Channel绑定到本地地址时被调用
connect(ctx, sa, sa, cp)	当请求将Channel连接到远程节点时被调用
disconnect(ctx, cp)	当请求将Channel从远程节点断开时被调用
close(ctx, cp)	当请求关闭Channel时被调用
deregister(ctx, cp)	当请求将Channel从它的EventLoop注销时被调用
read(ctx))	当请求从Channel读取更多的数据时被调用
flush(ctx)	当请求通过Channel将入队数据冲刷到远程节点时被调用
write(ctx, object, cp)	当请求通过Channel将数据写到远程节点时被调用

ChannelPromise(cp)：作用是在操作完成时得到通知。ChannelPromise是ChannelFuture的一个子类。

ChannelHandler适配器

点击加载

ChannelPipeline接口

可以这样理解，ChannelPipeline是一个拦截流经Channel的入站和出站事件的ChannelHandler实例链，那么就很容易看出这些ChannelHandler之间的交互是如何组成一个应用程序数据和事件处理逻辑核心的。
每一个新创建的Channel都将会被分配一个新的ChannelPipeline。这项关联是永久性的；Channel既不能附加另一个ChannelPipeline，也不能分离其当前的。
根据事件的起源，事件将会被ChannelInboundHandler或者ChannelOutboundHanlder处理。随后，通过调用ChannelHandlerContext实现，它（事件）将被转发给下一个的ChannelHandler。

点击加载

如图所示，Netty总是将ChannelPipeline的入站口（左侧）作为头部，而将出站口（该图右侧）作为尾端。

在ChannelPipeline传播事件时，它会测试ChannelPipeline中的下一个ChannelHandler的类型是否和事件的运动方向相匹配。如果不匹配，ChannelPipeline将跳过该ChannelHandler并前进到下一个，直到它找到和该事件所期望的方向相匹配为止。

ChanndelHandlerContext接口

ChannelHandlerContext的主要功能是管理它所关联的ChannelHandler和在同一个ChannelPipeline中的其他ChannelHandler之间的交互。

区别：调用Channel或者ChannelPipeline上的方法，它们将沿着整个ChannelPipeline上传播，而调用ChannelHandlerContext上的相同方法，则从所关联的ChannelHandler开始处理，并且只会传播给位于该ChannelPipe中的下一个能够处理该事件的ChannelHandler。

ChannelHandlerContext的API

方法名称	描述
alloc	返回和这个实例相关联的Channel所配置的ByteBufAllocator
bind	绑定到给定的SocketAddress，并返回ChannelFuture
channel	返回绑定到这个实例的Channel，并返回ChannelFuture
close	关闭Channel，并返回ChannelFuture
connect	连接给定的SocketAddress，并返回ChannelFuture
deregister	从之前分配的EventExecutor注销，并返回ChannelFuture
disconnect	从远程节点断开，并返回ChannelFuture
executor	返回调度事件的EventExecutor
handlder	返回绑定到这个实例的ChannelHandler
isRemoved	如果所关联的ChannelHandler已经被从ChannelPipeline中移除则返回true
name	返回这个实例的唯一名称
pipe	返回这个实例所关联的ChannelPipeline
read	将数据从Channel读取到第一个入站缓冲区；如果读取成功则触发一个ChannnelRead事件，并（在最后一个消息被读取后）通知ChannelInboundHandler的channelReadComplete(channelHandlerContext ctx)方法
write	通过这个实例写入消息经过ChannelPipeline
writeAndFlush	通过这个实例写入并冲刷消息，经过channelPipeline

当使用ChannelHandlerContextd的API时候，请牢记以下两点：

ChannelHandlerContext和ChannelHandler之间的关联（绑定）是永不会改变的，所以缓存对它的引用是安全的
ChannelHandlerContext的方法将产生更短的事件流

点击加载

如下代码，将通过ChannelHandlerContext获取到Channel的引用。调用Channel上的write()方法将会导致写入事件从尾端到头部地流经ChannelPipeline。

//从ChannelHandlerContext访问Channel
ChannelHandlerContext ctx = ...;
Channel channel = ctx.channel();
//通过Channel写入缓冲区
channel.write(Unpooled.copiedBuffer("Cherry", CharsetUtil.UTF_8));
//通过ChannelHandlerContext访问ChannelPipeline
ChannelHandlerContext ctx = ...;
ChannelPipeline pipeline = ctx.pipeline();
//通过ChannelPipeline写入缓冲区
pipeline.write(Unpooled.copiedBuffer("Cherry", CharsetUtil.UTF_8));

上面代码，被调用的Channel或ChannelPipeline上的write()方法将一直传播事件通过整个ChannelPipeline，但是在ChannelHandler级别上，事件从一个ChannelHandler到一下ChannelHandler的移动是由ChannelHandlerContext上的调用完成。
也就是我们的write(数据)中的数据会在整条流水线上传递。

点击加载

从ChannelPipe中的某个特定点进行事件传播

减少将事件传经对它不感兴趣的ChannelHandler所带来的开销
避免将时间传经那些可能会对它有副作用的ChannelHandler

1 2	ChannelHandlerContext ctx = ...; ctx.write(Unpooled.copiedBuffer("Hello", CharsetUtil.UTF8));

写入的数据将在流水线上，从本ChannelHandler及其之后的ChannelHanlder。

点击加载

高级用法

缓存ChannelHandlerContext的引用

public class WriteHandler extends ChannelHandlerAdapter{
	private ChannelHandlerContext ctx;
	@Override
	public void handlerAdd(ChannelHandlerContext ctx){
		this.ctx = ctx;
	}
	public void send(String msg){
		ctx.writeAndFlush(msg);
	}
}

因为一个ChannelHandler可以从属多个ChannelPipeline，所以它也可以绑定到多个ChannelHandlerContext实例。对于这种用法指在多个ChannelPipeline中共享同一个ChannelHandler，对应的ChannelHandlerI必须使用@ChannelHandler.Sharable注解标注；否则，试图将它添加到多个ChannelPipeline时将会触发异常。显而易见，为了安全地被用于多个并发的Channel(即连接)，这样的ChannelHandler必须是线程安全的。

共享同一个ChannelHandler的用处：再多个ChannelPipeline中安装同一个ChannelHandler的一个常见原因用于收集跨越多个Channel的统计信息。

异常处理

Netty-ByteBuf

发表于 2017-12-28 | 分类于 Netty

ByteBuf的优点

它可以被用户自定义的缓冲区类型扩展；
通过内置的复合缓冲区实现了透明的零拷贝；
容量可以按需增长（类似于JDK的StrigBuilder）;
在读和写这两种模式切换不需要调用ByteBuffer的filp()方法；
读和写使用了不同的索引
支持方法的链式调用
支持引用计数；
支持池化。

ByteBuf类——Netty的数据容器

ButeBuf维护了两个不同的索引：一个用于读取，一个用于写入。

名称read和write开头的ByteBuf方法，将会推进其对应的索引，而名称以set或者get开头的操作则不会。

堆缓冲区

最常用的ByteBuf模式是将数据存储在JVM的堆内存空间，这种模式被称为支撑数组，它能在没有使用池化的情况下提供快速的分配和释放。

ByteBuf heapBuf = ...;
if(heapBuf.hasArray()){
    byte []array = heapBuf.array();
    int offset = heapBuf.arrayOffset() + heapBuf.readerIndex(); //计算第一个字节的偏移量
    int length = heapBuf.readableBytes();   //获得可读字节数
    handleArray(array, offset, length);     //逻辑处理array
}

直接缓冲区

直接缓冲区是另外一种ByteBuf模式。直接缓冲区的内容将驻留在常规的会被垃圾回收的堆之外。直接缓冲区对于网络数据传输是理想的选择。如果数据包含在一个堆上分配的缓冲区中，那么事实上，在通过套接字发送之前，JVM将会在内部把缓冲区复制到一个直接缓冲区。

ByteBuf directBuf = ...;
if(!directBuf.hasArray){	//非支撑数组，则为直接缓冲区
	int length = directBuf.readableBytes();
	byte []array = new byte[length];
	directBuf.getBytes(directBuf.readerIndex(), array);  //将字节复制到array
	handle(array, 0, length);
}

复合缓冲区

复合缓冲区为多个ByteBuf提供一个聚合视图。在这里可以根据需要添加或者删除ByteBuf实例。

点击加载

CompositeByteBuf buf = Unpooled.compositeBuffer();
ByteBuf headBuf = ...;  //堆缓冲区或者直接缓冲区
ByteBuf bodyBuf = ...;  //同上
buf.addComponents(headBuf, bodyBuf);

Netty-传输

发表于 2017-12-28 | 分类于 Netty

传输API

点击加载

每个Chnnel都会被分配一个ChannelPipeline和ChannelConfig。

由于Channel是独一无二的，所以为了保证顺序将Channel声明为java.lang.Compare的一个子接口。因此，如果两个不同的Channel实例都返回了相同的散列码，那么AbstractChannel中的compareTe()方法的实现将会抛出一个Error。

ChannelPipeline持有将应用于入站和出站数据以及事件的ChannelHanlder实例，这些ChannelHandler实现了应用程序用于处理状态变化以及数据处理的逻辑。
ChannelHandler的典型用途包括：

将数据从一种格式转换为另一种格式
提供异常的通知
提供Channel变为活动或者非活动的通知；
提供当Channel注册到EventLoop或者从EventLoop注销时的通知；
提供有关用户自定义事件的通知。

Channel的方法

方法名	描述
eventLoop	返回分配给Channel的EventLoop
pipeLine	返回分配给Channel的ChannelPipeline
isActive	如果Channel是活动的，返回true
localAddress	返回本地的SocketAddress
remoteAddress	返回远程的ScoketAddress
write	将数据写到远程节点，这个数据将被传递给ChannelPipeline，并且排队直到它被冲刷
flush	将之前已写的数据立即冲刷到底层，进行传输，如一个socket
writeAndFlush	等同于两个方法的复合

Netty的Channel实现是线程安全的，因此可以在多线程情况下将数据存储到同一个Channel。

NIO——非阻塞I/O

NIO提供了一个所有I/O操作的全异步的实现。他利用了自NIO子系统被引入JDK1.4时便可以用的基于选择器的API。
选择器背后的基本概念是充当一个注册表，在那里可以将请求在Channel的状态变化发生变化时得到通知。可能的状态变化有：

新的Channel已被接受并且就绪；
Channel连接已经完成；
Channel有已经就绪的可供读取的数据；
Channel可用于写数据。

选择器运行在一个检查状态变化并对其做出响应的线程上，在应用程序状态的改变做出响应后，选择器会被重置，然后重复这个过程。

选择操作的位模式

名称	描述
OP_ACCEPT	请求在接受新连接并创建Channel时获得通知
OP_CONNECT	请求在建立一个连接时获得通知
OP_READ	请求当数据已经就绪，可以从Channel中读取时获取通知
OP_WRITE	请求当可以向Channel中写更多的数据时获得通知。这处理了套接字缓冲区被完全填满的情况，这种情况通常发生在数据的发送速度大于远程节点的接收数据速度

对于所有Netty的传输实现都公有的级别API完全地隐藏了这些NIO的内部细节。

点击加载

零拷贝

零拷贝是一种目前只有在使用NIO和Epoll传输时候才可以使用的特性。它快速高效地将数据从文件系统移动到网络接口，而不需要将其从内核空间复制到用户空间，像在FTP或者HTTP这样的协议中可以显著地提升性能。但是，并不是所有的操作系统都支持这个特性。特别，他对于实现了数据加密或者压缩的文件系统都不可用——只能传输文件的原始内容。

Netty-组件和设计

发表于 2017-12-28 | 分类于 Netty

…

Channel——Socket
EventLoop——控制流、多线程处理和并发
ChannelFuture——异步通知

Channel接口

基本的I/O操作（bind、connect、read和write）依赖于底层的网络传输提供的API。

EmbededChannel
LocalServerChannel
NioDatagramChannel
NioSctpChannel
NioSocketChannel

EventLoop接口

一个EventLoopGrroup包含一个或者多个EventLoop；
一个EventLoop在它的生命周期内只和一个Thread绑定
所有由EventLoop处理的I/O事件都将在它专有的Thread上被处理；
一个Channel在它的生命周期内注册于一个EeventLoop;
一个EventLoop可能会被分配给一个或者多个Channel

一个给定的Channel的I/O操作都是由相同的Thread执行的，实际上是消除了对于同步的需求。

点击加载

ChannelFuture接口

Netty的所有操作都是异步的。因为一个操作可能不会立即返回，所以我们需要一种用于在之后的某个时间点确定其返回结果的方法。为此，Netty提供ChannelFuture接口，其addListener()注册了一个ChannelFutureListener，以便在某个操作完成时候得到通知。

事件及其流水线

ChannelHandler和ChannelPipeline

ChannelHandler接口

ChannelHandler充当了所有处理入站和出站数据的应用程序逻辑的容器。该方法是由网络事件触发的。事实上，ChannelHandler可专门用于几乎任何类型的动作，例如将数据从一种格式转换为另一种格式，或者处理转换过程中所抛出的异常。

ChannelPipeline接口

ChannelPipeline提供了ChannelHandler链的容器，并定义了用于在该链上传播入站和出站事件流的API。当Channel被创建时，它会被自动分配到它专属的ChannelPipeline。
ChannelHandler安装到ChannelPipeline中的过程如下：

一个ChannelInitializer的实现被注册到了Bootstrap/ServerBootstrap中；
当ChannelInitializer.initChannel()方法被调用时，ChannelInitializer将在ChannelPipeline中安装一组自定义的ChannelHandler;
ChannelInitializer将它自己从ChannelPipeline中移除。

Netty能区分扩展自ChannelHandler的ChannelInboundHandler和ChannelOutboundHandler，并确保数据只会在具有相同定向类型的两个ChannelHandler之间传递。

ChannelHandlerContext

通过使用作为参数传递到每个方法的ChannelHandlerContext，事件可以被传递给当前ChannelHandler链中的下一个ChannelHandler。通过调用ChannelHandlerContext上对应的方法，每个都提供了简单地将事件传递给下一个ChannelHandler的方法的实现。

ChannelHandler的适配器类

Netty以适配器类的形式提供了大量默认的ChannelHandler实现，其旨在简化应用程序处理逻辑的开发过程。
有一些适配器类可以将自定义的ChannelHandler所需要的努力降到最低限度，因为它们提供了定义对应接口中所有方法的默认实现。
下面这些是编写自定义ChannelHandler时经常会用到的适配器类：

ChannelHandlerAdapter
ChannelInboundHandlerAdapter
ChannelOutboundHandlerAdapter
ChannelDuplexHandler

抽象类SimpleChannelInboundHandler< T>

最常见的情况，应用程序会利用一个ChannelHandler来接收解码消息，并对该数据应用业务逻辑。要创建一个这样的ChannelHandler，你只需要扩展基类SimpleChannelInboundHanlder< T>。其中最重要的方法是channelRead0(ChannelHandlerContext, ByteBuf)，除了要求不阻塞于当前I/O线程之外，其他具体实现都可以。

Netty-核心组件

发表于 2017-12-28 | 分类于 Netty

Channel

Channel是Java NIO的一个基本构造

它代表一个到实体的开放连接，如读操作或写操作。这里实体指的是，一个硬件设备、一个文件、一个网络套接字或者一个能够执行一个或者多个不同的I/O操作的程序组件。

目前，Channel可以看作是传入（入站）或者传出（出站）数据的载体。因此，它可以被打开或者被关闭，连接或者断开连接。

回调

一个回调就是一个方法，一个指向已经被提供给另外一个方法的方法的引用。这使得接受回调的方法可以在适当的时候调用回调方法。

其实就是函数指针作为参数。

Future

Future提供了一种在操作完成时通知应用程序的方式。这个对象可以看作是一个异步操作的结果的占位符；它将在某个时刻完成，并提供对其访问结果。

Netty提供了自己的future实现——ChannelFuture，用于在执行异步操作的时候使用。每个Netty的出站I/O操作都会返回一个Channel，也就是说，它们都不会阻塞。Netty完全是异步和事件驱动的。

ChannelFuture提供了几种额外的方法，这些方法使得我们可以注册一个或者多个ChannelFutureListener实例。监听器的回调方法operationComplete()，将会在对应的操作完成时被调用。如此一来，便可以消除java并发包Future需要手动检查是否完成带来的繁琐操作。

ChannelFutureListener可以看作是回调的一个更精细的版本；回调和Future是相互补充的机制。

Channel channel = ...;
//异步地连接到远程节点 (客户端操作)
ChannelFuture future = channel.connect(new InetSocketAddress("127.0.0.1", 8080));
//注册监听器ChannelFutureListener
//以便在连接操作完成的时候获得通知, 并且执行operation操作
future.addListener(new ChannelFutureListener(){
    @Override
    public void operationComplete(ChannelFuture future){
        if(future.isSuccess()){
            ByteBuf byteBuf = Unpooled.copiedBuffer("Cherry", CharsetUtil.UTF_8);
            //在连接操作完成以后, 将数据异步地发送到远程节点
            ChannelFuture cf = future.channel().writeAndFlush(byteBuf);
        }
        else{
            Throwable cause = future.cause();
            cause.getStackTrace();
        }
    }
});

事件ChannelHandler

Netty使用不同的事件来通知状态的改变或者是操作的状态。

Netty是一个网络编程框架，所以事件是按照它们与入站或者出站数据流的相关性进行分类的。
由入站数据或者相关的状态更改而触发的事件，包括：

连接已被激活或者连接失活；
数据读取；
用户事件；
错误事件。

由出站事件是未来将会触发的某个动作的操作结果，包括

打开或者关闭到远程节点的连接；
将数据写或者冲刷到套接字。