zztttt

database

发表于 2020-07-03 更新于 2022-08-13 分类于 zztttt ， interview

数据库事务

是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元（Unit)。
狭义上的事务特指数据库事务。一方面，当多个应用程序并发访问数据库时，事务可以在这些应用程序之间提供一个隔离方法，以防止彼此的操作互相干扰。另一方面，事务为数据库操作序列提供了一个从失败中恢复到正常状态的方法，同时提供了数据库即使在异常状态下仍能保持数据一致性的方法

ACID:
- Automicity：原子性，强调事务作为原子级别已经不可以再被分割，要么成功要么失败
- Consistency：一致性，即状态转换必须是由一种正确的状态转换到另外一种正确的状态
- Isolation：隔离性，即相互间必须不能被影响，处理并发的问题
- Durabillity：持久性，即事务提交后将被永久保存，即便出现其他故障，事务处理结果也应得到保存。
- 若不考虑Isolation则会有三个问题：？？下面哪一个不是啊？？
  - 脏读：B事务读取到了A事务尚未提交的数据（没提交可能会回滚，导致读到了错误的数据）
  - 不可重复读：一个事务中两次读取的数据的内容不一致（在这两次中别的事务修改了数据）
  - 幻读：一个事务中两次读取的数据的数量不一致（）
  - 丢失修改：多个并发事务修改，前面的被后面的覆盖掉
- 隔离级别分为三个：
  - read uncommitted：哪个都不能解决。对读的数据不加锁
  - read commited：解决脏读，oracle默认。对读的数据加行级共享锁
  - repeatable read：可重复读，解决脏读和不可重复读，mysql默认。读加共享锁，写加排它锁
  - serializable：相当于锁表，能解决三个问题。

MySQL语法

查询最新的10条数据。

1	select * from table order by id desc limit 10

索引

索引是什么？
索引就像书的目录。了解一下平衡树
没加主键之前，数据都是很整齐的顺序排列，加了主键之后，就成树状了，可以说整个表成了一个索引，这就是聚集索引
聚簇索引和非聚簇索引

聚簇索引	非聚簇索引
多行检测快	单行检测快
按照数据存分的物理位置为顺序的	不是
叶子节点即为数据块	叶子节点还是索引

索引不是越多越好？
大多数情况下索引能大幅度提高查询效率，但是！数据的变更（增删改）都需要维护索引，因此越多意味着维护成本越高，意味着需要更多的空间
比较小的表可能建立索引后更慢
什么时候不适合建立索引？
- 表太小
- 经常插入、删除、修改的表
- 数值重复且分布均匀？为什么
索引为什么快？
如果你采用合适的算法遍历整个树，可以得到一个有序的列表。这也是为什么如果有数据库索引的情况下，你order by你索引的值，就会速度特别快，因为它并没有给你真的排序，只是遍历树而已。

范式

三大范式：
- 每列保持原子性
- 每列都与主键相关
- 每列都与主键直接相关而不是间接相关
- …

多表连接

自然连接：要求属性值相同的行，并消除重复属性列
内连接：保证两个表分所有行都要满足连接条件，不过不要求属性值相同
外连接：
- 左外连接：以左边为准，右边没有的填null
- 右外连接：以右边为准，左边没有的填null

数据库的锁

共享锁
允许多个线程访问同一资源，例如读写锁read状态
互斥锁
在访问资源之前加锁，访问完成之后解锁。其他任何试图再次加锁的都会被阻塞，直到当前进程解锁。例如读写锁write状态

数据库的备份与恢复

备份：将源数据再次存储到新的位置。三种常见的：完全备份、增量备份、差异备份。

备份的内容：
- 数据
- 二进制日志
- InnoDB存储以前的事务日志文件
- 代码——存储过程，存储函数，触发器，事件调度器等
- 当前服务器上用于启动数据服务是所使用的配置文件
- 操作系统上与MySQL或MariaDB相关的配置——sudo任务、cron任务等
恢复：
将备份好的数据重新应用到数据库系统

大规模数据库设计

把经常用的和不经常用的分开几个表，横向切分
不同类型的分成几个表，纵向切分
服务器放几个硬盘，把数据、日志、索引分盘存放，提高I/O吞吐率
建立统计表（cache），避免每次查询都统计一次
注意负载均衡

一个每秒百万级访问量的互联网服务器，每个访问都有数据计算和I/O操作，如果让你设计，你怎么设计？

设计成分布式的，将这些请求分给多台服务器去处理，每台都有着相同的数据、日志

Java: Collection

发表于 2020-07-01 更新于 2022-08-13 分类于 zztttt ， interview

Hashmap

底层是数组+链表/红黑树实现的。

//成员变量
transient Node<K,V>[] table; //底层数据结构，用于存储添加到HashMap中的Key-value对
transient Set<Map.Entry<K,V>> entrySet; //返回Node实体
transient int size; //Map中的key-value对的数量
transient int modCount;
int threshold;//临界值,当超过临界值时，HashMap就该扩容
final float loadFactor;//装载因子,衡量HashMap满的程度，默认值为DEFAULT_LOAD_FACTOR=0.75f

