内存区域

JDK 1.8 和之前的 JVM 内存区域有所不同。

当应用程序发起 IO 系统调用后，会经历两个阶段：

• 内核等待 I/O 设备准备好数据。
• 内核将数据从内核空间拷贝到用户空间。

BIO

BIO（Blocking IO）属于同步阻塞 IO，应用程序发起 read 调用后，会一直阻塞，直到内核把数据拷贝到用户空间。BIO 因为应用程序一直阻塞，直到系统调用返回，所以效率不高。

NIO

NIO（Non-blocking/New IO），可以看作是多路复用 IO，Java 在 1.4 中引入 java.nio 包，提供了 Channel , Selector，Buffer 等抽象。

IO 多路复用模型中，线程首先发起 select 调用，询问内核数据是否准备就绪，等内核把数据准备好了，用户线程再发起 read 调用。read 调用的过程（数据从内核空间 -> 用户空间）还是阻塞的。IO 多路复用模型，通过减少无效的系统调用，减少了对 CPU 资源的消耗。

NIO 核心组件

Java 中的 NIO ，有一个非常重要的选择器 ( Selector ) 的概念，也可以被称为 多路复用器。通过它，只需要一个线程便可以管理多个客户端连接。当客户端数据到了之后，才会为其服务。

Buffer（缓冲区）：NIO 读写数据都是通过缓冲区进行操作的。读操作的时候将 Channel 中的数据填充到 Buffer 中，而写操作时将 Buffer 中的数据写入到 Channel 中。

Channel（通道）：Channel 是一个双向的、可读可写的数据传输通道，NIO 通过 Channel 来实现数据的输入输出。通道是一个抽象的概念，它可以代表文件、套接字或者其他数据源之间的连接。

Selector（选择器）：允许一个线程处理多个 Channel，基于事件驱动的 I/O 多路复用模型。所有的 Channel 都可以注册到 Selector 上，由 Selector 来分配线程来处理事件。

类比于 Golang：

• Channel 和 Buffer：可以看作是 channel 和 channel 的缓冲区。
• Selecter：go select

Buffer

在 Java nio 库中，所有数据都是用缓冲区处理的。使用 NIO 在读写数据时，都是通过缓冲区进行操作。

Buffer 的子类如下图所示。其中，最常用的是 ByteBuffer，它可以用来存储和操作字节数据。

Buffer 有四个成员变量：

• 容量 capacity：Buffer 可以存储的最大容量，创建时设置且不可改变。
• 界限 limit：Buffer 中可以读/写数据的边界。写模式下，limit 表示最多能写入的数据；读模式下，limit 表示最多能读取的数据。
• 位置 position：下一个可以被读写的数据的位置。从写操作模式到读操作模式切换的时候（flip），position 都会归零，这样就可以从头开始读写了。从读模式到写模式（clear），position 会归零，limit 设置为 capacity。
• 标记 mark：Buffer 允许将位置直接定位到该标记处，这是一个可选属性

Buffer 有读模式和写模式这两种模式，分别用于从 Buffer 中读取数据或者向 Buffer 中写入数据。Buffer 被创建之后默认是写模式，调用 flip 可以切换到读模式。如果要再次切换回写模式，可以调用 clear 或者 compact 方法。

Buffer 对象不能通过 new 调用构造方法创建对象 ，只能通过静态方法实例化 Buffer。

1
2
3
4

// 分配堆内存
public static ByteBuffer allocate(int capacity);
// 分配直接内存
public static ByteBuffer allocateDirect(int capacity);

Channel

Channel 是一个通道，它建立了与数据源（如文件、网络套接字等）之间的连接。Channel 和 Buffer 交互，读操作的时候将 Channel 中的数据填充到 Buffer 中，而写操作时将 Buffer 中的数据写入到 Channel 中。

通道与流的不同之处在于通道是双向的，它可以用于读、写或者同时用于读写。

Channel 的子类如下所示：

其中，最常用的是以下几种类型的通道：

• FileChannel：文件访问通道；
• SocketChannel、ServerSocketChannel：TCP 通信通道；
• DatagramChannel：UDP 通信通道；

Channel 最核心的两个方法：

1. read ：读取数据并写入到 Buffer 中。
2. write ：将 Buffer 中的数据写入到 Channel 中。

1
2
3
4

