Redis —— 数据库实现

Posted on 2018-08-01 Edited on 2021-05-30 In Redis

Redis系列：

Redis是一款NoSQL数据库，在大多数项目中作为缓存使用，也可以作为数据库，存储数据。

Redis源码

数据库

Redis服务器将所有数据库都保存在服务器状态 redis.h/redisServer 结构的 db 数组中，db 数组的每个项都是一个 redis.h/redisDb结构，每个 redis 结构代表个数据库:

struct redisServer {
    //...
    redisDb *db;//数组，保存服务器中的所有数据库
    //...
    int dbnum; //服务器数据库数量，默认16个
    //...
};
//数据库键空间
typedef struct redisDb {
    dict *dict;                 /* 数据库键空间，保存着数据库中所有键值对 */
    dict *expires;              /* 过期字典，保存所有过期时间*/
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

键空间和用户所见的数据库是直接对应的：

键空间的键也就是数据库的键，每个键都是一个字符串对象。
键空间的值也就是数据库的值，每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种 Redis 对象。

过期键删除策略

Redis —— 底层结构

Posted on 2018-07-31 Edited on 2021-03-30 In Redis

Redis系列：

对于Redis的一些基本知识，在之前的博客Redis——初识Redis中简单的介绍了。最近打算了解下Redis的一些底层内容，买了本书《Redis设计与实现》，这本书才看，也不好评价好坏。之所以选择这个本，是因为看到说这本书讲的是Redis的一些底层内容。

Redis对象

redis源码里面的结构体：

typedef struct redisObject {
    unsigned type:4; // 类型  
    unsigned encoding:4;// 编码方式 
    unsigned lru:LRU_BITS; // 对象的「热度」
    int refcount; // 引用计数
    void *ptr; // 对象的 body
} robj;

LRU

在 LRU 模式下，lru 字段存储的是 Redis 时钟 server.lruclock。Redis 时钟是一个 24bit 的整数，默认是 Unix 时间戳对 2^24 取模的结果，大约 97 天清零一次。当某个 key 被访问一次，它的对象头的 lru 字段值就会被更新为 server.lruclock。

默认 Redis 时钟值每毫秒更新一次，在定时任务 serverCron 里主动设置。Redis 的很多定时任务都是在 serverCron 里面完成的，比如大型 hash 表的渐进式迁移、过期 key 的主动淘汰、触发 bgsave、bgaofrewrite 等等。

如果 server.lruclock 没有折返 (对 2^24 取模)，它就是一直递增的，这意味着对象的 LRU 字段不会超过 server.lruclock 的值。如果超过了，说明 server.lruclock 折返了。通过这个逻辑就可以精准计算出对象多长时间没有被访问——对象的空闲时间。

Java阻塞队列 —— LinkedBlockingDeque 和 LinkedBlockingQueue

Posted on 2018-07-30 Edited on 2021-03-30 In Java

声明：如果本文有错误，希望指出。

LinkedBlockingDeque 则是一个由链表组成的双向阻塞队列。可以从对头、对尾两端插入和移除元素，同样意味着 LinkedBlockingDeque 支持FIFO、FILO两种操作方式。LinkedBlockingDeque 是可选容量的，在初始化时可以设置容量防止其过度膨胀，如果不设置，默认容量大小为Integer.MAX_VALUE。

LinkedBlockingQueue 是一个由链表组成的，只能从一端出一端入，支持 FIFO，并通过 ReentrantLock 和两个Condition实现。

LinkedBlockingDeque

结构定义

通过上面的Lock可以看出，LinkedBlockingDeque底层实现机制与LinkedBlockingQueue一样，依然是通过互斥锁ReentrantLock 来实现，notEmpty 、notFull 两个Condition做协调生产者、消费者问题。

public class LinkedBlockingDeque<E>
    extends AbstractQueue<E>
    implements BlockingDeque<E>, java.io.Serializable {
        static final class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;
        Node(E x) {
            item = x;
        }
    }
    transient Node<E> first;// 双向链表的表头
    transient Node<E> last;// 双向链表的表尾
    private transient int count;
    private final int capacity;//容量
    final ReentrantLock lock = new ReentrantLock();
    private final Condition notEmpty = lock.newCondition();
    private final Condition notFull = lock.newCondition();

基本API

LinkedBlockingDeque 的add、put、offer、take、peek、poll系列方法都是通过调用XXXFirst，XXXLast方法。因此只需要了解putFirst、putLast、pollFirst、pollLast。

putFirst

Java阻塞队列 —— DelayQueue

Posted on 2018-07-30 Edited on 2021-03-30 In Java

声明：如果本文有错误，希望指出。

DelayQueue是一个支持延时获取元素的无界阻塞队列。、队列元素会按照最终执行时间在队列中进行排序。当队列中的元素到达延迟时间时才会被取出。
主要作用：

缓存：清掉缓存中超时的缓存数据
任务超时处理

DelayQueue实现的关键主要有如下几个：

可重入锁ReentrantLock
用于阻塞和通知的Condition对象
根据Delay时间排序的优先级队列：PriorityQueue
用于优化阻塞通知的线程元素leader

Delayed

Delayed接口是用来标记那些应该在给定延迟时间之后执行的对象，它定义了一个long getDelay(TimeUnit unit)方法，该方法返回与此对象相关的的剩余时间。同时实现该接口的对象必须定义一个compareTo 方法，该方法提供与此接口的 getDelay 方法一致的排序。
先看下实例

class DelayTask implements Delayed {
    //定义该元素及其属性
    public String name;
    public Long delayTime;
    public TimeUnit delayTimeUnit;
    public Long executeTime;//ms

    DelayTask(String name, long delayTime, TimeUnit delayTimeUnit) {
        this.name = name;
        this.delayTime = delayTime;
        this.delayTimeUnit = delayTimeUnit;
        this.executeTime = System.currentTimeMillis() + delayTimeUnit.toMillis(delayTime);
    }
    //getDelay方法的作用即是计算当前时间到执行时间之间还有多长时间
    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(executeTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
    }
    //compareTo方法的作用即是判断队列中元素的顺序谁前谁后。当前元素比队列元素后执行时，返回一个正数，比它先执行时返回一个负数，否则返回0
    @Override
    public int compareTo(Delayed o) {
        if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
            return 1;
        } else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
            return -1;
        }
        return 0;
    }

}