Node是一个static内部类。多个Node以链表的形式连接起来，然后在Hashmap内用数组来保留这些链表的起点，结合了这两种数据结构，保留了各自的优点，又弥补了各自的缺点。
但是是JDK8中，如果链表长度太长就会转化为红黑树。

Node<K,V>[] table

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
}

因此Hashmap的结构如下所示。

Set<Map.Entry<K,V>> entrySet
entrySet变量为EntrySet实体，Map.Entry<K,V>是一个接口，Node类就实现了该接口

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

扩容机制
容量的规则为2的幂次，即capacity可以是1，2，4，8，16，32…
根据传进来的容量来找最近的2的幂次

static final int tableSizeFor(int capacity) {
    int n = capacity - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashSet

是java中Set接口的一个实现类，底层是用Hashmap实现的，而Hashmap是数组+链表/红黑树实现的。如果链表长度大于8，就转化为红黑树，如果容量不够，则需扩容。

1	public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable

常用方法：

private transient HashMap<E,Object> map;

//初始化一个空的set
public HashSet(){
    map = new HashMap<>();
}
// 传入的集合添加到新的set
public HashSet(Collection<? extends E> c){
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
} 
//明确初始容量和装载因子
public HashSet(int initialCapacity, float loadFactor){
    map = new HashMap<>(initialCapacity, loadFactor);
}
//明确容量
public HashSet(int initialCapacity){
    map = new HashMap<>(initialCapacity);
}
// add， value值是被写死的
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
// remove，调用map的remove
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
// 遍历
Iterator it = set.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

LinkedHashSet

是HashSet的派生类。源码没什么实质性的东西，都是对HashSet的一个继承。

public class LinkedHashSet<E> extends HashSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable {
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

TreeSet

完全依赖于TreeMap来实现。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
	public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
}

Reference

HashMap原理(一) 概念和底层架构
 Java集合 HashSet的原理及常用方法

computer network

发表于 2020-07-01 更新于 2022-08-13 分类于 zztttt ， interview

OSI七层模型

应用-运输（表示+会话+传输)-网络-链路-物理

层级	作用	样例
应用层	为网络应用提供访问OSI环境手段	FTP
表示层	处理两个通信系统中交换信息的表示方式
会话层	两个节点之间建立端连接。具体管理两个用户和进程之间的对话
传输层	常规数据递送-面向无连接或有连接	TCP/UDP。这里叫segment
网络层	通过寻址来建立两个节点之间的连接	IP。这里叫packet
数据链路层	将数据分帧，并处理流控制	网卡、交换机。这里叫frame
物理层	利用物理传输介质来为第二层提供物理连接	网线。比特流

在传输层tcp+data，传给网络层，封装为ip+data，传给链路层，以太hdr+data+以太ftr，封装结束。
封装结束后通过总线到达主机接口，再通过网线被送到主机A的接口，然后把报头层层去掉，给应用层

ARP：完成了MAC与IP地址的映射。发送到dst时，若ARP里面有IP对应的MAC，就直接发；
没有就ARP请求获得MAC

TCP（Transmission Control Protocol）

如何保证正确性？
- 数据别校验：checksum。若出错就丢弃报文，然后发送端超时重发
- 对乱序数据包重排序：顺序后才交给应用层
- 丢弃重复数据
- 应答机制：ack。发送一个确认
- 超时重发
- 流量控制：每一方都有固定大小的缓存空间，接收端只允许另一端发送接收端缓冲区所能接纳的数据，可以防止较快主机致使较慢的缓冲区溢出。通过sliding window
三次握手
- 我要和你连接；你真的要和我连接吗？；我真的要！
- 原因：
  为了防止已失效的链接请求报文突然又传送到了服务端产生错误。简单来说就是某一次client的请求延迟到了，事实上client已经不想连接了，但是server以为要连，然后建立连接，这时client忽略了server的请求，但是server一直在等client发送data，就浪费了资源
四次挥手
- 我要和你断开；好的断吧；我也要和你断开好的，断吧
- 最后一个ACK的作用：
  在主动发起close的一方，发送最后一个ACK后会进入time_wait状态（应该说在保持2MSL（Maximum Segment Lifetime）恢复。
  有可以最后一个ACK丢失。所以TIME_WAIT状态就是用来重发可能丢失的ACK报文。在Client发送出最后的ACK回复，但该ACK可能丢失。Server如果没有收到ACK，将不断重复发送FIN片段。所以Client不能立即关闭，它必须确认Server接收到了该ACK。
如何避免占用资源
改变服务器SO_REUSEADDR套接字选项来通知内核来让time_wait状态下端口仍然能重用
tcp头有多少字节？哪些字段？

