Heap And Stack 堆与栈的区别

堆与栈的区别

推荐:https://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/

栈是上下顺序存储的,且“先进后出LIFO”规则,只能删除顶部的元素,而堆是没有特定的顺序的存储,您可以删除任意元素。堆分配需要维护分配的内存和未分配的内存的完整记录,以及一些开销维护以减少碎片,找到足够大以适应请求大小的连续内存段,等等。内存可以随时释放,留出自由空间。有时,内存分配器将执行维护任务,比如通过将分配的内存到处移动来对内存进行碎片整理,或者在运行时进行垃圾收集——当内存不再处于作用域中时对其进行标识并释放它。

1. 栈用在线程中,程序执行时由线程创建有限数量的栈空间,当线程结束的时候会自动回收,属于系统级。
堆一般是由应用程序在启动时创建,由应用程序回收,属于应用级。

The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.

2. 栈的大小固定,通常在程序启动时已经确定了最大大小(部分语言支持动态扩容)。如果超出会出现“stack overflow”异常,经常在“递归”函数里出现。
堆是由”动态分配“的,其大小不固定,你可以在任何时间创建,再在任何时间回收(还是受限限系统虚拟内存 (ie: RAM and swap space))。

3. 每个线程可有一个堆栈,而应用程序通常只有一个堆(尽管对于不同类型的分配有多个堆并不罕见)

4. 栈的读取速度要更快。因为分配内存的机制,只是移动指针,而堆还要做查找等操作。

Which is faster – the stack or the heap? And why?

The stack is much faster than the heap. This is because of the way that memory is allocated on the stack. Allocating memory on the stack is as simple as moving the stack pointer up.

 

Variables allocated on the stack, or automatic variables, are stored directly to this memory. Access to this memory is very fast, and it’s allocation is dealt with when the program is compiled. Large chunks of memory, such as very large arrays, should not be allocated on the stack to avoid overfilling the stack memory (known as stack overflow). Stack variables only exist in the block of code in which they were declared. For example:

堆和栈在内存分配方面的不同:http://timmurphy.org/2010/08/11/the-difference-between-stack-and-heap-memory-allocation/

5. 堆和栈在用在函数变量的时候有些不同,一般动态创建的变量是存储在堆heap中,访问速度慢一些,而放在栈里的变量访问速度要快的多。

Variables allocated on the heap, or dynamic variables, have their memory allocated at run time (ie: as the program is executing). Accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory (ie: RAM and swap space). This memory remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was allocated.

如编码中的定义一个变量 int i = 20 则变量 i 存储在stack中;创建一个对象 user = new Account(); //这时user变量则存储在heap中。

堆与栈用法示例

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;

https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap

http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/

视频 https://www.youtube.com/watch?v=450maTzSIvA

https://blog.csdn.net/waidazhengzhao/article/details/76651923

Golang中的调度器

介绍(Introduction)
———————
Go 1.1最大的特色之一就是这个新的调度器,由Dmitry Vyukov贡献。新调度器让并行的Go程序获得了一个动态的性能增长,针对它我不能再做点更好的工作了,我觉得我还是为它写点什么吧。

这篇博客里面大多数东西都已经被包含在了[原始设计文档](https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw)中了,这个文档的内容相当广泛,但是过于技术化了。

关于新调度器,你所需要知道的都在那个设计文档中,但是我这篇博客有图片,所以更加清晰易懂。

带调度器的Go runtime需要什么?(What does the Go runtime need with a scheduler?)
——————————————————————————-
但是在我们开始看新调度器之前,我们需要理解为什么需要调度器。为什么既然操作系统能为我们调度线程了,我们又创造了一个用户空间调度器? Continue reading

MySQL中的半同步复制

MySQL当前存在的三种复制模式有:异步模式、半同步模式和组复制模式。注意:MySQL复制模式没有“同步复制”这一项的,文章中只是为了读者方便理解半同步复制的概念才介绍了同步复制概念https://dev.mysql.com/doc/refman/8.0/en/replication-semisync.html

从MySQL5.5开始,MySQL以插件的形式支持半同步复制。

