Linux服务器安装

安装Shadowsocks:
1.下载 pip3 install shadowsocks
2.运行ssserver -c config.json -d start
config.json
{
“server”:”45.76.160.201″,
“server_port”:8388,
“local_address”: “127.0.0.1”,
“local_port”:1080,
“password”:”*******”,
“timeout”:300,
“method”:”aes-256-cfb”,
“fast_open”: false,
“workers”: 1
}

关于Java Lambda的教程,简单明了

许多热门的编程语言如今都有一个叫做lambda或者闭包的语言特性,包括比较经典的函数式编程语言Lisp,Scheme,也有稍微年轻的语言比如JavaScript,Python,Ruby,Groovy,Scale,C#,甚至C++也有Lambda表达式。一些语言是运行在java虚拟机上,作为虚拟机最具代表的语言java当然也不想落后。

究竟什么是Lambda表达式?

Lambda表达式的概念来自于Lambda演算,下面是一个java lambda的简单例子,

(int x)->{ return x+1;}

简单来看lambda像一个没有名字的方法,它具有一个方法应该有的部分:参数列表int x,方法body return x+1,和方法相比lambda好像缺少了一个返回值类型、异常抛出和名字。返回值类型和异常是通过编译器在方法体中推导出来,在上面这个例子中返回值类型是int,没有抛出异常。真正缺少的就是一个名字,从这个角度来看,lambda表达式是一种匿名方法。

Lambda表达式和匿名内部类

从上面的分析可以看出lambda和java内部类的特性有点相似,匿名内部类不只是一个方法,而是一个包含一个或多个方法的类,他们的作用都是一样的,都是作为方法的参数传递,我从JDK源码中提取出来listFiles(FileFilter) 方法:

关于Java Lambda的教程,简单明了

public interface FileFilter { boolean accept(File pathname); }

fileFilter接收一个File对象返回一个boolean值,listFiles方法把Filter应用到所有的File对象接收 那些accept返回true的文件。对于listFiles方法来讲我们必须传递一个函数式接口给他,这是FileFileter的一个实现,一般我们通过匿名类来完成:

关于Java Lambda的教程,简单明了

我们现在可以用lambda来实现:

关于Java Lambda的教程,简单明了

这两种情况我们都是传递了一个函数式接口给方法就像传递对象一样,我们使用代码就像使用数据一样,使用匿名类我们实际上传递了一个对象给方法,使用lambda不再需要创建对象,我们只需要把lambda代码传递给方法。

除了传递lambda之外我们还可以传递一个方法引用,比如:

File[] files = myDir.listFiles( File::isFile );

Lambda表达式的表示

在之前的例子,我们使用lambda表达式定义了一个函数,我们可以把它作为参数传递给一个方法,方法把它当成一个对象来使用,lambda表达式有函数和对象的一些属性,看你从什么角度来看:

  • 从概念来讲,lambda表达式是一个匿名函数,它有签名和方法体但是没有名字
  • 当lambda表达式作为参数传递给方法时,接收方法把它当对象使用,在listFiles方法内部,lambda表达式是一个对象的引用,在这里lambda表达式是一种常规的对象,比如有地址和类型。

从实际的角度来分析,lambda对象是由编译期和运行时系统来创建的,这就允许编译期进行优化而使用者不需要关心具体细节,编译器从lambda表达式的上下文环境来获取lambda对象的语义类型,但是编译期并不创建那个对象而是直到运行时由虚拟机动态创建,这里说的动态创建是指调用

invokedynamic字节码指令来创建。使用动态创建可以推迟对象的创建到对象第一次被使用时,如果你只是定义了lambda表达式而从未使用,它的类型和对象都不会创建。

函数式接口

整个魔幻之处就在于类型的推导,这个类型称为目标类型,运行时系统动态创建的类型是目标类型的子类型。之前的那个例子我们看到目标类型是FileFilter,在例子中我们定义了一个lambda表达式把它传递给listFiles方法,然后listFiles方法把它作为FileFilter子类的一个对象来使用。这里看起来好像有点神奇,我们并没有声明lambda表达式实现了FileFilter接口,listFiles方法也没有表明它很愉快的接收了lambda表达式,它只是需要一个FileFilter的子类的对象,这是如何工作的?

这里面的魔术在于编译期执行了类型推导,编译器根据lambda表达式的上下文来决定需要什么类型的对象,然后编译器观察lambda表达式是否兼容需要的类型。如果Java是一种函数式编程语言的话lambda表达式最自然的类型就是某种函数式类型,用来描述函数的一种特殊类型。函数式类型仅仅描述了函数的签名比如(int,int)->boolean.但是Java不是函数式编程语言因此没有函数式类型,语言的设计者可以选择添加一种新的类型,由于他们不想给Java的类型系统引入太多的改变,因此他们尝试寻找一种办法来集成lambda表达式到语言中而不需要添加函数式类型。

结果他们使用函数式接口来代替,函数式接口是只有一个方法的接口,这样的接口在JDK里有很多,比如经典的Runnable接口,它只有一个方法void run(),还有很多其他的,比如Readable,Callable,Iterable,closeable,Flushnable,Formattable,Comparable,Comparator,或者我们前面提到的FileFilter接口。函数是接口和lambda表达式奕扬都只有一个方法,语言的设计者决定让编译器把lambda表达式转换成匹配的函数式接口。这种转换通常是自动的。比如我们前面提到的(File f) -> { return f.isFile(); },编译器知道listFiles方法的签名,因此我们需要的类型就是FileFilter,FileFilter是这样的:
public interface FileFilter { boolean accept(File pathname); }
FileFilter仅仅需要一个方法因此它是函数式接口类型,我们定义的lambda表达式有一个相匹配的签名,接收一个File对象,返回一个boolean值,不抛出检查的异常,因此编译器把lambda表达式转换成函数式接口FileFilter类型。

假如我们有下面两个函数式接口:
关于Java Lambda的教程,简单明了

我们的lambda表达式兼容两种函数式接口类型:
关于Java Lambda的教程,简单明了

当我们试图给两个变量相互赋值时编译器会报错,虽然两个变量都是同一个lambda表达式,原因很简单两个变量是不同的类型。也有可能出现编译器无法判断匹配的函数式接口类型,比如这个例子:
Object ref = (File f) -> { return f.isFile(); };
这个赋值语句的上下文没有提供足够的信息来转换,因此编译器会报错,解决这个问题最简单的方法就是添加一个类型转换:
Object ref = (FileFilter) (File f) -> { return f.isFile(); };

Lambda表达式和匿名内部类的区别

Lambda表达式出现在我们通常需要匿名内部类的地方,在很多场合他们是可以互换的。但是他们还是有几个区别:

1.语法

匿名类一般这样编写:
关于Java Lambda的教程,简单明了

而Lambda表达式有多种形式:
关于Java Lambda的教程,简单明了

2.运行时成本

匿名类相对Lambda表达式来讲多了一些成本,使用匿名类或造成新类型的创建、新类型对象的创建。运行时匿名内需要:类加载 > 内存分配、对象初始化 > 调用非静态方法。

Lambda表达式需要函数式接口的转换和最终的调用,类型推导发生在编译期,不需要运行时消耗,之前提到过,lambda对象的创建是通过字节码指令invokedynamic来完成的,减少了类型和实例的创建消耗。

3.变量绑定

匿名类可以访问外部域的final变量,如下所示关于Java Lambda的教程,简单明了

对于lambda表达式,cnt变量不需要显式声明为final的,一旦变量在lambda中使用编译期会自动把它当成是final的变量,换句话说在lambda中使用的外部域变量是隐式final的,

关于Java Lambda的教程,简单明了

从java8开始匿名内部类也不需要再显式声明final类,编译器会自动把它当成是final。

4.作用域

匿名内部类是一个类,也就是说它自己引入了一个作用域,你可以在里面定义变量,而lambda表达式没有自己的作用域。
关于Java Lambda的教程,简单明了

lambda表达式:
关于Java Lambda的教程,简单明了

不同的作用域规则对于this和super关键字有不同的效果,在匿名类中this表示匿名类对象本身的引用,super表示匿名类的父类。在lambda表达式this和super关键字意思和外部域中this和super的意思一样,this一般是包含它的那个对象,super表示包含它的类的父类。

java8的新特性以及用法简介,再不学习,代码都看不懂了

1. 介绍

本文简单介绍下java8里面有哪些新的特性,以及相关的用法。

JAVA8是意义深远的一个新版本。随着大数据的兴起,函数式编程在处理大数据上的优势开始体现。JAVA8也紧跟时代,引入了函数式语言的特性,值得关注。下面看看其有哪些新的内容。

2 接口的默认方法

Java 8允许我们给接口添加一个非抽象的方法实现,只需要使用 default关键字即可,这个特征又叫做扩展方法。JAVA可以实现多个接口,从而来对原本的类进行方法扩展。JAVA只能继承1个类,所以以前的接口没法提供这种灵活的扩展方法。现在要简单的扩展方法,也不需要使用Spring的代码织入了,直接用扩展方法即可。不过横切逻辑织入还是用Spring好。

下面看个例子:

interface Formula {  
    double calculate(int a);  
    
    //default修饰的扩展方法 
    default double sqrt(int a) {  
        return Math.sqrt(a);  
    } 
}

Formula接口在拥有calculate方法之外同时还定义了sqrt方法,实现了Formula接口的子类只需要实现一个calculate方法,默认方法sqrt将在子类上可以直接使用。

Formula formula = new Formula() {  
    @Override  
    public double calculate(int a) { 
        return sqrt(a * 100);  
    } 
}; 
formula.calculate(100); // 100.0 
formula.sqrt(16); // 4.0

新的Java 8 的这个特新在编译器实现的角度上来说更加接近Scala的trait。 在C#中也有名为扩展方法的概念,允许给已存在的类型扩展方法,和Java 8的这个在语义上有差别。

2 lambda表达式

首先看看在老版本的Java中是如何排列字符串的:

List<String> names = Arrays.asList("peter", "anna", "mike", "xenia"); 
Collections.sort(names, new Comparator<String>() {  
    @Override  
    public int compare(String a, String b) {  
         return b.compareTo(a);  
    } 
});

只需要给静态方法 Collections.sort 传入一个List对象以及一个比较器来按指定顺序排列。通常做法都是创建一个匿名的比较器对象然后将其传递给sort方法。在Java 8 中你就没必要使用这种传统的匿名对象的方式了,Java 8提供了更简洁的语法,lambda表达式:

Collections.sort(names, 
     (String a, String b) -> {  return b.compareTo(a); });

看到了吧,代码变得更段且更具有可读性,但是实际上还可以写得更短:

Collections.sort(names, (String a, String b) -> b.compareTo(a));

对于函数体只有一行代码的,你可以去掉大括号{}以及return关键字,但是你还可以写得更短点,Java编译器可以自动推导出参数类型,所以你可以不用再写一次类型。

Collections.sort(names, (a, b) -> b.compareTo(a));

2.1 函数式接口

每个lambda表达式对应一个函数式接口。函数式接口”是指仅仅只包含一个抽象方法的接口,每一个该类型的lambda表达式都会被匹配到这个抽象方法。因为 默认方法 不算抽象方法,所以你也可以给你的函数式接口添加默认方法。

我们可以将lambda表达式当作任意只包含一个抽象方法的接口类型,确保你的接口一定达到这个要求,你只需要给你的接口添加 @FunctionalInterface 注解,编译器如果发现你标注了这个注解的接口有多于一个抽象方法的时候会报错的。

//需要注解修饰表明是函数式接口
@FunctionalInterface
interface Converter<F, T> {  
    //必须仅包含一个抽象方法,用于lambda表达式给出具体实现。这里可以包    含扩展方法 
    T convert(F from); 
} 
// Integer.valueOf(from)是函数式接口里面抽象方法的实现。Converter<String, Integer> converter = 
      (from) -> Integer.valueOf(from); 
Integer converted = converter.convert("123"); System.out.println(converted); // 123

需要注意如果@FunctionalInterface如果没有指定,上面的代码也是对的。

译者注 将lambda表达式映射到一个单方法的接口上,这种做法在Java 8之前就有别的语言实现,比如Rhino JavaScript解释器,如果一个函数参数接收一个单方法的接口而你传递的是一个function,Rhino 解释器会自动做一个单接口的实例到function的适配器

2.2 方法与构造函数引用

Java 8 允许你使用 :: 关键字来传递方法或者构造函数引用

Converter<String, Integer> converter = Integer::valueOf; 
Integer converted = converter.convert("123"); System.out.println(converted); // 123

获取构造函数的引用的话使用 ::new,后面接new关键字即可。

2.3 访问局部变量

在lambda表达式中访问外层作用域和老版本的匿名对象中的方式很相似。你可以直接访问标记了final的外层局部变量,或者实例的字段以及静态变量。

//不用final修饰也可以访问,但是要确保其不备修改,所以还是建议用final修饰final
int num = 1; 
Converter<Integer, String> stringConverter = 
     (from) -> String.valueOf(from + num); 
stringConverter.convert(2); // 3

2.4 访问对象字段与静态变量

和本地变量不同的是,lambda内部对于实例的字段以及静态变量是即可读又可写。该行为和匿名对象是一致的:

class Lambda4 {  
    static int outerStaticNum;  
    int outerNum;  
    void testScopes() {  
        Converter<Integer, String> stringConverter1 = 
           (from) -> { outerNum = 23;  
                return String.valueOf(from);  
           };  
        Converter<Integer, String> stringConverter2 = 
           (from) -> {  
                outerStaticNum = 72; 
                return String.valueOf(from); 
           };  
     } 
}

3. 内建函数式接口

JDK 1.8 API包含了很多内建的函数式接口,在老Java中常用到的比如Comparator或者Runnable接口,这些接口都增加了@FunctionalInterface注解以便能用在lambda上。

Java 8 API同样还提供了很多全新的函数式接口来让工作更加方便,有一些接口是来自Google Guava库里的,即便你对这些很熟悉了,还是有必要看看这些是如何扩展到lambda上使用的。

这些已经默认提供的内建函数式接口主要是:

  • Predicate — 传入一个参数,返回一个bool结果, 方法为boolean test(T t)
  • Consumer — 传入一个参数,无返回值,纯消费。 方法为void accept(T t)
  • Function<t,r> — 传入一个参数,返回一个结果,方法为R apply(T t)</t,r>
  • Supplier — 无参数传入,返回一个结果,方法为T get()

3.1 Predicate接口

