拈花

转载请注明出处:www.huamo.online
字节杭州 求贤若渴:

  1. https://job.toutiao.com/s/JXTdQaH
  2. https://job.toutiao.com/s/JXTMWW3
  3. https://job.toutiao.com/s/JXT1tpC
  4. https://job.toutiao.com/s/JXTdu6h

拈花

这里集合一些小碎片知识

布隆过滤器

布隆过滤器主要用于判断一个元素是否在一个集合中,时间和空间方面都很高效。它可以用来判断一个元素绝对不存在于集合中,或者一个元素可能存在于集合中

原理

一个布隆过滤器指的是一个位数组和几个相互独立的Hash函数,用m代指数组中比特位的个数,用k代指Hash函数的数量。初始状态下,位数组中每一位都置为0

插入元素

一个新的元素进来,通过k个哈希函数作用后,映射到位数组中的k个位置,将这些位置都置为1

查找元素

查找一个元素是否在集合中,先将这个元素通过k个哈希函数映射,找到位数组中这k个位置,查看它们是否全为1

  • 如果全都为1,说明这个元素可能存在于集合中。

  • 否则,说明这个元素一定不存在于集合中

图例

下图是布隆过滤器的示意

可以看到:位数组m = 18, 哈希函数k = 3x, y, z三个元素插入到了布隆过滤器中,例如元素x映射在了{1, 5, 13}这3个位置上。当查找元素w是否在集合中时,由于映射位置不全为1,所以可以判断w一定不在这个集合中。而如果有一个元素s,它映射在了{3, 4, 5}这些位置上,全为1,那我们就知道s可能在这个集合中,因为从图中我们可以看出:这3个位置是x, y, z映射结果的一部分。

数据库事务

数据库中事务的四大特性ACID

  1. 原子性:事务中包含的所有操作要么全部成功,要么全部失败回滚。

  2. 一致性:事务必须使数据库从一个一致性状态变换到另一个一致性状态。即事务执行前后,各种constraint都依然满足。

  3. 隔离性:当多个用户并发操作时,多个并发事务所做的修改必须要相互隔离。事务查看数据时数据所处的状态,要么是另一并发事务修改它之前的状态,要么是另一事物修改它之后的状态,事务不会查看中间状态的数据。亦即:一个事务所产生的影响在该事务提交之前对其它事务都不可见。

  4. 持久性:事务完成之后,它对于系统的影响是永久性的。即使数据库系统遇到了故障,这次的修改也将一直保持。

不支持并发会出现的问题

不支持并发,即不支持事务的隔离性,则会产生如下几个问题:

  • 脏读:一个事务读取到了另一个并发事务尚未提交的修改。同一事务内不存在脏读。例如常见的转账操作,设想如下场景:
1
2
3
update account set money=money+100 where name=’B’;
(此时A通知B,让B check到账没)
update account set money=money - 100 where name=’A’;

转账事务包含了2条SQL,当事务执行完第一条语句后,A通知B,让B check账户到账没,于是B发起了一个新的select事务,由于没有隔离性,此时发生了脏读,select事务发现确实到账了,但此后,A刻意不提交该事务,数据被全部回滚,当B以后再次查看账户时,发现钱并没有增加。

  • 不可重复读:在一个事务内部,多次查询数据库中同一个值,返回了不同的数据结果。这是因为在查询间隔,数据被其它并发事务修改并提交了。

    和脏读不同,不可重复读是读取了一个已经修改完成的数据,而脏读是读取了一个中间状态的脏数据。虽然读取一个已经修改完成的数据看起来是合理的,但是在一个事务内部过程中,多次重复读应该返回同样的值,它要么是该事务开始时,数据已经被其它事务修改,此时该事务内部多次重复读,都返回修改后的,相同的数据;要么就是该事务开始时,数据还未被修改,此时该事务内部多次重复读,都返回未修改的,相同的数据,即使此时数据被其它事务修改并提交了,但是对这个事务内部来说,这个修改也应该是被隔离的。

  • 幻读:一个事务在操作过程中进行了2次查询,第二次查询结果包含了第一次查询中未出现的数据,就像产生了幻觉。这也是因为在2次查询间隔中,有另外的事务插入或删除了数据并提交。

    例如A事务做了一次对所有行update某一列的操作,然后B事务插入了一行新数据,然后A事务又做了一次select所有行的操作,以确认update是否正确完成,但此时发现有一行并没有被修改,这便是幻读。

    不可重复读针对的是同一数据的多次查询结果不同,而幻读则不讲究数据的同一性,甚至不要求2次操作是相同的SQL,它只是强调多次操作发现了之前操作中未出现过的数据。

  • 丢失修改:分两类情况。1. 当两个事务更新相同的数据源,两个事务同时读取了数据,A事务修改并提交,然后B事务失败回滚,数据回到了B事务执行前的状态。由于没有隔离,那么A事务做的更新也被回滚掉了。2. 有两个事务同时更新相同数据源,A事务修改并提交,然后B事务也修改并提交,那么A事务所做的写操作会被覆盖。