4位头部长度：标识tcp头部有多少字节
6位保留（flag）：ACK确认号是否有效、RST是否要对方重新连接、SYN表示请求一个连接、FIN通知关闭。
16位窗口大小：告诉tcp缓冲区还能容纳多少字节
16位校验和：有发送端填充，接收端对报文执行CRC判断tcp是否损坏
tcp选项：窗口扩大因子(TCP Window Scale Option)来增加TCP接收窗口的大小而超过65536字节
connect操作会阻塞，怎么办？
设置connect非阻塞，立即返回值。然后把sockfd加入select读写监听集合，通过select判断sockfd是否可写。即让select来等待连接完成，同时给select设置一个时间限制
长连接和短连接的区别
- 长连接：在一个TCP上可以连续发送多个数据包；若无数据包（心跳），则需要发送检测包以维持连接多用于频繁的读写，而且连接数不能太多的情况
- 短连接：通信双方有数据交互时，就建立一个TCP连接，数据发送完成后立即断开此连接。web网站的一般都是短连接，因为用户基数大，如果每个用户都长连接的话消耗资源

UDP（User Datagram Protocol）

udp调用connect有什么用
与tcp的connect不一样，tcp会触发三次握手，而udp仅仅是把ip&port给记录下来。
tcp只调用一次，udp可以调用多次，作用：1.记录新的ip&port2.断开之前的

TCP与UDP对比

类型	TCP	UDP
是否连接	是	否
传输可靠性	可靠	不可靠
应用场合	传输大量数据	少量数据
速度	慢	快
正确性	保证	丢包
复杂性	复杂	简单
应用场景	qq文件	qq语音视频
安全性	容易被攻击	不容易被攻击

拥塞控制机制

网络拥塞：对网络中某一资源的需求超过了该资源所能提供的可用部分，网络性能就要变坏，这种情况就叫做网络拥塞
四种解决方案：
发送方：维护拥塞窗口cwnd的状态变量。取决于拥塞程度。将拥塞窗口作为发送窗口，即swnd=cwnd。维护一个慢开始门限ssthresh状态变量。cwnd < ssthresh慢开始，否则拥塞避免。
- 慢开始（指数增长）
  发送方当前只能发送一个数据报文段（拥塞窗口cwnd的值是几，就能发送几个数据报文段），接收方收到该数据报文段后，给发送方回复一个确认报文段，发送方收到该确认报文后，将拥塞窗口的值变为2；后续就是2、4、8.。。之后改用拥塞避免算法
- 拥塞避免
  每个传输轮次，拥塞窗口cwnd只能线性加一，而不是像慢开始算法时，每个传输轮次，拥塞窗口cwnd按指数增长。
  假设24个报文段在传输过程中丢失4个，接收方只收到20个报文段，给发送方依次回复20个确认报文段，一段时间后，丢失的4个报文段的重传计时器超时了，发送发判断可能出现拥塞，更改cwnd和ssthresh.并重新开始慢开始算法。（发生超时重传）
- 快重传
  发送方发送1号数据报文段，接收方收到1号报文段后给发送方发回对1号报文段的确认，在1号报文段到达发送方之前，发送方还可以将发送窗口内的2号数据报文段发送出去。
  就是使发送方尽快进行重传，而不是等超时重传计时器超时再重传。
  接收方在收到了失序的报文段也要立即发出对已收到的报文段的重复确认
  发送方一旦接受到了三个连续的重复确认，就将相应的报文立即重传，而不是等该报文段的超时重传计时器。此时开始执行快恢复算法
- 快恢复
  ssthresh和cwnd调为原来的一半，再执行拥塞避免算法

第一二个方法的缺点：个别报文段意外丢失，但是没有阻塞，误认为发生拥塞，cwnd再次设为1，降低传输效率

Http与Https

http协议运行在tcp之上，明文传输，客户端/服务器无法验证对方身份。https是身披ssl的，添加了加密和认证机制的http。https开销大。

http请求方式：
- option：返回服务器对特定资源所支持的HTTP请求方法
- head：向服务器索要与GET请求相一致的响应，只不过这响应不会返回
- get：向特定资源发送请求
- post：向特定资源提交数据进行处理请求，数据被包含在请求体中。可能会导致新的资源的创建或已有资源的修改
- put：向指定资源上传其最新内容
- delete：请求服务器删除request-URL所标识的资源
- trace：回显服务器收到的请求，主要用于测试或判断
- connect：HTTP/1.1协议中预留给能够将连接改为管道方式的代理服务器
get和post区别：
get是获取资源，post是更新资源。get的请求url后面会有?带的参数，post会把数据放置在http请求的请求体中

网络安全

DDos攻击：是什么？
没有根治的方法，除非不使用tcp

Session与Cookie

类型	session	cookie
实现机制	依赖于cookie
大小限制	无	有
安全性	在服务器端，安全	本地有可能被攻击
服务器资源消耗	在服务器上保留一段时间消失	过多会增加服务器压力