Predicate 接口只有一个参数,返回boolean类型。该接口包含多种默认方法来将Predicate组合成其他复杂的逻辑(比如:与,或,非):

//用于做一些判断Predicate<String>

predicate = (s) -> s.length() > 0; 
predicate.test("foo"); // true
predicate.negate().test("foo"); // false 
Predicate<Boolean> nonNull = Objects::nonNull; 
Predicate<Boolean> isNull = Objects::isNull; 
Predicate<String> isEmpty = String::isEmpty; 
Predicate<String> isNotEmpty = isEmpty.negate();

3.2 Function 接口

Function 接口有一个参数并且返回一个结果,并附带了一些可以和其他函数组合的默认方法(compose, andThen):

Function<String, Integer> toInteger = Integer::valueOf; Function<String, String> backToString = toInteger.andThen(String::valueOf); 
backToString.apply("123"); // "123"

3.3 Supplier 接口

Supplier 接口返回一个任意范型的值,和Function接口不同的是该接口没有任何参数

Supplier<Person> personSupplier = Person::new; 
personSupplier.get(); // new Person

3.4 Consumer 接口

Consumer 接口表示执行在单个参数上的操作。

Consumer<Person> greeter = (p) -> System.out.println("Hello, " + p.firstName); 
greeter.accept(new Person("Luke", "Skywalker"));

3.5 Comparator 接口

Comparator 是老Java中的经典接口, Java 8在此之上添加了多种默认方法:

Comparator<Person> comparator = (p1, p2) -> p1.firstName.compareTo(p2.firstName); 
Person p1 = new Person("John", "Doe"); 
Person p2 = new Person("Alice", "Wonderland"); 
comparator.compare(p1, p2); // > 0 
comparator.reversed().compare(p1, p2); // < 0

3.6 Optional 接口

Optional 不是函数是接口,这是个用来防止NullPointerException异常的辅助类型,这是下一届中将要用到的重要概念,现在先简单的看看这个接口能干什么:

Optional 被定义为一个简单的容器,其值可能是null或者不是null。在Java 8之前一般某个函数应该返回非空对象但是偶尔却可能返回了null,而在Java 8中,不推荐你返回null而是返回Optional。

Optional<String> optional = Optional.of("bam"); 
optional.isPresent(); // true 
optional.get(); // "bam" optional.orElse("fallback"); // "bam" 
optional.ifPresent((s) -> System.out.println(s.charAt(0))); // "b"

3.7 Stream 接口

java.util.Stream 表示能应用在一组元素上一次执行的操作序列。Stream 操作分为中间操作或者最终操作两种,最终操作返回一特定类型的计算结果,而中间操作返回Stream本身,这样你就可以将多个操作依次串起来。Stream 的创建需要指定一个数据源,比如 java.util.Collection的子类,List或者Set, Map不支持。Stream的操作可以串行执行或者并行执行。

首先看看Stream是怎么用,首先创建实例代码的用到的数据List:

List<String> stringCollection = new ArrayList<>(); 
stringCollection.add("ddd2"); 
stringCollection.add("aaa2"); 
stringCollection.add("bbb1"); 
stringCollection.add("aaa1"); 
stringCollection.add("bbb3"); 
stringCollection.add("ccc"); 
stringCollection.add("bbb2"); 
stringCollection.add("ddd1");

Java 8扩展了集合类,可以通过 Collection.stream() 或者 Collection.parallelStream() 来创建一个Stream。下面几节将详细解释常用的Stream操作:

3.7.1 Filter过滤

过滤通过一个predicate接口来过滤并只保留符合条件的元素,该操作属于中间操作,所以我们可以在过滤后的结果来应用其他Stream操作(比如forEach)。forEach需要一个函数来对过滤后的元素依次执行。forEach是一个最终操作,所以我们不能在forEach之后来执行其他Stream操作。

stringCollection
   .stream()  
   .filter((s) -> s.startsWith("a"))
   .forEach(System.out::println); // "aaa2", "aaa1"

3.7.2 Sort 排序

排序是一个中间操作,返回的是排序好后的Stream。如果你不指定一个自定义的Comparator则会使用默认排序。

stringCollection
   .stream()
   .sorted()
   .filter((s) -> s.startsWith("a"))  
   .forEach(System.out::println); // "aaa1", "aaa2"

需要注意的是,排序只创建了一个排列好后的Stream,而不会影响原有的数据源,排序之后原数据stringCollection是不会被修改的:

System.out.println(stringCollection); // ddd2, aaa2, bbb1, aaa1, bbb3, ccc, bbb2, ddd1

3.7.3 Map 映射

中间操作map会将元素根据指定的Function接口来依次将元素转成另外的对象,下面的示例展示了将字符串转换为大写字符串。你也可以通过map来讲对象转换成其他类型,map返回的Stream类型是根据你map传递进去的函数的返回值决定的。

stringCollection
   .stream()  
   .map(String::toUpperCase)  
   .sorted((a, b) -> b.compareTo(a))  
   .forEach(System.out::println); // "DDD2", "DDD1", "CCC", "BBB3", "BBB2", "AAA2", "AAA1"

3.7.4 Match 匹配

Stream提供了多种匹配操作,允许检测指定的Predicate是否匹配整个Stream。所有的匹配操作都是最终操作,并返回一个boolean类型的值。

boolean anyStartsWithA = stringCollection  
    .stream() 
    .anyMatch((s) -> s.startsWith("a"));             System.out.println(anyStartsWithA); // true boolean 
allStartsWithA = stringCollection  
    .stream()  
    .allMatch((s) -> s.startsWith("a")); System.out.println(allStartsWithA); // false boolean
noneStartsWithZ =  stringCollection  
    .stream()  
    .noneMatch((s) -> s.startsWith("z")); System.out.println(noneStartsWithZ); // true

3.7.5 Count 计数

计数是一个最终操作,返回Stream中元素的个数,返回值类型是long。

long startsWithB = stringCollection  
    .stream()  
    .filter((s) -> s.startsWith("b"))  
    .count(); 
System.out.println(startsWithB); // 3

3.7.6 Reduce 规约

这是一个最终操作,允许通过指定的函数来讲stream中的多个元素规约为一个元素,规越后的结果是通过Optional接口表示的:

Optional<String> reduced = stringCollection
    .stream()  
    .sorted()  
    .reduce((s1, s2) -> s1 + "#" + s2); reduced.ifPresent(System.out::println); //"aaa1#aaa2#bbb1#bbb2#bbb3#ccc#ddd1#ddd2"

3.7.7 并行Streams

前面提到过Stream有串行和并行两种,串行Stream上的操作是在一个线程中依次完成,而并行Stream则是在多个线程上同时执行。

下面的例子展示了是如何通过并行Stream来提升性能:

首先我们创建一个没有重复元素的大表:

int max = 1000000; 
List<String> values = new ArrayList<>(max); 
for (int i = 0; i < max; i++) {  
   UUID uuid = UUID.randomUUID();  
   values.add(uuid.toString()); 
}

然后我们计算一下排序这个Stream要耗时多久,

串行排序:

long t0 = System.nanoTime(); 
long count = values.stream().sorted().count(); 
System.out.println(count); 
long t1 = System.nanoTime(); 
long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0); 
System.out.println(String.format("sequential sort took: %d ms",  millis));

// 串行耗时: 899 ms

并行排序:

long t0 = System.nanoTime(); 
long count = values.parallelStream().sorted().count(); System.out.println(count); 
long t1 = System.nanoTime(); 
long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0); 
System.out.println(String.format("parallel sort took: %d ms", millis));

// 并行排序耗时: 472 ms

上面两个代码几乎是一样的,但是并行版的快了50%之多,唯一需要做的改动就是将stream()改为parallelStream()。

4. Map

前面提到过,Map类型不支持stream,不过Map提供了一些新的有用的方法来处理一些日常任务。

Map<Integer, String> map = new HashMap<>(); 
for (int i = 0; i < 10; i++) {  
   map.putIfAbsent(i, "val" + i); 
}
map.forEach((id, val) -> System.out.println(val));

以上代码很容易理解, putIfAbsent 不需要我们做额外的存在性检查,而forEach则接收一个Consumer接口来对map里的每一个键值对进行操作。

下面的例子展示了map上的其他有用的函数:

map.computeIfPresent(3,(num, val) -> val + num); 
map.get(3); // val33 
map.computeIfPresent(9, (num, val) -> null); 
map.containsKey(9); // false 
map.computeIfAbsent(23, num -> "val" + num); 
map.containsKey(23); // true 
map.computeIfAbsent(3, num -> "bam"); 
map.get(3); // val33

接下来展示如何在Map里删除一个键值全都匹配的项:

map.remove(3, "val3"); 
map.get(3); // val33 
map.remove(3, "val33"); 
map.get(3); // null

另外一个有用的方法:

map.getOrDefault(42, "not found"); // not found

对Map的元素做合并也变得很容易了:

map.merge(9,"val9", (value, newValue) -> value.concat(newValue)); map.get(9); // val9 
map.merge(9, "concat", (value, newValue) -> value.concat(newValue)); 
map.get(9); // val9concat

Merge做的事情是如果键名不存在则插入,否则则对原键对应的值做合并操作并重新插入到map中。

5. Date API

Java 8 在包java.time下包含了一组全新的时间日期API。新的日期API和开源的Joda-Time库差不多,但又不完全一样,下面的例子展示了这组新API里最重要的一些部分:

5.1 Clock 时钟

Clock类提供了访问当前日期和时间的方法,Clock是时区敏感的,可以用来取代 System.currentTimeMillis() 来获取当前的微秒数。某一个特定的时间点也可以使用Instant类来表示,Instant类也可以用来创建老的java.util.Date对象。

Clock clock = Clock.systemDefaultZone(); 
long millis = clock.millis(); 
Instant instant = clock.instant(); 
Date legacyDate = Date.from(instant); // legacy java.util.Date

5.2 Timezones 时区

在新API中时区使用ZoneId来表示。时区可以很方便的使用静态方法of来获取到。 时区定义了到UTS时间的时间差,在Instant时间点对象到本地日期对象之间转换的时候是极其重要的。

System.out.println(ZoneId.getAvailableZoneIds());
 // prints all available timezone ids ZoneId zone1 = 
ZoneId.of("Europe/Berlin"); 
ZoneId zone2 = ZoneId.of("Brazil/East"); 
System.out.println(zone1.getRules()); 
System.out.println(zone2.getRules()); // 
ZoneRules[currentStandardOffset=+01:00] // 
ZoneRules[currentStandardOffset=-03:00]

5.3 LocalTime 本地时间

LocalTime 定义了一个没有时区信息的时间,例如 晚上10点,或者 17:30:15。下面的例子使用前面代码创建的时区创建了两个本地时间。之后比较时间并以小时和分钟为单位计算两个时间的时间差:

LocalTime now1 = LocalTime.now(zone1); 
LocalTime now2 = LocalTime.now(zone2); 
System.out.println(now1.isBefore(now2)); // false 
long hoursBetween = ChronoUnit.HOURS.between(now1, now2); 
long minutesBetween = ChronoUnit.MINUTES.between(now1, now2); 
System.out.println(hoursBetween); // -3 
System.out.println(minutesBetween); // -239

LocalTime 提供了多种工厂方法来简化对象的创建,包括解析时间字符串。

LocalTime late = LocalTime.of(23, 59, 59); 
System.out.println(late); // 23:59:59 
DateTimeFormatter germanFormatter =  
    DateTimeFormatter
    .ofLocalizedTime(FormatStyle.SHORT)  
    .withLocale(Locale.GERMAN); 
LocalTime leetTime = LocalTime.parse("13:37", germanFormatter); 
System.out.println(leetTime); // 13:37

5.4 LocalDate 本地日期

LocalDate 表示了一个确切的日期,比如 2014-03-11。该对象值是不可变的,用起来和LocalTime基本一致。下面的例子展示了如何给Date对象加减天/月/年。另外要注意的是这些对象是不可变的,操作返回的总是一个新实例。

LocalDate today = LocalDate.now(); 
LocalDate tomorrow = today.plus(1, ChronoUnit.DAYS); 
LocalDate yesterday = tomorrow.minusDays(2); 
LocalDate independenceDay = LocalDate.of(2014, Month.JULY, 4); DayOfWeek dayOfWeek = independenceDay.getDayOfWeek();

System.out.println(dayOfWeek); // FRIDAY

从字符串解析一个LocalDate类型和解析LocalTime一样简单:

DateTimeFormatter germanFormatter = DateTimeFormatter  
   .ofLocalizedDate(FormatStyle.MEDIUM)  
   .withLocale(Locale.GERMAN); 
LocalDate xmas = LocalDate.parse("24.12.2014", germanFormatter); 
System.out.println(xmas); // 2014-12-24

5.5 LocalDateTime 本地日期时间

LocalDateTime 同时表示了时间和日期,相当于前两节内容合并到一个对象上了。LocalDateTime和LocalTime还有LocalDate一样,都是不可变的。LocalDateTime提供了一些能访问具体字段的方法。

LocalDateTime sylvester = LocalDateTime.of(2014, Month.DECEMBER, 31, 23, 59, 59); 
DayOfWeek dayOfWeek = sylvester.getDayOfWeek(); 
System.out.println(dayOfWeek); // WEDNESDAY Month month = 
sylvester.getMonth(); 
System.out.println(month); // DECEMBER long 
minuteOfDay = sylvester.getLong(ChronoField.MINUTE_OF_DAY); 
System.out.println(minuteOfDay); // 1439

只要附加上时区信息,就可以将其转换为一个时间点Instant对象,Instant时间点对象可以很容易的转换为老式的java.util.Date。

Instant instant = sylvester  
   .atZone(ZoneId.systemDefault())  
   .toInstant(); 
Date legacyDate = Date.from(instant); 
System.out.println(legacyDate); // Wed Dec 31 23:59:59 CET 2014

格式化LocalDateTime和格式化时间和日期一样的,除了使用预定义好的格式外,我们也可以自己定义格式:

DateTimeFormatter formatter = DateTimeFormatter  
   .ofPattern("MMM dd, yyyy - HH:mm"); 
LocalDateTime parsed = LocalDateTime.parse("Nov 03, 2014 - 07:13", 
formatter); 
String string = formatter.format(parsed); 
System.out.println(string); // Nov 03, 2014 - 07:13

和java.text.NumberFormat不一样的是新版的DateTimeFormatter是不可变的,所以它是线程安全的。

6. Annotation 注解

6.1 多重注解

