0%

Redis系列:

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

Redis对象

redis源码里面的结构体:

1
2
3
4
5
6
7
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 折返了。通过这个逻辑就可以精准计算出对象多长时间没有被访问——对象的空闲时间。

Read more »

声明:如果本文有错误,希望指出。

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

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

LinkedBlockingDeque

结构定义

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

Read more »

声明:如果本文有错误,希望指出。

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

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

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

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

Delayed

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

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
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;
}

}

内部结构

1
2
3
4
5
6
7
8
9
10
11
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();
}
Read more »

声明:如果本文有错误,希望指出。

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

二叉堆

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

队列结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)。

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
    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;
}
Read more »

声明:如果本文有错误,希望指出。

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

1
ArrayBlockingQueue queue = new ArrayBlockingQueue(100);

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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") 异常。

1
2
3
4
5
6
7
8
9
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");
}
Read more »

声明:如果本文有错误,希望指出。

对于实现线程安全队列,现在有两种方式: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:删除元素
Read more »

欢迎指正。

索引的一些基本认知:

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

索引的基础知识

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

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

创建索引的原则

创建索引的一些原则:

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

MySQL 存储结构

Read more »

声明:如果本文有错误,希望指出。

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

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

Read more »

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上面拉取镜像,启动比较方便。

1
2
3
4
docker search mongodb
docker pull <镜像>
docker images
docker run -p 27017:27017 -td <镜像>
Read more »

在项目中,事务可以有效的防止在程序出错时,对于数据的错误修改,回滚到修改之前。
spring事务和数据库事务一样,都有四个特性(ACID):

  • 原子性(Atomicity):事务是一个原子操作,由一系列动作组成。事务的原子性确保动作要么全部完成,要么完全不起作用;

  • 一致性(Consistency):一旦事务完成(不管成功还是失败),系统必须确保它所建模的业务处于一致的状态,而不会是部分完成部分失败。在现实中的数据不应该被破坏;

  • 隔离性(Isolation):可能有许多事务会同时处理相同的数据,因此每个事务都应该与其他事务隔离开来,防止数据损坏;

  • 持久性(Durability):一旦事务完成,无论发生什么系统错误,它的结果都不应该受到影响,这样就能从任何系统崩溃中恢复过来。通常情况下,事务的结果被写到持久化存储器中;

事务的传播性

官方文档解释

  • PROPAGATION_NESTED:如果当前存在事务,则创建一个事务作为当前事务的嵌套事务来运行;如果当前没有事务,则该取值等价于TransactionDefinition.PROPAGATION_REQUIRED。(比如我们设计ServiceA.methodA的事务级别为PROPAGATION_REQUIRED,ServiceB.methodB的事务级别为PROPAGATION_NESTED,那么当执行到ServiceB.methodB的时候,ServiceA.methodA所在的事务就会挂起,ServiceB.methodB会起一个新的子事务并设置savepoint,等待ServiceB.methodB的事务完成以后,他才继续执行。)
  • PROPAGATION_REQUIRED:支持当前事务,如果不存在则创建新事务。(方法B已经运行在方法A的事务内部,就不再起新的事务,直接加入方法A)。
  • RROPAGATION_REQUIRES_NEW:创建一个新事务,并暂停当前事务(如果存在)。(方法A所在的事务就会挂起,方法B会起一个新的事务,方法B新起的事务不依赖方法A的事务,等待方法B的事务完成以后,方法A才继续执行,如果方法B执行没有异常,方法A抛出异常,方法B的操作不会被回滚,方法A中除了方法B外,会回滚数据)。
  • PROPAGATION_SUPPORTS:如果当前存在事务中,即以事务的形式运行;如果不存在则以非事务方式执行。(方法B看到自己已经运行在方法A的事务内部,就不再起新的事务,直接加入方法A)
  • PROPAGATION_NOT_SUPPORTED:支持当前事务,如果不存在则创建新事务。(方法A所在的事务就会挂起,而方法B以非事务的状态运行完,再继续方法A的事务)。
  • PROPAGATION_MANDATORY:支持当前事务,如果有,使用当前事务;如果不存在则抛出异常。
  • PROPAGATION_NEVER:如果事务存在,则以非事务方式执行,抛出异常。(假设ServiceA.methodA的事务级别是PROPAGATION_REQUIRED, 而ServiceB.methodB的事务级别是PROPAGATION_NEVER ,那么ServiceB.methodB就要抛出异常了。)

下面给出一张图,对上面的事务传播性,做出总结:

事务的隔离性

事务并发可能引起的问题:

  • 脏读:脏读发生在一个事务读取了另一个事务改写但尚未提交的数据时。如果改写在稍后被回滚了,那么第一个事务获取的数据就是无效的;

  • 不可重复读:不可重复读发生在一个事务执行相同的查询两次或两次以上,但是每次都得到不同的数据时。这通常是因为另一个并发事务在两次查询期间进行了更新;

  • 幻读:幻读是由“可重复读”隔离级别导致的事务问题。事务T1查询某条数据,发现数据库没有数据,同时事务T2也查询这条数据,也同样没查询到。这时T1就将数据插入到了数据,由于可重复读的隔离级别,所以T2还是查询不到这条数据,然后T2插入了同样的数据,然后提示说数据以及存在,但是在事务T2中有查询不到这条数据,就像出现幻觉一样。

Read more »