前言

本篇介绍Stream流List和Map互转，同时在转换过程中遇到的问题分析。

一、Map转List

1.1 分析

按照默认顺序

1

java复制代码mapToList.entrySet().stream().map(a -> new User(a.getKey(), a.getValue())).collect(Collectors.toList());

根据key排序

1

java复制代码mapToList.entrySet().stream().sorted(Comparator.comparing(a -> a.getKey())).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());

根据key排序

1

java复制代码mapToList.entrySet().stream().sorted(Map.Entry.comparingByKey()).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());

根据key倒序排序

1

java复制代码mapToList.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.reverseOrder())).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());

根据value排序

1

java复制代码mapToList.entrySet().stream().sorted(Comparator.comparing(Map.Entry::getValue)).map(a -> new User(a.getKey(), a.getValue())).collect(Collectors.toList());

根据value倒序排序

1

java复制代码mapToList.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());

1.2 完整代码

实体类

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

java复制代码/**
 * @author lilinchao
 * @date 2021/7/28
 * @description 1.0
 **/
public class User {
    private Integer id;
    private String name;

    public User() {
    }

    public User(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

Map转List代码

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

java复制代码import java.util.*;
import java.util.stream.Collectors;

/**
 * @author lilinchao
 * @date 2021/7/28
 * @description 1.0
 **/
public class StreamMapToList {

    /**
     * 数据初始化
     */
    private static final Map<Integer, String> mapToList;
    static
    {
        mapToList = new HashMap<Integer, String>();
        mapToList.put(1003, "Thymee");
        mapToList.put(1001, "Leefs");
        mapToList.put(1002, "Jeyoo");
    }
    public static void main(String ages[]){
        List<User> userList = defaultOrder();
        System.out.println(userList);
        List<User> userList2and = orderByKeyMethodOne();
        System.out.println(userList2and);
        List<User> userList3and = orderByKeyMethodTwo();
        System.out.println(userList3and);
        List<User> userList4and = reverseOrderByKey();
        System.out.println(userList4and);
        List<User> userList5and = orderByValue();
        System.out.println(userList5and);
        List<User> userList6and = reverseOrderByValue();
        System.out.println(userList6and);
    }

    /**
     * 按照默认顺序
     */
    public static List<User> defaultOrder(){
        List<User> userList = mapToList.entrySet().stream().map(a -> new User(a.getKey(), a.getValue())).collect(Collectors.toList());
        return userList;
    }
    /**
     *根据key排序，方法1
     */
    public static List<User> orderByKeyMethodOne(){
        List<User> userList = mapToList.entrySet().stream().sorted(Comparator.comparing(a -> a.getKey())).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());
        return userList;
    }
    /**
     *根据key排序，方法2
     */
    public static List<User> orderByKeyMethodTwo(){
        List<User> userList = mapToList.entrySet().stream().sorted(Map.Entry.comparingByKey()).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());
        return userList;
    }
    /**
     *根据key倒序排序
     */
    public static List<User> reverseOrderByKey(){
        List<User> userList = mapToList.entrySet().stream().sorted(Map.Entry.comparingByKey(Comparator.reverseOrder())).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());
        return userList;
    }
    /**
     * 根据value排序
     */
    public static List<User> orderByValue(){
        List<User> userList = mapToList.entrySet().stream().sorted(Comparator.comparing(Map.Entry::getValue)).map(a -> new User(a.getKey(), a.getValue())).collect(Collectors.toList());
        return userList;
    }
    /**
     *根据value倒序排序
     */
    public static List<User> reverseOrderByValue(){
        List<User> userList = mapToList.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).map(a -> new User(a.getKey(),a.getValue())).collect(Collectors.toList());
        return userList;
    }
}

运行结果

1
2
3
4
5
6

json复制代码[User{id=1001, name='Leefs'}, User{id=1002, name='Jeyoo'}, User{id=1003, name='Thymee'}]
[User{id=1001, name='Leefs'}, User{id=1002, name='Jeyoo'}, User{id=1003, name='Thymee'}]
[User{id=1001, name='Leefs'}, User{id=1002, name='Jeyoo'}, User{id=1003, name='Thymee'}]
[User{id=1003, name='Thymee'}, User{id=1002, name='Jeyoo'}, User{id=1001, name='Leefs'}]
[User{id=1002, name='Jeyoo'}, User{id=1001, name='Leefs'}, User{id=1003, name='Thymee'}]
[User{id=1003, name='Thymee'}, User{id=1001, name='Leefs'}, User{id=1002, name='Jeyoo'}]

二、List转Map

2.1 分析

指定key-value，value是对象中的某个属性值

1

java复制代码userList.stream().collect(Collectors.toMap(User::getId, User::getName));

指定key-value，value是对象本身

User->User 是一个返回本身的lambda表达式

1

java复制代码userList.stream().collect(Collectors.toMap(User::getId, User->User));

指定key-value，value是对象本身

Function.identity()是简洁写法，也是返回对象本身

1

java复制代码userList.stream().collect(Collectors.toMap(User::getId, Function.identity()));

指定key-value,key 冲突的解决办法

(key1,key2)->key2:第二个key覆盖第一个key
(key1,key2)->key1:保留第一个key

1

java复制代码userList.stream().collect(Collectors.toMap(User::getId, Function.identity(),(key1,key2)->key2));

2.2 完整代码

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

java复制代码import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @author lilinchao
 * @date 2021/7/28
 * @description 1.0
 **/
public class StreamListToMap {

    private static final List<User> userList;
    static
    {
        userList = Arrays.asList(
                new User(1003,"keko"),
                new User(1001,"jeek"),
                new User(1002,"mack")
        );
    }

    public static void main(String ages[]){

        Map<Integer, String> map = method01();
        System.out.println(map);
        Map<Integer, User> map2and = method02();
        System.out.println(map2and);
        Map<Integer, User> map3and = method03();
        System.out.println(map3and);
        Map<Integer, User> map4and = method04();
        System.out.println(map4and);
    }

    /**
     * 指定key-value，value是对象中的某个属性值
     */
    public static Map<Integer,String> method01(){
        Map<Integer, String> userMap = userList.stream().collect(Collectors.toMap(User::getId, User::getName));
        return userMap;
    }
    /**
     *指定key-value，value是对象本身，User->User 是一个返回本身的lambda表达式
     */
    public static Map<Integer,User> method02(){
        Map<Integer, User> userMap = userList.stream().collect(Collectors.toMap(User::getId, User->User));
        return userMap;
    }
    /**
     * 指定key-value，value是对象本身，Function.identity()是简洁写法，也是返回对象本身
     */
    public static Map<Integer,User> method03(){
        Map<Integer, User> userMap = userList.stream().collect(Collectors.toMap(User::getId, Function.identity()));
        return userMap;
    }
    /**
     * 指定key-value,key 冲突的解决办法
     * (key1,key2)->key2:第二个key覆盖第一个key
     * (key1,key2)->key1:保留第一个key
     */
    public static Map<Integer,User> method04(){
        Map<Integer, User> userMap = userList.stream().collect(Collectors.toMap(User::getId, Function.identity(),(key1,key2)->key2));
        return userMap;
    }
}

运行结果

1
2
3
4

json复制代码{1001=jeek, 1002=mack, 1003=keko}
{1001=User{id=1001, name='jeek'}, 1002=User{id=1002, name='mack'}, 1003=User{id=1003, name='keko'}}
{1001=User{id=1001, name='jeek'}, 1002=User{id=1002, name='mack'}, 1003=User{id=1003, name='keko'}}
{1001=User{id=1001, name='jeek'}, 1002=User{id=1002, name='mack'}, 1003=User{id=1003, name='keko'}}

三、List转Map常见问题

3.1 常见问题

问题一

报错Duplicate key xxxx

该问题是因为在生成Map集合时key值重复造成的

解决方案

1. 后面的value覆盖前面的value

1

java复制代码userList.stream().collect(Collectors.toMap(User::getId, User::getName, (key1, key2) -> key2));

也可以保留前面的value,将key2换成key1即可

2. value进行拼接

1

java复制代码userList.stream().collect(Collectors.toMap(User::getId, User::getName, (key1, key2) -> key1+","+key2));

3. key重复时，返回集合

1
2
3
4
5
6
7
8
9
10

java复制代码userList2and.stream().collect(Collectors.toMap(User::getId, p -> {
                    List<String> getNameList = new ArrayList<>();
                    getNameList.add(p.getName());
                    return getNameList;
                },
                (List<String> value1, List<String> value2) -> {
                    value1.addAll(value2);
                    return value1;
                }
        ));

问题二

报错：Exception in thread "main" java.lang.NullPointerException

该问题是因为在存入Map集合时value值为null

解决方案

在转换流中加上判空，即便value为空,依旧输出。(与上面方法三相同)

3.2 完整代码

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

java复制代码import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author lilinchao
 * @date 2021/7/28
 * @description 1.0
 **/
public class StreamListToMapAnalyze {

    private static final List<User> userList;
    private static final List<User> userList2and;
    static
    {
        //重复的key
        userList = Arrays.asList(
                new User(1003,"keko"),
                new User(1001,"jeek"),
                new User(1001,"teek"),
                new User(1002,"mack")
        );
        //重复的key,value为null
        userList2and = Arrays.asList(
                new User(1003,"keko"),
                new User(1001,"jeek"),
                new User(1001,"teek"),
                new User(1002,null)
        );
    }

    public static void main(String ages[]){
        Map<Integer, String> map = keyRepeatMethod01();
        System.out.println(map);
        Map<Integer, String> map2and = keyRepeatMethod02();
        System.out.println(map2and);
        Map<Integer,List<String>> map3and = keyRepeatMethod03();
        System.out.println(map3and);
    }

    /**
     * key重复时，后面的value覆盖前面的value
     */
    public static Map<Integer,String> keyRepeatMethod01(){
        Map<Integer, String> userMap = userList.stream().collect(Collectors.toMap(User::getId, User::getName, (key1, key2) -> key2));
        return userMap;
    }
    /**
     * key重复时，value进行拼接
     */
    public static Map<Integer,String> keyRepeatMethod02(){
        Map<Integer, String> userMap = userList.stream().collect(Collectors.toMap(User::getId, User::getName, (key1, key2) -> key1+","+key2));
        return userMap;
    }
    /**
     * key重复时，返回集合
     * value值为空，在转换流中加上判空，即便value为空,依旧输出
     */
    public static Map<Integer,List<String>> keyRepeatMethod03(){
        Map<Integer, List<String>> userListMap = userList2and.stream().collect(Collectors.toMap(User::getId, p -> {
                    List<String> getNameList = new ArrayList<>();
                    getNameList.add(p.getName());
                    return getNameList;
                },
                (List<String> value1, List<String> value2) -> {
                    value1.addAll(value2);
                    return value1;
                }
        ));
        return userListMap;
    }
}