在Java 8中支持多重注解了,先看个例子来理解一下是什么意思。

首先定义一个包装类Hints注解用来放置一组具体的Hint注解:

@interface Hints {  Hint[] value(); } 
@Repeatable(Hints.class) 
@interface Hint {  String value(); }

Java 8允许我们把同一个类型的注解使用多次,只需要给该注解标注一下@Repeatable即可。

例子:

  1. 使用包装类当容器来存多个注解(老方法) java @Hints({@Hint("hint1"), @Hint("hint2")}) class Person {}
  1. 使用多重注解(新方法) java @Hint("hint1") @Hint("hint2") class Person {} 第二个例子里java编译器会隐性的帮你定义好@Hints注解,了解这一点有助于你用反射来获取这些信息:
    java
    Hint hint = Person.class.getAnnotation(Hint.class);
    System.out.println(hint); // null
    Hints hints1 =
    Person.class.getAnnotation(Hints.class);
    System.out.println(hints1.value().length); // 2
    Hint[] hints2 =
    Person.class.getAnnotationsByType(Hint.class);
    System.out.println(hints2.length); // 2即便我们没有在Person类上定义@Hints注解,我们还是可以通过 getAnnotation(Hints.class) 来获取 @Hints注解,更加方便的方法是使用 getAnnotationsByType 可以直接获取到所有的@Hint注解。

6.2 新的target

另外Java 8的注解还增加到两种新的target上了:

@Target({ElementType.TYPE_PARAMETER, ElementType.TYPE_USE}) @interface MyAnnotation {}

7. more

JDK 1.8里还有很多很有用的东西,比如Arrays.parallelSort, StampedLock和CompletableFuture等等。

https://www.kancloud.cn/wizardforcel/modern-java-zh/141721

 

常见数据结构与算法整理总结(下)

这篇文章是常见数据结构与算法整理总结的下篇,上一篇主要是对常见的数据结构进行集中总结,这篇主要是总结一些常见的算法相关内容,文章中如有错误,欢迎指出。

一、概述
二、查找算法
三、排序算法
四、其它算法
五、常见算法题
六、总结

一、概述

以前看到这样一句话,语言只是工具,算法才是程序设计的灵魂。的确,算法在计算机科学中的地位真的很重要,在很多大公司的笔试面试中,算法掌握程度的考察都占据了很大一部分。不管是为了面试还是自身编程能力的提升,花时间去研究常见的算法还是很有必要的。下面是自己对于算法这部分的学习总结。

算法简介

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。对于同一个问题的解决,可能会存在着不同的算法,为了衡量一个算法的优劣,提出了空间复杂度与时间复杂度这两个概念。

时间复杂度

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记为 ** T(n) = O(f(n)) **,它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。这里需要重点理解这个增长率。

举个例子,看下面3个代码:

1、{++x;}

2、for(i = 1; i <= n; i++) { ++x; }

3、for(j = 1; j <= n; j++) 
        for(j = 1; j <= n; j++) 
             { ++x; }

上述含有 ++x 操作的语句的频度分别为1 、n 、n^2,

假设问题的规模扩大了n倍,3个代码的增长率分别是1 、n 、n^2

它们的时间复杂度分别为O(1)、O(n )、O(n^2)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

二、查找算法

查找和排序是最基础也是最重要的两类算法,熟练地掌握这两类算法,并能对这些算法的性能进行分析很重要,这两类算法中主要包括二分查找、快速排序、归并排序等等。

顺序查找

顺序查找又称线性查找。它的过程为:从查找表的最后一个元素开始逐个与给定关键字比较,若某个记录的关键字和给定值比较相等,则查找成功,否则,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录查找不成功,它的缺点是效率低下。

二分查找

  • 简介

二分查找又称折半查找,对于有序表来说,它的优点是比较次数少,查找速度快,平均性能好。

二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。

二分查找的时间复杂度为O(logn)

  • 实现
//给定有序查找表array 二分查找给定的值data
//查找成功返回下标 查找失败返回-1