select和epoll

	select	epoll
时间	毫秒	微秒
unix	支持	有些不支持
fd限制	有最大fd设置	没有

为什么select比epoll慢？
- select可以监听文件描述符是有限的，epoll可监听的文件描述符的个数为进程可打开的文件的个数。
- select中，当有事件就绪时，内核修改参数以通知用户，用户需要遍历所有的fd判断是哪个fd就绪，应用程序索引就绪文件描述符的时间复杂度是O(n)，IO效率随着监听的fd的数目增加而线性下降。
  而epoll中注册了回调函数，当有就绪事件发生的时候，设备驱动程序调用回调函数，将就绪的fd添加到rdllist中，调用epoll_wait时，将rdllist上就绪的fd发送给用户，应用程序索引就绪文件描述符的时间复杂度是O(1)，IO效率与fd的数目无关。
  epoll支持ET模式，当内核将该事件通知给用户后，用户必须立即处理，这样就减少了可读、可写、异常事件被触发的次数。
  select只能工作在相对较低效的LT模式
epoll有哪些触发模式？
水平与边缘

operating system

发表于 2020-06-30 更新于 2022-08-13 分类于 zztttt ， interview

进程（process）

进程空间分布：
一个进程内存分为五个segment，从高到低分别为（stack、heap、bss、data、text）segment
进程通信方式:
- 管道：父子与兄弟进程之间的通信，不是文件系统，存在于内存
- FIFO：与进程类型无关的通信方式，以特殊的文件形式存在于文件系统中
- 消息队列：消息的链列表
- 信号量：信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。
  即bitmap，与IPC结构不同，它是一个计数器，用于进程间的互斥与同步，需要结合共享内存。
  它基于operating system的PV操作，对信号量的操作都是原子操作，并且支持信号量组
- 共享内存：
  指两个或多个进程共享一个给定的存储区。
  共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。因为多个进程可以同时操作，所以需要进行同步。解除映射时才写回文件。
  优点：效率高。缺点：没有同步机制，需要信号量
进程资源的分配方式：
由PCB(process control block)管理，在32bit系统下，会分配4G内存，3G给用户，1G给内核。
内核态有一个task_struct，里面保存以下这些信息：

类型	内容
标识	pid ppid
file	打开的文件信息，file descriptor
memory	内存指针，指向虚拟地址空间的信息
context	寄存器的值、进程状态、堆栈的内容
signal	是否还有待处理的信号
I/O	记录进程和各种I/O设备的交互

生命周期：
- 僵尸态：子进程退出后，所有资源都消失了，只剩下 task_struct，父进程在 wait 函数中可以得到子进程的死亡原因。在 wait 之前子进程的状态就是僵尸态。
- 深度睡眠：等待资源到位后才醒过来
- 浅度睡眠：等待资源到位或收到信号后都会醒过来
- 暂停： stop状态是被外部命令作业控制等强制进程进入的状态。
- 就绪：未占有 CPU，等待调度算法调度到运行态的进程
- 运行：占有 CPU，正在运行的线程。
进程调度算法
- FIFO
- SJF
- 优先权
- 轮转时间片
- 多层队列：Linux默认调度算法
守护进程（daemon）：
是一类在后台运行的特殊进程，用于执行特定的系统任务。很多守护进程在系统引导的时候启动，并且一直运行直到系统关闭。另一些只在需要的时候才启动，完成任务后就自动结束。

线程

线程的使用：

C++-Linux：
pthread_join: 需要父线程调用，等待子线程执行完，回收资源。不然资源没法回收
pthread_detach: 在该线程运行结束后会自动释放所有资源。
pthread_cond_t: 必须在互斥锁的保护下使用相应的条件变量
阻塞在条件变量

pthread_mutex_lock(pthread_mutex_t *mutex);
while(condition_is_false){
    pthread_cond_wait(pthread_cond_t *cv, pthread_mutex_t *mutex);
}
pthread_mutex_unlock(pthread_mutex_t *mutex);

唤醒阻塞在某条件变量上的线程：

1
2
3

pthread_cond_signal(pthread_cond_t *cv); //唤醒至少一个阻塞在该cond上的线程
pthread_cond_broadcast(pthread_cond_t *cv); // 唤醒所有阻塞在该cond上的线程
//前者单播，后者广播

Java：
TODO

线程池
事先将线程放到一个容器中，当使用线程的时候，不用再去new出一个线程，直接从线程池取出来
优点：
- 降低资源消耗：即重复利用线程池中的线程可以节省线程创建和销毁带来的消耗
- 提高性能：当任务需求时，可以不用创建线程直接执行，主要是直接从线程池中取出线程去执行
- 提高线程的可管理性：线程是稀缺资源，而且也是任务中不可少的资源，如果频繁的且无限制的创建会消耗系统资源，降低系统稳定性导致系统崩溃，内存溢出等等问题
线程安全
多线程访问同一代码，不会产生不确定的结果。编写线程安全的代码是低依靠线程同步。
线程安全的类：StringBuffer， HashTable， Vector
线程不安全的类：StringBuilder（速度更快），HashMap
控制线程执行顺序：
- 信号量：signal，就上述关于pthread相关的函数
- sem_post:
  sem_t为一个变量，post是给她+1，wait如果它是0则阻塞，非0则-1
  例：初始化为0，线程1 wait直接阻塞，线程2 执行结束post给它加一，线程1则开始执行