运行结果

1
2
3

json复制代码{1001=teek, 1002=mack, 1003=keko}
{1001=jeek,teek, 1002=mack, 1003=keko}
{1001=[jeek, teek], 1002=[null], 1003=[keko]}

附：参考文章链接

www.cnblogs.com/fugitive/p/…

www.jb51.net/article/170…

本文转载自: 掘金

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

2021年，Linux更加受欢迎了，今天就和大家分享4个可以在Linux上运行的开源服务器。

1、Samba

Samba是种自由软件，用来让UNIX系列的操作系统与微软Windows操作系统的SMB/CIFS(Server Message Block/Common Internet File System)网络协定做连结。尽管大多都是低级代码，许多用户从来不会刻意使用它，但它的重要性不可低估。该项目可以确保Linux和Windows计算机轻松在同一网络运行，换句话说，Samba使通过本地网络共享文件变得很容易，而不管使用的是什么平台。

在KDE Plasma桌面，你可以右键单击任何目录选项并选择Properties。在属性对话框中，单击共享标签，选择“与Samba共享(Microsoft Windows)”。

)

就像这样，已经为本地网络上的用户打开了一个只读访问目录。这意味着，当你在家时，你家里使用同一WiFi网络的任何人都可以访问这个文件夹，当然，要访问它，其他用户需要知道在哪里找到它。计算机的路径可以表示为IP地址，也可以表示为主机名（取决于你的网络配置）。

项目地址：samba.org/

2、Snapdrop

Snapdrop 是一款开源的在线服务，只需要同时打开一个网页，就能传输文件了，不会在任何服务器端保存数据，P2P传输，基于浏览器的WebRTC接口，不支持IE和Safari，手机端与电脑端均可使用。

)

WebRTC支持通过web浏览器进行点对点连接，这意味着同一网络上的两个用户可以通过Snapdrop导航就能找到对方，然后直接相互通信，而不需要通过外部服务器。

一旦两个或多个客户端与Snapdrop服务取得联系，用户就可以通过本地网络来回交换文件和聊天消息。传输速度很快，你的数据也会留在本地。

项目地址：github.com/RobinLinus/…

3、VLC

流媒体服务比以往任何时候都更常见，但我对音乐和电影的品味不同寻常，所以那些典型的服务似乎很少有我想要的东西。幸运的是，只要把我的大媒体驱动器连接到电脑上，我就可以很容易地把我自己的内容传送出去，例如，当我想在电脑显示器以外的屏幕上看电影时，我可以在网络上播放电影文件，并通过任何可以接收HTTP的应用程序播放，无论该应用程序在我的电视、游戏机或手机上。

)

VLC 是一款自由、开源的跨平台多媒体播放器及框架，可播放大多数多媒体文件，以及 DVD、音频 CD、VCD 及各类流媒体协议。

项目地址：www.videolan.org/index.html

4、PulseAudio

我最喜欢的现代Linux功能之一是PulseAudio。Pulse为Linux上的音频提供了惊人的灵活性，包括自动发现本地网络流。对我来说，这一功能的好处是我可以在办公室的工作站点播放播客和技术会议视频，然后通过手机播放这些音频。这种能力早在PulseAudio之前就存在了，但Pulse让它变得更加简单。

)

使用之前，首先，你必须确保安装了PulseAudio首选项（paprefs）包，以便你可以在你的PulseAudio配置中启用网络音频。在paprefs中，启用对本地声音设备的网络访问，可能不需要验证，并启用你的计算机昨晚播放/RTP发送者。

项目地址：www.freedesktop.org/wiki/Softwa…

本文转载自: 掘金

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

本文首发于 robberphex.com/go-does-not…

像Go、Julia和Rust这样的现代语言不需要像Java c#所使用的那样复杂的垃圾收集器。但这是为什么呢?

我们首先要了解垃圾收集器是如何工作的，以及各种语言分配内存的方式有什么不同。首先，我们看看为什么Java需要如此复杂的垃圾收集器。

本文将涵盖许多不同的垃圾收集器话题：

• 为什么Java依赖快速GC？我将介绍Java语言本身中的一些设计选择，它们会给GC带来很大压力。
• 内存碎片及其对GC设计的影响。为什么这对Java很重要，但对Go就不那么重要。
• 值类型以及它们如何改变GC。
• 分代垃圾收集器，以及Go为什么不需要它。
• 逃逸分析 —— Go用来减少GC压力的一个技巧。
• 压缩垃圾收集器 —— 这在Java中很重要，但是Go却不需要它。为什么?
• 并发垃圾收集 —— Go通过使用多线程运行并发垃圾收集器来解决许多GC挑战。为什么用Java更难做到这一点。
• 对Go GC的常见批评，以及为什么这种批评背后的许多假设往往是有缺陷的或完全错误的。

为什么Java比其他语言更需要快速的GC

基本上，Java将内存管理完全外包给它的垃圾收集器。事实证明，这是一个巨大的错误。然而，为了能够解释这一点，我需要介绍更多的细节。

让我们从头说起。现在是1991年，Java的工作已经开始。垃圾收集器现在很流行。相关的研究看起来很有前途，Java的设计者们把赌注押在高级垃圾收集器上，它能够解决内存管理中的所有挑战。

由于这个原因，Java中的所有对象——除了整数和浮点值等基本类型——都被设计为在堆上分配。在讨论内存分配时，我们通常会区分所谓的堆和栈。

栈使用起来非常快，但空间有限，只能用于那些在函数调用的生命周期之内的对象。栈只适用于局部变量。

堆可用于所有对象。Java基本上忽略了栈，选择在堆上分配所有东西，除了整数和浮点等基本类型。无论何时，在Java中写下 new Something()消耗的都是堆上的内存。

然而，就内存使用而言，这种内存管理实际上相当昂贵。你可能认为创建一个32位整数的对象只需要4字节的内存。

1
2
3

java复制代码class Knight {
   int health;
}

然而，为了让垃圾收集器能够工作，Java存储了一个头部信息，包含：

• 类型/Type — 标识对象属于的类或它的类型。
• 锁/Lock — 用于同步语句。
• 标记/Mark — 标记和清除（mark and sweep）垃圾收集器使用。

这些数据通常为16字节。因此，头部信息与实际数据的比例是4:1。Java对象的c++源代码定义为：OpenJDK基类：

1
2
3
4

cpp复制代码class oopDesc {
    volatile markOop  _mark;   // for mark and sweep
    Klass*           _klass;   // the type
}

内存碎片

接下来的问题是内存碎片。当Java分配一个对象数组时，它实际上是创建一个引用数组，这些引用指向内存中的其他对象。这些对象最终可能分散在堆内存中。这对性能非常不利，因为现代微处理器不读取单个字节的数据。因为开始传输内存数据是比较慢的，每次CPU尝试访问一个内存地址时，CPU会读取一块连续的内存。

这块连续的内存块被称为cache line 。CPU有自己的缓存，它的大小比内存小得多。CPU缓存用于存储最近访问的对象，因为这些对象很可能再次被访问。如果内存是碎片化的，这意味着cache line也会被碎片化，CPU缓存将被大量无用的数据填满。CPU缓存的命中率就会降低。

Java如何克服内存碎片

为了解决这些主要的缺点，Java维护者在高级垃圾收集器上投入了大量的资源。他们提出了压缩（compact）的概念，也就是说，把对象移动到内存中相邻的块中。这个操作非常昂贵，将内存数据从一个位置移动到另一个位置会消耗CPU周期，更新指向这些对象的引用也会消耗CPU周期。

这些引用被使用的时候，垃圾收集器没法更新它们。所以更新这些引用需要暂停所有的线程。这通常会导致Java程序在移动对象、更新引用和回收未使用内存的过程中出现数百毫秒的完全暂停。

增加复杂性

为了减少这些长时间的暂停，Java使用了所谓的分代垃圾收集器（generational garbage collector）。这些都是基于以下前提：

在程序中分配的大多数对象很快就会被释放。因此，如果GC花更多时间来处理最近分配的对象，那么应该会减少GC的压力。

这就是为什么Java将它们分配的对象分成两组：

• 老年对象——在GC的多次标记和清除操作中幸存下来的对象。每次标记和扫描操作时，会更新一个分代计数器，以跟踪对象的“年龄”。
• 年轻对象——这些对象的“年龄”较小，也就是说他们是最近才分配出来的。

Java更积极地处理、扫描最近分配的对象，并检查它们是否应该被回收或移动。随着对象“年龄”的增长，它们会被移出年轻代区域。

所有这些优化会带来更多的复杂度，它需要更多的开发工作量。它需要支付更多的钱来雇佣更优秀的开发者。

现代语言如何避免与Java相同的缺陷

现代语言不需要像Java和c#那样复杂的垃圾收集器。这是在设计这些语言时，并没有像Java一样依赖垃圾回收器。

1
2
3
4

go复制代码type Point struct {
    X, Y int
}
var points [15000]Point

在上面的Go代码示例中，我们分配了15000个Point对象。这仅仅分配了一次内存，产生了一个指针。在Java中，这需要15000次内存分配，每次分配产生一个引用，这些应用也要单独管理起来。每个Point对象都会有前面提到的16字节头部信息开销。而不管是在Go语言、Julia还是Rust中，你都不会看到头部信息，对象通常是没有这些头部信息的。

在Java中，GC追踪和管理15000独立的对象。Go只需要追踪一个对象。

值类型

在除Java外的其他语言，基本上都支持值类型。下面的代码定义了一个矩形，用一个Min和Max点来定义它的范围。

1
2
3

go复制代码type Rect struct {
   Min, Max Point
}

这就变成了一个连续的内存块。在Java中，这将变成一个Rect对象，它引用了两个单独的对象，Min和Max对象。因此在Java中，一个Rect实例需要3次内存分配，但在Go、Rust、C/c++和Julia中只需要1次内存分配。

在将Git移植到Java时，缺少值类型造成了严重的问题。如果没有值类型，就很难获得良好的性能。正如Shawn O. Pearce在JGit开发者邮件列表上所说：

JGit一直纠结于没有一种有效的方式来表示SHA-1。C只需要输入unsigned char[20]并将其内联到容器的内存分配中。Java中的byte[20]将额外消耗16个字节的内存，而且访问速度较慢，因为这10个字节和容器对象位于不相邻的内存区域。我们试图通过将一个byte[20]转换为5个int来解决这个问题，但这需要耗费额外的CPU指令。