RandomAccessFile reader = new RandomAccessFile("/Users/guide/Documents/test_read.in", "r"))
FileChannel channel = reader.getChannel();
ByteBuffer buffer = ByteBuffer.allocate(1024);
channel.read(buffer);

Selector

Selector（选择器） 是 NIO 中的一个关键组件，它允许一个线程处理多个 Channel。

Selector 是基于事件驱动的 I/O 多路复用模型，主要运作原理是：通过 Selector 注册通道的事件，Selector 会不断地轮询注册在其上的 Channel。当事件发生时，比如：某个 Channel 上面有新的 TCP 连接接入、读和写事件，这个 Channel 就处于就绪状态，会被 Selector 轮询出来。Selector 会将相关的 Channel 加入到就绪集合中。通过 SelectionKey 可以获取就绪 Channel 的集合，然后对这些就绪的 Channel 进行相应的 I/O 操作。

一个多路复用器 Selector 可以同时轮询多个 Channel，由于 JDK 使用了 epoll() 代替传统的 select 实现，所以它并没有最大连接句柄 1024/2048 的限制。这也就意味着只需要一个线程负责 Selector 的轮询，就可以接入成千上万的客户端。

Selector 可以监听以下四种事件类型：

1. SelectionKey.OP_ACCEPT：表示通道接受连接的事件，这通常用于 ServerSocketChannel。
2. SelectionKey.OP_CONNECT：表示通道完成连接的事件，这通常用于 SocketChannel。
3. SelectionKey.OP_READ：表示通道准备好进行读取的事件，即有数据可读。
4. SelectionKey.OP_WRITE：表示通道准备好进行写入的事件，即可以写入数据。

Selector 是抽象类，可以通过调用此类的 open() 静态方法来创建 Selector 实例。Selector 可以同时监控多个 SelectableChannel 的 IO 状况，是非阻塞 IO 的核心。

一个 Selector 实例有三个 SelectionKey 集合：

1. 所有的 SelectionKey 集合：代表了注册在该 Selector 上的 Channel，这个集合可以通过 keys() 方法返回。
2. 被选择的 SelectionKey 集合：代表了所有可通过 select() 方法获取的、需要进行 IO 处理的 Channel，这个集合可以通过 selectedKeys() 返回。
3. 被取消的 SelectionKey 集合：代表了所有被取消注册关系的 Channel，在下一次执行 select() 方法时，这些 Channel 对应的 SelectionKey 会被彻底删除，程序通常无须直接访问该集合，也没有暴露访问的方法。

Selector 还提供了一系列和 select() 相关的方法：

• int select()：监控所有注册的 Channel，当它们中间有需要处理的 IO 操作时，该方法返回，并将对应的 SelectionKey 加入被选择的 SelectionKey 集合中，该方法返回这些 Channel 的数量。
• int select(long timeout)：可以设置超时时长的 select() 操作。
• int selectNow()：执行一个立即返回的 select() 操作，相对于无参数的 select() 方法而言，该方法不会阻塞线程。
• Selector wakeup()：使一个还未返回的 select() 方法立刻返回.

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

import java.io.IOException;
import java.net.InetSocketAddress;
import java.nio.ByteBuffer;
import java.nio.channels.SelectionKey;
import java.nio.channels.Selector;
import java.nio.channels.ServerSocketChannel;
import java.nio.channels.SocketChannel;
import java.util.Iterator;
import java.util.Set;

public class NioSelectorExample {