1. 异步复制(Asynchronous replication)

MySQL默认的复制即是异步的,主库在执行完客户端提交的事务后会立即将结果返给给客户端,并不关心从库是否已经接收并处理,这样就会有一个问题,主如果crash掉了,此时主上已经提交的事务可能并没有传到从上,如果此时,强行将从提升为主,可能导致新主上的数据不完整。

异步复制是MySQL最早的也是当前使用最多的复制模式,异步复制提供了一种简单的主-从复制方法,包含一个主库(master)和备库(一个,或者多个) 之间,主库执行并提交了事务,在这之后(因此才称之为异步),这些事务才在从库上重新执行一遍(基于statement)或者变更数据内容(基于 row),主库不检测其从库上的同步情况。在服务器负载高、服务压力大的情况下主从产生延迟一直是其诟病。工作流程简图如下:

而同步复制(Fully synchronous replication,MySQL中没有此复制概念)指当主库执行完一个事务,所有的从库都执行了该事务才返回给客户端。因为需要等待所有从库执行完该事务才能返回,所以全同步复制的性能必然会收到严重的影响。

2. 半同步复制(Semisynchronous replication)

介于异步复制和全同步复制之间,主库在执行完客户端提交的事务后不是立刻返回给客户端,而是等待至少一个从库接收到并写到relay log中才返回给客户端。相对于异步复制,半同步复制提高了数据的安全性,同时它也造成了一定程度的延迟,这个延迟最少是一个TCP/IP往返的时间。所以,半同步复制最好在低延时的网络中使用。

MySQL5.5 的版本在异步同步的基础之上,以插件的形式实现了一个变种的同步方案,称之为半同步复制(semi-sync replication)。这个插件在原生的异步复制上,添加了一个同步的过程:当从库接收到了主库的变更(即事务)时,会通知主库。主库上的操作有两种:接收到这个通知以后才去commit事务接受到之后释放session。这两种方式是由主库上的具体配置决定的。当主库收不到从库的变更通知超时时,由半同步复制自动切换到异步同步,这样就极大了保证了数据的一致性(至少一个从库),但是在性能上有所下降,特别是在网络不稳定的情况下,半同步和同步之间来回切换,对正常的业务是有影响的。其工作流程简图如下:

Continue reading

kubernetes中apiserver的证书

在kubernetes中,与api server 通讯时一般都需要使用https证书,这些证书文件存在放 /etc/kubernetes/pki 目录中(ubuntu)。主要有以下几种

/etc/kubernetes/pki/ca.{crt,key}

如果你已有现成的证书也可以直接将证书复制到这个目录里即可。这时kubeadm就会跳过证书生成这个步骤。

证书生成后,kubeadm 接下来会为其它组件生成访问api server 所需要的配置文件,这些文件路径为: /etc/kubernetes/xxx.conf:

ls /etc/kubernetes/
admin.conf controller-manager.conf kubelet.conf scheduler.conf

这里可以看到这四个配置文件,分别 为不同的组件之间提供配置。

这些配置文件中存储的是Master节点的ip地址、端口号、证书目录等信息。这样对应的客户端(scheduler,kubelet, controller-manager等)就可以直接加载并读取相应的配置文件来与kube-apiserver 建立安全连接,实现通讯。

附kubernetes架构图

Git中的git reset的三种参数的区别

我们平时在使用git的时候,经常会遇到需要撤销上次操作的需求,这时候需要用到git reset的这个命令,他的使用就是 “git-reset – Reset current HEAD to the specified state”, 注意这里主要操作的就是这个 HEAD

为了方便我们先了解一下 Git 的工作流程

相信大家对这个图已经很熟悉了,其中index也叫stage暂存区或者暂存索引区。git reset 共有三个互斥参数分别为”–soft”、”–mixed(默认参数)” 和 “–hard”,每种参数表示一种恢复模式,下面我们将分别看一下这git reset 三个参数的用法区别。 Continue reading

MySQL中对MVCC的理解总结

一、MVCC简介