我们在说什么?在Go语言中，我可以做和C/C++一样的事情，并定义一个像这样的结构:

1
2
3

go复制代码type Sha1 struct {
   data [20]byte
}

这些字节将位于一个完整的内存块中。而Java将创建一个指向其他地方的指针。

Java开发人员意识到他们搞砸了，开发者确实需要值类型来获得良好的性能。你可以说这种说法比较夸张，但你需要解释一下Valhalla项目。这是Oracle为Java值类型所做的努力，这样做的原因正是我在这里所谈论的。

值类型是不够的

那么Valhalla项目能解决Java的问题吗?不是的。它仅仅是将Java带到了与c#同等的高度上。c#比Java晚几年出现，并且意识到垃圾收集器并不像大家想象的那么神奇。因此，他们增加了值类型。

然而，在内存管理灵活性方面，这并没有使c#/Java与Go、C/C++等语言处于同等地位。Java不支持真正的指针。在Go中，我可以这样写：

1
2

go复制代码var ptr *Point = &rect.Min // 把指向 Min 的指针存储到 ptr 中
*ptr = Point(2, 4)         // 替换 rect.Min 对象

就像在C/C++中一样，你可以在Go中获取对象的地址或对象的字段，并将其存储在一个指针中。然后，您可以传递这个指针，并使用它来修改所指向的字段。这意味着您可以在Go中创建大的值对象，并将其作为函数指针传递，来优化性能。在c#中情况要好一些，因为它对指针的支持有限。前面的Go例子可以用c#写成：

1
2
3
4

C#复制代码unsafe void foo() {
   ref var ptr = ref rect.Min;
   ptr = new Point(2, 4);
}

然而c#的指针支持伴随着一些不适用于Go的警告:

• 使用指针的代码必须标记为unsafe。这会产生安全性较低且更容易崩溃的代码。
• 必须是在堆栈上分配的纯值类型(所有结构字段也必须是值类型)。
• 在fixed的范围内，fixed关键字关闭了垃圾收集。

因此，在c#中使用值类型的正常和安全的方法是复制它们，因为这不需要定义unsafe或fixed的代码域。但对于较大的值类型，这可能会产生性能问题。Go就没有这些问题了。您可以在Go中创建指向由垃圾收集器管理的对象的指针。Go语言中，不需要像在c#中那样，将使用指针的代码单独标记出来。

自定义二次分配器

使用正确的指针，你可以做很多值类型做不到的事情。一个例子就是创建二级分配器。Chandra Sekar S给出了一个例子：Go中的 Arena 分配。

1
2
3
4
5
6
7
8
9
10
11

go复制代码type Arena []Node

func (arena *Arena) Alloc() *Node {
    if len(*arena) == 0 {
        *arena = make([]Node, 10000)
    }

    n := &(*arena)[len(*arena)-1]
    *arena = (*arena)[:len(*arena)-1]
    return n
}

为什么这些有用？如果你查看一些微基准测试，比如构造二叉树的算法，通常会发现Java比Go有很大的优势。这是因为构造二叉树算法通常用于测试垃圾收集器在分配对象时的速度。Java在这方面非常快，因为它使用了我们所说的bump指针。它只是增加一个指针值，而Go将在内存中寻找一个合适的位置来分配对象。然而，使用Arena分配器，你也可以在Go中快速构建二叉树。

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

go复制代码func buildTree(item, depth int, arena *Arena) *Node {
    n := arena.Alloc()
    if depth <= 0 {
        *n = Node{item, nil, nil}
    } else {
        *n = Node{
              item,
              buildTree(2*item-1, depth-1, arena),
              buildTree(2*item, depth-1, arena),
        }
    }
    return n
}

这就是为什么真正的指针会有好处。你不能在一个连续的内存块中创建一个指向元素的指针，如下所示:

n := &(*arena)[len(*arena)-1]

Java Bump分配器的问题

Java GC使用的bump分配器与Arena分配器类似，您只需移动一个指针就能获取下一个值。但开发者不需要手动指定使用Bump分配器。这可能看起来更智能。但它会导致一些在Go语言中没有的问题：

• 或早或晚，内存都需要进行压缩（compact），这涉及到移动数据和修复指针。Arena分配器不需要这样做。
• 在多线程程序中，bump分配器需要锁(除非你使用线程本地存储)。这抹杀了它们的性能优势，要么是因为锁降低了性能，要么是因为线程本地存储将导致碎片化，这需要稍后进行压缩。

Ian Lance Taylor是Go的创建者之一，他解释了bump分配器的问题：

一般来说，使用一组每个线程缓存来分配内存可能会更有效率，而在这一点上，你已经失去了bump分配器的优势。因此，我要断言，通常情况下，尽管有许多警告，但对多线程程序使用压缩内存分配器并没有真正的优势。

分代GC和逃逸分析

Java垃圾收集器有更多的工作要做，因为它分配了更多的对象。为什么？我们刚刚讲过了。如果没有值对象和真正的指针，在分配大型数组或复杂的数据结构时，它将总是以大量的对象告终。因此，它需要分代GC。

分配更少对象的需求对Go语言有利。但Go语言还有另一个技巧。Go和Java在编译函数时都进行了逃逸分析。

逃逸分析包括查看在函数内部创建的指针，并确定该指针是否逃逸出了函数范围。

1
2
3
4
5
6
7
8
9
10

go复制代码func escapingPtr() []int {
   values := []int{4, 5, 10}
   return values
}

fun nonEscapingPtr() int {
    values = []int{4, 5, 10}
    var total int = addUp(values)
    return total
}

在第一个示例中，values指向一个切片，这在本质上与指向数组的指针相同。它逃逸了是因为它被返回了。这意味着必须在堆上分配values。

然而，在第二个例子中，指向values的指针并不会离开nonEscapingPtr函数。因此，可以在栈上分配values，这个动作非常快速，并且代价也很小。逃逸分析本身只分析指针是否逃逸。

Java逃逸分析的限制

Java也做转义分析，但在使用上有更多的限制。从Java SE 16 Oracle文档覆盖热点虚拟机：

对于不进行全局转义的对象，它不会将堆分配替换为堆栈分配。

然而，Java使用了另一种称为标量替换的技巧，它避免了将对象放在栈上的需要。本质上，它分解对象，并将其基本成员放在栈上。请记住，Java已经可以在栈上放置诸如int和float等基本值。然而，正如Piotr Kołaczkowski在2021年发现的那样，在实践中，标量替换即使在非常微不足道的情况下也不起作用。

相反，标量替换的主要的优点是避免了锁。如果你知道一个指针不会在函数之外使用，你也可以确定它不需要锁。

Go语言逃逸分析的优势

但是，Go使用逃逸分析来确定哪些对象可以在堆栈上分配。这大大减少了寿命短的对象的数量，这些对象本来可以从分代GC中受益。但是要记住，分代GC的全部意义在于利用最近分配的对象生存时间很短这一事实。然而，Go语言中的大多数对象可能会活得很长，因为生存时间短的对象很可能会被逃逸分析捕获。

与Java不同，在Go语言中，逃逸分析也适用于复杂对象。Java通常只能成功地对字节数组等简单对象进行逃逸分析。即使是内置的ByteBuffer也不能使用标量替换在堆栈上进行分配。

现代语言不需要压缩GC

您可以读到许多垃圾收集器方面的专家声称，由于内存碎片，Go比Java更有可能耗尽内存。这个论点是这样的：因为Go没有压缩垃圾收集器，内存会随着时间的推移而碎片化。当内存被分割时，你将到达一个点，将一个新对象装入内存将变得困难。

然而，由于两个原因，这个问题大大减少了：

1. Go不像Java那样分配那么多的小对象。它可以将大型对象数组作为单个内存块分配。
2. 现代的内存分配器，如谷歌的 TCMalloc 或英特尔的 Scalable Malloc 不会对内存进行分段。

在设计Java的时候，内存碎片是内存分配器的一个大问题。人们不认为这个问题可以解决。但即使回到1998年，在Java问世后不久，研究人员就开始解决这个问题。下面是Mark S. Johnstone和Paul R. Wilson的一篇论文：

这实质上加强了我们之前的结果，这些结果表明，内存碎片问题通常被误解了，好的分配器策略可以为大多数程序提供良好的内存使用。

因此，设计Java内存分配策略时的许多假设都不再正确。

分代GC vs 并发GC的暂停

使用分代GC的Java策略旨在使垃圾收集周期更短。要知道，为了移动数据和修复指针，Java必须停止所有操作。如果停顿太久，将会降低程序的性能和响应能力。使用分代GC，每次检查的数据更少，从而减少了检查时间。

然而，Go用一些替代策略解决了同样的问题：

1. 因为不需要移动内存，也不需要固定指针，所以在GC运行期间要做的工作会更少。Go GC只做一个标记和清理：它在对象图中查找应该被释放的对象。
2. 它并发运行。因此，单独的GC线程可以在不停止其他线程的情况下寻找要释放的对象。

为什么Go可以并发运行GC而Java却不行？因为Go不会修复任何指针或移动内存中的任何对象。因此，不存在尝试访问一个对象的指针，而这个对象刚刚被移动，但指针还没有更新这种风险。不再有任何引用的对象不会因为某个并发线程的运行而突然获得引用。因此，平行移动“已经死亡”的对象没有任何危险。

这是怎么回事？假设你有4个线程在一个Go程序中工作。其中一个线程在任意时间T秒内执行临时GC工作，时间总计为4秒。

现在想象一下，一个Java程序的GC只做了2秒的GC工作。哪个程序挤出了最多的性能?谁在T秒内完成最多?听起来像Java程序，对吧?错了！

Java程序中的4个工作线程将停止所有线程2秒。这意味着 2×4 = 8秒的工作在T秒中丢失。因此，虽然Go的停止时间更长，但每次停止对程序工作的影响更小，因为所有线程都没有停止。因此，缓慢的并发GC的性能可能优于依赖于停止所有线程来执行其工作的较快GC。

如果垃圾产生的速度比清理它的速度还快怎么办？

反对当前垃圾收集器的一个流行观点是，活动工作线程产生垃圾的速度可能比垃圾收集器线程收集垃圾的速度快。在Java世界中，这被称为“并发模式失败”。

在这种情况下，运行时别无选择，只能完全停止程序并等待GC周期完成。因此，当Go声称GC暂停时间非常低时，这种说法只适用于GC有足够的CPU时间和空间超过主程序的情况。

但是Go语言有一个聪明的技巧来绕过Go GC大师Rick Hudson所描述的这个问题。Go使用的是所谓的“Pacer”。