进程（process）与线程（thread）

线程是进程的一个执行流，一个进程可以由很多个线程组成

进程	线程
资源分配的最小单位	程序执行的最小单位
数据分开，需要IPC。共享复杂，同步简单	共享简单，同步复杂
占用内存多，切换复杂，CPU利用低	占用内存少，切换简单，CPU利用率高
编程简单调试简单	难
进程之间不会相互影响	一个线程挂掉将导致整个进程挂掉
分布式扩展到多台电脑比较简单	适用于多核分布
创建/销毁代价高	低
有独立的地址空间	多个线程共享同一个进程的地址空间

Linux系统

ELF文件：是一种文件格式。可执行文件、目标文件、共享库和核心转储。由四部分组成
- ELF header
- Program header table
- Section
- Section header table
  
  TODO: 其大小与程序中全局变量是否初始化有什么关系（注意未初始化的数据放在bss段）bss在一开始全部清零
系统调用和库函数

系统调用	库函数
操作系统为用户提供的一系列操作的接口	对系统调用的一层封装
线程安全	非线程安全

临界区：
在任意时刻只允许一个线程对共享资源进行访问。
如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。
临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。
内存管理机制：
虚拟地址、物理地址、逻辑地址。虚拟地址和物理地址之间采用多级页表映射
页面置换算法：
- FIFO：只是在按线性顺序访问地址空间时才是理想的，否则效率不高
- LRU：
  - 优点：命中率,当存在热点数据时,LRU的效率很好；实现相对简单
  - 缺点：偶发性的,周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重；命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部
- LFU
- CLOCK：LRU算法的近似实现
- OPT：最佳置换算法，实际上不可能实现。每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。
同步机制：
- 每个cpu一个变量
- 原子操作：PV
- 自旋锁：锁住一块临界区，进入时需要获取自旋锁。
  读写自旋锁：允许多个进程同时对同一数据结构进行读，但不允许多个进程同时修改同一数据结构，因此在实现上必须分为读锁和写锁。
- 顺序锁：写锁不会因为读锁而锁住
- 信号量：存在一个进程等待队列，未获取锁的进程将挂到该队列中，然后主动调用schedule()切换进程，让出cpu
- 禁止本地中断

读锁	写锁
实现多个进程能同时读同一数据结构，但是读的过程中不允许写	实现仅能有一个进程获取写锁进入临界区，获取写锁时同时保证没有进程已经获取读锁

链接：
分为动态链接和静态链接。
动态链接生成可执行文件时不将所需函数链接到一个文件，而是要用的时候从系统ddl里面找。静态链接就是把所有文件都放入exe里面
文件系统：ext2 ext3 ext4。。。

锁

可重入锁（递归锁）：
- 在同一个线程在外层方法获取锁的时候，再进入该线程的内层方法会自动获取锁（前提锁对象的是同一个对象或者class），不会因为之前已经获取过还没释放而阻塞
- 可重入锁可以让当前进程再次获取锁，不可重入锁会直接获取失败导致阻塞。可以一定程度避免死锁。
- 加锁：先尝试获取并更新status的值，如果为0表示没有其他的线程占用，将其置为1；若不为0，则判断是否是当前线程在占有锁，如果是，status++，并再次获取锁，不是则导致获取锁失败，阻塞
- 解锁：先获取status值，如果是当前线程战有锁，如果status == 1，则置为0并释放，否则status–，不释放。
乐观锁/悲观锁：

乐观锁	悲观锁
每次拿数据的时候认为别人不会改，所以不会锁	每次拿数据都会锁
适用于多读（在拿数据时会判断是否有人改数据）
java.util.concurrent.atomic	synchronized、ReentrantLock

生产者消费者模型：
生产者：生产消费者需要的资料。消费者：把资料做成产品
- 生产者生产数据到缓冲区中，消费者从缓冲区中取数据
- 如果缓冲区已经满了，则生产者线程阻塞
- 如果缓冲区为空，那么消费者线程阻塞

C/C++

发表于 2020-06-29 更新于 2022-08-13 分类于 zztttt ， interview

一个程序在内存中分为五个段：

text: 保存源代码
data：初始化的全局变量和静态变量
bss：未初始化的全局变量和静态变量或初始化为0的
stack：程序运行时栈，保存局部变量、可能存在的argument以及return的地址
heap: 用来保存手动分配出来的内存，由用户管理。内存块由一条链表来维护