MVCC (Multiversion Concurrency Control),即多版本并发控制技术。InnoDB数据库的事务隔离级别就是通过UNDO和MVCC来实现的(ACID特性),旧数据存储在UNDO中,再通过DB_ROLL_PTR 回溯查找历史版本。

二、MVCC原理

1、通过DB_ROLL_PT 回溯查找数据历史版本
2、通过read view判断行记录是否可见

理解这一块之前,我们必须先了解一下row的内部存储格式

字段说明:

  • DB_ROW_ID:长度6个字节。此值当由InnoDB自动生成,聚集索引时使用。如果用户未显式指定表主键时,表使用DB_ROW_ID的值作为主键ID,聚集索引会使用此值。如果指定了表主键的话,则聚集索引使用指定的值。
  • DB_TRX_ID:6个字节的事务ID。标记了最后更新此记录的事务ID,每开起一个新事务,其值自动+1
  • DB_ROLL_PTR:7字节的回滚指针。指向当前记录项的undo log记录,找之前版本的数据需通过此指针。

MySQL中的MVCC原理

新insert记录的DB_ROLL_PTR指针为NULL。修改新值后,记录的 DB_ROLL_PTR 回滚指针指向原始值在Undo Log 日志的位置,也就是说将原值在Unde Log的物理位置存储到原记录的 DB_POLL_PTR 字段。如果事务回滚的话,则从Undo Log 中把原始值读取出来再放到记录中去。如果直接commit的话,则直接保存即可。

– InnoDB Undo Log的日志类型
MySQL数据库InnoDB存储引擎的undo log采用了逻辑的日志
InnoDB undo log的格式可以概括为:<操作类型>+<Table ID>+<数据>.

  A. 从表中删除一行记录
TRX_UNDO_DEL_MARK_REC (将主键记入日志)
在删除一条记录时,并不是真正的将数据从数据库中删除,只是标记为已删除.这样做的好处是Undo Log中不用记录整行的信息.在undo时操作也变得很简单.
  B. 向表中插入一行记录
TRX_UNDO_INSERT_REC (仅将主键记入日志)
TRX_UNDO_UPD_DEL_REC (将主键记入日志) 当表中有一条被标记为删除的记录和要插入的数据主键相同时, 实际的操作是更新这个被标记为删除的记录。
  C. 更新表中的一条记录
TRX_UNDO_UPD_EXIST_REC (将主键被更新了的字段内容记入日志)
TRX_UNDO_DEL_MARK_REC 和 TRX_UNDO_INSERT_REC,当更新主键字段时,实际执行的过程是删除旧的记录然后,再插入一条新的记录。

事务隔离级别的区别:

  • RR隔离级别下,在每个事务开始的时候,会将当前系统中的所有的活跃事务拷贝到一个列表中(read view)。
  • RC隔离级别下,在事务中的每个语句开始(select)时,会将当前系统中的所有的活跃事务拷贝到一个列表中(read view)
  • 然后按照以下逻辑判断事务的可见性

MVCC解决了什么问题

  • MVCC使得数据库读不会对数据加锁,普通的SELECT请求不会加锁,提高了数据库的并发处理能力;
  • 借助MVCC,数据库可以实现RC,RR等隔离级别,用户可以查看当前数据的前一个或者前几个历史版本。保证了ACID中的I特性(隔离性)。

查看当前数据库中的活跃事务,可执行

SELECT * FROM INFORMATION_SCHEMA.INNODB_TRX

参考:
https://mp.weixin.qq.com/s/tNA_-_MoYt1fJT0icyKbMg

MySQL数据库InnoDB存储引擎Log漫游(2)

MySQL多版本并发控制分析 

MySQL之ICP、MRR、BKA、BNL

Index Condition Pushdown(ICP)

Index Condition Pushdown (ICP)mysql使用索引从表中检索行数据的一种优化方式。

ICP原理

禁用ICP,存储引擎会通过遍历索引定位基表中的行,然后返回给MySQL Server层,再去为这些数据行进行WHERE后的条件的过滤。