如果需要的话，Pacer会在加速标记的同时降低分配速度。在一个较高的水平，Pacer停止了Goroutine，它做了大量的分配，并让它做标记。工作量与Goroutine的分配成比例。这加快了垃圾收集器的速度，同时减慢了mutator的速度。

Goroutines有点像在线程池上复用的绿色线程。基本上，Go接管正在运行产生大量垃圾的工作负载的线程，并让它们帮助GC清理这些垃圾。它会一直接管线程，直到GC的运行速度超过产生垃圾的协程。

简而言之

虽然高级垃圾收集器解决了Java中的实际问题，但现代语言，如Go和Julia，从一开始就避免了这些问题，因此不需要使用Rolls Royce垃圾收集器。当您有了值类型、转义分析、指针、多核处理器和现代分配器时，Java设计背后的许多假设都被抛到了脑后。它们不再适用。

GC的Tradeoff不再适用

Mike Hearn在Medium上有一个非常受欢迎的故事，他批评了Go GC的说法：现代垃圾收集。

Hearn的关键信息是GC设计中总是存在权衡。他的观点是，因为Go的目标是低延迟收集，他们将在许多其他指标上受到影响。这是一本有趣的读物，因为它涵盖了很多关于GC设计中的权衡的细节。

首先，低延迟是什么意思?Go GC平均只暂停0.5毫秒，而各种Java收集器可能要花费数百毫秒。

我认为Mike Hearn的论点的问题在于，它们基于一个有缺陷的前提，即所有语言的内存访问模式都是相同的。正如我在本文中所提到的，根本不是这样的。Go生成的需要GC管理的对象会少得多，并且它会使用逃逸分析提前清理掉很多对象。

老技术本身就是坏的?

Hearn的论点声明，简单的收集在某种程度上是不好的：

Stop-the-world (STW)标记/清除是本科生计算机科学课程中最常用的GC算法。在做工作面试时，我有时会让应聘者谈论一些关于GC的内容，但几乎总是，他们要么将GC视为一个黑盒子，对它一无所知，要么认为它至今仍在使用这种非常古老的技术。

是的，它可能是旧的，但是这种技术允许并发地运行GC，这是“现代”的技术不允许的。在我们拥有多核的现代硬件世界中，这一点更重要。

Go 不是 C#

另一个说法:

由于Go是一种具有值类型的相对普通的命令式语言，它的内存访问模式可能可以与C#相比较，后者的分代假设当然成立，因此.NET使用分代收集器。

事实并非如此。C#开发人员会尽量减少大值对象的使用，因为不能安全地使用与指针相关的代码。我们必须假设c#开发人员更喜欢复制值类型而不是使用指针，因为这可以在CLR中安全地完成。这自然会带来更高的开销。

据我所知，C#也没有利用逃逸分析来减少堆上的短生命周期对象的产生。其次，C#并不擅长同时运行大量任务。Go可以利用它们的协程来同时加速收集，就像Pacer提到的那样。

内存压缩整理

压缩：因为没有压缩，你的程序最终会把堆碎片化。我将在下面进一步讨论堆碎片。在缓存中整齐地放置东西也不会给您带来好处。

在这里，Mike Hearn对分配器的描述并不是最新的。TCMalloc等现代分配器基本上消除了这个问题。

程序吞吐量:由于GC必须为每个周期做大量工作，这从程序本身窃取CPU时间，降低了它的速度。

当您有一个并发GC时，这并不适用。所有其他线程都可以在GC工作时继续运行——不像Java，它必须停止整个世界。

堆的开销

Hearn提出了“并发模式失败”的问题，假设Go GC会有跟不上垃圾生成器的速度的风险。

堆开销:因为通过标记/清除收集堆是非常慢的，你需要大量的空闲空间来确保你不会遭遇“并发模式失败”。默认的堆开销是100%，它会使你的程序需要的内存翻倍。

我对这种说法持怀疑态度，因为我看到的许多现实世界的例子似乎都建议围棋程序使用更少的内存。更不用说，这忽略了Pacer的存在，它会抓住Goroutines，产生大量垃圾，让他们清理。

为什么低延迟对Java也很重要

我们生活在一个Docker和微服务的世界。这意味着许多较小的程序相互通信和工作。想象一个请求要经过好几个服务。在一个链条，这些服务中如果有一个出现重大停顿，就会产生连锁反应。它会导致所有其他进程停止工作。如果管道中的下一个服务正在等待STW的垃圾收集，那么它将无法工作。

因此，延迟/吞吐量的权衡不再是GC设计中的权衡。当多个服务一起工作时，高延迟将导致吞吐量下降。Java对高吞吐量和高延迟GC的偏好适用于单块世界。它不再适用于微服务世界。

这是Mike Hearn观点的一个根本问题，他认为没有灵丹妙药，只有权衡取舍。它试图给人这样一种印象：Java的权衡是同样有效的。但权衡必须根据我们所生活的世界进行调整。

简而言之，我认为Go语言已经做出了许多聪明的举动和战略选择。如果这只是任何人都可以做的trade-off，那么省去它是不可取的。

本文翻译自 itnext.io/go-does-not…

本文转载自: 掘金

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

简介：本文为你详细的梳理一次 Inclavare Containers 项目的发展脉络，解读它的核心思想和创新技术。

作为业界首个面向机密计算场景的开源容器运行时，Inclavare Containers 项目于 2020 年 5 月开源，短短一年多时间内发展势头非常迅猛，吸引了众多领域专家和工程师的关注与贡献。2021 年 9 月 15 日，云原生计算基金会（CNCF）宣布通过全球 TOC 投票接纳 Inclavare Containers 成为 CNCF 官方沙箱项目，成为机密计算技术在云原生领域第一个进入 CNCF 的项目。

不过，如果你对机密计算领域不太关注，可能对 Inclavare Containers 还没有做过太深入的了解。别着急，本文为你详细的梳理一次 Inclavare Containers 项目的发展脉络，解读它的核心思想和创新技术。

首先，什么是 Inclavare Containers？

**一言以蔽之，Inclavare Containers 是业界首个面向机密计算场景的开源容器运行时。**可是，什么是机密计算呢？Inclavare Containers 跟机密计算又是什么关系？它能帮助我们解决什么问题？

数据安全与机密计算

数据在整个生命周期有三种状态：At-Rest（静态）、In-Transit（传输中）和 In-Use（使用中）。

• At-Rest 状态下，一般会把数据存放在硬盘、闪存或其他的存储设备中。保护 At-Rest 状态的数据有很多方法，比如对文件加密后再存放或者对存储设备加密。
• In-Transit 是指通过公网或私网把数据从一个地方传输到其他地方，用户可以在传输之前对文件加密或者采用安全的传输协议保证数据在传输中的安全，比如HTTPS、SSL、TLS、FTPS 等。
• In-Use 是指正在使用的数据。即便数据在传输过程中是被加密的，但只有把数据解密后才能进行计算和使用。也就意味着，如果数据在使用时没有被保护的话，仍然有数据泄露和被篡改的风险。

在这个世界上，我们不断地存储、使用和共享各种敏感数据：从信用卡数据到病历，从防火墙配置到地理位置数据。保护处于所有状态中的敏感数据比以往任何时候都更为重要。如今被广泛使用的加密技术可以用来提供数据机密性（防止未经授权的访问）和数据完整性（防止或检测未经授权的修改），但目前这些技术主要被用于保护传输中和静止状态的数据，目前对数据的第三个状态“使用中”提供安全防护的技术仍旧属于新的前沿领域。

机密计算指使用基于硬件的可信执行环境（Trusted Execution Environment，TEE）对使用中的数据提供保护。 通过使用机密计算，我们现在能够针对“使用中”的数据提供保护。

机密计算的核心功能有：

• 保护 In-Use 数据的机密性。未经授权的实体（主机上的应用程序、主机操作系统和Hypervisor、系统管理员或对硬件具有物理访问权限的任何其他人。）无法查看在TEE中使用的数据，内存中的数据是被加密的，即便被攻击者窃取到内存数据也不会泄露数据。
• 保护 In-Use 数据的完整性。防止未经授权的实体篡改正在处理中的数据，度量值保证了数据和代码的完整性，使用中有任何数据或代码的改动都会引起度量值的变化。
• 可证明性。通常 TEE 可以提供其起源和当前状态的证据或度量值，以便让另一方进行验证，并决定是否信任 TEE 中运行的代码。最重要的是，此类证据是由硬件签名，并且制造商能够提供证明，因此验证证据的一方就可以在一定程度上保证证据是可靠的，而不是由恶意软件或其他未经授权的实体生成的。

机密计算的现状与困境

业界内的诸多厂商就已经开始关注并投入到机密计算中。各大芯片厂家和云服务提供商（Cloud Service Provider，简称 CSP）都在机密计算领域投入研发资源，并组建了“机密计算联盟”。该联盟专门针对云服务及硬件生态，致力于保护计算时的数据安全。

目前支持TEE的硬件平台主要有 3 个：Intel® SGX、ARM TrustZone 和 AMD SEV，他们有不同的应用场景和实现方式。

1、ARM TrustZone 把硬件资源分为安全世界和非安全世界两部分，所有需要保密的操作在安全世界执行，其余操作在非安全世界执行，安全世界和非安全世界通过一个名为 Monitor Mode 的模式进行转换。典型的应用场景有移动支付、数字钱包等。

2、AMD 利用 SEV（AMD Secure Encrypted Virtualizationn），SME（AMD Secure Memory Encryption）和SEV-ES（Secure Encrypted Virtualization-Encrypted State）等技术实现虚拟机的 Guest 内存加密和安全隔离。

3、Intel® SGX 是 Intel 提供的一组指令，用于提高应用的代码和数据的安全性。Intel® SGX 程序由不可信代码和可信 Enclave 组成，敏感的代码和数据放入到 Enclave 中。Intel® SGX 指令在一个特定的加密内存区域（EPC）中创建和执行 Enclave，该区域由开发者定义受限的入口和出口函数，有效防止数据泄露。

目前**机密计算目前正处于百花齐发和百家争鸣的阶段，市场和商业化潜力非常巨大。**但机密计算在云原生场景中还有一些不足：

**1、目前提供的技术的使用和开发门槛高。**以开发 Intel® SGX 应用用例，用户需要学习 Intel® SGX 开发技能并对业务进行改造。相比传统开发方式，其使用和开发门槛很高，令很多开发者望而生畏。**2、机密计算容器化和对接 Kubernetes 的成本和复杂度高。**越来越多的用户开始拥抱云原生，即便用户掌握了机密计算的开发技能，让机密计算应用跑在容器里或者跑在 Kubernetes 里还要克服很多问题。比如如何在容器内加载 SGX 驱动，如何为容器合理分配 EPC 内存等。