volatile的作用

不可优化性：当一个变量即使是不用，也不让编译器去优化它。
下一条语句不会直接使用上一条语句对应的volatile变量的寄存器内容，而是重新从内存中读取。即不让编译器去随意把它给优化掉。

全局变量和局部变量的区别：

作用范围不同
在存储器中存储位置不同，全局是在数据段中，局部变量一般在堆/栈段
操作系统通过内存分配的位置来知道全局变量在全局数据段，在程序运行的时候加载
编译器通过词法分析来知道它是全局变量还是局部

static关键字:

static成员函数：只能调用static成员变量
static成员：所有instance共享，不能在类的内部初始号，在类的实现文件中初始化

const关键字：

const成员函数：不改变数据成员的成员函数都要在后面加 const，而对于改变数据成员的成员函数不能加 const。
const成员：不能在类的内部初始化，只能通过构造函数初始化

多态性：

静多态：template和函数重载
template在编译期决定，模板的实例化就在编译期对其进行替换。
重载是参数表，C++编译时会将函数的参数类型加在函数symbol的后面，因此参数不一样的函数也不一样
动多态
虚函数，是动态绑定，运行时决定

虚函数：

纯虚函数：virtual xxx = 0；在派生类中重写成员函数的实现

class A{
public:
    virtual void func1() = 0; // pure virtual function
    virtual void func2(); // normal virtual function
}

class B: public A {...};
class C: public A {...};

A* a = new B(); a->func1(); // B::func1
A* b = new C(); b->func1(); // C::func1
a->A::func1(); // A::func1

普通虚函数: 在基类中定义一个缺省实现，表示继承的是基类成员函数接口和缺省实现，由派生类选择是否重写该函数。
但是这种方式是很危险的！因为可能忘记重写！
解决方案：最好是基类中实现缺省行为，但只有在派生类要求时才提供该缺省行为。
使用C++11的关键字override,可以显式的在派生类中声明，哪些成员函数需要被重写，如果没被重写，则编译器会报错。
1
2
3
4
class Base{
public:
virtual void func1() override;
}
原理：
virtual table里存的成员函数地址，在继承重写的时候，会替换其相应位置重写后的函数地址，但是因为是同样的offset，所以在运行时会找到正确的函数地址。
使用：
构造函数不能为虚函数，而析构函数可以且常常是虚函数。 C++对象在三个地方构建：（1）函数堆栈 stack；（2）自由存储区，或称之为heap；（3）静态存储区。
无论在那里构建，其过程都是两步：首先，分配一块内存；其次，调用构造函数。好，问题来了，如果构造函数是虚函数，那么就需要通过vtable 来调用，但此时面对一块 raw memeory，到哪里去找 vtable 呢？毕竟，vtable 是在构造函数中才初始化的啊，而不是在其之前。因此构造函数不能为虚函数。
析构函数可以是虚函数，且常常如此。因为此时 vtable 已经初始化了；况且我们通常通过基类的指针来销毁对象，如果析构函数不为虚的话，就不能正确识别对象类型，从而不能正确销毁对象。
每个析构函数（不加 virtual）只负责清除自己的成员。但可能有基类指针，指向的确是派生类成员的情况。（这是很正常的）。那么当析构一个指向派生类成员的基类指针时，程序就不知道怎么办了。所以要保证运行适当的析构函数，基类中的析构函数必须为虚析构。

继承：

虚继承：

在多重继承中，如果发生了如：类B继承类A，类C继承类A，类D同时继承了类B和类C。最终在类D中就有了两份类A的成员，这在程序中是不能容忍的。当然解决这个问题的方法就是利用虚继承。
在派生时将关键字virtual加在相应相应继承方式前，就可防止在D类中同时出现两份A类成员。只会将虚基类的构造函数调用一次，忽略虚基类的其他派生类（class B，class C）对虚继承的构造函数的调用，从而保证了虚基类的数据成员不会被多次初始化
内存分布：

指针&&引用：
指针是一个变量，只不过这个变量存储的是一个地址，指向内存的一个存储单元，即指针是一个实体；而引用跟原来的变量实质上是同一个东西，只不过是原变量的一个别名
两者都是地址的概念；指针指向一块内存，它的内容是所指内存的地址；引用是某块内存的别名。
可以有const指针，但是没有const引用；
指针可以有多级，但是引用只能是一级（int **p；合法而 int &&a是不合法的）
指针的值可以为空，但是引用的值不能为NULL，并且引用在定义的时候必须初始化；
指针的值在初始化后可以改变，即指向其它的存储单元，而引用在进行初始化后就不会再改变了，从一而终。
”sizeof引用”得到的是所指向的变量(对象)的大小，而”sizeof指针”得到的是指针本身的大小；
指针和引用的自增(++)运算意义不一样

函数返回局部变量的引用