开启ICP,如果部分WHERE条件能使用索引中的字段,MySQL Server 会把这部分下推到存储引擎层,存储引擎通过索引过滤,把满足的行从表中读取出。ICP能减少引擎层访问基表的次数和MySQL Server 访问存储引擎的次数。

ICP的目标是减少从基表中全纪录读取操作的数量,从而降低IO操作

对于InnoDB表,ICP只适用于辅助索引。

ICP标识

当使用ICP优化时,执行计划的Extra列显示Using indexcondition提示

相关参数

optimizer_switch="index_condition_pushdown=on”; 

适用场景

#辅助索引INDEX (zipcode, lastname, firstname).

SELECT * FROM people WHERE zipcode='95054'AND lastname LIKE '%etrunia%'AND address LIKE '%Main Street%';

People表有个二级索引INDEX (zipcode, lastname, firstname),用户只知道某用户的zipcode,和大概的lastname、address,此时想查询相关信息。

若不使用ICP:则是通过二级索引中zipcode的值去基表取出所有zipcode=’95054’的数据,然后server层再对lastname LIKE ‘%etrunia%’AND address LIKE ‘%Main Street%’;进行过滤

若使用ICP:则lastname LIKE ‘%etrunia%’AND address LIKE ‘%Main Street%’的过滤操作在二级索引中完成,然后再去基表取相关数据

使用限制

l  只支持 select 语句

l  5.6 中只支持 MyISAM与InnoDB引擎

l  5.6中不支持分区表的ICP;从MySQL 5.7.3开始支持分区表的ICP

l  ICP的优化策略可用于range、ref、eq_ref、ref_or_null 类型的访问数据方法;

l  不支持主建索引的ICP(对于Innodb的聚集索引,完整的记录已经被读取到Innodb Buffer,此时使用ICP并不能降低IO操作)

l  当 SQL 使用覆盖索引时但只检索部分数据时,ICP 无法使用

l  ICP的加速效果取决于在存储引擎内通过ICP筛选掉的数据的比例。

Multi-Range Read (MRR)

MRR 的全称是 Multi-Range Read Optimization,是优化器将随机 IO 转化为顺序 IO 以降低查询过程中 IO 开销的一种手段。

MRR原理

select non_key_column from tb where ey_column=x;

在没有使用MRR特性时,MySQL执行查询的伪代码

第一步 先根据where条件中的辅助索引获取辅助索引与主键的集合,结果集为rest。

select key_column, pk_column from tb where key_column=x order by key_column

第二步 通过第一步获取的主键来获取对应的值。

for each pk_column value in rest do:

select non_key_column from tb where pk_column=val

使用MRR特性时,MySQL执行查询的伪代码

第一步 先根据where条件中的辅助索引获取辅助索引与主键的集合,结果集为rest

select key_column, pk_column from tb where key_column = x order by key_column

第二步 将结果集rest放在buffer里面(read_rnd_buffer_size 大小直到buffer满了),然后对结果集rest按照pk_column排序,得到结果集是rest_sort

第三步 利用已经排序过的结果集,访问表中的数据,此时是顺序IO.

       select non_key_column fromtb where pk_column in (rest_sort)

综上

在不使用 MRR 时,优化器需要根据二级索引返回的记录来进行“回表”,这个过程一般会有较多的随机IO, 使用MRR时,SQL语句的执行过程是这样的:

1)   优化器将二级索引查询到的记录放到一块缓冲区中

2)   如果二级索引扫描到文件的末尾或者缓冲区已满,则使用快速排序对缓冲区中的内容按照主键进行排序

3)   用户线程调用MRR接口取cluster index,然后根据cluster index 取行数据

4)   当根据缓冲区中的 cluster index取完数据,则继续调用过程 2) 3),直至扫描结束

通过上述过程,优化器将二级索引随机的 IO 进行排序,转化为主键的有序排列,从而实现了随机 IO 到顺序 IO 的转化,提升性能

此外MRR还可以将某些范围查询,拆分为键值对,来进行批量的数据查询,如下:

SELECT * FROM tWHERE key_part1 >= 1000 AND key_part1 <
2000AND 
key_part2 = 10000;