**3、服务提供商提供的技术方案相对单一。**现在很多服务提供商都提供了机密计算的技术方案，但方案总体来说比较单一，并不能完全满足用户上云的需求。 比如 Google 的 Asylo 和 Azure 的 OpenEnclave，他们是在 Intel® SGX SDK 的基础上做了封装，以降低用户使用机密计算技术的成本。但这仍然需要用户掌握 Intel® SGX 的开发技能，对用户而言仍然是有学习门槛的。 再比如 Occlum、GraphaneSGX 等 LibOS 技术，他们的目的是让用户在不改动代码或做改动很少的代码就能让应用运行在 Enclave中。对用户而言不必再去学习复杂的机密计算的开发技术，但这只是解决了用户开发的问题，但仍然没有解决在容器中运行机密计算应用的问题。

总之，目前已有的机密计算技术方案存在以上困境，不能够完全满足用户不同场景的安全需求。

为了解决以上问题，Inclavare Containers 提供了首个面向机密计算场景的开源容器运行时，把机密计算技术和容器技术完美地结合在一起，其价值可概括为三点：

• 抹平机密计算的高使用门槛，为用户提供与普通容器一致的使用体感。
• 基于处理器提供的多种硬件安全技术，提供对多种 Enclave 形态的支持，为用户在安全和成本之间提供更多的选择和灵活性。
• 加速基于零信任模型的机密计算云基础设施的构建。

Inclavare Containers：云原生机密计算的未来

Inclavare Containers 支持机密应用基于硬件的 TEE 被透明地容器化。带来了以下的好处：

• 轻松将机密应用带入云原生。
• 在基于硬件的 TEE 中运行修改/未修改的应用程序（取决于 Enclave Runtime）。
• 为应用的数据和代码提供机密性、完整性和可证明性。

如下图所示，Inclavare Containers 中包含多个组件，这些组件可以利用基于硬件支持的 Enclave 技术使可信应用运行在容器中。包含的组件有 rune、shim-rune、Enclave Runtime等。

• rune：rune 是一个命令行工具，用于根据 OCI 规范在容器中生成和运行 Enclave。rune 是在 runc 代码基础上开发的，既可以运行普通 runc 容器也可以运行 Enclave 容器；rune已经写入 OCI 运行时实现列表：

github.com/opencontain…

• shim-rune：为容器运行时 rune 提供的 shim，主要负责管理容器的生命周期、把普通镜像转换成 TEE 镜像；管理容器的生命周期，与 rune 配合完成容器的创建、启动、停止、删除等操作。
• Enclave Runtime：负责在 Enclave 内加载和运行受信任和受保护的应用程序。rune 和 Enclave Runtime 之间的接口是 Enclave Runtime PAL API，它允许通过定义良好的函数接口来调用 Enclave Runtime。机密计算应用通过这个接口与云原生生态系统进行交互。

一类典型的 Enclave Runtime 实现基于库操作系统。目前，推荐的与 rune 交互的 Enclave Runtime 是 Occlum，这是一种内存安全、多进程 Libos。另一类典型的 Enclave Runtime是带有 Intel® SGX WebAssembly Micro Runtime (WAMR)，这是一个占用空间很小的独立 WebAssembly (WASM) 运行时，包括一个 VM 核心、一个应用程序框架和一个 WASM 应用程序的动态管理。

此外，您可以使用您喜欢的任何编程语言和 SDK（例如英特尔 SGX SDK）编写自己的Enclave Runtime，只要它实现了 Enclave Runtime PAL API。

Inclavare Contianers主要有以下特点：

1、将 Intel® SGX 技术与成熟的容器生态结合，将用户的敏感应用以 Enclave 容器的形式部署和运行；Inclavare Contianers 的目标是希望能够无缝运行用户制作的普通容器镜像，这将允许用户在制作镜像的过程中，无需了解机密技术所带来的复杂性，并保持与普通容器相同的使用体感。

2、Intel® SGX 技术提供的保护粒度是应用而不是系统，在提供很高的安全防护手段的同时，也带来了一些编程约束，比如在 SGX enclave 中无法执行 syscall 指令；因此我们引入了 LibOS 技术，用于改善上述的软件兼容性问题，避免开发者在向 Intel® SGX Enclave 移植软件的过程中，去做复杂的软件适配工作。然后，虽然各个 LibOS 都在努力提升对系统调用的支持数量，但这终究难以企及原生 Linux 系统的兼容性，并且即使真的达成了这个目标，攻击面过大的缺点又会暴露出来。因此，Inclavare Containers 通过支持 Java 等语言Runtime 的方式，来补全和提升 Enclave 容器的泛用性，而不是将 Enclave 容器的泛用性绑定在“提升对系统调用的支持数量” 这一单一的兼容性维度上；此外，提供对语言 Runtime 的支持，也能将像 Java 这样繁荣的语言生态引入到机密计算的场景中，以丰富机密计算应用的种类和数量。

3、通过定义通用的 Enclave Runtime PAL API 来接入更多类型的 Enclave Runtime，比如 LibOS 就是一种 Enclave Runtime 形态；设计这层 API 的目标是为了繁荣 Enclave Runtime 生态，允许更多的 Enclave Runtime 通过对接 Inclavare Containers 上到云原生场景中，同时给用户提供更多的技术选择。

灵活的机密容器部署方式

Docker 集群

对于普通用户来说，如何运行一个机密容器是一个非常困难的事情，您需要掌握机密计算领域的专业知识，并按照 SGX 应用开发规范开发和构建镜像。而Inclavare Containers 设计并实现了符合 OCI 运行时规范的新型 OCI 运行时 rune，以便与现有的云原生生态系统保持一致，实现了机密容器形态。不仅可以帮您省去这些复杂过程，还可以使您像普通容器一样使用机密容器。

Inclavare Containers 可以与 dockerd 集成。 具体来说，您需要在构建容器镜像时安装首选的 Enclave Runtime，并在您的机器的docker 配置文件中添加 rune 的相关配置，例如，/etc/docker/daemon.json。

1
2
3
4
5
6
7
8

json复制代码{
        "runtimes": {
                "rune": {
                        "path": "/usr/local/bin/rune",
                        "runtimeArgs": []
                }
        }
}

然后重启 docker 服务即可。

由于 rune 是在 runc 代码基础上开发的，所以 rune 既可以创建 runc 容器，也可以创建 Enclave 容器。在 Docker 集群中，创建 runc 容器和创建 Enclave 容器的流程是完全一样的。他们的区别在于镜像。普通 runc 容器镜像是不能创建 Enclave 的，需要用户按照 Enclave Runtime 的要求生成特殊的镜像。如上图所示，使用 docker 启动一个 Occlum 机密容器的的流程如下：

1、用户开发机密应用。用户不需要掌握机密计算的知识，Occlum 提供了工具可以把普通应用转换为机密应用。需要注意的是：Occlum 有一些使用限制，详情请查阅文档：github.com/occlum/occl…

2、基于 Occlum 生成的文件构建镜像，构建成功后推入镜像仓库。3、通过标准 docker 拉起容器镜像，最终使用 rune 运行时启动 Enclave 容器并运行 Occlum 和 Enclave 应用。

Kubernetes 集群

虽然 Docker 集群中能运行 Enclave 容器，但还有一些不足：

• 无法动态管理和调度 EPC。
• 容器编排能力弱，没有 Kubernetes 面向终态设计的容器管理方式。

为此，Inclavare Containers 提供了 shim-rune 用于在云上 Kubernetes 机密计算集群中创建 Enclave 容器。在这种场景下，shim-rune 和 rune 可以组成一个 enclave 容器化栈，所以在构建容器镜像时不需要安装 Enclave Runtime，提供和普通容器一样的体验。

Inclavare Containers 已经添加到 containerd 的采用者列表中：github.com/containerd/… 此外，shim-rune也支持containerd shim v2 API：github.com/containerd/… 因此，您可以在系统上的 containerd 配置文件（例如 /etc/containerd/config.toml）中添加 shim-rune 的相关配置。

1
2
3
4

ini复制代码[plugins.cri.containerd]
          ...
          [plugins.cri.containerd.runtimes.rune]
            runtime_type = "io.containerd.rune.v2"

然后重启 containerd 即可。

如上图所示，在云上 Kubernetes 机密计算集群中创建 Occlum 机密容器的工作流程如下：

1、kubelet 向containerd 发起 CRI（Container Runtime Interface）请求，比如请求创建一个 Pod。

2、Containerd 中有一个 cri-containerd 的插件实现了 CRI 接口，Containerd 接收到请求后，把请求转给 shim-rune。

3、shim-rune 既可以创建 runc 容器也可以创建 rune 容器。在创建 runc 和 rune 容器的处理流程也有差异：

1. 创建 runc 容器：与创建普通 runc 容器过程完全一样，比如 Pod 的 pause 容器就是 runc 容器。
2. 创建 rune 容器：利用 LibOS 把普通镜像转换成 TEE 镜像，rune 会在容器内创建 Enclave 并把应用运行在 Enclave 中。

4、为每个容器分别创建一个 rune 进程，该进程负责来创建容器，创建 runc 容器和 Enclave 容器的流程是不同的：

1. 创建 runc 容器：与 runc 创建 runc 容器的流程完全一样。
2. 创建 Enclave 容器：每种 Enclave Runtime 都会提供一个实现了 Enclave Runtime PAL API 的动态库so 。rune 先在 Host 上加载 liberpal.so，然后按照 runc 的方式创建容器，并在容器内启动 1 号进程 init-runelet ，init-runelet 接收到 rune 的请求后加载并创建 Enclave。Encalve 包含一般包含两部分：LibOS 和 App/语言 Runtime。LibOS 是 Enclave Runtime 提供的用于支撑应用运行的操作系统库，App/语言 Runtime 是应用本身，有的语言也会有语言 Runtime，比如运行 OpenJDK 11 应用需要 JVM。

5、rune 进程退出，并把 Enclave 容器内 1 号进程的父进程设置为 shim-rune。6、shim-rune 请求 rune 启动 Enclave。至此一个可信应用就运行起来了。

K8s 集群级远程证明架构

为了进一步满足“用户敏感数据的安全性在传输链路上也能够完全不再依赖云厂商”这一安全需求，Inclavare Containers 设计了一套通用的和跨平台的远程证明架构 Enclave Attestation Architecture（简称 EAA）。EAA 以“关联了带有硬件可执行环境的远程证明证据的 TLS 证书”为信任根，确保通信各方的通信信道的安全性完全是基于硬件可信执行环境的。

