MisakaDB-kv型小型数据库 | 记录3

主要内容：

1. entry编解码的实现
2. 操作文件的接口以及封装文件IO以实现操作文件的接口
3. entry+操作文件统一封装并且暴露接口
4. Hash数据类型操作总结



该项目大量借鉴RoseDB（意思其实就是没有RoseDB估计我写能写好长时间）

### 1 Entry编解码的实现

先记录几个方法：

:::tip{title="提示"}
`binary.PutVarint()`：`func PutVarint(buf []byte, x int64) int`，该方法会将给定的整数x以变长编码的方式转换为字节并且存入buf中，返回的整数值是对x编码后的字节长度。
:::

:::tip{title="提示"}
Go中，切片和切片指针是一个东西，具体看这个图就能理解：

![image.png](https://www.misaka19327.cc/static/img/4f01ad3e03b2dbd0e6352892b5d86460.image.png)
:::

:::tip{title="提示"}
`binary.LittleEndian.PutUint32(buffer[:4], crc)`：`func (littleEndian) PutUint32(b []byte, v uint32)`，以小端字节序将无符号整数v放入字节切片中。小端字节序是一种字节排列方式，它将整数的最低有效字节放在最前面，最高有效字节放在最后面。
:::

:::tip{title="提示"}
`binary.Varint`：`func Varint(buf []byte) (int64, int)`，在给定的字节数组中从头开始解析，尝试解析出一个整数。第一个返回值是被解析出来的整数，第二个返回值是被解析出来的整数的字节长度。如果第二个返回值等于0，说明给定的字节数组太小；如果小于0，则说明要解析的整数的字节长度超过64位。
:::

:::tip{title="提示"}
`crc32.Update`：`func Update(crc uint32, tab *Table, p []byte) uint32`，相当于在已经计算好的crc校验和上，加入新的字节数组继续计算一次。（tab一般为`crc32.IEEETable`）。
:::

Entry结构如下代码所示。

``` go
// entry.go
package storage

import (
	"encoding/binary"
	"hash/crc32"
)

// entry编码结构：
// +-------+--------+----------+------------+-----------+-------+---------+
// |  crc  |  type  | key size | value size | expiresAt |  key  |  value  |
// +-------+--------+----------+------------+-----------+-------+---------+
// |------------------------HEADER----------------------|
//         |--------------------------crc check---------------------------|

// header长度：
// crc32	typ    kSize	vSize	expiredAt
//  4    +   1   +   5   +   5    +    10      = 25 (refer to binary.MaxVarintLen32 and binary.MaxVarintLen64)

// MaxEntryHeaderLength 规定Entry头部信息最长长度为25 同时整个Entry长度不能小于25
const MaxEntryHeaderLength = 25

// EntryType 标识entry类型
type EntryType byte

const (
	TypeDelete   EntryType = iota + 1 // 标识记录删除信息的entry 这个iota写法是让常量从0开始
	TypeRecord                      // 标识记录信息的entry
)

// 因为整个数据库的操作 增删改查 体现在文件上的只有删除和新增两种（改可以通过新增的方式进行覆盖）

// Entry 具体一个Entry所记录的信息
type Entry struct {
	Key       []byte    // 键
	Value     []byte    // 值
	EntryType EntryType // entry类型标识
	ExpiredAt int64 // 过期时间 这里放时间戳
}

// entryHeaderInfo 一个entry所对应的header信息
type entryHeaderInfo struct {
	crc         uint32    // 校验和 对剩余部分进行检验
	entryType   EntryType // entry类型标识
	keyLength   uint32
	valueLength uint32
	expiredAt   int64 // 过期时间 这里放时间戳
}

// Encode 将entry转换为byte数组 另外返回写入内容的长度 byte数组强制必须大于25 如果不够就用0凑足成25 否则读取文件时不够25会EOF
func (e *Entry) Encode() ([]byte, int) {
	if e == nil {
		return nil, 0
	}
	
	header := make([]byte, MaxEntryHeaderLength)
	
	// 先放头信息里除了校验和之外的其他东西
	header[4] = byte(e.EntryType)
	index := 5
	index += binary.PutVarint(header[index:], int64(len(e.Key)))
	index += binary.PutVarint(header[index:], int64(len(e.Value)))
	index += binary.PutVarint(header[index:], e.ExpiredAt)
	
	// 再放key和value
	size := index + len(e.Key) + len(e.Value)
	if size < MaxEntryHeaderLength {
		size = MaxEntryHeaderLength
	}
	buffer := make([]byte, size)
	copy(buffer[:index], header[:])
	copy(buffer[index:], e.Key)
	copy(buffer[index + len(e.Key):], e.Value)
	
	// 最后放crc校验和
	crc := crc32.ChecksumIEEE(buffer[4:index + len(e.Key) + len(e.Value)])
	binary.LittleEndian.PutUint32(buffer[:4], crc)
	return buffer, size
}

// 将给定的byte数组解码为entryHeaderInfo 即Entry的头信息 返回该头信息和头信息的字节长度
func decodeEntryHeader (input []byte) (*entryHeaderInfo, int64) {
	if len(input) <= 4 {
		return nil, 0
	}
	result := &entryHeaderInfo{
		crc:       binary.LittleEndian.Uint32(input[:4]),
		entryType: EntryType(input[4]),
	}
	index := 5
	kSize, n := binary.Varint(input[index:])
	result.keyLength = uint32(kSize)
	index += n
	
	vSize, n := binary.Varint(input[index:])
	result.valueLength = uint32(vSize)
	index += n
	
	e, n := binary.Varint(input[index:])
	result.expiredAt = e
	
	return result, int64(index + n)
}

// getEntryCRC 给定字节数组和Entry 计算该数组+Entry键+Entry值的crc校验和
func getEntryCRC(entry *Entry, h []byte) uint32 {
	if entry == nil { return 0 }
	result := crc32.ChecksumIEEE(h)
	result = crc32.Update(result, crc32.IEEETable, entry.Key)
	result = crc32.Update(result, crc32.IEEETable, entry.Value)
	return result
}
```

### 2 操作文件的接口以及封装文件IO以实现操作文件的接口

``` go
// fileWriter.go
package storage

// FileWriter 定义封装文件操作的基本行为 因为bitcask模型只有对文件的读 追加和整理 所以这里并不涉及对文件的已经写入的数据进行修改
type FileWriter interface {
    Write (input []byte, offset int) error // 在文件的指定位置进行写入
    Read (buf []byte, offset int) error // 在文件的指定位置进行读取
    Sync () error // 强制内存和文件同步一次 以保证一致性
    Delete () error // 删除文件
    Close () error // 关闭文件
    Length () (int64, error) // 返回该文件的长度
}

// attention 实现FileWriter接口的结构体不需要并发安全 因为它和index一一对应 而index会带一个读写锁
```

这个接口定义了如何对文件进行操作。无论是使用传统的文件IO的方式做，还是MMap方式去做，必须实现这五个接口。

之后是对传统的文件IO的方式进行封装：

``` go
// fileIO.go
package storage

import "os"

type FileIO struct {
	file *os.File
}

func NewFileIO (filePath string) (*FileIO, error) {
	file, e := os.OpenFile(filePath, os.O_CREATE | os.O_RDWR, 0644)
	if e != nil {
		// todo logger
		return nil, e
	}
	result := &FileIO{
		file: file,
	}
	return result, nil
}

func (f *FileIO) Write(input []byte, offset int) error {
	_, e := f.file.WriteAt(input, int64(offset))
	return e
}

func (f *FileIO) Read(buf []byte, offset int) error {
	_, e := f.file.ReadAt(buf, int64(offset))
	return e
}

func (f *FileIO) Sync() error {
	return f.file.Sync()
}

func (f *FileIO) Delete() error {
	e := f.file.Close()
	if e == nil {
		// todo logger
		return e
	}
	return os.Remove(f.file.Name())
	// attention *os.File.Remove()只会报PathError 其他的问题导致删除文件不成功的话它报不了错的
	// attention *os.File.Name()返回的是当初创建文件时给定的字符串 不论这个字符串是文件绝对路径还是只是文件名
}

func (f *FileIO) Close() error {
	return f.file.Close()
}

func (f *FileIO) Length () (int64, error) {
	fileStat, e := f.file.Stat()
	if e != nil {
		return 0, e
	}
	return fileStat.Size(), nil
}

// 检查接口实现
var _ FileWriter = (*FileIO)(nil)
```

:::tip{title="提示"}
`os.OpenFile`：`func OpenFile(name string, flag int, perm FileMode) (*File, error)`，标准库中提供的打开文件的方法。flag如下：

``` go
// Flags to OpenFile wrapping those of the underlying system. Not all
// flags may be implemented on a given system.
const (
	// Exactly one of O_RDONLY, O_WRONLY, or O_RDWR must be specified.
	O_RDONLY int = syscall.O_RDONLY // open the file read-only.
	O_WRONLY int = syscall.O_WRONLY // open the file write-only.
	O_RDWR   int = syscall.O_RDWR   // open the file read-write.
	// The remaining values may be or'ed in to control behavior.
	O_APPEND int = syscall.O_APPEND // append data to the file when writing.
	O_CREATE int = syscall.O_CREAT  // create a new file if none exists.
	O_EXCL   int = syscall.O_EXCL   // used with O_CREATE, file must not exist.
	O_SYNC   int = syscall.O_SYNC   // open for synchronous I/O.
	O_TRUNC  int = syscall.O_TRUNC  // truncate regular writable file when opened.
)
```

第三个参数指定该文件的权限，第一位表示文件类型，后三位就和Linux中的777概念一致。一般情况下0644够用了。
:::

测试文件：

``` go
// fileIO_test.go
package storage

import "testing"

func TestNewFileIO(t *testing.T) {
	file, e := NewFileIO("C:\\Users\\Misaka19327\\OneDrive\\Projects\\GoLandProjects\\MisakaDB\\test.txt")
	if e != nil {
		t.Log(e)
		return
	}
	
	defer func() {
		e = file.Close()
		if e != nil {
			t.Log(e)
		}
	}()
	
	t.Log(file.file.Name())
	e = file.Write([]byte{1, 2, 3, 4, 5}, 0)
	if e != nil {
		t.Log(e)
	}
	buffer := make([]byte, 5)
	e = file.Read(buffer, 0)
	if e != nil {
		t.Log(e)
	} else {
		t.Log(buffer)
	}
}
```

### 3 entry+操作文件统一封装并且暴露接口

数据库所需要的文件操作，就是对一个数据文件写入和读取Entry，同时还需要打开（包括打开已经存在的数据文件），关闭，删除（整理文件时需要）该数据文件。

:::warning{title="注意"}
个人认为文件这里不需要加读写锁，只需要对index加读写锁即可。因为对index的读写一定会一比一地反映到某一个文件上，而如果对index加锁了，那么对文件的读写一定是并发安全的。
:::

``` go
package storage

import (
	"MisakaDB/src/logger"
	storage "MisakaDB/src/storage/file" // 别名写法
	"fmt"
	"hash/crc32"
	"os"
	"path"
	"path/filepath"
	"strconv"
	"strings"
)

// FileForData 指定该数据文件存储的数据类型
type FileForData int8

const (
	String FileForData  = iota
	Hash
	List
	Set
	ZSet
)

var (
	// 文件名的后缀
	fileNameSuffix = map[FileForData]string {
		String: "record.string.",
		Hash: "record.hash.",
		List: "record.list.",
		Set: "record.set.",
		ZSet: "record.zset.",
	}
	
	// 根据文件名解析该文件的存储数据的类型
	filenameToDataTypeMap = map[string]FileForData {
		"string": String,
		"hash": Hash,
		"list": List,
		"set": Set,
		"zset": ZSet,
	}
)

// RecordFile 将数据文件抽象为该结构体
type RecordFile struct {
	file storage.FileWriter // 对文件进行操作的结构体
	fileID uint32 // 文件ID
	newestOffset int64 // 该文件写入位置 或者说最新偏移位也可以
	dataType FileForData // 该文件存储的键值对的类型
	fileMaxSize int64 // 该文件最大的大小
}

// FileIOType 指定文件的读写模式
type FileIOType int8

const (
	MMapIOFile FileIOType = iota // MMap方式
	TraditionalIOFile // 传统IO方式
)

// NewRecordFile 给定路径 读写模式 存储数据类型 文件ID和文件最大大小 新建一个RecordFile
func NewRecordFile (ioType FileIOType, dataType FileForData, fid uint32, path string, fileMaxSize int64) (*RecordFile, error) {
	result := &RecordFile{
		fileID: fid,
		fileMaxSize: fileMaxSize,
		newestOffset: 0,
		dataType: dataType,
	}
	fileFullPath, e := getFileName(fid, dataType, path)
	if e != nil {
		return nil, e
	}
	var fileWriter storage.FileWriter
	switch ioType {
	case MMapIOFile:
		return nil, logger.MMapIsNotSupport
	case TraditionalIOFile:
		fileWriter, e = storage.NewFileIO(fileFullPath)
	}
	result.file = fileWriter
	return result, nil
}

// LoadRecordFileFromDisk 加载一个文件
func LoadRecordFileFromDisk(filePath string, fileMaxSize int64) (*RecordFile, error) {
	if _, e := os.Stat(filePath); e != nil {
		return nil, logger.FileIsNotExist
	}
	file, e := storage.NewFileIO(filePath)
	if e != nil {
		return nil, e
	}
	fileLen, e := file.Length()
	if e != nil {
		return nil, e
	}
	result := &RecordFile{
		file: file,
		fileMaxSize: fileMaxSize,
		newestOffset: fileLen,
	}
	result.fileID, result.dataType, e = parseFileName(path.Base(filePath))
	if e != nil {
		return nil, e
	}
	return result, nil
}

// WriteEntryIntoFile 尝试将Entry写入文件 如果文件剩余大小已经不足以再写入Entry 则返回FileBytesIsMaxedOut错误
func (rf *RecordFile) WriteEntryIntoFile (entry *Entry) error {
	writeContent, length := entry.Encode()
	if int64(length) + rf.newestOffset > rf.fileMaxSize {
		return logger.FileBytesIsMaxedOut
	}
	e := rf.file.Write(writeContent, int(rf.newestOffset))
	rf.newestOffset += int64(length) // 调整偏移位
	return e
}

// ReadIntoEntry 在RecordFile中 从给定的offset开始 尝试读取一个完整的Entry并且返回 第二个返回值为当此读取Entry的长度 用以快速定位下次Entry的offset
func (rf *RecordFile) ReadIntoEntry (offset int64) (*Entry, int64, error) {
	entryHeaderBytes := make([]byte, MaxEntryHeaderLength)
	e := rf.file.Read(entryHeaderBytes, int(offset))
	if e != nil {
		return nil, 0, e
	}
	entryHeader, index := decodeEntryHeader(entryHeaderBytes)
	result := &Entry{
		EntryType: entryHeader.entryType,
		ExpiredAt: entryHeader.expiredAt,
		Key:       make([]byte, entryHeader.keyLength),
		Value:     make([]byte, entryHeader.valueLength),
	}
	e = rf.file.Read(result.Key, int(offset + index))
	if e != nil {
		return nil, 0, e
	}
	e = rf.file.Read(result.Value, int(offset + index) + int(entryHeader.keyLength))
	if e != nil {
		return nil, 0, e
	}
	if crc := getEntryCRC(result, entryHeaderBytes[crc32.Size:index]); crc != entryHeader.crc {
		return nil, 0, logger.CRCCheckSumNotPassed
	}
	entrySize := index + int64(entryHeader.keyLength + entryHeader.valueLength)
	if entrySize < MaxEntryHeaderLength { // 注意Entry的最小长度为25
		return result, MaxEntryHeaderLength, nil
	}
	return result, entrySize, nil
}

// Sync 强制刷新缓冲区到文件中
func (rf *RecordFile) Sync () error {
	return rf.file.Sync()
}

// Delete 删除该文件
func (rf *RecordFile) Delete () error {
	return rf.file.Delete()
}

// Close 关闭该文件
func (rf *RecordFile) Close () error {
	return rf.file.Close()
}

// getFileName 给record文件起名 示例名字：record.string.000000001.misaka
func getFileName (fid uint32, dataType FileForData, path string) (string, error) {
	if _, ok := fileNameSuffix[dataType]; !ok {
		return "", logger.UnSupportDataType
	}
	fileName := fileNameSuffix[dataType] + fmt.Sprintf("%09d", fid) + ".misaka"
	return filepath.Join(path, fileName), nil
}

// parseFileName 给定的FileName中 解析出需要的信息 示例文件名：record.string.000000001.misaka
func parseFileName (fileName string) (uint32, FileForData, error) {
	strs := strings.Split(fileName, ".")
	resultNum, e := strconv.Atoi(strs[2])
	if e != nil {
		return 0, String, e
	}
	return uint32(resultNum), filenameToDataTypeMap[strs[1]], nil
}
```

:::tip{title="提示"}
```
const (
	String FileForData  = iota
	Hash
	List
	Set
	ZSet
)
```

这种定义常量的写法，iota的含义是从0开始。
:::

测试文件：

``` go
package storage

import (
	"fmt"
	"testing"
)

func TestNewRecordFile(t *testing.T) {
	testFile, e := NewRecordFile(TraditionalIOFile, String, 1, "D:\\MisakaDBTest", 65536)
	if e != nil {
		fmt.Println(e)
		return
	}
	testEntry := &Entry{
		Key:       []byte("testKey"),
		Value:     []byte("testValue"),
		EntryType: TypeRecord,
		ExpiredAt: 0,
	}
	e = testFile.WriteEntryIntoFile(testEntry)
	if e != nil {
		fmt.Println(e)
		return
	}
	e = testFile.Sync()
	if e != nil {
		fmt.Println(e)
		return
	}
	testReadEntry, length, e := testFile.ReadIntoEntry(0)
	if e != nil {
		fmt.Println(e)
		return
	}
	fmt.Println(string(testReadEntry.Key))
	fmt.Println(string(testReadEntry.Value))
	fmt.Println(length)
	
	testEntry = &Entry{
		Key:       []byte("testKey----2"),
		Value:     []byte("testValue----2"),
		EntryType: TypeRecord,
		ExpiredAt: 0,
	}
	e = testFile.WriteEntryIntoFile(testEntry)
	if e != nil {
		fmt.Println(e)
		return
	}
	e = testFile.Sync()
	if e != nil {
		fmt.Println(e)
		return
	}
	testReadEntry, length, e = testFile.ReadIntoEntry(25)
	if e != nil {
		fmt.Println(e)
		return
	}
	fmt.Println(string(testReadEntry.Key))
	fmt.Println(string(testReadEntry.Value))
	fmt.Println(length)
	
	testEntry = &Entry{
		Key:       []byte("Key3"),
		Value:     []byte("Value3"),
		EntryType: TypeRecord,
		ExpiredAt: 0,
	}
	e = testFile.WriteEntryIntoFile(testEntry)
	if e != nil {
		fmt.Println(e)
		return
	}
	e = testFile.Sync()
	if e != nil {
		fmt.Println(e)
		return
	}
	testReadEntry, length, e = testFile.ReadIntoEntry(59)
	if e != nil {
		fmt.Println(e)
		return
	}
	fmt.Println(string(testReadEntry.Key))
	fmt.Println(string(testReadEntry.Value))
	fmt.Println(length)
	
	e = testFile.Close()
	if e != nil {
		fmt.Println(e)
		return
	}
}

func TestParseFileName(t *testing.T) {
	result1, result2, e := parseFileName("record.string.000000001.misaka")
	if e != nil {
		t.Log(e)
	} else {
		t.Log(result1)
		t.Log(result2)
	}
}

func TestLoadRecordFileFromDisk(t *testing.T) {
	rf, e := LoadRecordFileFromDisk("D:\\MisakaDBTest\\record.string.000000001.misaka", 65536)
	if e != nil {
		t.Log(e)
		return
	}
	t.Log(rf.newestOffset)
	
	testEntry := &Entry{
		Key:       []byte("testKey5"),
		Value:     []byte("testValue5"),
		EntryType: TypeRecord,
		ExpiredAt: 0,
	}
	e = rf.WriteEntryIntoFile(testEntry)
	if e != nil {
		fmt.Println(e)
		return
	}
	e = rf.Sync()
	if e != nil {
		fmt.Println(e)
		return
	}
	
	testReadEntry, length, e := rf.ReadIntoEntry(84)
	if e != nil {
		fmt.Println(e)
		return
	}
	fmt.Println(string(testReadEntry.Key))
	fmt.Println(string(testReadEntry.Value))
	fmt.Println(length)
	
	testReadEntry, length, e = rf.ReadIntoEntry(59)
	if e != nil {
		fmt.Println(e)
		return
	}
	fmt.Println(string(testReadEntry.Key))
	fmt.Println(string(testReadEntry.Value))
	fmt.Println(length)
	
	fmt.Println(rf.newestOffset)
}
```

![image.png](https://www.misaka19327.cc/static/img/cb63d2a97ba54b502933955aface4bc1.image.png)

### 3 Hash数据操作类型

1. HSet：`hset key field value`，设置值。如果设置成功则返回1，否则返回0。
2. HSetNX：`hsetnx key field value`，设置值，但是它只有在field不存在时才能设置成功。
3. HGet：`hget key field`，获取值，如果key或者field不存在则返回nil。
4. HDel：`hdel key field [field ...]`，删除值，返回被删除的值的数量。
5. HLen：`hlen key`，获取值的field个数。
6. HExists：`hexists key field`，判断field是否存在，存在返回1，反之返回0。
7. HStrLen：`hstrlen key field`，获取value的长度，如果field不存在则返回0。


![image.png](https://www.misaka19327.cc/static/img/f93409a676909f251cd5ea0166d3a883.image.png)

MisakaDB-kv型小型数据库 | 记录2

记录实验4过程及代码。



### 1 引入依赖

Maven项目修改pom.xml，添加以下依赖：

``` xml
        <dependency>
            <groupId>mysql</groupId>
            <artifactId>mysql-connector-java</artifactId>
            <version>8.0.33</version>
        </dependency>

        <dependency>
            <groupId>commons-dbutils</groupId>
            <artifactId>commons-dbutils</artifactId>
            <version>1.8.0</version>
        </dependency>

        <dependency>
            <groupId>com.alibaba</groupId>
            <artifactId>druid</artifactId>
            <version>1.2.22</version>
        </dependency>

        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.13.2</version>
            <scope>test</scope>
        </dependency>
```

### 实验要求1～6

数据库初始化：

![image.png](https://www.misaka19327.cc/static/img/0ac2636e218fea562c7a72e1671492d3.image.png)

``` java
// SQLConnect.java
package org.example.webstructure.experiment4;

import com.alibaba.druid.pool.DruidDataSource;
import org.apache.commons.dbutils.DbUtils;
import org.apache.commons.dbutils.QueryRunner;
import org.apache.commons.dbutils.ResultSetHandler;
import org.apache.commons.dbutils.handlers.BeanHandler;
import org.apache.commons.dbutils.handlers.ScalarHandler;

import java.sql.*;

public class SQLConnect {
    public static void main(String[] args) throws SQLException {

        Connection connection = DriverManager.getConnection("jdbc:mysql://127.0.0.1:19327/test", "root", "123456");

        // 增
        PreparedStatement preparedStatement = connection.prepareStatement("insert into testtable values('textKey2', 'textValue2')");
        int columnNum = preparedStatement.executeUpdate();
        System.out.println(columnNum);
        preparedStatement = connection.prepareStatement("select value1 from testtable where key1 = 'textKey2'");
        ResultSet result = preparedStatement.executeQuery();
        result.next();
        System.out.println(result.getString("value1"));

        // 删
        preparedStatement = connection.prepareStatement("delete from testtable where key1 = 'textKey2'");
        columnNum = preparedStatement.executeUpdate();
        System.out.println(columnNum);
        preparedStatement = connection.prepareStatement("select count(value1) from testtable where key1 = 'textKey2'");
        result = preparedStatement.executeQuery();
        result.next();
        System.out.println(result.getInt(1));

        // 改
        // 先增一个数据用来改
        preparedStatement = connection.prepareStatement("insert into testtable values('textKey2', 'textValue2')");
        columnNum = preparedStatement.executeUpdate();
        System.out.println(columnNum);
        preparedStatement = connection.prepareStatement("update testtable set value1 = 'textValue3' where key1 = 'textKey2'");
        columnNum = preparedStatement.executeUpdate();
        System.out.println(columnNum);
        preparedStatement = connection.prepareStatement("select value1 from testtable where key1 = 'textKey2'");
        result = preparedStatement.executeQuery();
        result.next();
        System.out.println(result.getString("value1"));

        // 查
        preparedStatement = connection.prepareStatement("select * from testtable");
        result = preparedStatement.executeQuery();
        result.next();
        System.out.println(result.getString("value1"));
        // 再删一次 省得我重复运行的时候这块老是报错
        preparedStatement = connection.prepareStatement("delete from testtable where key1 = 'textKey2'");
        columnNum = preparedStatement.executeUpdate();

        // 释放资源
        result.close();
        preparedStatement.close();
        connection.close();

        // 连接池初始化
        DruidDataSource dataSource = getDruidDataSource();
        // 获取连接
        Connection connectionFromPool = dataSource.getConnection();
        connectionFromPool.close();

        // 通过DBUtils进行增删改查
        connection = DriverManager.getConnection("jdbc:mysql://127.0.0.1:19327/test", "root", "123456");
        QueryRunner queryRunner = new QueryRunner();
        ResultSetHandler<test> resultSetHandler = new BeanHandler<>(test.class);
        try {
            // 查
            test t = queryRunner.query(connection, "select key1, value1 from testtable where key1 = 'testKey1'", resultSetHandler);
            System.out.println(t.getKey1() + " " + t.getValue1());

            // 增
            queryRunner.update(connection, "insert into testtable values('testKey3', 'testValue3')");
            t = queryRunner.query(connection, "select key1, value1 from testtable where key1 = 'testKey3'", resultSetHandler);
            System.out.println(t.getKey1() + " " + t.getValue1());

            // 改
            queryRunner.update(connection, "update testtable set value1 = 'testValue4' where key1 = 'testKey3'");
            t = queryRunner.query(connection, "select * from testtable where key1 = 'testKey3'", resultSetHandler);
            System.out.println(t.getKey1() + " " + t.getValue1());

            // 删
            queryRunner.update(connection, "delete from testtable where key1 = 'testKey3'");
            Long i = queryRunner.query(connection, "select count(*) from testtable;", new ScalarHandler<>());
            System.out.println(i);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            DbUtils.close(connection);
        }
    }

    private static DruidDataSource getDruidDataSource() {
        // 数据源配置
        DruidDataSource dataSource = new DruidDataSource();
        dataSource.setUrl("jdbc:mysql://127.0.0.1:19327/test");
        dataSource.setDriverClassName("com.mysql.cj.jdbc.Driver"); //这个可以缺省的，会根据url自动识别
        dataSource.setUsername("root");
        dataSource.setPassword("123456");

        // 下面都是可选的配置
        dataSource.setInitialSize(10);  // 初始连接数，默认0
        dataSource.setMaxActive(30);  // 最大连接数，默认8
        dataSource.setMinIdle(10);  // 最小闲置数
        dataSource.setMaxWait(2000);  // 获取连接的最大等待时间，单位毫秒
        dataSource.setPoolPreparedStatements(true); // 缓存PreparedStatement，默认false
        dataSource.setMaxOpenPreparedStatements(20); // 缓存PreparedStatement的最大数量，默认-1（不缓存）。大于0时会自动开启缓存PreparedStatement，所以可以省略上一句代码
        return dataSource;
    }
}
```

``` java
// test.java
package org.example.webstructure.experiment4;

public class test {
    private String key1;
    private String value1;

    public String getKey1() {
        return key1;
    }

    public void setKey1(String key1) {
        this.key1 = key1;
    }

    public String getValue1() {
        return value1;
    }

    public void setValue1(String value1) {
        this.value1 = value1;
    }

    public test() {}
}
```

![image.png](https://www.misaka19327.cc/static/img/9052319cd2745548130896f002ad2127.image.png)

### 2 实验要求7

``` java
// SQLConnectTest.java
package org.example.webstructure.experiment4;

import com.alibaba.druid.pool.DruidDataSource;

import java.sql.*;

public class SQLConnectTest {

    DruidDataSource dataSource;

    public SQLConnectTest() {
        this.dataSource = new DruidDataSource();
        dataSource.setUrl("jdbc:mysql://127.0.0.1:19327/test");
        dataSource.setDriverClassName("com.mysql.cj.jdbc.Driver");
        dataSource.setUsername("root");
        dataSource.setPassword("123456");
        dataSource.setInitialSize(10);
        dataSource.setMaxActive(30);
        dataSource.setMinIdle(10);
        dataSource.setMaxWait(2000);
        dataSource.setPoolPreparedStatements(true);
        dataSource.setMaxOpenPreparedStatements(20);
    }

    public String UseTraditionalConnection() throws SQLException {
        StringBuilder r = new StringBuilder();
        Connection connection = DriverManager.getConnection("jdbc:mysql://127.0.0.1:19327/test", "root", "123456");
        for (int i = 2; i <= 50; i++) {
            PreparedStatement preparedStatement = connection.prepareStatement("select value1 from testtable where key1 = 'testKey1'");
            ResultSet result = preparedStatement.executeQuery();
            result.next();
            r.append(result.getString("value1")).append(", ");
        }
        return r.toString();
    }

    public String UseConnectPool() throws SQLException {
        StringBuilder r = new StringBuilder();
        Connection connectionFromPool = dataSource.getConnection();
        for (int i = 2; i <= 50; i++) {
            PreparedStatement preparedStatement = connectionFromPool.prepareStatement("select value1 from testtable where key1 = 'testKey1'");
            ResultSet result = preparedStatement.executeQuery();
            result.next();r.append(result.getString("value1")).append(", ");
        }
        return r.toString();
    }
}
```

先新建并且复制上面的代码，然后右键找Generate/生成，里面有个Test...：

![image.png](https://www.misaka19327.cc/static/img/55117adbc61da0aad5fcc25d12b11d7e.image.png)

点进去之后指定类名和对应JUnit版本（上面引入依赖时引入的是JUnit 4.13），再把要生成测试方法的两个方法勾上：

![image.png](https://www.misaka19327.cc/static/img/912fc17a02c9d294eaa181d0d41a24ed.image.png)

之后生成的文件参照下面的代码：

``` java
// SQLConnectTestTest.java
package org.example.webstructure.experiment4;

import org.junit.Test;

import java.sql.SQLException;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;

public class SQLConnectTestTest {

    SQLConnectTest test = new SQLConnectTest();

    @Test
    public void test() throws InterruptedException {
        Thread.sleep(20000); // 20秒连接jConsole
    }

    @Test
    public void useTraditionalConnection() throws InterruptedException {
        List<Thread> threadSet = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            Thread t = new Thread(() -> {
                try {
                    test.UseTraditionalConnection();
                } catch (SQLException e) {
                    e.getErrorCode();
                }
            });
            threadSet.add(t);
            t.start();
        }
        for (Thread thread : threadSet) {
            thread.join();
        }
    }

    @Test
    public void useConnectPool() throws InterruptedException {
        List<Thread> threadSet = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            Thread t = new Thread(() -> {
                try {
                    test.UseConnectPool();
                } catch (SQLException e) {
                    e.getErrorCode();
                }
            });
            threadSet.add(t);
            t.start();
        }
        for (Thread thread : threadSet) {
            thread.join();
        }
    }
}
```

类名旁边有个运行的按钮，点它就可以直接运行全部的测试方法。但是这会先别急运行，先找到Java安装目录下的bin文件夹下的jconsole.exe文件，双击运行：

![image.png](https://www.misaka19327.cc/static/img/ca06e0d4a6765e0bea5fb3ec1aba40fa.image.png)

![image.png](https://www.misaka19327.cc/static/img/6d559aff846ce650654000363545c6f5.image.png)

找到之后回到IDEA中运行全部测试方法，再回来找左上角的Connection -> New Connection，找到运行测试的那个进程进行连接。test中阻塞线程的20秒就是用来连接这个的，如果时间不够可以自己调整。

![image.png](https://www.misaka19327.cc/static/img/eb3f75e9802ad2d467e4dfd10b1ae8a7.image.png)

从这里可以看到Java进程所有的线程，加载的类，堆内存使用情况，占用的CPU和内存资源的使用情况，在IDEA中可以看到两个测试方法的运行时间（对应实验要求的响应时间和资源利用率）：

![image.png](https://www.misaka19327.cc/static/img/cb933b96ca6ce52eebb3043cf6839266.image.png)

Web体系结构与程序设计 实验4

今日任务：

1. LeetCode84 柱状图中最大的矩形
2. 代码随想录一刷完结



资料来源：

1. [代码随想录 | LeetCode84 柱状图中最大的矩形](https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html)

### 1 LeetCode84 柱状图中最大的矩形

:::info{title="题目"}
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

示例 1:

![image.png](https://www.misaka19327.cc/static/img/5a0c2fcd8050fd7b515ffb2dfe90ed6d.image.png)

```
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
```
示例 2：
```
输入： heights = [2,4]
输出： 4
```

提示：

- 1 <= heights.length <=$$10 ^ 5$$
- 0 <= heights[i] <= $$10 ^ 4$$
:::

这题得先想明白怎么求。如果是按照单调栈的求法，它的思路是这样的：对于每个高度x，向左向右同时找第一个比它小的高度，那么在这两个比x小的高度之间，就是能以x为高度存在的最长的矩形。比如说示例1中的下标为2的元素，它的左右比它低的高度下标分别是1和4，那么以5为高度的矩形实际大小为$$5 * (4 - 1 - 1) = 10$$。

既然是要找左右第一个比它小的高度，那么单调栈就得反着用了。如果入栈元素比栈顶元素大就入栈；如果入栈元素比栈顶元素小，则一直出栈到没有元素再比栈顶元素小了再入栈。这个过程中，栈顶元素就是高度x，入栈元素就是右侧第一个比x小的元素，出栈后的栈顶元素就是左侧第一个比x小的元素。有了这三个元素就可以计算区域了。

另外注意两件事：第一个就是，在开始循环尝试入栈之前，给定数组头尾各加一个0。这个是用于防类似`[2, 4, 6, 8]`和`[8, 6, 4, 2]`这样的用例。没有数组尾部的0，前者只会入栈，不会触发出栈，更不会计算区域；没有数组头的0，后者会剩一个2在栈里面出不来；第二个是和接雨水一样，元素相等必须先弹出再入栈一次，理由也差不多，不这样处理的话`[0, 9]`用例会给出答案18，相当于又是把距离算多了。

``` go
func largestRectangleArea(heights []int) int {
	if len(heights) == 1 {
		return heights[0]
	}
	
	result := 0
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	stack := []int{0}
	for i := 1; i < len(heights); i++ {
		top := stack[len(stack) - 1]
		if heights[top] == heights[i] {
			stack = stack[:len(stack) - 1]
			stack = append(stack, i)
		} else if heights[top] < heights[i] {
			stack = append(stack, i)
		} else {
			for len(stack) != 0 && heights[top] > heights[i] {
				middle := top
				stack = stack[:len(stack) - 1]
				if len(stack) != 0 {
					top = stack[len(stack) - 1]
					l := i - top - 1
					result = max(result, l * heights[middle])
				}
			}
			stack = append(stack, i)
		}
	}
	
	return result
}
```

### 2 一刷结束

虽然说一刷结束了，但是感觉还是有点阿巴阿巴在身上的。动态规划感觉啥都想不起来，单调栈也是非常不熟练。二刷准备在下下次开营时开始，顺带把LeetCode Hot100刷完。

代码随想录算法训练营第六十三天 | LeetCode84 柱状图中最大的矩形

今日内容：

1. LeetCode503 下一个更大元素Ⅱ
2. LeetCode42 接雨水



资料来源：

1. [代码随想录 | LeetCode503 下一个更大元素Ⅱ](https://programmercarl.com/0503.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0II.html)
2. [代码随想录 | LeetCode42 接雨水](https://programmercarl.com/0042.%E6%8E%A5%E9%9B%A8%E6%B0%B4.html)

### 1 LeetCode503 下一个更大元素Ⅱ

:::info{title="题目"}
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

 

示例 1:
```
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
```
示例 2:
```
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
```

提示:

- 1 <= nums.length <= $$10^4$$
- $$-10^9$$ <= nums[i] <= $$10^9$$
:::

这题和每日温度差不多，它和每日温度的唯一的区别在于，它的数组是可循环的。可以对给定的数组循环两次，别的都一样。

``` go
func nextGreaterElements(nums []int) []int {
	if len(nums) == 1 {
		return []int{-1}
	}
	
	result := make([]int, len(nums))
	for i := range result {
		result[i] = -1
	}
	stack := []int{0}
	for i := 1; i <= len(nums) * 2 - 1; i++ {
		front := stack[len(stack) - 1]
		if nums[front] >= nums[i % len(nums)] {
			stack = append(stack, i % len(nums))
		} else { // 一直移除栈顶元素
			for len(stack) != 0 && nums[i % len(nums)] > nums[front] {
				result[front] = nums[i % len(nums)]
				stack = stack[:len(stack) - 1]
				if len(stack) != 0 {
					front = stack[len(stack) - 1]
				}
			}
			stack = append(stack, i % len(nums))
		}
	}
	
	return result
}
```

### 2 LeetCode42 接雨水

:::info{title="题目"}
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：

![image.png](https://www.misaka19327.cc/static/img/956360371933cff1d95d44a8e6ff75f6.image.png)
```
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
```
示例 2：
```
输入：height = [4,2,0,3,2,5]
输出：9
```

提示：

- n == height.length
- 1 <= n <= 2 * $$10^4$$
- 0 <= height[i] <= $$10^5$$
:::

这题需要先想明白，**如何统计雨水**？对于每一横行来说，每次统计有多少雨水就需要知道的是它的长度，高度。又对于每个竖列来说，每一行的长度就是它左边的比它高的第一个列到它右边比它高的第一个列的距离，每一行的高度就是这两个比自己高的列中较低的那个和自己的高度差值。那么按照竖列找到左右比它高的竖列，就是单调栈应该做的了。每次比较中，如果栈顶的元素小于准备进入栈的元素，栈顶的第一个元素就是要计算的竖列，栈顶的第二个元素就是栈顶元素那个竖列的左侧的比它高的元素，准备进入栈的元素就是栈顶元素那个竖列的右侧比它高的元素。

![f43cd43268e99c6062ccf917bab7b82.jpg](https://www.misaka19327.cc/static/img/37d5af77ab934b73f5be44195d79e9d3.f43cd43268e99c6062ccf917bab7b82.jpg)

在以上的分析中，已经明确了单调栈比较大小的大或者小两种情况。那么如果想要进入栈的元素和栈顶元素相同呢？这时必须弹出栈顶元素，再加入新的元素，以防止`[5, 5, 1, 7]`这种情况。如果不先弹出元素再加入新的元素，在1处准备计算雨水时，长度就会从第一个元素开始计算，导致结果错误。

![25dc7546d2683f5a63bf53315b8f3f6.jpg](https://www.misaka19327.cc/static/img/ce899dfc04cb0548bd1b492b18221fb2.25dc7546d2683f5a63bf53315b8f3f6.jpg)

``` go
func trap(height []int) int {
	if len(height) == 1 || len(height) == 2 {
		return 0
	}
	
	result := 0
	stack := []int{0}
	for i := 1; i < len(height); i++ {
		top := stack[len(stack) - 1]
		if height[i] == height[top] {
			stack = stack[:len(stack) - 1]
			stack = append(stack, i)
		} else if height[i] < height[top] {
			stack = append(stack, i)
		} else {
			for len(stack) != 0 && height[i] > height[top] {
				middle := top
				stack = stack[:len(stack) - 1] // 弹出
				if len(stack) != 0 {
					top = stack[len(stack) - 1]
					h := min(height[top], height[i]) - height[middle]
					l := i - top - 1
					result += h * l
				}
			}
			stack = append(stack, i)
		}
	}
	
	return result
}
```