表t上有二级索引(key_part1, key_part2),索引根据key_part1,key_part2的顺序排序。

若不使用MRR:索引扫描会将key_part1在1000到2000的索引元组,而不管key_part2的值,这样对key_part2不等于10000的索引元组也做了额外的扫描。此时扫描的范围是:

[{1000, 10000}, {2000, MIN_INT}]此间隔可能包含key_part2不等于10000的部分

若使用MRR:扫描则分为多个范围,对于每一个Key_part1(1000,1001…,1999)单个值的扫描只需要扫描索引中key_part2为10000的元组。如果索引中包含很多key_part2不为10000的元组,最终MRR的效果越好。MRR扫描的范围是多个单点间隔[{1000, 10000}],
…, [{1999, 10000}] 此间隔只包含key_part2=10000的部分。

MRR标识

当使用ICP优化时,执行计划的Extra列显示Using MRR提示

相关参数

用optimizer_switch 的标记来控制是否使用MRR.设置mrr=on时,表示启用MRR优化。

mrr_cost_based表示是否通过cost base的方式来启用MRR.

mrr=on,mrr_cost_based=on,则表示cost base的方式还选择启用MRR优化,当发现优化后的代价过高时就会不使用该项优化

当mrr=on,mrr_cost_based=off,则表示总是开启MRR优化

SET  @@optimizer_switch='mrr=on,mrr_cost_based=on';

参数read_rnd_buffer_size 用来控制键值缓冲区的大小。二级索引扫描到文件的末尾或者缓冲区已满,则使用快速排序对缓冲区中的内容按照主键进行排序

适用场景

#辅助索引key_part1,查询key_part110002000范围内的数据

SELECT * FROM t WHERE key_part1 >= 1000 AND key_part1 < 2000

不使用MRR:先通过二级索引的key_part1字段取出满足条件的key_part1,pk_col order by key_part1.然后通过pk_col去表中取出满足条件的数据,此时,因为取出的pk_col是乱序的,而表又是pk_col存放数据的,当去表中取数据时,则会产生大量的随机IO

使用MRR:先通过二级索引的key_part1字段取出满足条件的key_part1,pk_col order by key_part1.放到缓存中(read_rnd_buffer_size),当对应的缓冲满了以后,将这部分key值按照pk_col排序,最后再按照排序后的reset去取表中数据,此时pk_col1是顺序的,将随机IO转化为顺序IO,多页数据记录可一次性读入或根据此次的主键范围分次读入,以减少IO操作,提高查询效率

使用限制

MRR 适用于range、ref、eq_ref的查询

Batched Key Access (BKA)和Block Nested-Loop(BNL)

Batched Key Access (BKA)– 提高表join性能的算法。

当被join的表能够使用索引时,就先排好顺序,然后再去检索被join的表,听起来和MRR类似,实际上MRR也可以想象成二级索引和primary key的join

如果被Join的表上没有索引,则使用老版本的BNL策略(BLOCK Nested-loop)

BKA原理

对于多表join语句,当MySQL使用索引访问第二个join表的时候,使用一个join buffer来收集第一个操作对象生成的相关列值。BKA构建好key后,批量传给引擎层做索引查找。key是通过MRR接口提交给引擎的(mrr目的是较为顺序).这样,MRR使得查询更有效率。

大致的过程如下:

1 BKA使用join buffer保存由join的第一个操作产生的符合条件的数据

2 然后BKA算法构建key来访问被连接的表,并批量使用MRR接口提交keys到数据库存储引擎去查找查找。

3 提交keys之后,MRR使用最佳的方式来获取行并反馈给BKA

BNL和BKA都是批量的提交一部分行给被join的表,从而减少访问的次数,那么它们有什么区别呢?

 第一 BNL比BKA出现的早,BKA直到5.6才出现,而NBL至少在5.1里面就存在。

 第二 BNL主要用于当被join的表上无索引

 第三 BKA主要是指在被join表上有索引可以利用,那么就在行提交给被join的表之前,对这些行按照索引字段进行排序,因此减少了随机IO,排序这才是两者最大的区别,但是如果被join的表没用索引呢?那就使用NBL了。