EAA的主要组件有：

• Enclave-TLS

Enclave-TLS 增强了标准 TLS 以支持基于机密计算技术的异构硬件 TEE 之间的可信通信，是一种支持异构硬件可执行环境的双向传输层安全性协议 (Transport Layer Security，简称TLS）。通过使用 Enclave-TLS，即使是非硬件 TEE 平台也可以通过经过认证的安全信道与硬件 TEE（例如 SGX Enclave）通信以传输敏感信息。总的来说，TCB 的边界从执行环境扩展到使用 Enclave-TLS 的网络传输。此外，Enclave-TLS 有一个可扩展的模型来支持各种硬件 TEE。

• 机密容器

机密容器扮演证明者的角色。响应来自 Inclavared 的请求，并返回机密容器的attestation evidence（mrenclave 值和 mrsigner 值）。

• Inclavared

Inclavared 负责转发下游的机密容器和上游的客户端验证者程序 Shelter 之间的流量，通信过程受到经过证明的 Enclave-TLS 通道的保护。

• Shelter

Shelter 作为部署在云下的远程证明验证者，记录 Enclave 运行时的启动度量，然后基于 Enclave-TLS 建立可信信道 Inclavared 进行通信。最后，Shelter 对Enclave 运行时的度量值进行验证，以便租户能够明确知道他们的工作负载是否在真正的 TEE 环境中加载。

具体的工作流程如下：

当用户想验证工作负载是否运行在可信平台上时，可以启动 Shelter 工具发送验证请求给 Inclavared。

1、当接收到 Shelter 的验证请求之后，Inclavared 将请求发送给机密容器，Inclavared 和机密容器分别产生带有 SGX 远程认证信息的 TLS 证书。

2、Inclavared 和 Shelter 之间基于 Enclave-TLS 建立经过证明的安全信道。

3、Inclavared 与机密容器之间基于 Enclave-TLS 建立经过双向认证的安全信道。

4、Inclavared 转发机密容器提供的硬件可执行环境信息和敏感信息给 Shelter。

5、Shelter 对 Enclave 运行时的度量值进行验证，并返回验证结果给用户。

五大技术创新

Inclavare Containers 提供了兼容 OCI Runtime 的容器运行时，用户可根据需要在 Docker 集群或者 Kubernetes 集群中运行 Enclave 容器。通过 Enclave Runtime 抹去了用户使用机密计算技术的门槛，在 Kubernetes 集群中更是保持了与普通容器一致的使用体验。通过 Encalve Runtime PAL API 可以提供多种 Runtime 实现，为用户提供更多 Enclave 选择，在安全和成本之间提供更多的选择和灵活性。

Inclavare Containers 的技术创新主要体现在以下几点：

1、实现了标准的应用 enclave 化技术。

• 将机密计算硬件技术（如Intel® SGX）与成熟的容器生态结合，兼容 OCI Runtime 和 OCI 镜像标准，实现了机密容器形态。用户的敏感应用以机密容器的形式部署和运行，并保持与使用普通容器相同的使用体感。

2、基于Enclave-TLS、shelter、inclavared 设计了灵活可扩展的 K8s 集群级远程证明架构。

• 通过构建通用且跨平台的远程证明安全架构，能够向用户证明其敏感的工作负载是运行在真实可信的基于硬件的可信执行环境中的。

3、制定了通用的PAL API，规范化了enclave runtime 对接 Inclavare Containers 的接口，打造 Inclavare Containers 的生态。

• 通过标准的 API 规范来对接各种形态的 Enclave Runtime，在简化特定的Enclave Runtime 对接云原生生态的同时，也为用户提供了更多的技术选择。

4、构造基于零信任模型的机密计算集群基础设施。

• 移除对云服务提供商的信任，Inclavare Containers 的安全威胁模型假设用户无需信任云服务提供商，即用户工作负载的安全性不再依赖云服务提供商控制的特权组件。

5、与 Kubernetes 生态无缝整合。

• Inclavare Containers 可以部署在任何公共云 Kubernetes 平台中，实现了统一的机密容器部署方式。

结语

作为业界首个面向机密计算场景的开源容器运行时，Inclavare Containers 为ACK-TEE（ACK-Trusted Execution Environment）提供了使用机密容器的最佳实践。ACK-TEE 依托 Inclavare Containers，能够无缝地运行用户制作的机密容器镜像，并保持与普通容器相同的使用体感。ACK-TEE 可被广泛应用于各种隐私计算的场景，包括：区块链、安全多方计算、密钥管理、基因计算、金融安全、AI、数据租赁。

未来，Inclavare Containers将继续为开源社区提供面向云原生场景的机密计算容器技术、机密计算集群技术和安全架构，并成为该领域的事实标准。在不断深化实施零信任模型原则的同时，不断提升开发者和用户的使用体验，并最终完全消除与运行普通容器在使用体感上的差别。同时，Inclavare Containers 将积极参与共建云原生社区，深度联手上下游伙伴一同推动云原生安全技术不断进步，为打造更安全的云原生环境不懈努力。

原文链接

本文为阿里云原创内容，未经允许不得转载。

本文转载自: 掘金

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

这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战

Mybatis设计模式之代理模式

基本概念

代理模式(Proxy Pattern):给某⼀个对象提供⼀个代理，并由代理对象控制对原对象的引⽤。代理模式的英⽂叫做Proxy，它是⼀种对象结构型模式，代理模式分为静态代理和动态代理，我们来介绍动态代理

举例：

（1）创建⼀个抽象类，Person接⼝，使其拥有⼀个没有返回值的doSomething⽅法。

（2）创建⼀个名为Bob的Person接⼝的实现类，使其实现doSomething⽅法

(3) 创建JDK动态代理类，使其实现InvocationHandler接⼝。拥有⼀个名为target的变量，并创建getTarget获取代理对象⽅法

创建JDK动态代理测试类J DKDynamicTest

Mybatis中实现

代理模式可以认为是Mybatis的核⼼使⽤的模式，正是由于这个模式，我们只需要编写Mapper.java接
⼝，不需要实现，由Mybati s后台帮我们完成具体SQL的执⾏。
当我们使⽤Configuration的getMapper⽅法时，会调⽤mapperRegistry.getMapper⽅法，⽽该⽅法⼜会调⽤ mapperProxyFactory.newInstance(sqlSession)来⽣成⼀个具体的代理：

在这⾥，先通过T newInstance(SqlSession sqlSession)⽅法会得到⼀个MapperProxy对象，然后调⽤T newInstance(MapperProxy mapperProxy)⽣成代理对象然后返回。⽽查看MapperProxy的代码，可以看到如下内容：

⾮常典型的，该MapperProxy类实现了InvocationHandler接⼝，并且实现了该接⼝的invoke⽅法。通 过这种⽅式，我们只需要编写Mapper.java接⼝类，当真正执⾏⼀个Mapper接⼝的时候，就会转发给MapperProxy.invoke⽅法，⽽该⽅法则会调⽤后续的sqlSession.cud>executor.execute>prepareStatement 等⼀系列⽅法，完成 SQL 的执⾏和返回。
至此Mybatis使用的代理模式就简单介绍完毕，Mybatis中还有很多地方使用到啦代理模式，需要自己尝试阅读源码去发现。

本文转载自: 掘金

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

为了构建更为完整的物联网大数据处理生态，支持简单高效地从其他时序数据库迁移到TDengine，我们开发了taosAdapter。

TDengine是涛思数据专为物联网、车联网、工业互联网、IT运维等设计和优化的大数据平台。除核心的快10倍以上的时序数据库功能外，还提供缓存、数据订阅、流式计算等功能，最大程度减少研发和运维的复杂度，且核心代码包括集群功能全部开源。自TDengine于2019年7月宣布开源以来，在GitHub上已经已经获得非常积极的反馈，有17,300多人给了star,4,100多人fork了代码。越来越多的用户开始采用TDengine。

taosAdapter是一个新的独立程序，可以包含在TDengine 2.3.0.0及以上版本中。taosAdapter的核心出发点是解决用户的痛点，降低迁移成本。

在物联网和运维监控等领域，有些用户还在使用传统解决方案或者比较老的产品解决时序数据处理问题，比如OpenTSDB。OpenTSDB也是一款开源的分布式时序数据库，它没有自己的存储引擎，相关功能完全基于HBase。因为产生时间较早，所以很多运维监控项目选择了该系统。

以顺丰科技为例，他们采用了 OpenTSDB+HBase 作为大数据监控平台全量监控数据的存储方案。但是随着该平台接入的数据量越来越大，他们遇到了很多痛点，像系统依赖多、使用成本高和性能不如意等。

具体而言：

• 依赖多，稳定性较差：大数据监控平台是底层的基础设施，在数据存储方面又要依赖 Kafka、Spark和HBase等大数据组件。这样数据处理链路就会很长，而数据链路越长，要保证系统的可靠性，挑战也就越大。如果监控系统本身出现问题，也就无从基于它来发现和定位业务系统的问题了。
• 使用成本高：监控数据的写入量非常大，而且为了追溯历史问题，他们需要将全量监控数据保存半年以上。数据存储成本居高不下。
• 性能不能满足需求：OpenTSDB作为全量监控数据存储方案，在写入方面性能基本满足需求，但是在日常大跨度和高频次查询方面已无法满足要求。

为了解决这些痛点，当时顺丰科技的工程师们认为有必要对全量监控数据存储方案进行升级。他们调研了多款时序数据库产品，最终决定选择 TDengine。之后他们基于TDengine对系统进行了改造。改造完成后，TDengine集群轻松扛住了全量监控数据写入，目前运行稳定。

这次改造带来的效果提升非常亮眼：服务端物理机由21台降至3台，每日所需存储空间同等条件下仅为OpenTSDB+HBase的约 1/10，大大降低了硬件成本。在查询性能方面，在使用预计算函数情况下，查询p99都在0.7秒以内，已经能够满足日常绝大部分查询需求；在做大跨度（6 个月）非预计算查询情况下，首次查询耗时在 10 秒左右，后续类似查询耗时会有大幅下降（2-3s）。

睿信物联网平台也遇到了类似问题，他们之前采用OpenTSDB存储时序数据，功能上是能够满足需求的；但是由于OpenTSDB架构复杂，体量过重，给开发测试、安装部署以及运维管理等工作带来了不小的麻烦，随着业务规模的发展，问题愈发严重。同样在经过调研之后，他们也选择了TDengine。在升级改造的过程中，他们需要保留历史数据，所以需要将历史数据从OpenTSDB迁移到TDengine。为此他们还专门开发了一个数据迁移工具，并进行了详尽的测试。

用户的需求就是产品演进的动力。TDengine的研发团队开始思考这个问题：既然很多用户都有这种迁移需求，那是不是可以官方给出一个统一的解决方案呢？

taosAdapter就是我们的答案。taosAdapter主要有以下功能：

• RESTful 接口
• 兼容InfluxDB v1 write 接口
• 兼容OpenTSDB JSON 和 Telnet 格式写入
• 无缝连接Telegraf、collectd、StatsD、Icinga、TCollector

它能够兼容OpenTSDB的Telnet/JSON写入协议，对于运维监控类业务，用户可以将collectd和StatsD收集的数据通过taosAdapter直接推送到TDengine。在数据能够正常写入TDengine后，可以调整适配Grafana，将写入TDengine的数据以可视化方式呈现出来。TDengine也为Grafana提供了连接插件。如果要迁移历史数据，涛思数据还开发了数据同步工具DataX的插件，能够帮助用户将数据自动写入到TDengine中。用户无需修改任何一行代码，只需要改几个配置，即可无缝迁移。

下一步，taosAdapter也将继续完善，支持从更多平台向TDengine迁移。

🌟点击链接，探索taosAdapter！

本文转载自: 掘金

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

JSON处理：

SpringMVC默认的Json解决方案是Jackson,所以只需要导入jackson的jar，即可使用

(1) 导入依赖

(2)使用ResponseBody

当返回值不是字符串时，将handle返回值自动转为json并返回给客户端。
返回中文时可能会有乱码，此时只需要在ResquestMapping注解加上字符集设置即可

(3)使用RestController

Controller类上加上了@RestController注解，等价于在类的每个方法上都加了@ResponseBody

(4)使用@RequestBody

@RequestBody的作用，接收json参数

定义handler：

下面是一个实际的例子，将一个json格式字符串userJson发送到json/test4中。

(5)Jackson常用注解

5.1 日期格式化

5.2 属性名修改

5.3 属性忽略

5.4 null和empty属性排除
Jackson 默认会输出null值的属性，如果不需要，可以排除。

@JsonInclude (JsonInclude.Include.NON_NULL) // null值属性不输出

@JsonInclude (value = JsonInclude.NON_EMPTY) //empty属性不输出（空串，长度为0的集合,null值）

5.5 自定义序列化
@JsonSeriallize(using = MySerializer.class) // 使用MySerializer输出某属性

本文转载自: 掘金

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

「这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战」

简介

树是类似于链表的数据结构，和链表的线性结构不同的是，树是具有层次结构的非线性的数据结构。

树是由很多个节点组成的，每个节点可以指向很多个节点。

如果一个树中的每个节点都只有0，1，2个子节点的话，这颗树就被称为二叉树，如果我们对二叉树进行一定的排序。

比如，对于二叉树中的每个节点，如果左子树节点的元素都小于根节点，而右子树的节点的元素都大于根节点，那么这样的树被叫做二叉搜索树（Binary Search Tree）简称BST。

今天我们来探讨一下BST的性质和对BST的基本操作。

BST的基本性质

刚刚我们已经讲过BST的基本特征了，现在我们再来总结一下：

1. BST中任意节点的左子树一定要比该节点的值要小
2. BST中任意节点的右子树一定要比该节点的值要大
3. BST中任意节点的左右子树一定要是一个BST。

看一张图直观的感受一下BST：

BST的构建

怎么用代码来构建一个BST呢？

首先，BST是由一个一个的节点Node组成的，Node节点除了保存节点的数据之外，还需要指向左右两个子节点，这样我们的BST完全可以由Node连接而成。

另外我们还需要一个root节点来表示BST的根节点。

相应的代码如下：

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

java复制代码public class BinarySearchTree {

    //根节点
    Node root;

    class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
}

BST的搜索

先看下BST的搜索，如果是上面的BST，我们想搜索32这个节点应该是什么样的步骤呢？

先上图：

搜索的基本步骤是：

1. 从根节点41出发，比较根节点和搜索值的大小
2. 如果搜索值小于节点值，那么递归搜索左侧树
3. 如果搜索值大于节点值，那么递归搜索右侧树
4. 如果节点匹配，则直接返回即可。

相应的java代码如下：

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

java复制代码//搜索方法，默认从根节点搜索
    public Node search(int data){
        return search(root,data);
    }

    //递归搜索节点
    private Node search(Node node, int data)
    {
        // 如果节点匹配，则返回节点
        if (node==null || node.data==data)
            return node;

        // 节点数据大于要搜索的数据，则继续搜索左边节点
        if (node.data > data)
            return search(node.left, data);

        // 如果节点数据小于要搜素的数据，则继续搜索右边节点
        return search(node.right, data);
    }

BST的插入

搜索讲完了，我们再讲BST的插入。

先看一个动画：

上的例子中，我们向BST中插入两个节点30和55。

插入的逻辑是这样的：

1. 从根节点出发，比较节点数据和要插入的数据
2. 如果要插入的数据小于节点数据，则递归左子树插入
3. 如果要插入的数据大于节点数据，则递归右子树插入
4. 如果根节点为空，则插入当前数据作为根节点

相应的java代码如下：

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

java复制代码// 插入新节点，从根节点开始插入
    public void insert(int data) {
        root = insert(root, data);
    }

    //递归插入新节点
    private Node insert(Node node, int data) {

        //如果节点为空，则创建新的节点
        if (node == null) {
            node = new Node(data);
            return node;
        }

        //节点不为空，则进行比较，从而递归进行左侧插入或者右侧插入
        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);

        //返回插入后的节点
        return node;
    }