内部结构

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {
        /** 可重入锁 */
    private final transient ReentrantLock lock = new ReentrantLock();
    /** 支持优先级的BlockingQueue */
    private final PriorityQueue<E> q = new PriorityQueue<E>();
     /** 用于优化阻塞 */
    private Thread leader = null;
    /** Condition */
    private final Condition available = lock.newCondition();
    }

Java阻塞队列 —— PriorityBlockingQueue

Posted on 2018-07-29 Edited on 2021-03-30 In Java

声明：如果本文有错误，希望指出。

PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。在Thread中，我们可以通过 setPriority(int newPriority) 来设置优先级，线程优先级高的线程先执行，优先级低的后执行。 PriorityBlockingQueue 默认情况下元素采用自然顺序升序排序，当然我们也可以通过构造函数来指定Comparator来对元素进行排序。需要注意的是PriorityBlockingQueue不能保证同优先级元素的顺序。
PriorityBlockingQueue底层是二叉堆构成实现的，下面先介绍一些二叉堆知识点。

二叉堆

二叉堆是一种特殊的堆，就结构性而言就是完全二叉树或者是近似完全二叉树，满足树结构性和堆序性。树机构特性就是完全二叉树应该有的结构，堆序性则是：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。

队列结构定义

public class PriorityBlockingQueue<E> extends AbstractQueue<E>
    implements BlockingQueue<E>, java.io.Serializable {
    private static final long serialVersionUID = 5595510919245408276L;
    //默认初始化大小11
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    //定义列表最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //二叉堆数组
    private transient Object[] queue;
    private transient int size;//队列个数
    // 比较器，如果为空，则为自然顺序
    private transient Comparator<? super E> comparator;
    private final ReentrantLock lock;
    private final Condition notEmpty;
    }

入队