BKA和BNL标识

Using join buffer (Batched Key Access)Using join buffer (Block Nested Loop)

相关参数

BAK使用了MRR,要想使用BAK必须打开MRR功能,而MRR基于mrr_cost_based的成本估算并不能保证总是使用MRR,官方推荐设置mrr_cost_based=off来总是开启MRR功能。打开BAK功能(BAK默认OFF):

SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

BKA使用join buffer size来确定buffer的大小,buffer越大,访问被join的表/内部表就越顺序。

BNL默认是开启的,设置BNL相关参数:

SET optimizer_switch=’block_nested_loop’

适用场景

支持inner join, outer join, semi-join operations,including nested outer joins

BKA主要适用于join的表上有索引可利用,无索引只能使用BNL

简单总结

以下部分来源:http://www.cnblogs.com/zhoujinyi/p/4746483.html

 ICP优化Index
Condition Pushdown

Index Condition Pushdown (ICP)MySQL用索引去表里取数据的一种优化。禁用ICP(MySQL5.6之前),引擎层会利用索引在基表中寻找数据行,然后返回给MySQL
Server层,再去为这些数据行进行WHERE后的条件的过滤(回表)。启用ICP(MySQL5.6之后),如果部分WHERE条件能使用索引中的字段MySQL会把这部分下推到引擎层。存储引擎通过使用索引把满足的行从表中读取出。ICP减少了引擎层访问基表的次数和MySQL
Server 访问存储引擎的次数。总之是 ICP的优化在引擎层就能够过滤掉大量的数据,减少io次数,提高查询语句性能


MRR
优化
Multi-Range Read

 

Multi-Range Read 多范围读(MRR) 它的作用是基于辅助/第二索引的查询,减少随机IO,并且将随机IO转化为顺序IO,提高查询效率。在没有MRR之前(MySQL5.6之前),先根据where条件中的辅助索引获取辅助索引与主键的集合,再通过主键来获取对应的值。辅助索引获取的主键来访问表中的数据会导致随机的IO(辅助索引的存储顺序并非与主键的顺序一致),不同主键不在同一个page里面时必然导致多次IO 和随机读。使用MRR优化(MySQL5.6之后),先根据where条件中的辅助索引获取辅助索引与主键的集合,再将结果集放在buffer里面(read_rnd_buffer_size 大小直到buffer满了),然后对结果集按照pk_column排序,得到有序的结果集rest_sort。最后利用已经排序过的结果集,访问表中的数据,此时是顺序IO。即MySQL 将根据辅助索引获取的结果集根据主键进行排序,将无序化为有序,可以用主键顺序访问基表,将随机读转化为顺序读,多页数据记录可一次性读入或根据此次的主键范围分次读入,以减少IO操作,提高查询效率。


Nested Loop Join
算法:

将驱动表/外部表的结果集作为循环基础数据,然后循环该结果集,每次获取一条数据作为下一个表的过滤条件查询数据,然后合并结果,获取结果集返回给客户端。Nested-Loop一次只将一行传入内层循环所以外层循环(的结果集)有多少行内存循环便要执行多少次,效率非常差。


Block Nested-Loop Join
算法:

将外层循环的行/结果集存入join buffer, 内层循环的每一行与整个buffer中的记录做比较,从而减少内层循环的次数。主要用于当被join的表上无索引。


Batched Key Access
算法:

当被join的表能够使用索引时,就先排好顺序,然后再去检索被join的表。对这些行按照索引字段进行排序,因此减少了随机IO。如果被Join的表上没有索引,则使用老版本的BNL策略(BLOCK
Nested-loop)

 

参考:

http://dev.mysql.com/doc/refman/5.7/en/select-optimization.html

http://blog.itpub.net/22664653

http://www.kancloud.cn/taobaomysql/monthly/117959

http://www.kancloud.cn/taobaomysql/monthly/67181

http://www.cnblogs.com/zhoujinyi/p/4746483.html

转:https://blog.csdn.net/caomiao2006/article/details/52205177