当函数返回引用类型时，没有复制返回值，相反，返回的是对象本身。
千万不要返回局部对象的引用！千万不要返回指向局部对象的指针！当函数执行完毕时，将释放分配给局部对象的存储空间。此时对局部对象的引用会指向不确定的内存！返回指向局部对象的指针也是一样的，当函数结束时，局部对象被释放，返回的指针就变成了不再存在对象的悬垂指针。
返回引用时，要求在函数的参数中，包含有以引用方式或指针方式存在的，需要被返回的参数。

内存泄漏

不再会被使用的对象的内存不能被回收，就是内存泄露
在C++中，所有被分配了内存的对象，不再使用后，都必须程序员手动释放他们。所以，每个类，都会含有一个析构函数，作用就是完成清理工作，如果我们忘记了某些对象的释放，就会造成内存泄露。

构造/析构函数的执行顺序

构造的时候先构造基类后子类，析构的时候相反先析构子类后析构基类

内联成员函数（编译展开），静态成员函数（编译确定，不能重写）

重写（override）和重载（overload）：

重写是覆盖，是派生类重写基类的相应方法。要求函数名、参数相同
重载是同样的函数名，但是不同的参数，有参数表的存在。比如类的多个构造函数

重载的过程

C++为了支持函数重载，是编译器的函数符号改名机制，符号名是在对应的函数名上改编的。
简单来说就是函数的symbol是根据函数名、函数参数表（类型、数量）相关的
例如 func(…)参数为一个int，就加一个i，为float就加一个f，char就加一个c，int&则加Ri，依此类推
所以可以容易理解，用C++去找由C编译的函数，则会找不到定义。所以应该加一个extern C

hexo theme: Next background

发表于 2020-06-19 更新于 2022-08-13 分类于 others

hexo给主题next设置背景图片。
首先了解hexo部署在GitHub page上的原理。它将 $HEXO_ROOTDIR/source 目录下的内容编译成静态html页面，因此可以将图片放在新建的picture目录下。
关于theme的背景，则是在 $HEXO_ROOTDIR/$THEME/source 目录下，编辑 /css/_custom/custom.styl 文件，插入以下代码。
然后将所选图片放入images/目录下即可

body {
 	background:url(/images/bz.jpg);// 设定背景图片,images同处于theme/source文件夹下
 	background-repeat: no-repeat;// 设定背景图片非重复填充
    background-attachment:fixed;// 设置背景图片不随页面滚动
    background-position:50% 50%;// 设置背景图片位置
	background-size: cover// 设置保持图像的纵横比并将图像缩放成将完全覆盖背景定位区域的最小大小
}
// 页面头样式属性
.header-inner {
  // 也可以同时定义背景色
  // background: #ddd 
  // 透明度
  // opacity: 0.8;
}
// sidebar侧边工具栏样式属性
.sidebar{
    // 动画过渡时间
	transition-duration: 0.4s;
    // 透明度
	opacity: 0.8
}
// 标题样式
.posts-expand .post-title-link {
	// 设置字体颜色
	color: #222;
}

// 文章版块样式
.post-block {
    //background: var(--content-bg-color);
	background: #fff
    border-radius: initial;
    box-shadow: 0 2px 2px 0 rgba(0,0,0,0.12), 0 3px 1px -2px rgba(0,0,0,0.06), 0 1px 5px 0 rgba(0,0,0,0.12);
    padding: 40px;
}

最后重新部署一遍

1	hexo clean && hexo generate && hexo deploy

Reference

Next主题设置背景图片

hexo theme: Next configuration

发表于 2020-06-17 更新于 2022-08-13 分类于 others

项目地址：theme-next

cd $HEXO_ROOTDIR
git clone https://github.com/theme-next theme/next
vim _config.yml
set: theme: hexo-theme-next
     language: zh-Hans

cd themes/hexo-theme-next
vim _config.yml
set: scheme: Gemini

打开分类和标签页面

1 2	cd $HEXO_ROOTDIR hexo new page categories && hexo new page tags

会提示

1 2	INFO Created: ~/source/categories/index.md INFO Created: ~/source/tags/index.md

在index.md中修改成

---
title: 文章分类
date: xxx
type: "categories"
---

...

最后在文章中添加

title: xxx
data: xxx
categories: Categories
tags: 
- Tags1
- Tags2

最后在远端更新

1 2	cd $HEXO_ROOTDIR hexo clean && hexo generate && hexo deploy

Reference:

Next主题更改语言
 Next主题添加标签

C++：Virtual Table

发表于 2019-05-19 更新于 2022-08-13 分类于 zztttt ， programming

本文旨在分析C++中虚函数的实现细节，着重于class类内部的内存空间分布
对以下类，其内存空间分布为：

class A{
public:
    int a;
    long long b;
}
A t;
sizeof(t) = 16
&t = &t.a = base;
&t.b = base + 0x8;

high<---|---------| ->base + 0x10
        |   ll    | 
        |---------| ->base + 0x8
        |    |int | 
low<----|---------| ->base