static int funBinSearch(int[] array, int data) {

    int low = 0;
    int high = array.length - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        if (data == array[mid]) {
            return mid;
        } else if (data < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

三、排序算法

排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍,并分析它们的时空复杂度。

常见排序算法

常见排序算法性能比较:

图片来自网络

上面这张表中有稳定性这一项,排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前和排序后他们的相对位置不发生变化。

下面从冒泡排序开始逐一介绍。

冒泡排序

  • 简介

冒泡排序的基本思想是:设排序序列的记录个数为n,进行n-1次遍历,每次遍历从开始位置依次往后比较前后相邻元素,这样较大的元素往后移,n-1次遍历结束后,序列有序。

例如,对序列(3,2,1,5)进行排序的过程是:共进行3次遍历,第1次遍历时先比较3和2,交换,继续比较3和1,交换,再比较3和5,不交换,这样第1次遍历结束,最大值5在最后的位置,得到序列(2,1,3,5)。第2次遍历时先比较2和1,交换,继续比较2和3,不交换,第2次遍历结束时次大值3在倒数第2的位置,得到序列(1,2,3,5),第3次遍历时,先比较1和2,不交换,得到最终有序序列(1,2,3,5)。

需要注意的是,如果在某次遍历中没有发生交换,那么就不必进行下次遍历,因为序列已经有序。

  • 实现
// 冒泡排序 注意 flag 的作用
static void funBubbleSort(int[] array) {

    boolean flag = true;

    for (int i = 0; i < array.length - 1 && flag; i++) {

        flag = false;

        for (int j = 0; j < array.length - 1 - i; j++) {

            if (array[j] > array[j + 1]) {

                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                flag = true;
            }
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}
  • 分析

最佳情况下冒泡排序只需一次遍历就能确定数组已经排好序,不需要进行下一次遍历,所以最佳情况下,时间复杂度为** O(n) **。

最坏情况下冒泡排序需要n-1次遍历,第一次遍历需要比较n-1次,第二次遍历需要n-2次,…,最后一次需要比较1次,最差情况下时间复杂度为** O(n^2) **。

简单选择排序

  • 简介

简单选择排序的思想是:设排序序列的记录个数为n,进行n-1次选择,每次在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有效序列中的第i个记录。

例如,排序序列(3,2,1,5)的过程是,进行3次选择,第1次选择在4个记录中选择最小的值为1,放在第1个位置,得到序列(1,3,2,5),第2次选择从位置1开始的3个元素中选择最小的值2放在第2个位置,得到有序序列(1,2,3,5),第3次选择因为最小的值3已经在第3个位置不需要操作,最后得到有序序列(1,2,3,5)。

  • 实现
static void funSelectionSort(int[] array) {

    for (int i = 0; i < array.length - 1; i++) {

        int mink = i;

            // 每次从未排序数组中找到最小值的坐标
        for (int j = i + 1; j < array.length; j++) {

            if (array[j] < array[mink]) {
                mink = j;
            }
        }

        // 将最小值放在最前面
        if (mink != i) {
            int temp = array[mink];
            array[mink] = array[i];
            array[i] = temp;
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}
  • 分析

简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况** 无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为 O(n^2) ,进行移动操作的时间复杂度为 O(n) 。总的时间复杂度为 O(n^2) **。

最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。

简单选择排序是不稳定排序。

直接插入排序

  • 简介

直接插入的思想是:是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。

例如,排序序列(3,2,1,5)的过程是,初始时有序序列为(3),然后从位置1开始,先访问到2,将2插入到3前面,得到有序序列(2,3),之后访问1,找到合适的插入位置后得到有序序列(1,2,3),最后访问5,得到最终有序序列(1,2,3,5).

  • 实现
static void funDInsertSort(int[] array) {

    int j;

    for (int i = 1; i < array.length; i++) {

        int temp = array[i];

        j = i - 1;

        while (j > -1 && temp < array[j]) {

            array[j + 1] = array[j];

            j--;
        }

        array[j + 1] = temp;

    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}
  • 分析

最好情况下,当待排序序列中记录已经有序时,则需要n-1次比较,不需要移动,时间复杂度为** O(n) 。最差情况下,当待排序序列中所有记录正好逆序时,则比较次数和移动次数都达到最大值,时间复杂度为 O(n^2) 。平均情况下,时间复杂度为 O(n^2) **。

希尔排序

希尔排序又称“缩小增量排序”,它是基于直接插入排序的以下两点性质而提出的一种改进:(1) 直接插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(2) 直接插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。点击查看更多关于希尔排序的内容

归并排序

  • 简介

归并排序是分治法的一个典型应用,它的主要思想是:将待排序序列分为两部分,对每部分递归地应用归并排序,在两部分都排好序后进行合并。

例如,排序序列(3,2,8,6,7,9,1,5)的过程是,先将序列分为两部分,(3,2,8,6)和(7,9,1,5),然后对两部分分别应用归并排序,第1部分(3,2,8,6),第2部分(7,9,1,5),对两个部分分别进行归并排序,第1部分继续分为(3,2)和(8,6),(3,2)继续分为(3)和(2),(8,6)继续分为(8)和(6),之后进行合并得到(2,3),(6,8),再合并得到(2,3,6,8),第2部分进行归并排序得到(1,5,7,9),最后合并两部分得到(1,2,3,5,6,7,8,9)。

  • 实现
    //归并排序
    static void funMergeSort(int[] array) {

        if (array.length > 1) {

            int length1 = array.length / 2;
            int[] array1 = new int[length1];
            System.arraycopy(array, 0, array1, 0, length1);
            funMergeSort(array1);

            int length2 = array.length - length1;
            int[] array2 = new int[length2];
            System.arraycopy(array, length1, array2, 0, length2);
            funMergeSort(array2);

            int[] datas = merge(array1, array2);
            System.arraycopy(datas, 0, array, 0, array.length);
        }

    }

    //合并两个数组
    static int[] merge(int[] list1, int[] list2) {

        int[] list3 = new int[list1.length + list2.length];

        int count1 = 0;
        int count2 = 0;
        int count3 = 0;

        while (count1 < list1.length && count2 < list2.length) {

            if (list1[count1] < list2[count2]) {
                list3[count3++] = list1[count1++];
            } else {
                list3[count3++] = list2[count2++];
            }
        }

        while (count1 < list1.length) {
            list3[count3++] = list1[count1++];
        }

        while (count2 < list2.length) {
            list3[count3++] = list2[count2++];
        }

        return list3;
    }
  • 分析

归并排序的时间复杂度为O(nlogn),它是一种稳定的排序,java.util.Arrays类中的sort方法就是使用归并排序的变体来实现的。

快速排序

  • 简介

快速排序的主要思想是:在待排序的序列中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分中的所有元素都大于主元,然后对两部分递归地应用快速排序算法。

  • 实现
// 快速排序
static void funQuickSort(int[] mdata, int start, int end) {
    if (end > start) {
        int pivotIndex = quickSortPartition(mdata, start, end);
        funQuickSort(mdata, start, pivotIndex - 1);
        funQuickSort(mdata, pivotIndex + 1, end);
    }
}

// 快速排序前的划分
static int quickSortPartition(int[] list, int first, int last) {

    int pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {

        while (low <= high && list[low] <= pivot) {
            low++;
        }

        while (low <= high && list[high] > pivot) {
            high--;
        }

        if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }

    while (high > first && list[high] >= pivot) {
        high--;
    }

    if (pivot > list[high]) {
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else {
        return first;
    }
}
  • 分析

在快速排序算法中,比较关键的一个部分是主元的选择。在最差情况下,划分由n个元素构成的数组需要进行n次比较和n次移动,因此划分需要的时间是O(n)。在最差情况下,每次主元会将数组划分为一个大的子数组和一个空数组,这个大的子数组的规模是在上次划分的子数组的规模上减1,这样在最差情况下算法需要(n-1)+(n-2)+…+1= ** O(n^2) **时间。

最佳情况下,每次主元将数组划分为规模大致相等的两部分,时间复杂度为** O(nlogn) **。

堆排序

  • 简介

在介绍堆排序之前首先需要了解堆的定义,n个关键字序列K1,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):(1) ki <= k(2i)且 ki <= k(2i+1) (1 ≤ i≤ n/2),当然,这是小根堆,大根堆则换成>=号。

如果将上面满足堆性质的序列看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不大于(或不小于)其左右孩子节点的值。

堆排序的主要思想是:给定一个待排序序列,首先经过一次调整,将序列构建成一个大顶堆,此时第一个元素是最大的元素,将其和序列的最后一个元素交换,然后对前n-1个元素调整为大顶堆,再将其第一个元素和末尾元素交换,这样最后即可得到有序序列。

  • 实现
//堆排序
public class TestHeapSort {

    public static void main(String[] args) {
        int arr[] = { 5, 6, 1, 0, 2, 9 };
        heapsort(arr, 6);
        System.out.println(Arrays.toString(arr));
    }

    static void heapsort(int arr[], int n) {

        // 先建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, n);
        }

        for (int i = 0; i < n - 1; i++) {
            swap(arr, 0, n - i - 1);
            heapAdjust(arr, 0, n - i - 1);
        }
    }

    // 交换两个数
    static void swap(int arr[], int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    // 调整堆
    static void heapAdjust(int arr[], int index, int n) {

        int temp = arr[index];

        int child = 0;

        while (index * 2 + 1 < n) {
                        
            child = index * 2 + 1;
                        
            // child为左右孩子中较大的那个
            if (child != n - 1 && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果指定节点大于较大的孩子 不需要调整
            if (temp > arr[child]) {
                break;
            } else {
                // 否则继续往下判断孩子的孩子 直到找到合适的位置
                arr[index] = arr[child];
                index = child;
            }
        }

        arr[index] = temp;
    }
}

  • 分析

由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序时间复杂度也为O(nlogn),空间复杂度为O(1)。它是不稳定的排序方法。与快排和归并排序相比,堆排序在最差情况下的时间复杂度优于快排,空间效率高于归并排序。

四、其它算法

在上面的篇幅中,主要是对查找和常见的几种排序算法作了介绍,这些内容都是基础的但是必须掌握的内容,尤其是二分查找、快排、堆排、归并排序这几个更是面试高频考察点。(这里不禁想起百度一面的时候让我写二分查找和堆排序,二分查找还行,然而堆排序当时一脸懵逼…)下面主要是介绍一些常见的其它算法。

递归

  • 简介

在平常解决一些编程或者做一些算法题的时候,经常会用到递归。程序调用自身的编程技巧称为递归。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。上面介绍的快速排序和归并排序都用到了递归的思想。

  • 经典例子

斐波那契数列,又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)。

//斐波那契数列 递归实现
static long funFib(long index) {

    if (index == 0) {
        return 0;
    } else if (index == 1) {
        return 1;
    } else {
        return funFib(index - 1) + funFib(index - 2);
    }
}

上面代码是斐波那契数列的递归实现,然而我们不难得到它的时间复杂度是O(2^n),递归有时候可以很方便地解决一些问题,但是它也会带来一些效率上的问题。下面的代码是求斐波那契数列的另一种方式,效率比递归方法的效率高。

static long funFib2(long index) {

    long f0 = 0;
    long f1 = 1;
    long f2 = 1;

    if (index == 0) {
        return f0;
    } else if (index == 1) {
        return f1;
    } else if (index == 2) {
        return f2;
    }

    for (int i = 3; i <= index; i++) {
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
    }

    return f2;
}

分治算法

分治算法的思想是将待解决的问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立最终的解。分治算法中关键地一步其实就是递归地求解子问题。关于分治算法的一个典型例子就是上面介绍的归并排序。查看更多关于分治算法的内容

动态规划

动态规划与分治方法相似,都是通过组合子问题的解来求解待解决的问题。但是,分治算法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,而动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。动态规划方法通常用来求解最优化问题。查看更多关于动态规划的内容

动态规划典型的一个例子是最长公共子序列问题。

常见的算法还有很多,比如贪心算法,回溯算法等等,这里都不再详细介绍,想要熟练掌握,还是要靠刷题,刷题,刷题,然后总结。

五、常见算法题

下面是一些常见的算法题汇总。

不使用临时变量交换两个数

static void funSwapTwo(int a, int b) {

    a = a ^ b;
    b = b ^ a;
    a = a ^ b;

    System.out.println(a + " " + b);
}

判断一个数是否为素数

static boolean funIsPrime(int m) {

    boolean flag = true;

    if (m == 1) {
        flag = false;
    } else {

        for (int i = 2; i <= Math.sqrt(m); i++) {
            if (m % i == 0) {
                flag = false;
                break;
            }
        }
    }

    return flag;
}

其它算法题

1、15道使用频率极高的基础算法题
2、二叉树相关算法题
3、链表相关算法题
4、字符串相关算法问题

六、总结

以上就是自己对常见的算法相关内容的总结,算法虐我千百遍,我待算法如初恋,革命尚未成功,同志仍需刷题,加油。

常见数据结构与算法整理总结(上)

数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。

为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,有需要的可以阅读这篇文章。Java – 集合框架完全解析

一、线性表
  1.数组实现
  2.链表
二、栈与队列
三、树与二叉树
  1.树
  2.二叉树基本概念
  3.二叉查找树
  4.平衡二叉树
  5.红黑树
四、图
五、总结

一、线性表

线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。

实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)。

数组实现

数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后,它的大小就无法改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

  • 代码1 创建一个更大的数组来替换当前数组
int[] oldArray = new int[10];
        
int[] newArray = new int[20];
        
for (int i = 0; i < oldArray.length; i++) {
    newArray[i] = oldArray[i];
}

// 也可以使用System.arraycopy方法来实现数组间的复制     
// System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
        
oldArray = newArray;
  • 代码2 在数组位置index上添加元素e
//oldArray 表示当前存储元素的数组
//size 表示当前元素个数
public void add(int index, int e) {

    if (index > size || index < 0) {
        System.out.println("位置不合法...");
    }

    //如果数组已经满了 就扩容
    if (size >= oldArray.length) {
        // 扩容函数可参考代码1
    }

    for (int i = size - 1; i >= index; i--) {
        oldArray[i + 1] = oldArray[i];
    }

    //将数组elementData从位置index的所有元素往后移一位
    // System.arraycopy(oldArray, index, oldArray, index + 1,size - index);

    oldArray[index] = e;

    size++;
}

上面简单写出了数组实现线性表的两个典型函数,具体我们可以参考Java里面的ArrayList集合类的源码。数组实现的线性表优点在于可以通过下标来访问或者修改元素,比较高效,主要缺点在于插入和删除的花费开销较大,比如当在第一个位置前插入一个元素,那么首先要把所有的元素往后移动一个位置。为了提高在任意位置添加或者删除元素的效率,可以采用链式结构来实现线性表。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next的指向,效率很高。

单链表的结构

下面主要用代码来展示链表的一些基本操作,需要注意的是,这里主要是以单链表为例,暂时不考虑双链表和循环链表。

  • 代码3 链表的节点
class Node<E> {

    E item;
    Node<E> next;
    
    //构造函数
    Node(E element) {
       this.item = element;
       this.next = null;
   }
}
  • 代码4 定义好节点后,使用前一般是对头节点和尾节点进行初始化
//头节点和尾节点都为空 链表为空
Node<E> head = null;
Node<E> tail = null;
  • 代码5 空链表创建一个新节点
//创建一个新的节点 并让head指向此节点
head = new Node("nodedata1");

//让尾节点也指向此节点
tail = head;
  • 代码6 链表追加一个节点
//创建新节点 同时和最后一个节点连接起来
tail.next = new Node("node1data2");

//尾节点指向新的节点
tail = tail.next;
  • 代码7 顺序遍历链表
Node<String> current = head;
while (current != null) {
    System.out.println(current.item);
    current = current.next;
}
  • 代码8 倒序遍历链表
static void printListRev(Node<String> head) {
//倒序遍历链表主要用了递归的思想
    if (head != null) {
        printListRev(head.next);
        System.out.println(head.item);
    }
}
  • 代码 单链表反转
//单链表反转 主要是逐一改变两个节点间的链接关系来完成
static Node<String> revList(Node<String> head) {

    if (head == null) {
        return null;
    }

    Node<String> nodeResult = null;

    Node<String> nodePre = null;
    Node<String> current = head;

    while (current != null) {

        Node<String> nodeNext = current.next;

        if (nodeNext == null) {
            nodeResult = current;
        }

        current.next = nodePre;
        nodePre = current;
        current = nodeNext;
    }

    return nodeResult;
}

上面的几段代码主要展示了链表的几个基本操作,还有很多像获取指定元素,移除元素等操作大家可以自己完成,写这些代码的时候一定要理清节点之间关系,这样才不容易出错。

链表的实现还有其它的方式,常见的有循环单链表,双向链表,循环双向链表。 循环单链表 主要是链表的最后一个节点指向第一个节点,整体构成一个链环。 双向链表 主要是节点中包含两个指针部分,一个指向前驱元,一个指向后继元,JDK中LinkedList集合类的实现就是双向链表。** 循环双向链表** 是最后一个节点指向第一个节点。

二、栈与队列

栈和队列也是比较常见的数据结构,它们是比较特殊的线性表,因为对于栈来说,访问、插入和删除元素只能在栈顶进行,对于队列来说,元素只能从队列尾插入,从队列头访问和删除。

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈顶,对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表,即后进先出。

栈的模型

下面我们看一道经典题目,加深对栈的理解。

关于栈的一道经典题目

上图中的答案是C,其中的原理可以好好想一想。

因为栈也是一个表,所以任何实现表的方法都能实现栈。我们打开JDK中的类Stack的源码,可以看到它就是继承类Vector的。当然,Stack是Java2前的容器类,现在我们可以使用LinkedList来进行栈的所有操作。

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列示意图

我们可以使用链表来实现队列,下面代码简单展示了利用LinkedList来实现队列类。

  • 代码9 简单实现队列类
public class MyQueue<E> {

    private LinkedList<E> list = new LinkedList<>();

    // 入队
    public void enqueue(E e) {
        list.addLast(e);
    }

    // 出队
    public E dequeue() {
        return list.removeFirst();
    }
}

普通的队列是一种先进先出的数据结构,而优先队列中,元素都被赋予优先级。当访问元素的时候,具有最高优先级的元素最先被删除。优先队列在生活中的应用还是比较多的,比如医院的急症室为病人赋予优先级,具有最高优先级的病人最先得到治疗。在Java集合框架中,类PriorityQueue就是优先队列的实现类,具体大家可以去阅读源码。

三、树与二叉树

树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用。在介绍二叉树之前,我们先简单了解一下树的相关内容。

** 树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。它具有以下特点:每个节点有零个或多个子节点;没有父节点的节点称为节点;每一个非根节点有且只有一个 父节点 **;除了根节点外,每个子节点可以分为多个不相交的子树。

树的结构

二叉树基本概念

  • 定义

二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

  • 相关性质

二叉树的每个结点至多只有2棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

二叉树的第i层至多有2(i-1)个结点;深度为k的二叉树至多有2k-1个结点。

一棵深度为k,且有2^k-1个节点的二叉树称之为** 满二叉树 **;

深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为** 完全二叉树 **。

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

  • 三种遍历方法

在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点进行某种处理,这就涉及到二叉树的遍历。二叉树主要是由3个基本单元组成,根节点、左子树和右子树。如果限定先左后右,那么根据这三个部分遍历的顺序不同,可以分为先序遍历、中序遍历和后续遍历三种。

(1) 先序遍历 若二叉树为空,则空操作,否则先访问根节点,再先序遍历左子树,最后先序遍历右子树。
(2) 中序遍历 若二叉树为空,则空操作,否则先中序遍历左子树,再访问根节点,最后中序遍历右子树。
(3) 后序遍历 若二叉树为空,则空操作,否则先后序遍历左子树访问根节点,再后序遍历右子树,最后访问根节点。

给定二叉树写出三种遍历结果
  • 树和二叉树的区别

(1) 二叉树每个节点最多有2个子节点,树则无限制。
(2) 二叉树中节点的子树分为左子树和右子树,即使某节点只有一棵子树,也要指明该子树是左子树还是右子树,即二叉树是有序的。
(3) 树决不能为空,它至少有一个节点,而一棵二叉树可以是空的。

上面我们主要对二叉树的相关概念进行了介绍,下面我们将从二叉查找树开始,介绍二叉树的几种常见类型,同时将之前的理论部分用代码实现出来。

二叉查找树

  • 定义

二叉查找树就是二叉排序树,也叫二叉搜索树。二叉查找树或者是一棵空树,或者是具有下列性质的二叉树:

(1) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2) 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3) 左、右子树也分别为二叉排序树;
(4) 没有键值相等的结点。

典型的二叉查找树的构建过程
  • 性能分析

对于二叉查找树来说,当给定值相同但顺序不同时,所构建的二叉查找树形态是不同的,下面看一个例子。

不同形态平衡二叉树的ASL不同

可以看到,含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度为n,其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉查找树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比。平均情况下,二叉查找树的平均查找长度和logn是等数量级的,所以为了获得更好的性能,通常在二叉查找树的构建过程需要进行“平衡化处理”,之后我们将介绍平衡二叉树和红黑树,这些均可以使查找树的高度为O(log(n))。

  • 代码10 二叉树的节点

class TreeNode<E> {

    E element;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E e) {
        element = e;
    }
}

二叉查找树的三种遍历都可以直接用递归的方法来实现:

  • 代码12 先序遍历
protected void preorder(TreeNode<E> root) {

    if (root == null)
        return;

    System.out.println(root.element + " ");

    preorder(root.left);

    preorder(root.right);
}
  • 代码13 中序遍历
protected void inorder(TreeNode<E> root) {

    if (root == null)
        return;

    inorder(root.left);

    System.out.println(root.element + " ");

    inorder(root.right);
}
  • 代码14 后序遍历
protected void postorder(TreeNode<E> root) {

    if (root == null)
        return;

    postorder(root.left);

    postorder(root.right);

    System.out.println(root.element + " ");
}
  • 代码15 二叉查找树的简单实现
/**
 * @author JackalTsc
 */
public class MyBinSearchTree<E extends Comparable<E>> {

    // 根
    private TreeNode<E> root;

    // 默认构造函数
    public MyBinSearchTree() {
    }

    // 二叉查找树的搜索
    public boolean search(E e) {

        TreeNode<E> current = root;

        while (current != null) {

            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else {
                return true;
            }
        }

        return false;
    }

    // 二叉查找树的插入
    public boolean insert(E e) {

        // 如果之前是空二叉树 插入的元素就作为根节点
        if (root == null) {
            root = createNewNode(e);
        } else {
            // 否则就从根节点开始遍历 直到找到合适的父节点
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while (current != null) {
                if (e.compareTo(current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else {
                    return false;
                }
            }
            // 插入
            if (e.compareTo(parent.element) < 0) {
                parent.left = createNewNode(e);
            } else {
                parent.right = createNewNode(e);
            }
        }
        return true;
    }

    // 创建新的节点
    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode(e);
    }

}

// 二叉树的节点
class TreeNode<E extends Comparable<E>> {

    E element;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E e) {
        element = e;
    }
}

上面的代码15主要展示了一个自己实现的简单的二叉查找树,其中包括了几个常见的操作,当然更多的操作还是需要大家自己去完成。因为在二叉查找树中删除节点的操作比较复杂,所以下面我详细介绍一下这里。

  • 二叉查找树中删除节点分析

要在二叉查找树中删除一个元素,首先需要定位包含该元素的节点,以及它的父节点。假设current指向二叉查找树中包含该元素的节点,而parent指向current节点的父节点,current节点可能是parent节点的左孩子,也可能是右孩子。这里需要考虑两种情况:

  1. current节点没有左孩子,那么只需要将parent节点和current节点的右孩子相连。
  2. current节点有一个左孩子,假设rightMost指向包含current节点的左子树中最大元素的节点,而parentOfRightMost指向rightMost节点的父节点。那么先使用rightMost节点中的元素值替换current节点中的元素值,将parentOfRightMost节点和rightMost节点的左孩子相连,然后删除rightMost节点。
    // 二叉搜索树删除节点
    public boolean delete(E e) {

        TreeNode<E> parent = null;
        TreeNode<E> current = root;

        // 找到要删除的节点的位置
        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                parent = current;
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                parent = current;
                current = current.right;
            } else {
                break;
            }
        }

        // 没找到要删除的节点
        if (current == null) {
            return false;
        }

        // 考虑第一种情况
        if (current.left == null) {
            if (parent == null) {
                root = current.right;
            } else {
                if (e.compareTo(parent.element) < 0) {
                    parent.left = current.right;
                } else {
                    parent.right = current.right;
                }
            }
        } else { // 考虑第二种情况
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;
            // 找到左子树中最大的元素节点
            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }

            // 替换
            current.element = rightMost.element;

            // parentOfRightMost和rightMost左孩子相连
            if (parentOfRightMost.right == rightMost) {
                parentOfRightMost.right = rightMost.left;
            } else {
                parentOfRightMost.left = rightMost.left;
            }
        }

        return true;
    }