BST的删除

BST的删除要比插入复杂一点，因为插入总是插入到叶子节点，而删除可能删除的是非叶子节点。

我们先看一个删除叶子节点的例子：

上面的例子中，我们删除了30和55这两个节点。

可以看到，删除叶子节点是相对简单的，找到之后删除即可。

我们再来看一个比较复杂的例子，比如我们要删除65这个节点：

可以看到需要找到65这个节点的右子树中最小的那个，替换掉65这个节点即可（当然也可以找到左子树中最大的那个）。

所以删除逻辑是这样的：

1. 从根节点开始，比较要删除节点和根节点的大小
2. 如果要删除节点比根节点小，则递归删除左子树
3. 如果要删除节点比根节点大，则递归删除右子树
4. 如果节点匹配，又有两种情况
5. 如果是单边节点，直接返回节点的另外一边
6. 如果是双边节点，则先找出右边最小的值，作为根节点，然后将删除最小值过后的右边的节点，作为根节点的右节点

看下代码的实现：

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

java复制代码 // 删除新节点，从根节点开始删除
    void delete(int data)
    {
        root = delete(root, data);
    }

    //递归删除节点
    Node delete(Node node, int data)
    {
        //如果节点为空，直接返回
        if (node == null)  return node;

        //遍历左右两边的节点
        if (data < node.data)
            node.left = delete(node.left, data);
        else if (data > root.data)
            node.right = delete(node.right, data);

        //如果节点匹配
        else
        {
            //如果是单边节点，直接返回其下面的节点
            if (node.left == null)
                return node.right;
            else if (node.right == null)
                return node.left;

            //如果是双边节点，则先找出右边最小的值，作为根节点，然后将删除最小值过后的右边的节点，作为根节点的右节点
            node.data = minValue(node.right);

            // 从右边删除最小的节点
            node.right = delete(node.right, node.data);
        }
        return node;
    }

这里我们使用递归来实现的删除双边节点，大家可以考虑一下有没有其他的方式来删除呢？

本文的代码地址：

learn-algorithm

本文收录于 <www.flydean.com>

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

本文转载自: 掘金

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

这是我参与11月更文挑战的第30天，活动详情查看：2021最后一次更文挑战

什么是布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

实现原理

HashMap 的问题

讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成**多个哈希值，**并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：

Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：

值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

这是为什么呢？答案很简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

python实现布隆过滤器-手动定义布隆

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

python复制代码import mmh3
from bitarray import bitarray


# Implement a simple bloom filter with murmurhash algorithm.
# Bloom filter is used to check whether an element exists in a collection,
# and it has a good performance in big data situation.
# It may has positive rate depend on hash functions and elements count.


BIT_SIZE = 5000000


class BloomFilter:

    def __init__(self, bit_size=BIT_SIZE):
        # Initialize bloom filter, set size and all bits to 0
        self.bit_size = bit_size
        self.bit_array = bitarray(self.bit_size)
        self.bit_array.setall(0)

    def add(self, url):
        # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.)
        # Here use 7 hash functions.
        point_list = self.get_positions(url)

        for b in point_list:
            self.bit_array[b] = 1

    def is_contain(self, url):
        # Check if a url is in a collection
        point_list = self.get_positions(url)
        is_contain = True
        for b in point_list:
            is_contain = is_contain and self.bit_array[b]
        return is_contain

    def get_positions(self, url):
        # Get points positions in bit vector.
        return [mmh3.hash(url, 41+i) % self.bit_size for i in range(7)]


if __name__ == '__main__':
    bl = BloomFilter()
    bl.add('baidu')
    result = bl.is_contain('baidu11')
    print(result)

Python中使用布隆过滤器-基于线程模块

安装模块：bitarray、pybloom_live

1
2
3
4
5

python复制代码#python3.6 安装
#需要先安装bitarray
pip3 install bitarray-0.8.1-cp36-cp36m-win_amd64.whl（pybloom_live依赖这个包，需要先安装）
#下载地址：https://www.lfd.uci.edu/~gohlke/pythonlibs/
pip3 install pybloom_live

示例一

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

python复制代码#ScalableBloomFilter 可以自动扩容
from pybloom_live import ScalableBloomFilter

bloom = ScalableBloomFilter(
    initial_capacity=100, 
    error_rate=0.001, 
    mode=ScalableBloomFilter.LARGE_SET_GROWTH
)

url = "www.cnblogs.com"
url2 = "www.sougou.com"

bloom.add(url)

print(url in bloom)		# 存在返回True
print(url2 in bloom)	# 不存在返回False

示例二

1
2
3
4
5
6
7
8
9
10

python复制代码Copy#BloomFilter 是定长的
from pybloom_live import BloomFilter

bf = BloomFilter(capacity=1000)
url='www.baidu.com'
bf.add(url)

print(url in bf)

print("www.sougou.com" in bf)

结语

文章首发于微信公众号程序媛小庄，同步于掘金。

码字不易，转载请说明出处，走过路过的小伙伴们伸出可爱的小指头点个赞再走吧(╹▽╹)

本文转载自: 掘金

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

这是我参与11月更文挑战的第30天，活动详情查看：2021最后一次更文挑战

单例模式