PriorityBlockingQueue是无界的，所以不可能会阻塞。内部调用offer(E e)。

    public void put(E e) {
        offer(e); // never need to block
    }
    public boolean add(E e) {
        return offer(e);
    }
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        int n, cap;
        Object[] array;
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator;
            // 根据比较器是否为null，做不同的处理
            if (cmp == null)
                siftUpComparable(n, e, array);
            else
                siftUpUsingComparator(n, e, array, cmp);
            size = n + 1;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
        return true;
    }
    //采用自然排序，调用siftUpComparable方法
    private static <T> void siftUpComparable(int k, T x, Object[] array) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = array[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            array[k] = e;
            k = parent;
        }
        array[k] = key;
    }
//当比较器不为null时，采用所指定的比较器，调用siftUpUsingComparator方法
    private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
                                       Comparator<? super T> cmp) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = array[parent];
            if (cmp.compare(x, (T) e) >= 0)
                break;
            array[k] = e;
            k = parent;
        }
        array[k] = x;
    }

Java阻塞队列 —— ArrayBlockingQueue

Posted on 2018-07-29 Edited on 2021-03-30 In Java

声明：如果本文有错误，希望指出。

ArrayBlockingQueue 是一个数组实现的有界阻塞队列，采用FIFO算法对队列元素进行排序。

1	ArrayBlockingQueue queue = new ArrayBlockingQueue(100);

定义

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    private static final long serialVersionUID = -817911632652898426L;
    //一个定长数组，维护ArrayBlockingQueue的元素
    final Object[] items;
    //为ArrayBlockingQueue对首位置
    int takeIndex;
    //ArrayBlockingQueue对尾位置
    int putIndex;
    //元素个数
    int count;
    //重入锁，出列入列都必须获取该锁，两个步骤公用一个锁
    final ReentrantLock lock;
    //出列条件
    private final Condition notEmpty;
    //入列条件
    private final Condition notFull;
    transient Itrs itrs = null;
}

ArrayBlockingQueue继承AbstractQueue，实现BlockingQueue接口。AbstractQueue提供了对queue操作的骨干实现。BlockingQueue继承java.util.Queue为阻塞队列的核心接口，提供了在多线程环境下的出列、入列操作，作为使用者，则不需要关心队列在什么时候阻塞线程，什么时候唤醒线程，所有一切均由BlockingQueue来完成。
ArrayBlockingQueue内部使用可重入锁ReentrantLock + Condition来完成多线程环境的并发操作。

入队

add(E e)

add(E e)调用父类AbstractQueue接口，如果添加成功，返回true，否则抛出 IllegalStateException("Queue full") 异常。

public boolean add(E e) {
    return super.add(e);
}
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

Java并发容器 —— ConcurrentLinkedQueue

Posted on 2018-07-27 Edited on 2021-03-30 In Java

声明：如果本文有错误，希望指出。

对于实现线程安全队列，现在有两种方式：1、使用阻塞算法；2、使用非阻塞算法。使用阻塞算法的队列是锁的应用。非阻塞则是CAS算法的应用。

简介

CoucurrentLinkedQueue是一个基于链接节点的无界线程安全队列，采用 FIFO 对节点排序。CoucurrentLinkedQueue是一个非阻塞队列。
CoucurrentLinkedQueue规定了如下几个不变性：

在入队的最后一个元素的next为null
队列中所有未删除的节点的item都不能为null且都能从head节点遍历到
对于要删除的节点，不是直接将其设置为null，而是先将其item域设置为null（迭代器会跳过item为null的节点）
允许head和tail更新滞后。这是什么意思呢？意思就说是head、tail不总是指向第一个元素和最后一个元素。

CoucurrentLinkedQueue结构

CoucurrentLinkedQueue 继承 AbstractQueue。CoucurrentLinkedQueue 是由head节点和tair节点组成，每个节点（Node）又节点元素（item）和主项下一个节点的（next）组成。默认情况下head节点存储的元素为空，tair节点等于head节点。

CoucurrentLinkedQueue主要方法：

add/offer：add是调用offer方法的，指定元素插入到队列尾部
poll：拉取头部元素
remove：删除元素

MySQL 索引

Posted on 2018-07-24 Edited on 2021-03-30 In MySQL

欢迎指正。

索引的一些基本认知：