平衡二叉树

平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

平衡二叉树

AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

红黑树

红黑树是平衡二叉树的一种,它保证在最坏情况下基本动态集合操作的事件复杂度为O(log n)。红黑树和平衡二叉树区别如下:

(1) 红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
(2) 平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。点击查看更多

四、图

  • 简介

图是一种较线性表和树更为复杂的数据结构,在线性表中,数据元素之间仅有线性关系,在树形结构中,数据元素之间有着明显的层次关系,而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。图的应用相当广泛,特别是近年来的迅速发展,已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

  • 相关阅读

因为图这部分的内容还是比较多的,这里就不详细介绍了,有需要的可以自己搜索相关资料。

(1) 《百度百科对图的介绍》
(2) 《数据结构之图(存储结构、遍历)》

五、总结

到这里,关于常见的数据结构的整理就结束了,断断续续大概花了两天时间写完,在总结的过程中,通过查阅相关资料,结合书本内容,收获还是很大的,在下一篇博客中将会介绍常用数据结构与算法整理总结(下)之算法篇,欢迎大家关注。

POSIX I/O模型之阻塞、非阻塞、同步、异步浅析

服务端编程常需要接触I/O。最近对I/O模型有了进一步的认识,这里就总结一下POSIX I/O模型,并简略总结一下Java中的Network I/O模型。常见的POSIX I/O模型有四种:

  • 同步阻塞I/O(Synchrohous, blocking I/O)
  • 同步非阻塞I/O(Synchrohous, non-blocking I/O)
  • I/O多路复用(I/O Multiplexing),较为典型的有selectepoll模型
  • 异步I/O(Asynchronous I/O)

通俗解释

在详细解释各个I/O模型之前,我们先来通俗地解释一下各个I/O模型,便于理解。

  • 同步阻塞I/O:去餐厅吃饭,等餐的时候需要在取餐处一直等着,不能干其他事情。
  • 同步非阻塞I/O:去餐厅吃饭,等餐的时候可以干别的事,但需要不断去窗口询问饭是否准备好了(轮询)。
  • 异步I/O:去餐厅吃饭,等餐的时候只需要坐着等人送来即可。

下面我们来详细解释一下各个I/O模型,为了简单起见这里采用UDP协议作为示例。

Blocking I/O

首先对于一个从socket读取数据的操作,通常将其分为两个阶段:

  1. 等待远程数据就绪。网卡会将数据报文传给协议栈,封装处理之后拷贝到内核缓冲区中
  2. 将数据从内核缓冲区拷贝到进程中

最简单的模型就是blocking I/O模型了。进行recvfrom系统调用(读取数据)以后,调用者进程会被阻塞,直到内核接收到数据并拷贝到进程中才返回。进行recvfrom系统调用后,内核首先会等待数据就绪,这通常需要一段时间。当数据就绪并到达内核缓冲区后,内核就会将数据拷贝至用户内存空间,并且返回结果,此时调用者进程才会解除阻塞状态,恢复执行。Blocking I/O不会浪费CPU时间片,但是只能处理一个连接,对于多个连接的情况就需要用到下面要提到的的I/O多路复用了。

可以看出,blocking I/O会阻塞上面两个阶段:

Synchrohous, blocking IO

Non-blocking I/O

与blocking I/O不同,non-blocking I/O的意思是在读取数据(recvfrom)时,如果数据没有就绪则立刻返回一个错误,而不会被阻塞住,这样我们还可以继续进行其它的操作。为了读取到数据,我们需要不断调用recvfrom进行轮询操作,一旦数据准备好了,内核就会将数据拷贝至用户内存空间,并且返回读取成功的结果。这种模型的弊端就是轮询操作会占用时间片,浪费CPU资源。可以看出,non-blocking I/O会阻塞上面的阶段(2):

Non-blocking IO

I/O multiplexing

I/O多路复用(multiplexing)是网络编程中最常用的模型,像我们最常用的selectepoll都属于这种模型。以select为例:

IO Multiplexing

看起来它与blocking I/O很相似,两个阶段都阻塞。但它与blocking I/O的一个重要区别就是它可以等待多个文件描述符就绪,即可以处理多个连接。这里的select相当于一个“代理”,调用select以后进程会被select阻塞,这时候在内核空间内select会监听指定的的多个文件描述符(如socket连接),如果其中任意一个数据就绪了就返回。此时程序再进行数据读取操作,将数据拷贝至当前进程内。由于select可以监听多个socket,我们可以用它来处理多个连接。

select模型中每个socket一般都设置成non-blocking,虽然阶段(1)仍然是阻塞状态,但是它是被select调用阻塞的,而不是直接被I/O阻塞的。select底层通过轮询机制来判断每个socket读写是否就绪。

当然select也有一些缺点,比如底层轮询机制会增加开销、支持的文件描述符数量过少等。为此,Linux引入了epoll作为select的改进版本,具体的区别和改进后面会另开一篇总结。

Asynchronous I/O

Asynchronous I/O的过程:

Asynchronous IO

这里面的读取操作的语义与上面的几种模型都不同。这里的读取操作(aio_read)会通知内核进行读取操作并将数据拷贝至进程中,完事后通知进程整个操作全部完成(绑定一个回调函数处理数据)。读取操作会立刻返回,程序可以进行其它的操作,所有的读取、拷贝工作都由内核去做,做完以后通知进程,进程调用绑定的回调函数来处理数据。

异步I/O在网络编程中几乎用不到,在File I/O中可能会用到。

Java中的Network I/O模型

Java原生的Network I/O模型分为以下几种:

  • BIO(如ServerSocket)
  • NIO(JDK 1.4引入,如ServerSocketChannel)
  • NIO.2(AIO, JDK 1.7引入,如AsynchronousServerSocketChannel)

其中BIO对应传统的同步阻塞I/O,而NIO对应I/O多路复用(select模型,Reactor模式),NIO.2则对应异步IO模型(依然是基于I/O多路复用,和POSIX的asynchronous I/O模型不同)。在Linux下,NIO和NIO.2底层都是通过epoll实现的。

Netty的I/O模型也类似,分为OIO和NIO两种。

总结

我们来总结一下阻塞、非阻塞,同步和异步这两组概念。

先来说阻塞和非阻塞。阻塞调用会一直等待远程数据就绪再返回,即上面的阶段(1)会阻塞调用者,直到读取结束。而非阻塞无论在什么情况下都会立即返回。

接下来是同步和异步。POSIX标准里是这样定义同步和异步的:

  • A synchronous I/O operation causes the requesting process to be blocked until that I/O operation completes.
  • An asynchronous I/O operation does not cause the requesting process to be blocked.

同步方法会一直阻塞进程,直到I/O操作结束,注意这里相当于上面的(1)(2)两个阶段都会阻塞调用者。而异步方法不会阻塞调用者进程,即使是从内核空间的缓冲区将数据拷贝到进程中这一操作也不会阻塞进程,拷贝完毕后内核会通知进程数据拷贝结束。

下面的这张图很好地总结了之前讲的这几种POSIX I/O模型(来自Unix Network Programming):

IO模型比较


References

Spring Boot 使用Redis缓存

续接上文:Spring Boot 1.5.4集成Redis

Spring Cache的官方文档,请看这里

缓存存储

Spring 提供了很多缓存管理器,例如:

  • SimpleCacheManager
  • EhCacheCacheManager
  • CaffeineCacheManager
  • GuavaCacheManager
  • CompositeCacheManager
    这里我们要用的是除了核心的Spring框架之外,Spring Data提供的缓存管理器:RedisCacheManager

在Spring Boot中通过@EnableCaching注解自动化配置合适的缓存管理器(CacheManager),默认情况下Spring Boot根据下面的顺序自动检测缓存提供者:

  • Generic
  • JCache (JSR-107)
  • EhCache 2.x
  • Hazelcast
  • Infinispan
  • Redis
  • Guava
  • Simple

但是因为我们之前已经配置了redisTemplate了,Spring Boot就无法自动给RedisCacheManager设置redisTemplate了,所以接下来要自己配置CacheManager 。

  1. 首先修改RedisConfig配置类,添加@EnableCaching注解,并继承CachingConfigurerSupport,重写CacheManager 方法
...
@Configuration
@EnableCaching
public class RedisConfig extends CachingConfigurerSupport {

    @Bean
    public RedisTemplate<String, String> redisTemplate(RedisConnectionFactory factory) {
        RedisTemplate<String, String> redisTemplate = new RedisTemplate<String, String>();
        redisTemplate.setConnectionFactory(factory);
        redisTemplate.afterPropertiesSet();
        setSerializer(redisTemplate);
        return redisTemplate;
    }

    private void setSerializer(RedisTemplate<String, String> template) {
        Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new Jackson2JsonRedisSerializer(Object.class);
        ObjectMapper om = new ObjectMapper();
        om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
        om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
        jackson2JsonRedisSerializer.setObjectMapper(om);
        template.setKeySerializer(new StringRedisSerializer());
        template.setValueSerializer(jackson2JsonRedisSerializer);
    }

@Bean
    public CacheManager cacheManager(RedisTemplate redisTemplate) {
        RedisCacheManager rcm = new RedisCacheManager(redisTemplate);
        // 设置缓存过期时间,秒
        rcm.setDefaultExpiration(60);
        return rcm;
    }
...

Spring提供了如下注解来声明缓存规则:

  • @Cacheable triggers cache population
  • @CacheEvict triggers cache eviction
  • @CachePut updates the cache without interfering with the method execution
  • @Caching regroups multiple cache operations to be applied on a method
  • @CacheConfig shares some common cache-related settings at class-level
注  解 描  述
@Cacheable 表明Spring在调用方法之前,首先应该在缓存中查找方法的返回值。如果这个值能够找到,就会返回缓存的值。否则的话,这个方法就会被调用,返回值会放到缓存之中
@CachePut 表明Spring应该将方法的返回值放到缓存中。在方法的调用前并不会检查缓存,方法始终都会被调用
@CacheEvict 表明Spring应该在缓存中清除一个或多个条目
@Caching 这是一个分组的注解,能够同时应用多个其他的缓存注解
@CacheConfig 可以在类层级配置一些共用的缓存配置

@Cacheable和@CachePut有一些共有的属性

属  性 类  型 描  述
value String[] 要使用的缓存名称
condition String SpEL表达式,如果得到的值是false的话,不会将缓存应用到方法调用上
key String SpEL表达式,用来计算自定义的缓存key
unless String SpEL表达式,如果得到的值是true的话,返回值不会放到缓存之中
  1. 在一个请求方法上加上@Cacheable注解,测试下效果
    @Cacheable(value="testallCache")
    @RequestMapping(value = "/redis/user/{userId}", method = RequestMethod.GET)
    public User getUser(@PathVariable() Integer userId) {
        User user = userService.getUserById(userId);
        return user;
    }
  2. 然后访问这个请求,控制台就报错啦。
    java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
    at org.springframework.data.redis.serializer.StringRedisSerializer.serialize(StringRedisSerializer.java:33)
    at org.springframework.data.redis.cache.RedisCacheKey.serializeKeyElement(RedisCacheKey.java:74)
    at org.springframework.data.redis.cache.RedisCacheKey.getKeyBytes(RedisCacheKey.java:49)
    at org.springframework.data.redis.cache.RedisCache$1.doInRedis(RedisCache.java:176)
    at org.springframework.data.redis.cache.RedisCache$1.doInRedis(RedisCache.java:172)
    at org.springframework.data.redis.core.RedisTemplate.execute(RedisTemplate.java:207)

    原因如下:
    先看一下Redis缓存默认的Key生成策略