若它有一个虚函数,则其内存空间分布为：

class A{
public:
    int a;
    long long b;
    virtual void vfun() {};
    
}
sizeof(A) = 24;

high<---|---------| ->base + 0x18
        |   ll    | 
        |---------| ->base + 0x10
        |    |int |                                  
        |---------| ->base + 0x8                   vtable
        |  void** | ->vfptr:0x7FF684A63308 ---->|----------|
low<----|---------| ->base                      |   void*  |->0x7FF684A61070 -> vfun1
                                                |----------|
                                                |   void*  |->0x7FF684A610B0 -> vfun2
                                                |----------|

C++：SmartPointer

发表于 2019-04-26 更新于 2022-08-13 分类于 zztttt ， programming

为何使用智能指针？

因为能帮我们管理内存，避免内存泄漏
能帮我们处理空悬指针（俗称野指针，即delete掉指针后，原来的指针指向了垃圾区域）的问题

智能指针的类型

shared_ptr: 多个智能指针指向同一块区域，该对象会在最后一个引用被销毁时释放。
unique_ptr: 每个对象只能有一个智能指针指向它，避免资源泄漏。

shared_ptr的实现

详见 SmartPtr
类的内部细节如下：
内部ptr保留的是真实的指针，由该类来自动维护它
count是对真实指针引用的计数

template<class T>
class sharedPtr {
private:
	T* ptr;
	int* count;
public:
	sharedPtr();
	sharedPtr(T*);
	~sharedPtr();
	sharedPtr(const sharedPtr<T>& t);
	sharedPtr<T>& operator=(const sharedPtr<T>& right);
};

对于 p1(p2)这种复制构造，事实上是将参数的count加一，即又增加了对资源的引用

template<class T>
sharedPtr<T>::sharedPtr(const sharedPtr<T>& t)
{
	ptr = t.ptr;
	count = t.count;
	(*count)++;
	cout << "copy from " << &t << "to" << this << endl;
}

对于p2 = p2这种复制构造，事实上是将右侧的的count减一，将左侧的count减一，减后进行判断是否要进行资源的释放来自行维护。

template<class T>
sharedPtr<T>& sharedPtr<T>::operator=(const sharedPtr<T>& right)
{
	(*right.count)++;
	(*count)--;
	if (*count == 0) {
		delete ptr;
		delete count;
		ptr = nullptr;
		count = nullptr;
		cout << "delete left element:" << this << endl;
	}
	ptr = right.ptr;
	count = right.count;
	cout << "copy right to left" << endl;
	return *this;
}

hexo主题的切换

发表于 2019-04-25 更新于 2022-08-13 分类于 others

网上找到一个比较清爽的主题，也就是我现在用的这一个maupassant
步骤如下：

git clone https://github.com/tufu9441/maupassant-hexo themes/maupassant
npm install hexo-renderer-pug --save
npm install hexo-renderer-sass --save
cd themes/maupassant
修改 theme:landscape -> theme:maupassant

这时在在本地能正确渲染出新的主题

1 2	hexo server --debug curl localhost:4000

部署到remote

1	hexo clean && hexo generate && hexo deploy

然而直接访问zztttt.github.io发现只有内容，css渲染失败。很容易想到F12打开浏览器去寻找css代码的地址是否正确
请求网址：~~http://zztttt.github.io/css/style.css~~
应当为：http://zztttt/github.io/zztttt.ghub.io/css/style.css
因为zztttt.github.io是你的repo地址，相当于把你的blog部署到你的URL的Repo目录下
直接修改_config.yml配置即可

# URL
## If your site is put in a subdirectory, set url as 'http://yoursite.com/child' and root as '/child/'
url: http://github.com #???
root: /zztttt.github.io
permalink: :year/:month/:day/:title/
permalink_defaults:

然后再按照上述步骤部署一遍即可。

数据库事务

MySQL语法

索引

范式

多表连接

数据库的锁

数据库的备份与恢复

大规模数据库设计

一个每秒百万级访问量的互联网服务器，每个访问都有数据计算和I/O操作，如果让你设计，你怎么设计？

Hashmap

HashSet

LinkedHashSet

TreeSet

Reference

OSI七层模型

TCP（Transmission Control Protocol）

UDP（User Datagram Protocol）

TCP与UDP对比

拥塞控制机制

Http与Https

网络安全

Session与Cookie

select和epoll

进程（process）

线程

进程（process）与线程（thread）

Linux系统

锁

一个程序在内存中分为五个段：

volatile的作用

全局变量和局部变量的区别：

static关键字:

const关键字：

多态性：

虚函数：

继承：

指针&&引用：

函数返回局部变量的引用

内存泄漏

构造/析构函数的执行顺序

内联成员函数（编译展开），静态成员函数（编译确定，不能重写）

重写（override）和重载（overload）：

重载的过程

Reference

Reference:

为何使用智能指针？

智能指针的类型

shared_ptr的实现

Reference