索引可以加快数据库的检索速度
表经常进行INSERT/UPDATE/DELETE操作就不要建立索引了，换言之：索引会降低插入、删除、修改等维护任务的速度。
索引需要占物理和数据空间。
了解过索引的最左匹配原则
知道索引的分类：聚集索引和非聚集索引
MySQL 支持Hash索引和B+树索引两种

索引的基础知识

为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间 (因为索引也要随之变动)。
创建索引可以大大提高系统的性能。

通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
可以加速表和表之间的连接，
使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

创建索引的原则

创建索引的一些原则：

较频繁的作为查询条件的字段应该创建索引
唯一性太差的字段不适合单独创建索引，即使频繁作为查询条件
更新非常频繁的字段不适合创建索引（数据库会将索引数据根据算法排序，数据量大之后重新排序会占用过多资源）
用于索引的最好的备选数据列是那些出现在WHERE子句、join子句、ORDER BY或GROUP BY子句中的列。

MySQL 存储结构

Java 对象地址问题

Posted on 2018-07-23 Edited on 2021-03-30 In 问题

声明：如果本文有错误，希望指出。

上周在写代码的时候，碰到一个问题：代码结构如下图，前端传过来一个对象，我在service方法中会通过不同方法，每个方法中都有相对于的修改，然后插入数据库。但是发现在方法A中对传值进行修改，其中修改后的值，使用了静态变量保存，但是发现前面的变量的值编程了C中最后的变量。

后来分析了下，通过 = 去进行赋值，只是把变量的地址指向了对象，然后，修改对象，变量重新指向对象，最后发现变量也跟着对象改变了。

Spring Boot 整合 MongoDB

Posted on 2018-07-11 Edited on 2021-03-30 In Spring Boot

MongoDB简介

MongoDB（来自于英文单词“Humongous”，中文含义为“庞大”）是可以应用于各种规模的企业、各个行业以及各类应用程序的开源数据库。作为一个适用于敏捷开发的数据库，MongoDB的数据模式可以随着应用程序的发展而灵活地更新。与此同时，它也为开发人员提供了传统数据库的功能：二级索引，完整的查询系统以及严格一致性等等。 MongoDB能够使企业更加具有敏捷性和可扩展性，各种规模的企业都可以通过使用MongoDB来创建新的应用，提高与客户之间的工作效率，加快产品上市时间，以及降低企业成本。

MongoDB是专为可扩展性，高性能和高可用性而设计的数据库。它可以从单服务器部署扩展到大型、复杂的多数据中心架构。利用内存计算的优势，MongoDB能够提供高性能的数据读写操作。 MongoDB的本地复制和自动故障转移功能使您的应用程序具有企业级的可靠性和操作灵活性。

MongoDB是一个介于关系数据库和非关系数据库之间的产品，是非关系数据库当中功能最丰富，最像关系数据库的。他支持的数据结构非常松散，是类似json的bjson格式，因此可以存储比较复杂的数据类型。Mongo最大的特点是他支持的查询语言非常强大，其语法有点类似于面向对象的查询语言，几乎可以实现类似关系数据库单表查询的绝大部分功能，而且还支持对数据建立索引。

传统的关系数据库一般由数据库（database）、表（table）、记录（record）三个层次概念组成，MongoDB是由数据库（database）、集合（collection）、文档对象（document）三个层次组成。MongoDB对于关系型数据库里的表，但是集合中没有列、行和关系概念，这体现了模式自由的特点。

MongoDB中的一条记录就是一个文档，是一个数据结构，由字段和值对组成。MongoDB文档与JSON对象类似。字段的值有可能包括其它文档、数组以及文档数组。MongoDB支持OS X、Linux及Windows等操作系统，并提供了Python，PHP，Ruby，Java及C++语言的驱动程序，社区中也提供了对Erlang及.NET等平台的驱动程序。

MongoDB的适合对大量或者无固定格式的数据进行存储，比如：日志、缓存等。对事物支持较弱，不适用复杂的多文档（多表）的级联查询。文中演示mongodb版本为3.4

MongoDB安装

对于MongoDB的安装，可以选择官网下载，也可以通过docker安装等。个人感觉直接从docker上面拉取镜像，启动比较方便。

docker search mongodb
docker pull <镜像>
docker images
docker run -p 27017:27017 -td <镜像>