    • If no params are given, return SimpleKey.EMPTY.
    • If only one param is given, return that instance.
    • If more the one param is given, return a SimpleKey containing all parameters.

从上面的生成策略可以知道,上面的缓存testallCache使用的key是整形的userId参数,但是我们之前在redisTemplate里设置了template.setKeySerializer(new StringRedisSerializer());,所以导致类型转换错误。虽然也可以使用SpEL表达式生成Key(详见这里),但是返回结果还是需要是string类型(比如#root.methodName就是,#root.method就不是),更通用的办法是重写keyGenerator定制Key生成策略。

  1. 修改RedisConfig类,重写keyGenerator方法:
    @Bean
    public KeyGenerator keyGenerator() {
        return new KeyGenerator() {
            @Override
            public Object generate(Object target, Method method, Object... params) {
                StringBuilder sb = new StringBuilder();
                sb.append(target.getClass().getName());
                sb.append(":" + method.getName());
                for (Object obj : params) {
                    sb.append(":" + obj.toString());
                }
                return sb.toString();
            }
        };
    }
  2. 再次进行刚才的请求(分别以1,2作为userId参数),浏览器结果如下图:image
    image
    使用redisclient工具查看下:image
    image
    可以看到Redis里保存了:
  • 两条string类型的键值对:key就是上面方法生成的结果,value就是user对象序列化成json的结果
  • 一个有序集合:其中key为@Cacheable里的value+~keys,分数为0,成员为之前string键值对的key

这时候把userId为1的用户的username改为ansel(原来是ansel1),再次进行https://localhost:8443/redis/user/1 请求,发现浏览器返回结果仍是ansel1,证明确实是从Redis缓存里返回的结果。

image

image

缓存更新与删除

  1. 更新与删除Redis缓存需要用到@CachePut和@CacheEvict。这时候我发现如果使用上面那种key的生成策略,以用户为例:它的增删改查方法无法保证生成同一个key(方法名不同,参数不同),所以修改一下keyGenerator,使其按照缓存名称+userId方式生成key:
    @Bean
    public KeyGenerator keyGenerator() {
        return new KeyGenerator() {
            @Override
            public Object generate(Object target, Method method, Object... params) {
                StringBuilder sb = new StringBuilder();
                String[] value = new String[1];
                // sb.append(target.getClass().getName());
                // sb.append(":" + method.getName());
                Cacheable cacheable = method.getAnnotation(Cacheable.class);
                if (cacheable != null) {
                    value = cacheable.value();
                }
                CachePut cachePut = method.getAnnotation(CachePut.class);
                if (cachePut != null) {
                    value = cachePut.value();
                }
                CacheEvict cacheEvict = method.getAnnotation(CacheEvict.class);
                if (cacheEvict != null) {
                    value = cacheEvict.value();
                }
                sb.append(value[0]);
                for (Object obj : params) {
                    sb.append(":" + obj.toString());
                }
                return sb.toString();
            }
        };
    }
  2. 接下来编写user的增删改查方法:
    @CachePut(value = "user", key = "#root.caches[0].name + ':' + #user.userId")
    @RequestMapping(value = "/redis/user", method = RequestMethod.POST)
    public User insertUser(@RequestBody User user) {
        user.setPassword(SystemUtil.MD5(user.getPassword()));
        userService.insertSelective(user);
        return user;
    }
    
    @Cacheable(value = "user")
    @RequestMapping(value = "/redis/user/{userId}", method = RequestMethod.GET)
    public User getUser(@PathVariable Integer userId) {
        User user = userService.getUserById(userId);
        return user;
    }
    //#root.caches[0].name:当前被调用方法所使用的Cache, 即"user"
    @CachePut(value = "user", key = "#root.caches[0].name + ':' + #user.userId")
    @RequestMapping(value = "/redis/user", method = RequestMethod.PUT)
    public User updateUser(@RequestBody User user) {
        user.setPassword(SystemUtil.MD5(user.getPassword()));
        userService.updateByPrimaryKeySelective(user);
        return user;
    }
    
    @CacheEvict(value = "user")
    @RequestMapping(value = "/redis/user/{userId}", method = RequestMethod.DELETE)
    public void deleteUser(@PathVariable Integer userId) {
        userService.deleteByPrimaryKey(userId);
    }

    因为新增和修改传递的参数为user对象,keyGenerator无法获取到userId,只好使用SpEL显示标明key了。

然后进行测试:

进行insert操作:

image

插入后,进行get请求:

image

查看Redis存储:

image

image


进行update操作:

image

更新后,进行get请求:

image

查看Redis存储:

image


进行delete操作:

image

查看Redis存储:

image

发现user:3的记录已经没有了,只剩user:1,user:2了


一直很想知道网上很多用之前那种keyGenerator方法的,他们是怎么进行缓存更新和删除的,有知道的可以告知下。

Spring Boot 1.5.4集成Redis

本文示例源码,请看这里

如何安装与配置Redis,请看这里


  1. 首先添加起步依赖:
    <dependency>  
    <groupId>org.springframework.boot</groupId>  
    <artifactId>spring-boot-starter-data-redis</artifactId>  
    </dependency>  

    该依赖里默认包含了spring-data-redis和Jedis依赖,见这里

  2. 编辑application.properties,配置Redis
    # Redis 配置
    # Redis数据库索引(默认为0)
    spring.redis.database=0
    # Redis服务器地址
    spring.redis.host=192.168.10.128
    # Redis服务器连接端口
    spring.redis.port=6379
    # Redis服务器连接密码(默认为空)
    spring.redis.password=123qwe
    # 连接池最大连接数(使用负值表示没有限制)
    spring.redis.pool.max-active=8
    # 连接池最大阻塞等待时间(使用负值表示没有限制)
    spring.redis.pool.max-wait=-1
    # 连接池中的最大空闲连接
    spring.redis.pool.max-idle=8
    # 连接池中的最小空闲连接
    spring.redis.pool.min-idle=0
    # 连接超时时间(毫秒)
    spring.redis.timeout=0
  3. 添加一个string类型的键值对,测试一下
@RestController
public class RedisController {

    @Autowired
    private StringRedisTemplate stringRedisTemplate;

    @RequestMapping(value = "/redis/string", method = RequestMethod.GET)
    public void insertString() {
        stringRedisTemplate.opsForValue().set("stringKey", "stringValue");
    }   
}

可以看到已经添加进去了:

[root@localhost ~]# redis-cli
127.0.0.1:6379> get stringKey
"stringValue"

如果这不是一个Spring Boot项目,要想使用spring-data-redis还至少需要进行下面的配置:

    @Bean
    public RedisConnectionFactory jedisConnectionFactory() {
        JedisConnectionFactory jcf = new JedisConnectionFactory();
        jcf.setHostName("192.168.10.128");
        jcf.setPort(6379);
        jcf.setPassword("123qwe");
        return jcf;
    }

    @Bean
    public RedisTemplate<String, String> redisTemplate(RedisConnectionFactory factory) {
        RedisTemplate<String, String> redisTemplate = new RedisTemplate<String, String>();
        redisTemplate.setConnectionFactory(jedisConnectionFactory());
        return redisTemplate;
    }

但是,从springboot的Redis自动配置类RedisAutoConfiguration.java里可以看到,springboot已经帮我们配置好了。

Spring Data Redis提供了两个模板:

  • RedisTemplate
  • StringRedisTemplate

RedisTemplate会使用JdkSerializationRedisSerializer,这意味着key和value都会通过Java进行序列化。 StringRedisTemplate默认会使用StringRedisSerializer

所以要是操作字符串的话,用StringRedisTemplate就可以了。但要是想要存储一个对象(比如:User),我们就需要使用RedisTemplate,并对key采用string序列化方式,对value采用json序列化方式,这时候就需要对redisTemplate自定义配置了:

@Bean
    public RedisTemplate<String, String> redisTemplate(RedisConnectionFactory factory) {
        RedisTemplate<String, String> redisTemplate = new RedisTemplate<String, String>();

        redisTemplate.setConnectionFactory(factory);
        redisTemplate.afterPropertiesSet();
        setSerializer(redisTemplate);
        return redisTemplate;
    }

    private void setSerializer(RedisTemplate<String, String> template) {
        Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new Jackson2JsonRedisSerializer(Object.class);
        ObjectMapper om = new ObjectMapper();
        om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
        om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
        jackson2JsonRedisSerializer.setObjectMapper(om);
        template.setKeySerializer(new StringRedisSerializer());
        template.setValueSerializer(jackson2JsonRedisSerializer);
    }

添加一条数据,测试效果:

    @RequestMapping(value = "/redis/string/object", method = RequestMethod.GET)
    public void insertStringObject() {
        User user = new User();
        user.setUserId(1);
        user.setUsername("user1");
        user.setPassword("password1");
        redisTemplate.opsForValue().set("stringKeyObject", user);
    }

在redis-cli里查看一下:

127.0.0.1:6379> get stringKeyObject
"[\"com.ansel.testall.mybatis.model.User\",{\"userId\":1,\"username\":\"user1\",\"password\":\"password1\"}]"

使用代码获取刚才存储的对象:

    @RequestMapping(value = "/redis/string/object/get", method = RequestMethod.GET)
    public User getStringObject() {
        User user = (User) redisTemplate.opsForValue().get("stringKeyObject");
        return user;
    }

image

更多方法详见下表:

方  法 子API接口 描  述
opsForValue() ValueOperations 操作具有简单值的条目
opsForList() ListOperations 操作具有list值的条目
opsForSet() SetOperations 操作具有set值的条目
opsForZSet() ZSetOperations 操作具有ZSet值(排序的set)的条目
opsForHash() HashOperations 操作具有hash值的条目
boundValueOps(K) BoundValueOperations 以绑定指定key的方式,操作具有简单值的条目
boundListOps(K) BoundListOperations 以绑定指定key的方式,操作具有list值的条目
boundSetOps(K) BoundSetOperations 以绑定指定key的方式,操作具有set值的条目
boundZSet(K) BoundZSetOperations 以绑定指定key的方式,操作具有ZSet值(排序的set)的条目
boundHashOps(K) BoundHashOperations 以绑定指定key的方式,操作具有hash值的条目

Java NIO 基础知识

前言

前言部分是科普,读者可自行选择是否阅读这部分内容。

为什么我们需要关心 NIO?我想很多业务猿都会有这个疑问。

我在工作的前两年对这个问题也很不解,因为那个时候我认为自己已经非常熟悉 IO 操作了,读写文件什么的都非常溜了,IO 包无非就是 File、RandomAccessFile、字节流、字符流这些,感觉没什么好纠结的。最混乱的当属 InputStream/OutputStream 一大堆的类不知道谁是谁,不过了解了装饰者模式以后,也都轻松破解了。

在 Java 领域,一般性的文件操作确实只需要和 java.io 包打交道就可以了,尤其对于写业务代码的程序员来说。不过,当你写了两三年代码后,你的业务代码可能已经写得很溜了,蒙着眼睛也能写增删改查了。这个时候,也许你会想要开始了解更多的底层内容,包括并发、JVM、分布式系统、各个开源框架源码实现等,处于这个阶段的程序员会开始认识到 NIO 的用处,因为系统间通讯无处不在。

可能很多人不知道 Netty 或 Mina 有什么用?和 Tomcat 有什么区别?为什么我用 HTTP 请求就可以解决应用间调用的问题却要使用 Netty?

当然,这些问题的答案很简单,就是为了提升性能。那意思是 Tomcat 性能不好?当然不是,它们的使用场景就不一样。当初我也不知道 Nginx 摆在 Tomcat 前面有什么用,也是经过实践慢慢领悟到了那么些意思。

Nginx 是 web 服务器,Tomcat/Jetty 是应用服务器,Netty 是通讯工具。

也许你现在还不知道 NIO 有什么用,但是一定不要放弃学习它。

缓冲区操作

缓冲区是 NIO 操作的核心,本质上 NIO 操作就是缓冲区操作。

写操作是将缓冲区的数据排干,如将数据从缓冲区持久化到磁盘中。

读操作是将数据填充到缓冲区中,以便应用程序后续使用数据。

当然,我们这里说的缓冲区是指用户空间的缓冲区。

Java NIO 基础知识

.

简单分析下上图。应用程序发出读操作后,内核向磁盘控制器发送命令,要求磁盘返回相应数据,磁盘控制器通过 DMA 直接将数据发送到内核缓冲区。一旦内核缓冲区满了,内核即把数据拷贝到请求数据的进程指定的缓冲区中。

DMA: Direct Memory Access

Wikipedia:直接内存访问是计算机科学中的一种内存访问技术。它允许某些电脑内部的硬件子系统(电脑外设),可以独立地直接读写系统内存,而不需中央处理器(CPU)介入处理 。在同等程度的处理器负担下,DMA 是一种快速的数据传送方式。很多硬件的系统会使用 DMA,包含硬盘控制器、绘图显卡、网卡和声卡。

也就是说,磁盘控制器可以在不用 CPU 的帮助下就将数据从磁盘写到内存中,毕竟让 CPU 等待 IO 操作完成是一种浪费

很容易看出来,数据先到内核,然后再从内核复制到用户空间缓冲区的做法并不高效,下面简单说说为什么需要这么设计。

  • 首先,用户空间运行的代码是不可以直接访问硬件的,需要由内核空间来负责和硬件通讯,内核空间由操作系统控制。
  • 其次,磁盘存储的是固定大小的数据块,磁盘按照扇区来组织数据,而用户进程请求的一般都是任意大小的数据块,所以需要由内核来负责协调,内核会负责组装、拆解数据。

内核空间会对数据进行缓存和预读取,所以,如果用户进程需要的数据刚好在内核空间中,直接拷贝过来就可以了。如果内核空间没有用户进程需要的数据的话,需要挂起用户进程,等待数据准备好。

虚拟内存

这个概念大家都懂,这里就继续啰嗦一下了,虚拟内存是计算机系统内存管理的一种技术。前面说的缓存区操作看似简单,但是具体到底层细节,还是蛮复杂的。

下面的描述,我尽量保证准确,但是不会展开得太具体,因为虚拟内存还是蛮复杂的,要完全介绍清楚,恐怕需要很大的篇幅,如果读者对这方面的内容感兴趣的话,建议读者寻找更加专业全面的介绍资料,如《深入理解计算机系统》。

物理内存被组织成一个很大的数组,每个单元是一个字节大小,然后每个字节都有一个唯一的物理地址,这应该很好理解。

虚拟内存是对物理内存的抽象,它使得应用程序认为它自己拥有连续可用的内存(一个连续完整的地址空间),而实际上,应用程序得到的全部内存其实是一个假象,它通常会被分隔成多个物理内存碎片(后面说的页),还有部分暂时存储在外部磁盘存储器上,在需要时进行换入换出。

举个例子,在 32 位系统中,每个应用程序能访问到的内存是 4G(32 位系统的最大寻址空间 2^32),这里的 4G 就是虚拟内存,每个程序都以为自己拥有连续的 4G 空间的内存,即使我们的计算机只有 2G 的物理内存。也就是说,对于机器上同时运行的多个应用程序,每个程序都以为自己能得到连续的 4G 的内存。这中间就是使用了虚拟内存。

我们从概念上看,虚拟内存也被组织成一个很大的数组,每个单元也是一个字节大小,每个字节都有唯一的虚拟地址。它被存储于磁盘上,物理内存是它的缓存。

物理内存作为虚拟内存的缓存,当然不是以字节为单位进行组织的,那样效率太低了,它们之间是以页(page)进行缓存的。虚拟内存被分割为一个个虚拟页,物理内存也被分割为一个个物理页,这两个页的大小应该是一致的,通常是 4KB – 2MB。

举个例子,看下图:

Java NIO 基础知识

.

进程 1 现在有 8 个虚拟页,其中有 2 个虚拟页缓存在主存中,6 个还在磁盘上,需要的时候再读入主存中;进程 2 有 7 个虚拟页,其中 4 个缓存在主存中,3 个还在磁盘上。

在 CPU 读取内存数据的时候,给出的是虚拟地址,将一个虚拟地址转换为物理地址的任务我们称之为地址翻译。在主存中的查询表存放了虚拟地址到物理地址的映射关系,表的内容由操作系统维护。CPU 需要访问内存时,CPU 上有一个叫做内存管理单元的硬件会先去查询真实的物理地址,然后再到指定的物理地址读取数据。

上面说的那个查询表,我们称之为页表,虚拟内存系统通过页表来判断一个虚拟页是否已经缓存在了主存中。如果是,页表会负责到物理页的映射;如果不命中,也就是我们经常会见到的概念缺页,对应的英文是 page fault,系统首先判断这个虚拟页存放在磁盘的哪个位置,然后在物理内存中选择一个牺牲页,并将虚拟页从磁盘复制到内存中,替换这个牺牲页。

在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)。

下面,简单介绍下虚拟内存带来的好处。

SRAM缓存:表示位于 CPU 和主存之间的 L1、L2 和 L3 高速缓存。

DRAM缓存:表示虚拟内存系统的缓存,缓存虚拟页到主存中。

物理内存访问速度比高速缓存要慢 10 倍左右,而磁盘要比物理内存慢大约 100000 倍。所以,DRAM 的缓存不命中比 SRAM 缓存不命中代价要大得多,因为 DRAM 缓存一旦不命中,就需要到磁盘加载虚拟页。而 SRAM 缓存不命中,通常由 DRAM 的主存来服务。而从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约 100000 倍。

了解 Kafka 的读者应该知道,消息在磁盘中的顺序存储对于 Kafka 的性能至关重要。

结论就是,IO 的性能主要是由 DRAM 的缓存是否命中决定的。

内存映射文件

英文名是 Memory Mapped Files,相信大家也都听过这个概念,在许多对 IO 性能要求比较高的 java 应用中会使用到,它是操作系统提供的支持,后面我们在介绍 NIO Buffer 的时候会碰到的 MappedByteBuffer 就是用来支持这一特性的。

是什么:

我们可以认为内存映射文件是一类特殊的文件,我们的 Java 程序可以直接从内存中读取到文件的内容。它是通过将整个文件或文件的部分内容映射到内存页中实现的,操作系统会负责加载需要的页,所以它的速度是非常快的。

优势:

  • 一旦我们将数据写入到了内存映射文件,即使我们的 JVM 挂掉了,操作系统依然会帮助我们将这部分内存数据持久化到磁盘上。当然了,如果是断电的话,还是有可能会丢失数据的。
  • 另外,它比较适合于处理大文件,因为操作系统只会在我们需要的页不在内存中时才会去加载页数据,而用其处理大量的小文件反而可能会造成频繁的缺页。
  • 另一个重要的优势就是内存共享。我们可以在多个进程中同时使用同一个内存映射文件,也算是一种进程间协作的方式吧。想像下进程间的数据通讯平时我们一般采用 Socket 来请求,而内存共享至少可以带来 10 倍以上的性能提升。

我们还没有接触到 NIO 的 Buffer,下面就简单地示意一下:

import
 java.io.RandomAccessFile;import java.nio.MappedByteBuffer;import 
java.nio.channels.FileChannel;public class MemoryMappedFileInJava {  
private static int count = 10485760; //10 MB public static void 
main(String[] args) throws Exception { RandomAccessFile memoryMappedFile
 = new RandomAccessFile("largeFile.txt", "rw"); // 将文件映射到内存中,map 方法 
MappedByteBuffer out = 
memoryMappedFile.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, 
count); // 这一步的写操作其实是写到内存中,并不直接操作文件 for (int i = 0; i < count; i++) {
 out.put((byte) 'A'); } System.out.println("Writing to Memory Mapped 
File is completed"); // 这一步的读操作读的是内存 for (int i = 0; i < 10 ; i++) { 
System.out.print((char) out.get(i)); } System.out.println("Reading from 
Memory Mapped File is completed"); }}

我们需要注意的一点就是,用于加载内存映射文件的内存是堆外内存。

参考资料:Why use Memory Mapped File or MapppedByteBuffer in Java

分散/聚集 IO

scatter/gather IO,个人认为这个看上去很酷炫,实践中比较难使用到。

分散/聚集 IO(另一种说法是 vectored I/O 也就是向量 IO)是一种可以在单次操作中对多个缓冲区进行输入输出的方法,可以把多个缓冲区的数据写到单个数据流,也可以把单个数据流读到多个缓冲区中。

Java NIO 基础知识

.

Java NIO 基础知识

.

这个功能是操作系统提供的支持,Java NIO 包中已经给我们提供了操作接口 。这种操作可以提高一定的性能,因为一次操作相当于多次的线性操作,同时这也带来了原子性的支持,因为如果用多线程来操作的话,可能存在对同一文件的操作竞争。

非阻塞 IO

相信读者在很多地方都看到过说 NIO 其实不是代表 New IO,而是 Non-Blocking IO,我们这里不纠结这个。我想之所以会有这个说法,是因为在 Java 1.4 第一次推出 NIO 的时候,提供了 Non-Blocking IO 的支持。

在理解非阻塞 IO 前,我们首先要明白,它的对立面 阻塞模式为什么不好。

比如说 InputStream.read 这个方法,一旦某个线程调用这个方法,那么就将一直阻塞在这里,直到数据传输完毕,返回 -1,或者由于其他错误抛出了异常。

我们再拿 web 服务器来说,阻塞模式的话,每个网络连接进来,我们都需要开启一个线程来读取请求数据,然后到后端进行处理,处理结束后将数据写回网络连接,这整个流程需要一个独立的线程来做这件事。那就意味着,一旦请求数量多了以后,需要创建大量的线程,大量的线程必然带来创建线程、切换线程的开销,更重要的是,要给每个线程都分配一部分内存,会使得内存迅速被消耗殆尽。我们说多线程是性能利器,但是这就是过多的线程导致系统完全消化不了了。

通常,我们可以将 IO 分为两类:面向数据块(block-oriented)的 IO 和面向流(stream-oriented)的 IO。比如文件的读写就是面向数据块的,读取键盘输入或往网络中写入数据就是面向流的。

注意,这节混着用了流和通道这两个词,提出来这点是希望不会对读者产生困扰。

面向流的 IO 往往是比较慢的,如网络速度比较慢、需要一直等待用户新的输入等。

这个时候,我们可以用一个线程来处理多个流,让这个线程负责一直轮询这些流的状态,当有的流有数据到来后,进行相应处理,也可以将数据交给其他子线程来处理,这个线程继续轮询。

问题来了,不断地轮询也会带来资源浪费呀,尤其是当一个线程需要轮询很多的数据流的时候。

现代操作系统提供了一个叫做 readiness selection 的功能,我们让操作系统来监控一个集合中的所有的通道,当有的通道数据准备好了以后,就可以直接到这个通道获取数据。当然,操作系统不会通知我们,但是我们去问操作系统的时候,它会知道告诉我们通道 N 已经准备好了,而不需要自己去轮询(后面我们会看到,还要自己轮询的 select 和 poll)。

后面我们在介绍 Java NIO 的时候会说到 Selector,对应类 java.nio.channels.Selector,这个就是 java 对 readiness selection 的支持。这样一来,我们的一个线程就可以更加高效地管理多个通道了。

Java NIO 基础知识

.

上面这张图我想大家也都可能看过,就是用一个 Selector 来管理多个 Channel,实现了一个线程管理多个连接。说到底,其实就是解决了我们前面说的阻塞模式下线程创建过多的问题。

在 Java 中,继承自 SelectableChannel 的子类就是实现了非阻塞 IO 的,我们可以看到主要有 socket IO 中的 DatagramChannel 和 SocketChannel,而 FileChannel 并没有继承它。所以,文件 IO 是不支持非阻塞模式的。

在系统实现上,POSIX 提供了 select 和 poll 两种方式。它们两个最大的区别在于持有句柄的数量上,select 最多只支持到 FD_SETSIZE(一般常见的是 1024),显然很多场景都会超过这个数量。而 poll 我们想创建多少就创建多少。它们都有一个共同的缺点,那就是当有任务完成后,我们只能知道有几个任务完成了,而不知道具体是哪几个句柄,所以还需要进行一次扫描。

正是由于 select 和 poll 的不足,所以催生了以下几个实现。BSD& OS X 中的 kqueue,Solaris 中的 /dev/poll,还有 Linux 中的 epoll。

Windows 没有提供额外的实现,只能使用 select。

在不同的操作系统上,JDK 分别选择相应的系统支持的非阻塞实现方式。

异步 IO

我们知道 Java 1.4 引入了 New IO,从 Java 7 开始,就不再是 New IO 了,而是 More New IO 来临了,我们也称之为 NIO2。

Java7 在 NIO 上带来的最大的变化应该就属引入了 Asynchronous IO(异步 IO)。本来吧,异步 IO 早就提上日程了,可是大佬们没有时间完成,所以才一直拖到了 java 7 的。废话不多说,简单来看看异步 IO 是什么。

要说异步 IO 是什么,当然还得从 Non-Blocking IO 没有解决的问题入手。非阻塞 IO 很好用,它解决了阻塞式 IO 的等待问题,但是它的缺点是需要我们去轮询才能得到结果。

而异步 IO 可以解决这个问题,线程只需要初始化一下,提供一个回调方法,然后就可以干其他的事情了。当数据准备好以后,系统会负责调用回调方法。

异步 IO 最主要的特点就是回调,其实回调在我们日常的代码中也是非常常见的。

最简单的方法就是设计一个线程池,池中的线程负责完成一个个阻塞式的操作,一旦一个操作完成,那么就调用回调方法。比如 web 服务器中,我们前面已经说过不能每来一个请求就新开一个线程,我们可以设计一个线程池,在线程池外用一个线程来接收请求,然后将要完成的任务交给线程池中的线程并提供一个回调方法,这样这个线程就可以去干其他的事情了,如继续处理其他的请求。等任务完成后,池中的线程就可以调用回调方法进行通知了。

另外一种方式就是自己不设计线程池,让操作系统帮我们实现。流程也是基本一样的,提供给操作系统回调方法,然后就可以干其他事情了,等操作完成后,操作系统会负责回调。这种方式的缺点就是依赖于操作系统的具体实现,不过也有它的一些优势。

首先,我们自己设计处理任务的线程池的话,我们需要掌握好线程池的大小,不能太大,也不能太小,这往往需要凭我们的经验;其次,让操作系统来做这件事情的话,操作系统可以在一些场景中帮助我们优化性能,如文件 IO 过程中帮助更快找到需要的数据。

操作系统对异步 IO 的实现也有很多种方式,主要有以下 3 中:

  1. Linux AIO:由 Linux 内核提供支持
  2. POSIX AIO:Linux,Mac OS X(现在该叫 Mac OS 了),BSD,solaris 等都支持,在 Linux 中是通过 glibc 来提供支持的。
  3. Windows:提供了一个叫做 completion ports 的机制。

这篇文章 asynchronous disk I/O 的作者表示,在类 unix 的几个系统实现中,限制太多,实现的质量太差,还不如自己用线程池进行管理异步操作。

而 Windows 系统下提供的异步 IO 的实现方式有点不一样。它首先让线程池中的线程去自旋调用 GetQueuedCompletionStatus.aspx) 方法,判断是否就绪。然后,让任务跑起来,但是需要提供特定的参数来告诉执行任务的线程,让线程执行完成后将结果通知到线程池中。一旦任务完成,操作系统会将线程池中阻塞在 GetQueuedCompletionStatus 方法的线程唤醒,让其进行后续的结果处理。

Windows 智能地唤醒那些执行 GetQueuedCompletionStatus 方法的线程,以让线程池中活跃的线程数始终保持在合理的水平。这样就不至于创建太多的线程,降低线程切换的开销。

Java 7 在异步 IO 的实现上,如果是 Linux 或者其他类 Unix 系统上,是采用自建线程池实现的,如果是 Windows 系统上,是采用系统提供的 completion ports 来实现的。

所以,在非阻塞 IO 和异步 IO 之间,我们应该怎么选择呢?

如果是文件 IO,我们没得选,只能选择异步 IO。

如果是 Socket IO,在类 unix 系统下我们应该选择使用非阻塞 IO,Netty 是基于非阻塞模式的;在 Windows 中我们应该使用异步 IO。

当然了,Java 的存在就是为了实现平台无关化,所以,其实不需要我们选择,了解这些权当让自己涨点知识吧。

总结

和其他几篇文章一样,也没什么好总结的,要说的都在文中了,希望读者能学到点东西吧。

如果哪里说得不对了,我想也是正常的,我这些年写的都是 Java,对于底层了解得愈发的少了,所以如果读者发现有什么不合理的内容,非常希望读者可以提出来。

Linux下同步工具inotify+rsync使用详解

1. rsync

1.1 什么是rsync

rsync是一个远程数据同步工具,可通过LAN/WAN快速同步多台主机间的文件。它使用所谓的“Rsync演算法”来使本地和远程两个主机之间的文件达到同步,这个算法只传送两个文件的不同部分,而不是每次都整份传送,因此速度相当快。所以通常可以作为备份工具来使用。

运行Rsync server的机器也叫backup server,一个Rsync server可同时备份多个client的数据;也可以多个Rsync server备份一个client的数据。Rsync可以搭配ssh甚至使用daemon模式。Rsync server会打开一个873的服务通道(port),等待对方rsync连接。连接时,Rsync server会检查口令是否相符,若通过口令查核,则可以开始进行文件传输。第一次连通完成时,会把整份文件传输一次,下一次就只传送二个文件之间不同的部份。

基本特点:

  1. 可以镜像保存整个目录树和文件系统;
  2. 可以很容易做到保持原来文件的权限、时间、软硬链接等;
  3. 无须特殊权限即可安装;
  4. 优化的流程,文件传输效率高;
  5. 可以使用rcp、ssh等方式来传输文件,当然也可以通过直接的socket连接;
  6. 支持匿名传输。

命令语法:
rsync的命令格式可以为以下六种:
rsync [OPTION]… SRC DEST
rsync [OPTION]… SRC [USER@]HOST:DEST
rsync [OPTION]… [USER@]HOST:SRC DEST
rsync [OPTION]… [USER@]HOST::SRC DEST
rsync [OPTION]… SRC [USER@]HOST::DEST
rsync [OPTION]… rsync://[USER@]HOST[:PORT]/SRC [DEST]

对应于以上六种命令格式,我们可以总结rsync有2种不同的工作模式:

  • shell模式:使用远程shell程序(如ssh或rsh)进行连接。当源路径或目的路径的主机名后面包含一个冒号分隔符时使用这种模式,rsync安装完成后就可以直接使用了,无所谓启动。(目前没有尝试过这个方法)
  • daemon模式:使用TCP直接连接rsync daemon。当源路径或目的路径的主机名后面包含两个冒号,或使用rsync://URL时使用这种模式,无需远程shell,但必须在一台机器上启动rsync daemon,默认端口873,这里可以通过rsync --daemon使用独立进程的方式,或者通过xinetd超级进程来管理rsync后台进程。

当rsync作为daemon运行时,它需要一个用户身份。如果你希望启用chroot,则必须以root的身份来运行daemon,监听端口,或设定文件属主;如果不启用chroot,也可以不使用root用户来运行daemon,但该用户必须对相应的模块拥有读写数据、日志和lock file的权限。当rsync以daemon模式运行时,它还需要一个配置文件——rsyncd.conf。修改这个配置后不必重启rsync daemon,因为每一次的client连接都会去重新读取该文件。

我们一般把DEST远程服务器端成为rsync Server,运行rsync命令的一端SRC称为Client。

安装:
rsync在CentOS6上默认已经安装,如果没有则可以使用yum install rsync -y,服务端和客户端是同一个安装包。

# rsync -h

1.2 同步测试

关于rsync命令的诸多选项说明,见另外一篇文章rsync与inotifywait命令和配置选项说明

1.2.1 本机文件夹同步

# rsync -auvrtzopgP –progress /root/ /tmp/rsync_bak/

会看到从/root/传输文件到/tmp/rsync_bak/的列表和速率,再运行一次会看到sending incremental file list下没有复制的内容,可以在/root/下touch某一个文件再运行看到只同步了修改过的文件。

上面需要考虑以下问题:

  • 删除/root/下的文件不会同步删除/tmp/rsync_bak,除非加入--delete选项
  • 文件访问时间等属性、读写等权限、文件内容等有任何变动,都会被认为修改
  • 目标目录下如果文件比源目录还新,则不会同步
  • 源路径的最后是否有斜杠有不同的含义:有斜杠,只是复制目录中的文件;没有斜杠的话,不但要复制目录中的文件,还要复制目录本身

1.3 同步到远程服务器

在服务器间rsync传输文件,需要有一个是开着rsync的服务,而这一服务需要两个配置文件,说明当前运行的用户名和用户组,这个用户名和用户组在改变文件权限和相关内容的时候有用,否则有时候会出现提示权限问题。配置文件也说明了模块、模块化管理服务的安全性,每个模块的名称都是自己定义的,可以添加用户名密码验证,也可以验证IP,设置目录是否可写等,不同模块用于同步不同需求的目录。

1.3.1 服务端配置文件

/etc/rsyncd.conf:

#2014-12-11 by Sean
uid=root
gid=root
use chroot=no
max connections=10
timeout=600
strict modes=yes
port=873
pid file=/var/run/rsyncd.pid
lock file=/var/run/rsyncd.lock
log file=/var/log/rsyncd.log
[module_test]
path=/tmp/rsync_bak2
comment=rsync test logs
auth users=sean
uid=sean
gid=sean
secrets file=/etc/rsyncd.secrets
read only=no
list=no
hosts allow=172.29.88.204
hosts deny=0.0.0.0/32

这里配置socket方式传输文件,端口873,[module_test]开始定义一个模块,指定要同步的目录(接收)path,授权用户,密码文件,允许哪台服务器IP同步(发送)等。关于配置文件中选项的详细说明依然参考rsync与inotifywait命令和配置选项说明

经测试,上述配置文件每行后面不能使用#来来注释

/etc/rsyncd.secrets:

sean:passw0rd

一行一个用户,用户名:密码。请注意这里的用户名和密码与操作系统的用户名密码无关,可以随意指定,与/etc/rsyncd.conf中的auth users对应。

修改权限:chmod 600 /etc/rsyncd.d/rsync_server.pwd

1.3.2 服务器启动rsync后台服务

修改/etc/xinetd.d/rsync文件,disable 改为 no

# default: off
# description: The rsync server is a good addition to an ftp server, as it \
# allows crc checksumming etc.
service rsync
{
4disable = no
4flags = IPv6
4socket_type = stream
4wait = no
4user = root
4server = /usr/bin/rsync
4server_args = –daemon
4log_on_failure += USERID
}

执行service xinetd restart会一起重启rsync后台进程,默认使用配置文件/etc/rsyncd.conf。也可以使用/usr/bin/rsync --daemon --config=/etc/rsyncd.conf

为了以防rsync写入过多的无用日志到/var/log/message(容易塞满从而错过重要的信息),建议注释掉/etc/xinetd.conf的success:

# log_on_success = PID HOST DURATION EXIT

如果使用了防火墙,要添加允许IP到873端口的规则。

# iptables -A INPUT -p tcp -m state –state NEW -m tcp –dport 873 -j ACCEPT
# iptables -L 查看一下防火墙是不是打开了 873端口
# netstat -anp|grep 873

建议关闭selinux,可能会由于强访问控制导致同步报错。

1.3.3 客户端测试同步

单向同步时,客户端只需要一个包含密码的文件。
/etc/rsync_client.pwd:

passw0rd

chmod 600 /etc/rsync_client.pwd

命令:
将本地/root/目录同步到远程172.29.88.223的/tmp/rsync_bak2目录(module_test指定):

/usr/bin/rsync -auvrtzopgP –progress –password-file=/etc/rsync_client.pwd /root/ sean@172.29.88.223::module_test

当然你也可以将远程的/tmp/rsync_bak2目录同步到本地目录/root/tmp:

/usr/bin/rsync -auvrtzopgP –progress –password-file=/etc/rsync_client.pwd sean@172.29.88.223::module_test /root/

从上面两个命令可以看到,其实这里的服务器与客户端的概念是很模糊的,rsync daemon都运行在远程172.29.88.223上,第一条命令是本地主动推送目录到远程,远程服务器是用来备份的;第二条命令是本地主动向远程索取文件,本地服务器用来备份,也可以认为是本地服务器恢复的一个过程。

1.4 rsync不足

与传统的cp、tar备份方式相比,rsync具有安全性高、备份迅速、支持增量备份等优点,通过rsync可以解决对实时性要求不高的数据备份需求,例如定期的备份文件服务器数据到远端服务器,对本地磁盘定期做数据镜像等。

随着应用系统规模的不断扩大,对数据的安全性和可靠性也提出的更好的要求,rsync在高端业务系统中也逐渐暴露出了很多不足,首先,rsync同步数据时,需要扫描所有文件后进行比对,进行差量传输。如果文件数量达到了百万甚至千万量级,扫描所有文件将是非常耗时的。而且正在发生变化的往往是其中很少的一部分,这是非常低效的方式。其次,rsync不能实时的去监测、同步数据,虽然它可以通过crontab方式进行触发同步,但是两次触发动作一定会有时间差,这样就导致了服务端和客户端数据可能出现不一致,无法在应用故障时完全的恢复数据。基于以上原因,rsync+inotify组合出现了!

2. inotify-tools

2.1 什么是inotify

inotify是一种强大的、细粒度的、异步的文件系统事件监控机制,Linux内核从2.6.13开始引入,允许监控程序打开一个独立文件描述符,并针对事件集监控一个或者多个文件,例如打开、关闭、移动/重命名、删除、创建或者改变属性。

CentOS6自然已经支持:
使用ll /proc/sys/fs/inotify命令,是否有以下三条信息输出,如果没有表示不支持。

total 0
-rw-r–r– 1 root root 0 Dec 11 15:23 max_queued_events
-rw-r–r– 1 root root 0 Dec 11 15:23 max_user_instances
-rw-r–r– 1 root root 0 Dec 11 15:23 max_user_watches
  • /proc/sys/fs/inotify/max_queued_evnets表示调用inotify_init时分配给inotify instance中可排队的event的数目的最大值,超出这个值的事件被丢弃,但会触发IN_Q_OVERFLOW事件。
  • /proc/sys/fs/inotify/max_user_instances表示每一个real user ID可创建的inotify instatnces的数量上限。
  • /proc/sys/fs/inotify/max_user_watches表示每个inotify instatnces可监控的最大目录数量。如果监控的文件数目巨大,需要根据情况,适当增加此值的大小。

inotify-tools:

inotify-tools是为linux下inotify文件监控工具提供的一套C的开发接口库函数,同时还提供了一系列的命令行工具,这些工具可以用来监控文件系统的事件。 inotify-tools是用c编写的,除了要求内核支持inotify外,不依赖于其他。inotify-tools提供两种工具,一是inotifywait,它是用来监控文件或目录的变化,二是inotifywatch,它是用来统计文件系统访问的次数。

下载inotify-tools-3.14-1.el6.x86_64.rpm,通过rpm包安装:

# rpm -ivh /apps/crm/soft_src/inotify-tools-3.14-1.el6.x86_64.rpm
warning: /apps/crm/soft_src/inotify-tools-3.14-1.el6.x86_64.rpm: Header V3 DSA/SHA1 Signature, key ID 4026433f: NOKEY
Preparing… ########################################### [100%]
1:inotify-tools ########################################### [100%]
# rpm -qa|grep inotify
inotify-tools-3.14-1.el5.x86_64

2.2 inotifywait使用示例

监控/root/tmp目录文件的变化:

/usr/bin/inotifywait -mrq –timefmt ‘%Y/%m/%d%H:%M:%S‘ –format ‘%T %w %f‘ \
-e modify,delete,create,move,attrib /root/tmp/

上面的命令表示,持续监听/root/tmp目录及其子目录的文件变化,监听事件包括文件被修改、删除、创建、移动、属性更改,显示到屏幕。执行完上面的命令后,在/root/tmp下创建或修改文件都会有信息输出:

2014/12/11-15:40:04 /root/tmp/ new.txt
2014/12/11-15:40:22 /root/tmp/ .new.txt.swp
2014/12/11-15:40:22 /root/tmp/ .new.txt.swx
2014/12/11-15:40:22 /root/tmp/ .new.txt.swx
2014/12/11-15:40:22 /root/tmp/ .new.txt.swp
2014/12/11-15:40:22 /root/tmp/ .new.txt.swp
2014/12/11-15:40:23 /root/tmp/ .new.txt.swp
2014/12/11-15:40:31 /root/tmp/ .new.txt.swp
2014/12/11-15:40:32 /root/tmp/ 4913
2014/12/11-15:40:32 /root/tmp/ 4913
2014/12/11-15:40:32 /root/tmp/ 4913
2014/12/11-15:40:32 /root/tmp/ new.txt
2014/12/11-15:40:32 /root/tmp/ new.txt~
2014/12/11-15:40:32 /root/tmp/ new.txt

3. rsync组合inotify-tools完成实时同步

这一步的核心其实就是在客户端创建一个脚本rsync.sh,适用inotifywait监控本地目录的变化,触发rsync将变化的文件传输到远程备份服务器上。为了更接近实战,我们要求一部分子目录不同步,如/root/tmp/log和临时文件。

3.1 创建排除在外不同步的文件列表

排除不需要同步的文件或目录有两种做法,第一种是inotify监控整个目录,在rsync中加入排除选项,简单;第二种是inotify排除部分不监控的目录,同时rsync中也要加入排除选项,可以减少不必要的网络带宽和CPU消耗。我们选择第二种。

3.1.1 inotifywait排除

这个操作在客户端进行,假设/tmp/src/mail/2014/以及/tmp/src/mail/2015/cache/目录下的所有文件不用同步,所以不需要监控,/tmp/src/下的其他文件和目录都同步。(其实对于打开的临时文件,可以不监听modify时间而改成监听close_write

inotifywait排除监控目录有--exclude <pattern>--fromfile <file>两种格式,并且可以同时使用,但主要前者可以用正则,而后者只能是具体的目录或文件。

# vi /etc/inotify_exclude.lst:
/tmp/src/pdf
@/tmp/src/2014

使用fromfile格式只能用绝对路径,不能使用诸如*正则表达式去匹配,@表示排除。

如果要排除的格式比较复杂,必须使用正则,那只能在inotifywait中加入选项,如--exclude '(.*/*\.log|.*/*\.swp)$|^/tmp/src/mail/(2014|201.*/cache.*)',表示排除/tmp/src/mail/以下的2014目录,和所有201*目录下的带cache的文件或目录,以及/tmp/src目录下所有的以.log或.swp结尾的文件。

3.1.2 rsync排除

使用inotifywait排除监控目录的情况下,必须同时使用rsync排除对应的目录,否则只要有触发同步操作,必然会导致不该同步的目录也会同步。与inotifywait类似,rsync的同步也有--exclude--exclude-from两种写法。

个人还是习惯将要排除同步的目录卸载单独的文件列表里,便于管理。使用--include-from=FILE时,排除文件列表用绝对路径,但FILE里面的内容请用相对路径,如:
/etc/rsyncd.d/rsync_exclude.lst

mail/2014/
mail/201*/201*/201*/.??*
mail??*
src/*.html*
src/js/
src/ext3/
src/2014/20140[1-9]/
src/201*/201*/201*/.??*
membermail/
membermail??*
membermail/201*/201*/201*/.??*

排除同步的内容包括,mail下的2014目录,类似2015/201501/20150101/下的临时或隐藏文件,等。

3.2 客户端同步到远程的脚本rsync.sh

下面是一个完整的同步脚本,请根据需要进行裁剪,rsync.sh

#rsync auto sync script with inotify
#2014-12-11 Sean
#variables
current_date=$(date +%Y%m%d_%H%M%S)
source_path=/tmp/src/
log_file=/var/log/rsync_client.log
#rsync
rsync_server=172.29.88.223
rsync_user=sean
rsync_pwd=/etc/rsync_client.pwd
rsync_module=module_test
INOTIFY_EXCLUDE=‘(.*/*\.log|.*/*\.swp)$|^/tmp/src/mail/(2014|20.*/.*che.*)’
RSYNC_EXCLUDE=‘/etc/rsyncd.d/rsync_exclude.lst’
#rsync client pwd check
if [ ! -e ${rsync_pwd} ];then
echo -e “rsync client passwod file ${rsync_pwd} does not exist!”
exit 0
fi
#inotify_function
inotify_fun(){
/usr/bin/inotifywait -mrq –timefmt ‘%Y/%m/%d-%H:%M:%S’ –format ‘%T %w %f’ \
–exclude ${INOTIFY_EXCLUDE} -e modify,delete,create,move,attrib ${source_path} \
| while read file
do
/usr/bin/rsync -auvrtzopgP –exclude-from=${RSYNC_EXCLUDE} –progress –bwlimit=200 –password-file=${rsync_pwd} ${source_path} ${rsync_user}@${rsync_server}::${rsync_module}
done
}
#inotify log
inotify_fun >> ${log_file} 2>&1 &

--bwlimit=200用于限制传输速率最大200kb,因为在实际应用中发现如果不做速率限制,会导致巨大的CPU消耗。

在客户端运行脚本# ./rsync.sh即可实时同步目录。

疑问
对于rsync的同步海量存在一个疑问,假如我的文件数很多即使在排除不监控和不同步目录的情况下依然有10万个文件,仅文件列表就达10M,那么岂不是每一次有文件产生或修改都会触发同步,很容易导致大部分情况下在传输文件列表和进行列表的比对,仅同步一个小文件而使用的网络带宽和CPU代价很高,特别是网络状况不佳时,上一次的列表还未传送完,又有新的文件产生触发发送文件列表。不知道rsync内部有没有这样的处理?

其他功能:双向同步sersync2实时同步多远程服务器

参考