  public static void main(String[] args) {
    try {
      ServerSocketChannel serverSocketChannel = ServerSocketChannel.open();
      serverSocketChannel.configureBlocking(false);
      serverSocketChannel.socket().bind(new InetSocketAddress(8080));

      Selector selector = Selector.open();
      // 将 ServerSocketChannel 注册到 Selector 并监听 OP_ACCEPT 事件
      serverSocketChannel.register(selector, SelectionKey.OP_ACCEPT);

      while (true) {
        int readyChannels = selector.select();

        if (readyChannels == 0) {
          continue;
        }

        Set<SelectionKey> selectedKeys = selector.selectedKeys();
        Iterator<SelectionKey> keyIterator = selectedKeys.iterator();

        while (keyIterator.hasNext()) {
          SelectionKey key = keyIterator.next();

          if (key.isAcceptable()) {
            // 处理连接事件
            ServerSocketChannel server = (ServerSocketChannel) key.channel();
            SocketChannel client = server.accept();
            client.configureBlocking(false);

            // 将客户端通道注册到 Selector 并监听 OP_READ 事件
            client.register(selector, SelectionKey.OP_READ);
          } else if (key.isReadable()) {
            // 处理读事件
            SocketChannel client = (SocketChannel) key.channel();
            ByteBuffer buffer = ByteBuffer.allocate(1024);
            int bytesRead = client.read(buffer);

            if (bytesRead > 0) {
              buffer.flip();
              System.out.println("收到数据：" +new String(buffer.array(), 0, bytesRead));
              // 将客户端通道注册到 Selector 并监听 OP_WRITE 事件
              client.register(selector, SelectionKey.OP_WRITE);
            } else if (bytesRead < 0) {
              // 客户端断开连接
              client.close();
            }
          } else if (key.isWritable()) {
            // 处理写事件
            SocketChannel client = (SocketChannel) key.channel();
            ByteBuffer buffer = ByteBuffer.wrap("Hello, Client!".getBytes());
            client.write(buffer);

            // 将客户端通道注册到 Selector 并监听 OP_READ 事件
            client.register(selector, SelectionKey.OP_READ);
          }

          keyIterator.remove();
        }
      }
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
}

NIO 直接读取 零拷贝

直接读取

MappedByteBuffer 是 NIO 基于内存映射（mmap）这种零拷贝方式的提供的⼀种实现，底层实际是调用了 Linux 内核的 mmap 系统调用。

它可以将一个文件或者文件的一部分映射到内存中，形成一个虚拟内存文件，这样就可以直接操作内存中的数据，而不需要通过系统调用来读写文件。

1
2
3
4
5
6
7
8
9
10

private void loadFileIntoMemory(File xmlFile) throws IOException {
  FileInputStream fis = new FileInputStream(xmlFile);
  // 创建 FileChannel 对象
  FileChannel fc = fis.getChannel();
  // FileChannel.map() 将文件映射到直接内存并返回 MappedByteBuffer 对象
  MappedByteBuffer mmb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
  xmlFileBuffer = new byte[(int)fc.size()];
  mmb.get(xmlFileBuffer);
  fis.close();
}

零拷贝

FileChannel 的transferTo()/transferFrom()是 NIO 基于发送文件（sendfile）这种零拷贝方式的提供的一种实现，底层实际是调用了 Linux 内核的 sendfile系统调用。

它可以直接将文件数据从磁盘发送到网络，而不需要经过用户空间的缓冲区。

AIO

AIO（Asynchronous IO）异步 IO，Java 7 中引入。异步 IO 是基于事件和回调机制实现的，也就是应用操作之后会直接返回，不会堵塞在那里，当后台处理完成，操作系统会通知相应的线程进行后续的操作。

IO 设计模式

在 Java IO 中，所用到的设计模式总结。

装饰器模式

装饰器（Decorator）模式 可以在不改变原有对象的情况下拓展其功能。

对于字节流，FilterInputStream 和 FilterOutputStream 是装饰器模式的核心，用于增强 InputStream 和 OutputStream 子类对象的功能。

对于装饰器类而言，构造器的输入为被装饰类，同时可以嵌套多个装饰器。所以，装饰器类需要跟原始类继承相同的抽象类或者实现相同的接口。

举例，BufferedInputStream 为 InputStream 提供了缓冲功能，ZipOutputStream 为 OutputStream 提供了 zip 压缩功能，他们的构造函数都是输出一个 InputStream 或者 OutputStream。

适配器模式

适配器（Adapter Pattern）模式 主要用于接口互不兼容的类的协调工作，适配器模式中存在被适配的对象或者类称为适配者(Adaptee) ，作用于适配者的对象或者类称为适配器(Adapter) 。适配器分为对象适配器和类适配器。类适配器使用继承关系来实现，对象适配器使用组合关系来实现。

IO 流中的字符流和字节流的接口不同，它们之间可以协调工作就是基于适配器模式来做的，更准确点来说是对象适配器。通过适配器，可以将字节流对象适配成一个字符流对象，可以直接通过字节流对象来读取或者写入字符数据。

InputStreamReader OutputStreamWriter

之前提到的 InputStreamReader 和 OutputStreamWriter 就是两个适配器，是字节流和字符流之间的桥梁。

• InputStreamReader 使用 StreamDecoder（流解码器）对字节进行解码，实现字节流到字符流的转换。
• OutputStreamWriter 使用 StreamEncoder（流编码器）对字节进行编码，实现字符流到字节流的转换。

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

public class InputStreamReader extends Reader {
 //用于解码的对象
 private final StreamDecoder sd;
    public InputStreamReader(InputStream in) {
        super(in);
        try {
            // 获取 StreamDecoder 对象
            sd = StreamDecoder.forInputStreamReader(in, this, (String)null);
        } catch (UnsupportedEncodingException e) {
            throw new Error(e);
        }
    }
    // 使用 StreamDecoder 对象做具体的读取工作
 public int read() throws IOException {
        return sd.read();
    }
}

工厂模式

工厂模式用于创建对象，NIO 中大量用到了工厂模式，比如 Files 类的 newInputStream 方法用于创建 InputStream 对象（静态工厂）、 Paths 类的 get 方法创建 Path 对象（静态工厂）、ZipFileSystem 类（sun.nio包下的类，属于 java.nio 相关的一些内部实现）的 getPath 的方法创建 Path 对象（简单工厂）。

1

InputStream is = Files.newInputStream(Paths.get(generatorLogoPath))

观察者模式

NIO 中的文件目录监听服务使用到了观察者模式。NIO 中的文件目录监听服务基于 WatchService 接口和 Watchable 接口。WatchService 属于观察者，Watchable 属于被观察者。使用方法如下：

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

// 创建 WatchService 对象
WatchService watchService = FileSystems.getDefault().newWatchService();

// 初始化一个被监控文件夹的 Path 类:
Path path = Paths.get("workingDirectory");
// 将这个 path 对象注册到 WatchService（监控服务） 中去
WatchKey watchKey = path.register(watchService, StandardWatchEventKinds...);

while ((key = watchService.take()) != null) {
    for (WatchEvent<?> event : key.pollEvents()) {
      // 可以调用 WatchEvent 对象的方法做一些事情比如输出事件的具体上下文信息
    }
    key.reset();
}

Watchable

Path 实现了 Watchable 接口，说明 Path 是被观察者。Watchable 接口中，watcher 指定了观察者，events 指定了被观察的事件（监听事件）。常用的监听事件：StandardWatchEventKinds.ENTRY_CREATE：文件创建；StandardWatchEventKinds.ENTRY_DELETE : 文件删除；StandardWatchEventKinds.ENTRY_MODIFY : 文件修改。

1
2
3
4
5
6
7
8
9
10

public interface Path
    extends Comparable<Path>, Iterable<Path>, Watchable{
}

public interface Watchable {
    WatchKey register(WatchService watcher,
                      WatchEvent.Kind<?>[] events,
                      WatchEvent.Modifier... modifiers)
        throws IOException;
}

WatchService

WatchService 内部通过一个 daemon thread（守护线程）采用定期轮询的方式来检测文件的变化，伪代码如下：

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

class PollingWatchService
    extends AbstractWatchService
{
    // 定义一个 daemon thread（守护线程）轮询检测文件变化
    private final ScheduledExecutorService scheduledExecutor;

    PollingWatchService() {
        scheduledExecutor = Executors
            .newSingleThreadScheduledExecutor(new ThreadFactory() {
                 @Override
                 public Thread newThread(Runnable r) {
                     Thread t = new Thread(r);
                     t.setDaemon(true);
                     return t;
                 }});
    }

  void enable(Set<? extends WatchEvent.Kind<?>> events, long period) {
    synchronized (this) {
      // 更新监听事件
      this.events = events;

        // 开启定期轮询
      Runnable thunk = new Runnable() { public void run() { poll(); }};
      this.poller = scheduledExecutor
        .scheduleAtFixedRate(thunk, period, period, TimeUnit.SECONDS);
    }
  }
}

IO 流在 Java 中分为输入流和输出流，按照传输单位（数据处理方式）又分为字节流和字符流。Java 有四个 IO 流抽象类基类：

• InputStream/OutputStream：字节输入流，字节输出流。
• Reader/Writer：字符输入流，字符输出流。

字节流

InputStream

InputStream 用于从源头（如文件）读取字节数据到内存中，InputStream 的常用用法：

• read()：返回输入流中下一个字节的数据。返回的值介于 0 到 255 之间。如果未读取任何字节，则代码返回 -1 ，表示文件结束。
• read(byte b[ ]) : 从输入流中读取一些字节存储到数组 b 中。如果数组 b 的长度为零，则不读取。如果没有可用字节读取，返回 -1。如果有可用字节读取，则最多读取的字节数最多等于 b.length ， 返回读取的字节数。这个方法等价于 read(b, 0, b.length)。
• read(byte b[], int off, int len)：在 read(byte b[ ]) 方法的基础上增加了 off 参数（偏移量）和 len 参数（要读取的最大字节数）。
• skip(long n)：忽略输入流中的 n 个字节 ,返回实际忽略的字节数。
• available()：返回输入流中可以读取的字节数。
• close()：关闭输入流释放相关的系统资源。

从 Java 9 开始，InputStream 新增加了多个实用的方法：

• readAllBytes()：读取输入流中的所有字节，返回字节数组。
• readNBytes(byte[] b, int off, int len)：阻塞直到读取 len 个字节。
• transferTo(OutputStream out)：将所有字节从一个输入流传递到一个输出流。

常见 InputStream

常用的 InputStream 如下：

• FileInputStream：用于读取文件。
• BufferInputStream：带缓冲区的 InputStream，缓冲区缓冲数据，有助于减少 IO。
• DataInputStream：用于读取指定类型数据，如 readBoolean、readInt、readUTF 等。
• ObjectInputStream：用于从输入流中读取 Java 对象（反序列化）。

OnjectInputStream 用于序列化和反序列化的类必须实现 Serializable 接口，对象中如果有属性不想被序列化，使用 transient 修饰。

Map

HashMap

HashMap 和 Hashtable 的区别

HashMap 和 Hashtable 的区别如下：

• 线程安全：HashMap 不是线程安全的，Hashtable 是线程安全的（函数都由 synchronized 修饰，但是锁的粒度很大，并发度为一）。
• 效率：HashMap 效率更高，因为 Hashtable 线程安全，效率更低（Hashtable 已被淘汰，不要使用）。
• 对 Null 的支持：HashMap 支持 Null 的 Key 和 Value，而 Hashtable 不支持。
• 初始容量和扩容大小：
  • Hashtable：如果不指定初始容量，默认初始容量为 11，每一次扩容 2n+1。
  • HashMap：如果不知道初始容量，默认初始容量为 16，每一次扩容 2n；指定初始容量时，容量扩充为 2 的幂次方大小。
• 底层数据结构：HashMap 在 JDK 1.8 之前，采用数组+链表的方式，之后采用数组+链表/红黑树的方式（当链表长度大于16，会将链表转为红黑树。但是如果数组长度小于 64，会优先扩容数组）

为什么 HashMap 的容量是 2 的幂次方？

因为在通过对哈希取模选则数组下标时，2 的幂次方可以快速计算：(n-1) & hash = hash % 数组长度

HashMap 和 TreeMap 的区别

HashMap 和 TreeMap 都继承自 AbstractMap，但是 TreeMap 还实现了 NavigableMap 接口和 SortedMap 接口。实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索能力；实现 SortedMap 接口让 TreeMap 有了对集合中元素根据 key 的排序能力。

HashMap 多线程死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

ConcurrentHashMap

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式不同：

• 底层数据结构：Hashtable 采用数组+链表的方式。ConcurrentHashMap 在 JDK 1.7 采用分段锁+链表，JDK 1.8 采用数组+链表/红黑树的方式。
• 实现线程安全的方式：
  • ConcurrentHashMap：在 JDK 1.7 时，使用分段锁的方式保证线程安全；在 JDK 1.8 时，摒弃了分段锁而是直接使用 Node 数组+链表/红黑树的方式，并发控制使用 synchronized 和 CAS 操作。
  • Hashtable：使用 synchronized（同一把锁）保证线程安全，并发程度为 1。

ConcurrentHashMap 并发实现机制

ConcurrentHashMap 在 JDK 1.7 和 1.8 中实现并发的机制不同：

• JDK 1.7：分段锁的方式实现并发，默认 16 个段，也就是说最多支持 16 个线程并发访问。段的个数一旦初始化之后不能改变。
• JDK 1.8：摈弃了分段锁的概念，采用 Node 数组+synchronized+CAS 保证并发安全。锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

ConcurrentHashMap 为什么 key 和 value 不支持 null

多线程环境下，存在一个线程操作该 ConcurrentHashMap 时，其他的线程将该 ConcurrentHashMap 修改的情况，所以无法通过 containsKey(key) 来判断否存在这个键值对，也就没办法解决二义性问题了。

与此形成对比的是，HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 HashMap 修改的情况，所以可以通过 contains(key)来做判断是否存在这个键值对，从而做相应的处理，也就不存在二义性问题。

也就是说，多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。

List

ArrayList、LinkedList、Vector 实现了 List 接口。其中 Vector 是 ArrayList 的古老实现类，最重要的还是 ArrayList 和 LinkedList。那么 ArrayList 和 LinkedList 的区别有什么？

• 是否线程安全：二者都是线程不安全的，不保证并发访问。
• 底层数据结构：ArrayList 底层采用数组，而 LinkedList 底层采用双向链表。
• 插入和删除：ArrayList 除了在尾部插入和删除的时间复杂度为 O(1)，其余时间复杂度均为 O(n)。LinkedList 在头尾插入和删除的时间复杂度为 O(1)，其余位置因为需要先定位元素再删除，时间复杂度为 O(n)。
• 是否支持随机访问：ArrayList 支持快速的随机访问，而 LinkedList 不支持。
• 内存占用：ArrayList 的空间浪费体现在容量大于长度的情况，LinkedList 的空间浪费体现在每一个元素都要记录前驱和后继。

一般都会使用 ArrayList，需要用到 LinkedList 的场景几乎可以用 ArrayList 代替。

集合概述

Java 集合（容器）由两大接口派生而来：Collection 接口，用于存放单一的元素；Map 接口，用于存放键值对。对于 Collection 接口，派生出了几个子接口：List、Set、Queue。

区别

几个接口的区别如下：

• List：顺序存储元素。
• Set：存储的元素是不可重复的。
• Queue：队列，按照某种规则进行排队。
• Map：键值对。

底层数据结构

Collection

Collection 接口下集合的数据结构：

• List：
  • ArrayList：Object 数组。
  • Vector：Object 数组，并发安全，是 ArrayList 的古老实现类。
  • LinkedList：双向链表。
• Set：
  • HashSet：基于 HashMap 实现，底层使用 HashMap 存储元素。
  • LinkedHashSet：是 HashSet 的子类，内部是通过 LinkedHashMap 实现的。
  • TreeSet：红黑树。
• Queue：
  • PriorityQueue：Object 数组实现的小顶堆。
  • DelayQueue：延迟队列，基于 PriorityQueue 实现的。
  • ArrayDeque：可以动态扩容的双向数组。

Map

Map 接口下集合的数据结构：

• HashMap：JDK 1.8 之前由数组+链表组成，使用拉链法解决哈希冲突。JDK 1.8 之后在解决哈希冲突时有了较大变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
• LinkedHashMap：继承自 HashMap，底层依然是数组+链表/红黑树的结构。另外，LinkedHashMap 在HashMap 的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了顺序访问相关逻辑。
• Hashtable：数组+链表组成，使用拉链法解决哈希冲突。
• TreeMap：红黑树。

GaiaDB 是百度自研的云原生数据库，GaiaDB 采用计算与存储分离的架构，不仅在性能、扩展性和高可用方面有大幅提升，而且架构的解耦使得计算层和存储层都获得了很大的优化空间。

架构

GaiaDB 在运行形态上是一个多节点集群，集群中有一个主节点和多个从节点，日志服务（LogService）用于持久化主节点生成的日志，所有节点共享底层的分布式存储（PageServer），各模块分布到不同的K8S容器内。

架构上采用合-分-合的架构，在扩展性和使用便捷性之间保持了平衡，使得对于上层应用程序来说，就像使用一个单点的MySQL数据库一样简单。

• 【合】最上层是接入代理，作为统一的入口。
• 【分】中间数据库引擎作为计算层，扩展为一个主节点合多个从节点，提高扩展性。
• 【合】底层采用一套分布式存储，节省成本。

GaiaDB 代理层

GaiaDB 通过内部的代理层（Proxy）对外提供服务，也就是说所有的应用程序都先经过这层代理，然后才访问到具体的数据库节点。这样的好处：

• Proxy 提供安全认证和保护。
• Proxy 解析 SQL，把写操作（比如事务、Update、Insert、Delete、DDL 等）发送到主节点，把读操作（比如 Select）均衡地分发到多个读节点，这个也叫读写分离。
• 通过 Proxy 把不同的业务用不同的连接地址，使用不同的数据节点。这样就可以避免相互影响，不会影响在线业务。

GaiaDB 计算层

计算层由一个主节点合最多十五个从节点组成。计算层百分百支持 MySQL 语法，相对于 MySQL 的主从节点来说，GaiaDB 的计算节点是无状态的。

• 主节点：处理读写请求，处理事务。相比于 MySQL 的主节点，GaiaDB 的主节点仅需要将日志（RedoLog）发送至日志服务（LogService）持久化，不需要写数据。数据是由数据存储节点（PageServer）从 LogService 拉取日志并回放。
• 从节点：处理只读负载。从 PageServer 拉取最新的数据。

这样的设计具有以下优势：

• 计算节点无状态，弹性快速扩容。计算层节点无持久化数据，本地文件不复存在，包括日志文件，所以支持快速扩容，大概在 30 秒内就能快速创建从节点并提供服务。
• 只有单机事务，没有分布式事务问题。集群所有的事务都请求到主节点，主节点自身保障事务的 ACID 特性。
• 单机故障不影响集群一致性，底层存储层利用 Raft 一致性算法保障数据的一致性。事务产生的 Redo 日志均实时写入 LogService，从节点利用 PageServer 上的数据文件和 LogService 中的 Redo 日志，在内存中恢复最新的数据对外提供服务。每一次主备故障切换，从节点均可以获取最新的事务 Redo 日志，因此不会出现数据丢失。

GaiaDB 存储层

存储层是由多组数据存储节点（PageServer）和一组日志服务节点（LogService）组成。包括两个组件，LogService 和 Page Server。

• LogService 用于持久化数据库日志（RedoLog），采用 Raft 一致性协议保障日志的高可用和一致性。缓存近期产生的日志，供从节点和 PageServer 快速拉取。

• PageServer 用于缓存和持久化数据页，每组包含三个 PageServer 节点，一组 PageServer 管理 32GB 的数据（这 32GB 的数据称为一个 Segment）。

这样的设计有以下优势：

• 数据的一致性和数据存储分离，LogService 专注一致性保障，PageServer 专注持久化数据。
• PageServer 和 LogService 都采用多副本的方式保障高可用。
• PageServer 之间逻辑独立。独立从 LogService 拉取数据，LogService 保障数据的一致性。
• 存储节点的扩容只需要增加 PageServer 的个数，扩容操作对用户无感。

原子类都存放在java.util.concurrent.atomic下：

根据操作的数据类型，可以将 JUC 包中的原子类分为 4 类：

基本类型

• AtomicInteger：整型原子类。
• AtomicLong：长整型原子类。
• AtomicBoolean：布尔型原子类。

数组类型

• AtomicIntegerArray：整型数组原子类。
• AtomicLongArray：长整型数组原子类。
• AtomicReferenceArray：引用类型数组原子类。

引用类型

• AtomicReference：引用类型原子类。
• AtomicMarkableReference：原子更新带有标记的引用类型，该类将 boolean 标记与引用关联起来。
• AtomicStampedReference：原子更新带有版本号的引用类型。该类将整数值与引用关联起来，可用于解决原子的更新数据和数据的版本号，可以解决使用 CAS 进行原子更新时可能出现的 ABA 问题。

对象的属性修改类型

• AtomicIntegerFieldUpdater:原子更新整型字段的更新器。
• AtomicLongFieldUpdater：原子更新长整型字段的更新器。
• AtomicReferenceFieldUpdater：原子更新引用类型里的字段。

Java 的悲观锁可以使用 ReentrantLock，乐观锁采用版本号或者 CAS 实现。

CAS 的 ABA 问题：

如果一个变量 V 初次读取的时候是 A 值，并且在准备赋值的时候检查到它仍然是 A 值，那我们就能说明它的值没有被其他线程修改过了吗？很明显是不能的，因为在这段时间它的值可能被改为其他值，然后又改回 A，那 CAS 操作就会误认为它从来没有被修改过。这个问题被称为 CAS 操作的 ABA 问题。

ABA 问题的解决思路是在变量前面追加上版本号或者时间戳。JDK 1.5 以后的 AtomicStampedReference 类就是用来解决 ABA 问题的，其中的 compareAndSet() 方法就是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

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

public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { Pair<V> current = pair; return expectedReference == current.reference && expectedStamp == current.stamp && ((newReference == current.reference && newStamp == current.stamp) || casPair(current, Pair.of(newReference, newStamp))); }