数据库4种隔离级别

  • Read Uncommitted(可以读取未提交的数据):即使一个更新事务还没有提交,但是它内部所做的改变也可以被别的事务读取到。这是最低级别的隔离,允许脏读的发生,这一级别基本不能正确的支持并发。

  • Read Committed(只能读取到已经提交的数据):只有事务提交了以后,所做的改变才能被其它事务读取到,可以避免脏读的发生,但是不能解决不可重复读的问题。

  • Repeatable Read(可重复读):意思很明了,就是可重复读,这个级别可以避免脏读,也可以避免不可重复读,但是不能避免幻读。这也是MySQL默认的隔离级别。

  • Serializable(串行化操作):将所有的事务序列化操作,一个事务执行的时候不允许别的事务并发执行,完全一个单线程的样子读,每个事务执行都需要获得表级共享锁,读写相互都会阻塞。因为完全序列化操作,不允许不一致现象的出现,所以就没有上述并发问题。

事务并发控制实现方式

为了实现事务的ACID特性,数据库实现中大量用到了锁,根据并发控制的方式划分,可以分为悲观锁(PCC)乐观锁(OCC)

悲观锁:对每次数据操作都持悲观态度,认为有别人正在操作这个数据。所以悲观锁控制就是指每次去操作数据的时候,都会尝试给数据加锁,如果锁成功,则安心修改数据,提交事务,解锁释放;如果锁失败,则说明别人正在操作,等待解锁或者直接报错。

乐观锁:对每次数据操作都持乐观态度,认为别人正在操作这个数据的概率极低。所以乐观锁控制就是指每次去操作数据的时候,不需要加锁直接对读取的数据副本进行修改,一直到事务完成要提交的时候,再去真正比对在这期间数据是否已经被别人修改,如果在事务操作期间,没人修改这个数据,则提交修改;如果这期间数据被别人修改了,则回滚自己的修改,并向用户报错。

乐观锁一般都用一个额外的version字段来实现,每次修改数据前都将连带的version字段也读取出来,提交时比对version是否变化,如果变化说明别人修改了数据则报错,如果没有变则说明没人修改数据,提交修改并version + 1

或者

如果不能新增额外字段,也可以check待更新字段作为数据是否过时的标准

操作系统中的锁

自旋锁:和互斥锁类似,也是为了实现互斥得使用共享资源。但是自旋锁不会引起线程的睡眠,而是处于一直忙等待的状态,自旋二字因此得名,避免了进程上下文的切换开销。被自旋锁阻塞的线程还会一直占用CPU,因为它要一直轮询锁是否已经被释放。

数据库中的锁

行级锁

MySQL中的行级锁是锁定粒度最细的锁,它分为共享锁排他锁两种。

  • 共享锁(Share Lock 或者 S锁):又称读锁,是读取操作创建的锁。其它事务可以并发读取数据,但任何事务都不能对数据进行修改,直到已释放所有共享锁。如果事务T对数据A加上共享锁后,则其它事务只能对A再加共享锁,不能加排他锁。获准共享锁的事务只能读数据,不能修改数据。

    用法:select ... lock in share mode;

    在查询语句后面增加lock in share mode,MySQL会对查询结果中的每一行都尝试加共享锁,当没有其它线程对其中任一行使用排他锁时,共享锁便可以申请成功,否则就会被阻塞。其它线程也可以读取使用了共享锁的数据,而且这些线程读取到的都是同一版本的数据。

  • 排他锁(eXclusive Lock 或者 X锁):又称写锁,如果事务T对数据A加上排他锁后,则其它事务不能再对A加任何类型的锁。获取排他锁的事务既能读数据,又能修改数据。

    用法:select ... for update;

    在查询语句后面增加for update,MySQL会对查询结果中每一行都加排他锁,当没有其它线程对其中任一行使用任何行级锁时,排他锁即可申请成功,否则会被阻塞。

表级锁

意向锁就是表级别的锁,就像名字那样,其目的是为了在事务中揭示下一行将要被请求锁的类型,包含:意向共享锁(IS锁),意向排他锁(IX锁)。

意向共享锁(IS锁):表示事务准备给数据行加入S锁,即一个数据行加共享锁之前必须先取得该表的IS锁

意向排他锁(IX锁):表示事务准备给数据行加入X锁,即一个数据行加排他锁之前必须先取得该表的IX锁

意向锁是InnoDB自动加的,不需要用户干预。对于insert, update, delete,InnoDB会自动给涉及的数据加上排他锁;对于一般的select语句,InnoDB不会加任何锁。

待续

转载请注明出处:www.huamo.online