单例模式是一个软件的设计模式，为了保证一个类，无论调用多少次产生的实例对象，都是指向同一个内存地址，仅仅只有一个实例（只有一个对象）。

单例模式的优点

1、由于单例模式要求在全局内只有一个实例，因而可以节省比较多的内存空间；
2、全局只有一个接入点，可以更好地进行数据同步控制，避免多重占用；
3、单例可长驻内存，减少系统开销。

单例模式的缺点

1、单例模式的扩展是比较困难的；
2、赋于了单例以太多的职责，某种程度上违反单一职责原则;
3、单例模式是并发协作软件模块中需要最先完成的，因而其不利于测试；
4、单例模式在某种情况下会导致“资源瓶颈”。

单例模式的应用举例

1、生成全局惟一的序列号；
2、访问全局复用的惟一资源，如磁盘、总线等；
3、单个对象占用的资源过多，如数据库等；
4、系统全局统一管理，如Windows下的Task Manager；
5、网站计数器。

设计模式

设计模式是面对各种问题进行提炼和抽象而形成的解决方案。这些设计方案是前人不断试验，考虑了封装性、复用性、效率、可修改、可移植等各种因素的高度总结。它不限于一种特定的语言，它是一种解决问题的思想和方法

补充：常见设计模式，设计模式也衍生出了很多的新的种类，不局限于这23种

设计模式可以分为三个大类：创建类设计模式、结构类设计模式、行为类设计模式

创建类设计模式（5种）

单例模式、工厂模式（简单工厂模式、抽象工厂模式）、建造者模式、原型模式

结构类设计模式（7种）

代理模式、装饰器模式、适配器模式、门面模式、组合模式、享元模式、桥梁模式

行为类设计模式（11种）

策略模式、责任链模式、命令模式、中介者模式、模板模式、迭代器模式、访问者模式、观察者模式、解释器模式、备忘录模式、状态模式

实现单例模式

实现单例模式的手段有很多种，但总的原则是保证一个类只要实例化一个对象，下一次再实例的时候就直接返回这个对象，不再做实例化的操作。所以这里面的关键一点就是，如何判断这个类是否实例化过一个对象。

这里介绍两类方式：

• 一类是通过模块导入的方式；
• 一类是通过魔法方法判断的方式；

1
2
3
4
5
6
7
8
9

python复制代码# 基本原理：
- 第一类通过模块导入的方式，借用了模块导入时的底层原理实现。
- 当一个模块（py文件）被导入时，首先会执行这个模块的代码，然后将这个模块的名称空间加载到内存。
- 当这个模块第二次再被导入时，不会再执行该文件，而是直接在内存中找。
- 于是，如果第一次导入模块，执行文件源代码时实例化了一个类，那再次导入的时候，就不会再实例化。

- 第二类主要是基于类和元类实现，在'对象'的魔法方法中判断是否已经实例化过一个对象
- 这类方式，根据实现的手法不同，又分为不同的方法，如：
- 通过类的绑定方法；通过元类；通过类下的__new__；通过装饰器（函数装饰器，类装饰器）实现等。

下面分别介绍这几种不同的实现方式，仅供参考实现思路，不做具体需求。

通过模块导入

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

python复制代码# cls_singleton.py
class Foo(object):
    pass

instance = Foo()

# test.py
import cls_singleton

obj1 = cls_singleton.instance
obj2 = cls_singleton.instance
print(obj1 is obj2)

# 原理：模块第二次导入从内存找的机制

通过类的绑定方法

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

python复制代码class Student:
    _instance = None	# 记录实例化对象

    def __init__(self, name, age):
        self.name = name
        self.age = age

    @classmethod
    def get_singleton(cls, *args, **kwargs):
        if not cls._instance:
            cls._instance = cls(*args, **kwargs)
        return cls._instance

stu1 = Student.get_singleton('jack', 18)
stu2 = Student.get_singleton('jack', 18)
print(stu1 is stu2)
print(stu1.__dict__, stu2.__dict__)

# 原理：类的绑定方法是第二种实例化对象的方式，
# 第一次实例化的对象保存成类的数据属性 _instance，
# 第二次再实例化时，在get_singleton中判断已经有了实例对象，直接返回类的数据属性 _instance

补充：这种方式实现的单例模式有一个明显的bug；bug的根源在于如果用户不通过绑定类的方法实例化对象，而是直接通过类名加括号实例化对象，那这样不再是单利模式了。

通过魔法方法__new__

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

python复制代码class Student:

    _instance = None

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __new__(cls, *args, **kwargs):
        # if cls._instance:
        #     return cls._instance	                # 有实例则直接返回
        # else:
        #     cls._instance = super().__new__(cls)	# 没有实例则new一个并保存
        #     return cls._instance	                # 这个返回是给是给init，再实例化一次，也没有关系

        if not cls._instance:	                        # 这是简化的写法，上面注释的写法更容易提现判断思路
            cls._instance = super().__new__(cls)
        return cls._instance


stu1 = Student('jack', 18)
stu2 = Student('jack', 18)
print(stu1 is stu2)
print(stu1.__dict__, stu2.__dict__)

# 原理：和方法2类似，将判断的实现方式，从类的绑定方法中转移到类的__new__中
# 归根结底都是 判断类有没有实例，有则直接返回，无则实例化并保存到_instance中。

补充：这种方式可以近乎完美地实现单例模式，但是依然不够完美。不完美的地方在于没有考虑到并发的极端情况下，有可能多个线程同一时刻实例化对象。关于这一点的补充内容在本文的最后一节介绍(!!!进阶必会)。

通过元类

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

python复制代码class Mymeta(type):

    def __init__(cls, name, bases, dic):
        super().__init__(name, bases, dic)
        cls._instance = None		                  # 将记录类的实例对象的数据属性放在元类中自动定义了

    def __call__(cls, *args, **kwargs):	                  # 此call会在类被调用（即实例化时触发）
        if cls._instance:				  # 判断类有没有实例化对象
            return cls._instance
        else:						  # 没有实例化对象时，控制类造空对象并初始化
            obj = cls.__new__(cls, *args, **kwargs)
            obj.__init__(*args, **kwargs)
            cls._instance = obj			          # 保存对象，下一次再实例化可以直接返回而不用再造对象
            return obj
        
        	# 上述四行代码可以简写为下述两行代码
            # cls._instance = super().__call__(cls, *args, **kwargs)
            # return  cls._instance


class Student(metaclass=Mymeta):
    def __init__(self, name, age):
        self.name = name
        self.age = age


stu1 = Student('jack', 18)
stu2 = Student('jack', 18)
print(stu1 is stu2)
print(stu1.__dict__, stu2.__dict__)

# 原理：类定义时会调用元类下的__init__，类调用(实例化对象)时会触发元类下的__call__方法
# 类定义时，给类新增一个空的数据属性，
# 第一次实例化时，实例化之后就将这个对象赋值给类的数据属性；第二次再实例化时，直接返回类的这个数据属性
# 和方式3的不同之处1：类的这个数据属性是放在元类中自动定义的，而不是在类中显示的定义的。
# 和方式3的不同之处2：类调用时触发元类__call__方法判断是否有实例化对象，而不是在类的绑定方法中判断

函数装饰器

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

python复制代码def singleton(cls):
    _instance_dict = {}		                  # 采用字典，可以装饰多个类，控制多个类实现单例模式
  
    def inner(*args, **kwargs):
        if cls not in _instance_dict:
            _instance_dict[cls] = cls(*args, **kwargs)
        return _instance_dict.get(cls)
    return inner


@singleton
class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    # def __new__(cls, *args, **kwargs):	  # 将方法3的这部分代码搬到了函数装饰器中
    #     if not cls._instance:
    #         cls._instance = super().__new__(cls)
    #     return cls._instan
    
stu1 = Student('jack', 18)
stu2 = Student('jack', 18)
print(stu1 is stu2)
print(stu1.__dict__, stu2.__dict__)

类装饰器

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

python复制代码class SingleTon:
    _instance_dict = {}

    def __init__(self, cls_name):
        self.cls_name = cls_name

    def __call__(self, *args, **kwargs):
        if self.cls_name not in SingleTon._instance_dict:
            SingleTon._instance_dict[self.cls_name] = self.cls_name(*args, **kwargs)
        return SingleTon._instance_dict.get(self.cls_name)


@SingleTon		                              # 这个语法糖相当于Student = SingleTon(Student),即Student是SingleTon的实例对象
class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age

stu1 = Student('jack', 18)
stu2 = Student('jack', 18)
print(stu1 is stu2)
print(stu1.__dict__, stu2.__dict__)

# 原理：在函数装饰器的思路上，将装饰器封装成类。
# 程序执行到与语法糖时，会实例化一个Student对象，这个对象是SingleTon的对象。
# 后面使用的Student本质上使用的是SingleTon的对象。
# 所以使用Student('jack', 18)来实例化对象，其实是在调用SingleTon的对象，会触发其__call__的执行
# 所以就在__call__中，判断Student类有没有实例对象了。

!!!进阶必会

本部分主要是补充介绍多线程并发情况下，多线程高并发时，如果同时有多个线程同一时刻（极端条件下）事例化对象，那么就会出现多个对象，这就不再是单例模式了。

解决这个多线程并发带来的竞争问题，第一个想到的是加互斥锁，于是我们就用互斥锁的原理来解决这个问题。

解决的关键点，无非就是将具体示例化操作的部分加一把锁，这样同时来的多个线程就需要排队。

这样一来只有第一个抢到锁的线程实例化一个对象并保存在_instance中，同一时刻抢锁的其他线程再抢到锁后，不会进入这个判断if not cls._instance，直接把保存在_instance的对象返回了。这样就实现了多线程下的单例模式。

此时还有一个问题需要解决，后面所有再事例对象时都需要再次抢锁，这会大大降低执行效率。解决这个问题也很简单，直接在抢锁前，判断下是否有单例对象了，如果有就不再往下抢锁了（代码第11行判断存在的意义）。

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

python复制代码import threading

class Student:
    _instance = None				# 保存单例对象
    _lock = threading.RLock()		        # 锁

    def __new__(cls, *args, **kwargs):
        if cls._instance:			# 如果已经有单例了就不再去抢锁，避免IO等待
            return cls._instance
        
        with cls._lock:				# 使用with语法，方便抢锁释放锁
            if not cls._instance:	
                cls._instance = super().__new__(cls, *args, **kwargs)
            return cls._instance

结语

文章首发于微信公众号程序媛小庄，同步于掘金。

码字不易，转载请说明出处，走过路过的小伙伴们伸出可爱的小指头点个赞再走吧(╹▽╹)

本文转载自: 掘金

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