Skip to content

zhaojunHouse/studyGuide

BranchesTags

Repository files navigation

计算机专业课程

数据结构&算法

  • 建立时间复杂度、空间复杂度意识，写出高质量的代码
  • 性能更优，核心竞争力
  • 数据结构算法导图

1 复杂度分析

1.1 时间复杂度

  • 所有代码执行时间与数据规模增长的趋势，叫时间复杂度。
  • 可以理解每行代码执行时间都是unit_time,执行次数和数据量的关系。知道执行次数，就能知道复杂度。

1.2 时间复杂度量级

  • 常数阶、对数阶、线性阶、线性对数阶、指数阶，平方阶，立方阶，k次方阶，阶乘阶。

1.3 空间复杂度

  • 算法存储空间与数据量的关系。

1.4 最好最坏平均均摊时间复杂度

  • 平均：执行次数*概率

2 数组

2.1 定义

  • 内存连续（随机访问），数据类型相同，线性表。

2.2 插入删除

  • 插入删除 平均复杂度O（n）

2.3 查找

  • 查找 todo
  • 随机访问 下标访问复杂度O（1）

3 链表

3.1 插入删除

  • 插入删除 复杂度为O（1）

3.2 查找

  • 查找 复杂度O（n）

3.3 单链&双向链表&循环链表

  • 单链表，双向链表，循环链表. 带头链表，不带头链表

3.4 链表操作

  • 反转，合并有序链表，是否有环，删除倒数第n个节点，查找中间节点。

4 栈

4.1 入栈出栈

  • 入栈，出栈，栈顶元素。

4.2 顺序栈&链式栈

  • 数组实现顺序栈，链表实现链式栈。

4.3 栈应用

  • 用栈实现：表达式求值

5 队列

5.1 队头队尾

  • 队头出队，队尾入队

5.2 顺序队列&链式队列

  • 顺序对列，链式队列

5.3 循环队列

  • 队满：（tail+1）% n = head；
  • 队空： tail== head；

5.4 阻塞队列&并发队列

6 递归

6.1 堆栈溢出

  • 递归用循环代替
  • 堆栈溢出，重复计算，空间度高，函数调用耗时多。

7 排序

  • 判断排序算法效率衡量：
    • 1 时间复杂度（最好，最坏，平均）
    • 2 时间复杂度，系数，常熟，低阶
    • 3 内存消耗（原地排序）
    • 4 稳定性（都为3，排序前后位置不变的就是稳定算法）

7.1 冒泡排序

  • 原地排序，稳定性
  • 有序度，逆序度，满有序度 n*（n-1）/2
  • 时间复杂度。 O（n*n）

7.2 插入排序

  • 优于冒泡

7.3 选择排序

  • 低于冒泡和插入

7.4 归并排序

  • 时间复杂度：都为 nlogn
  • 空间负责度： n

7.5 快排

  • 取分区点，大于在右，小于在左。利用插入排序思想原地排序。
  • 时间复杂度对数阶。
  • 优化：三数取中，随机法取分区点。

7.6 桶排序

  • 分为多个桶，多个桶之间有排序，桶内快排

7.7 计数排序

7.8 基数排序

8 二分查找

  • 只适合数组
  • 只适合有序
  • 数据太小或太大都不适合
  • 如何在100MB内存之内，在1000W数据中查找。（数组排序，二分查找）
  • 二分查找变形：第一个小于等于某个值。。。

9 跳表

9.1 什么是跳表

  • 链表+多级索引+有序

9.2 特性

  • 空间复杂度 O（n）
  • 查找的时间复杂度 O（logn）
  • 插入删除时间复杂度 O（logn） 查找复杂度+操作复杂度
  • 防止跳表退化成链表：通过随机数k，把1-k层添加索引

9.3 Reids有序集合

  • 为什么不用红黑树？ 查询在区间内的数时，跳表效率比红黑树高。

10 散列表

10.0 定义

  • 通过散列函数把元素的键值映射为下标，将数据存储在数组下标中

10.1 散列冲突

  • 哈希冲突： 链表法；开放寻址法；重复哈希

10.2 设计工业级散列表

    1. hash函数设计
    1. hash表初始大小，动态扩容，高效扩容先扩容，然后等插入数据时再拷贝数据到新的散列表
    1. 散列冲突链表法可以用红黑树替代；

10.3 hash表+链表

  • LRU缓存淘汰算法：散列表+双向链表；复杂度都是O（1）
  • Redis有序集合：散列表+跳表 ；可以按照添加顺序 顺序访问
  • 插入，删除，查找 时间复杂度可到O（1）

10.4 哈希算法

  • 应用： 安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储

10.6 一致性哈希算法

  • hash环，算法对2的32次方取模。添加和删除机器只需要对部分数据迁移。
  • 节点太少可以添加虚拟节点

11 树

11.1 概念

  • 高度/深度/层

11.2 二叉树&满二叉树&完全二叉树

  • 存储方法：数组，链表；
  • 完全二叉树用数组方式存储浪费的空间少。
  • 前序遍历，中序遍历，后续遍历；用递归实现
  • 遍历时间复杂度O（n）

11.3 二叉查找树

  • 插入，查找，删除（如果有两个子节点，找到右节点的最小值，替换。）
  • 重复：链表法或数组动态扩容放在一个节点；放在右子树；

11.4 Hash表vs红黑树

  • 散列表无序
  • hash表扩容，hash冲突时，性能不稳定
  • 时间复杂度常量级不一定比对数级更优
  • hash表考虑因素多。hash冲突，扩容缩容。

11.5 红黑树

  • 根节点是黑色的；

  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据

  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节隔开。

  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数的黑色节点

  • 平衡二叉查找树，任何节点都左右节点高度不大于1.

  • 查找插入删除 时间复杂度：logn

  • 插入3种调整方式，删除4种调整方式。

11.6 递归树

  • 用来分析时间复杂度

11.7 B树&B+树

12 堆

12.1 定义

  • 完全二叉树
  • 每个节点比它的子节点都大或是都小。大顶堆，小顶堆。

12.2 插入删除

  • 堆插入，删除 ，堆化的过程。
  • 插入删除时间复杂度。logn

12.3 堆排序

  • 建堆，排序 。复杂度nlogn
  • 堆排序，取最顶堆化再重复。
  • 交换次数比快排多；跳跃访问。所以性能比快排低。

12.4 堆应用

  • 优先级队列、求 Top K 问题和求中位数问题

13 图

13.1 定义

  • 顶点，边，度，有向图，无向图，加权图。

13.2 图的存储

  • 邻阶矩阵存储。浪费空间。
  • 邻阶表存储（可以把链表换成散列表，跳表，红黑树）
  • 小规模（邻阶表+跳表实现）
  • 大规模（hash分片之后用跳表；或数据库）

13.3 深度，广度优先搜索

  • 广度：地毯式搜索，一层一层向外搜索。
  • 深度：回溯思想。
  • 时间复杂度O（边数），空间复杂度O（顶点数）

14 字符串匹配算法

14.1 BF算法（暴力匹配算法）

14.2 RK算法 （发明者名字命名）

  • 把模式串和主串 hash，再比较hash值。
  • 每个小串计算hash时不用遍历，有关系表达式。

14.3 BM算法 （字符串匹配向后滑动）

  • 坏字符原则
  • 好后缀原则

14.4 KMP算法 （发明者名字命名）

  • O（m+n）时间复杂度
  • 字符串匹配算法

14.5 字典树（trie树）

  • 公共的前缀重合在一起，多叉树

14.6 AC自动机

  • 多模式串匹配算法
  • 类似在树结构上加了next数组

15 算法思想

15.1 贪心算法

  • 霍夫曼编码。根据字符串频率编码后再存储

15.2 分治思想

  • MapReduce实现思想就是多台机器分治

15.3 回溯思想

  • 回退再试
  • 时间复杂度 指数级

15.4 动态规划

  • 分多个阶段，取最后阶段就是最大重量。
  • 思路：状态转移表；状态转移方程；
  • 时间复杂度 线性级

15.5 动态规划实例

16 其他算法

16.1 拓扑排序

16.2 最短路径

  • 有权有向图，放到优先级队列中。
  • 应用：地图推荐最短路径

16.3 位图

  • 布隆过滤器：位图 + hash
  • 应用：爬虫URL去重

16.4 概率统计

  • 应用：过滤垃圾短信

16.5 向量空间

  • 欧几里得距离
  • 应用：推荐系统

16.6 mysql索引B+树

16.7 A*算法

  • 应用：游戏寻路

16.8 索引

  • hash表：redis，memcache 适合hash表构建索引
  • 红黑树：适合构建内存索引
  • B+树：适合构建磁盘索引。mysql，oracle等数据库
  • 跳表：redis有序集合

16.9 并行计算

17 算法实战

17.1 reids数据结构与算法

  • list： 压缩列表+循环链表
  • hash： 压缩列表+hash表
  • set： 有序数组+hash表
  • 有序集合： 压缩列表+ 跳表+hash表

17.2 百度&谷歌 搜索引擎

  • 搜索，分析，索引，查询

操作系统

1 计算机原理

2 CPU

3 进程

4 线程

5 协程

6 Linux

7 并发

7.1 并发的原理

  • 交替执行，叠加执行。
  • 单处理系统中：进程切换&共享变量，中断可能会在进程中任何地方停止 引起并发问题！
  • 多处理系统中：多进程，上述问题或 同时执行同时访问同一变量 都会引起并发问题！

7.2 竞争条件

  • 多个进程，线程读写数据时，结果依赖多个进程的指令执行顺序。

7.3 进程的交互

  • 竞争；共享；通信；

7.4 互斥（硬件的支持）

  • 禁用中断（多处理器中无效）；
  • 专用机器指令
  • 信号量
  • 管程
  • 消息传递

网络

1 网络协议

1.1 TCP/IP

  • 《OSI七层网络协议模型》

    • OSI七层：物理层（IEEE 802.1A, IEEE 802.2到IEEE 802.11）、数据链路层（FDDI, Ethernet, Arpanet, PDN, SLIP, PPP）、网络层（IP, ICMP, ARP, RARP, AKP, UUCP）、传输层（TCP, UDP）、会话层（SMTP, DNS）、表示层（Telnet, Rlogin, SNMP, Gopher）、应用层（HTTP、TFTP, FTP, NFS, WAIS、SMTP）
    • TCP/IP四层：数据链路层、网络层、传输层、应用层

  • 《点对点 ，端到端》

    • 端到端：针对传输层，发送端与接收端之间建立连接再发数据。
    • 点到点：针对数据链路层或网络层，数据发给直接相连的设备。

  • 《TCP/IP四层协议理解》

    • 链路层：对电信号进行分组并形成具有特定意义的数据帧，然后以广播的形式通过物理介质发送给接收方
    • 网络层：（IP协议，ARP协议，路由协议）定义网络地址，区分网段，子网内MAC寻址，对于不同子网的数据包进行路由
    • 传输层：定义端口，标识应用程序身份，实现端口到端口的通信，TCP协议可以保证数据传输的可靠性。
    • 应用层：定义数据格式并按照对应的格式解读数据

  • 《TCP三次握手，四次挥手》《TCP三次握手，四次挥手详解》

    • URG 紧急指针是否有效。为1，表示某一位需要被优先处理。
    • ACK 确认号是否有效，一般置为1。
    • PSH 提示接收端应用程序立即从TCP缓冲区把数据读走。
    • RST 对方要求重新建立连接，复位。
    • SYN 请求建立连接，并在其序列号的字段进行序列号的初始值设定。建立连接，设置为1.
    • FIN 希望断开连接。
    • 三次握手： 1. SYN = 1，seq = j 2. SYN=1，ACK=1,ack= j+1,seq= k 3.ACK=1,ack=k+1
    • 四次挥手： 1. FIN=m 2.ACK=m+1 3.FIN=n 4 ACK=1,ack=n+1

  • 《TCP客户端服务端，连接断开，示例》

1.2 HTTP

  • 《HTTP协议详解，抓包分析》《HTTP2.0原理详解》《HTTP2.0二进制帧》

    • HTTP2.0二进制桢
    • HTTP2.0:多路复用、压缩头信息、请求划分优先级、支持服务器端主动推送
    • HTTP1.0:每个请求都需单独建立连接（keep-alive能解决部分问题单不能交叉推送）、每个请求和响应都需要完整的头信息、数据未加密

  • 《HTTPS原理》《一个故事讲清HTTPS》

      1. 浏览器发送HTTPS请求 2 服务器发送数字证书给客户端 3 浏览器CA列表验证证书 4 浏览器产生对称密钥，用公钥加密 5 用私钥揭秘获得对称密钥 6 用对称密钥加密通信。

1.3 LOT七大通信协议

2 网络模型

2.1 I/O模型

  • 《web优化必须了解的原理之I/o的五种模型和web的三种工作模式》
    • I/O步骤：进程向操作系统请求数据 ;操作系统把外部数据加载到内核的缓冲区中;操作系统把内核的缓冲区拷贝到进程的缓冲区 ;进程获得数据完成自己的功能 ;
    • 五种I/O模型：阻塞I/O，非阻塞I/O，I/O复用、事件(信号)驱动I/O、异步I/O，前四种I/O属于同步操作，I/O的第一阶段不同、第二阶段相同，最后的一种则属于异步操作。
    • 三种 Web Server 工作方式：Prefork(多进程)、Worker方式(线程方式)、Event方式。
  • 《一文读懂I/O复用》
    • 第一阶段select阻塞，第二阶段recvfrom阻塞

2.2 select，poll，epoll

2.3 BIO NIO AIO

2.4 kqueue

2.5 长连接短链接

设计模式

1 设计模式六大原则

  • 《设计模式的六大原则》
    • 开闭原则：对扩展开放,对修改关闭，多使用抽象类和接口。
    • 里氏替换原则：基类可以被子类替换，使用抽象类继承,不使用具体类继承。
    • 依赖倒转原则：要依赖于抽象,不要依赖于具体，针对接口编程,不针对实现编程。
    • 接口隔离原则：使用多个隔离的接口,比使用单个接口好，建立最小的接口。
    • 迪米特法则：一个软件实体应当尽可能少地与其他实体发生相互作用，通过中间类建立联系。
    • 合成复用原则：尽量使用合成/聚合,而不是使用继承。

2 23种设计模式

设计思想&开发模式

TODO

中间件

1 Web Server

1.1 nginx

  • 《nginx入门教程》《nginx中文文档》

    • 进程模型：一个master进程，管理多个worker进程。一个请求只能一个worker进程处理。worker进程抢acceptMutex锁,然后接受请求，处理请求，返回请求，断开连接
    • 事件模型：高并发，异步非阻塞事件机制（例如epoll，循环处理准备好的事件请求，IO事件没有准备好就放回epoll)。
    • connection: TCP三次握手
    • request: 请求行、请求头、请求体、响应行、响应头、响应体

  • 《nginx配置》

  • 《nginx正向代理和反向代理》

    • 正向代理：访问无法访问的服务器；缓存，加速访问；登陆授权；访问日志记录；
    • 反向代理：负载均衡；保证原始服务器安全；
    • 正向代理和反向代理 配置文档
    • 正向代理和反向代理 配置示例

  • 《一个HTTP请求过程》《HTTP请求过程》

    • DNS域名解析；TCP连接；接受请求；处理请求；返回响应；关闭TCP；记录日志；解析HTML展示页面；

1.2 apache

1.3 OpenResty

2 缓存

2.1 本地缓存

2.2 客户端缓存

2.3 服务端缓存

2.3.1 web缓存
2.3.2 Memcache
2.3.3 Redis
2.3.4 Tair

3 消息队列

3.1 消息队列常见问题

3.2 RabbitMQ

3.3 RocketMQ

3.4 ActiveMQ

3.5 Kafka

3.6 Redis

  • 《Redis用作消息队列》
    • 生产者、消费者模式完全是客户端行为，list 和 拉模式实现，阻塞等待采用 blpop 指令。

4 定时调度

5 API网关

请求转发、安全认证、协议转换、容灾

6 配置中心

数据库

1 基本理论

1.1 三大范式

1.2 事物隔离级别

  • 原子性，一致性，隔离性，持久性
  • 读不提交，出现脏读
  • 读提交，出现不可重复读
  • 重复读，出现幻读
  • 序列化，--

2 原理

2.1 架构设计

  • 连接层，优化/缓存层，存储引擎

2.2 数据存储

  • frm文件表空间描述
  • ibd文件索引和数据
  • page页：头双向链表，body链表存储记录
  • 索引：B+树

3 索引

3.0 索引原理

  • 聚族索引与非聚簇索引
  • B+树，非叶子结点不存数据，只存索引键值，叶子结点存数据。

3.1 索引类型

  • 聚族索引与非聚簇索引
  • 单列索引
  • 索引覆盖
  • 组合索引，索引合并
  • 全文索引

3.2 索引原则

  • 1.在经常需要搜索的列上,可以加快索引的速度

  • 2.主键列上可以确保列的唯一性

  • 3.在表与表的而连接条件上加上索引,可以加快连接查询的速度

  • 4.在经常需要排序(order by),分组(group by)和的distinct 列上加索引 可以加快排序查询的时间, (单独order by 用不了索引，索引考虑加where 或加limit)

  • 5.在一些where 之后的 < <= > >= BETWEEN IN 以及某个情况下的like 建立字段的索引(B-TREE)

  • 6.like语句的 如果你对nickname字段建立了一个索引.当查询的时候的语句是 nickname lick '%ABC%' 那么这个索引讲不会起到作用.而nickname lick 'ABC%' 那么将可以用到索引

  • 7.索引不会包含NULL列,如果列中包含NULL值都将不会被包含在索引中,复合索引中如果有一列含有NULL值那么这个组合索引都将失效,一般需要给默认值0或者 ' '字符串

  • 8.使用短索引,如果你的一个字段是Char(32)或者int(32),在创建索引的时候指定前缀长度 比如前10个字符 (前提是多数值是唯一的..)那么短索引可以提高查询速度,并且可以减少磁盘的空间,也可以减少I/0操作.

  • 9.不要在列上进行运算,这样会使得mysql索引失效,也会进行全表扫描

  • 10.选择越小的数据类型越好,因为通常越小的数据类型通常在磁盘,内存,cpu,缓存中 占用的空间很少,处理起来更快

  • 尽量选择区分度高的列作索引

3.3 索引失效

  • 索引列 like "%xx"
  • 使用函数计算
  • or 有没有索引的列
  • 类型不一致
  • order by 查询的列不是主键排序就不走索引

3.4 explain

  • 《explain分析SQL》
    • select_type：simple，primary，subquery，derived，union，union result
    • type：system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL

并发

1 并发概念

1.1 并发

1.2 多线程

1.3 线程安全

  • 《线程安全问题及解决方案》
    • 产生原因：CPU切换时间片执行多线程产生竞态条件
    • 原子性，可见性，时序性；原子性：要么都执行，要么都不执行。a++是先查，后加，不是原子操作。
    • 加锁

2 锁

  • 《锁的分类》
    • 乐观锁&悲观锁，互斥锁/写锁，共享锁/读锁，公平锁/非公平锁，重入锁/非重入锁，分段锁等。

2.1 悲观锁

2.2 乐观锁

2.3 死锁

性能

1 性能优化方法

2 容量评估

3 CDN加速

4 连接池

5 优化工具

安全

1 堡垒机（跳板机）

2 web 安全

2.1 XSS

2.2 CSRF

2.3 SQL 注入

2.4 HashDos

2.5 脚本注入

2.6 漏洞扫描工具

2.7 验证码

3 DDoS防范

4 用户隐私信息保护

  1. 用户密码非明文保存，加动态salt。
  2. 身份证号，手机号如果要显示，用 “*” 替代部分字符。
  3. 联系方式在的显示与否由用户自己控制。
  4. TODO

5 序列化漏洞

6 加密解密

6.1 对称加密

  • 《常见对称加密算法》
    • DES、3DES、Blowfish、AES
    • DES 采用 56位秘钥，Blowfish 采用1到448位变长秘钥，AES 128，192和256位长度的秘钥。
    • DES 秘钥太短（只有56位）算法目前已经被 AES 取代，并且 AES 有硬件加速，性能很好。

6.2 哈希算法

6.3 非对称加密

7 服务器安全

8 数据安全

8.1 数据备份

TODO

9 网络隔离

9.1 内外网分离

TODO

9.2 登录跳板机

在内外环境中通过跳板机登录到线上主机。

10 授权、认证

10.1 RBAC

10.2 OAuth2.0

10.3 双因素认证（2FA）

2FA - Two-factor authentication，用于加强登录验证

常用做法是 登录密码 + 手机验证码（或者令牌Key，类似于与网银的 USB key）

10.4 单点登录(SSO)

运维&统计&技术支持

1 常规监控

1.1 命令行监控工具

2 日志服务

3 RPC

4 docker

5 APM

application performance management

6 统计分析

7 持续集成

8 自动化运维

9 灰度蓝绿AB

10 虚拟化

11 devops&openstack

12 测试

12.1 压力测试

  • 《apache ab测试使用指南》

    • too many open files (解决方案：ulimit -n; nginx配置events同级 worker_rlimit_nofile 15360;)
    • apr_socket_recv:Operation timed out (解决方法：ab加上-k 开启keepAlive)
    • apr_socket_connect(): Operation already in progress (解决方法：apache/conf/extra/httpd-mpm.conf 修改 ThreadsPerChild)
    • apr_socket_recv: Connection reset by peer (54)
    • setsockopt(TCP_NODELAY) failed (22: Invalid argument) while keepalive

  • 《大型网站压力测试及优化方案》

12.2 测试驱动开发

12.3 单元测试

  • 《单元测试》
    • 单元测试可以有效地测试某个程序模块的行为，是未来重构代码的信心保证。
    • 单元测试的测试用例要覆盖常用的输入组合、边界条件和异常。
    • 单元测试代码要非常简单，如果测试代码太复杂，那么测试代码本身就可能有bug。
    • 单元测试通过了并不意味着程序就没有bug了，但是不通过程序肯定有bug。

13 CGI

架构&框架

1 架构

1.1 架构师修炼图

1.2 微服务架构

分布式设计

1 扩展性设计

1.1 分布式&异步

1.2 分布式之数据切分

  • 《可扩展性设计之数据切分》
    • 垂直切分，水平切分，联合切分
    • 垂直切分缺点： join表分页搜索需要程序完成；事务处理复杂；
    • 水平切分缺点： 维护数据变复杂；切分无具体标准；
    • 切分与整合带来的问题：分布式事务；跨节点join（全局表，冗余，数据组装）；跨节点合并分页排序（先排序分页，再数据组装）；

1.3 分布式事务一致性

2 稳定性&高可用

  • 《系统设计：关于高可用系统的一些技术方案》

    • 可扩展：水平扩展、垂直扩展。 通过冗余部署，避免单点故障。一主多从。
    • 隔离：避免单一业务占用全部资源。避免业务之间的相互影响 2. 机房隔离避免单点故障。
    • 解耦：降低维护成本，降低耦合风险。减少依赖，减少相互间的影响。
    • 限流：遇到突发流量时，保证系统稳定。
    • 降级：紧急情况下释放非核心功能的资源。牺牲非核心业务，保证核心业务的高可用。
    • 熔断：异常情况超出阈值进入熔断状态，快速失败。减少不稳定的外部依赖对核心服务的影响。
    • 自动化测试：通过完善的测试，减少发布引起的故障。
    • 灰度发布：灰度发布是速度与安全性作为妥协，能够有效减少发布故障。

  • 《关于高可用的系统》

    • 数据不丢，就必需要持久化；服务高可用，就必需要有备用；复制，就会有数据一致性

2.1 负载均衡

2.2 限流

  • 《谈谈高并发系统的限流》
    • 计数器：通过滑动窗口计数器，控制单位时间内的请求次数，简单粗暴。
    • 漏桶算法：固定容量的漏桶，漏桶满了就丢弃请求，比较常用。
    • 令牌桶算法：固定容量的令牌桶，按照一定速率添加令牌，处理请求前需要拿到令牌，拿不到令牌则丢弃请求，或进入丢队列，可以通过控制添加令牌的速率，来控制整体速度。Guava 中的 RateLimiter 是令牌桶的实现。
    • Nginx 限流：通过 limit_req 等模块限制并发连接数。

2.3 容灾

2.4 平滑重启

3 数据库扩展

3.1 读写分离

3.2 分片模式

4 服务治理

4.1 服务发现

4.2 服务路由

5 分布式一致性

5.1 CAP与BASE理论

  • 《从分布式一致性谈到CAP理论、BASE理论》
    • 一致性分类：强一致(立即一致)；弱一致(可在单位时间内实现一致，比如秒级)；最终一致(弱一致的一种，一定时间内最终一致)
    • CAP：一致性、可用性、分区容错性(网络故障引起)
    • BASE：Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）
    • BASE理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。

5.2 分布式锁

5.3 分布式一致性

5.4 幂等

6 分布式文件系统

7 唯一ID生成

8 一致性HASH算法

大数据

1 流式计算

1.1 Storm

1.2 Flink

1.3 Kafka Stream

1.4 应用场景

例如：

  • 广告相关实时统计；
  • 推荐系统用户画像标签实时更新；
  • 线上服务健康状况实时监测；
  • 实时榜单；
  • 实时数据统计。

2 Hadoop

2.1 HDFS

2.2 MapReduce

2.3 Yarn

3 Spark

搜索引擎

1 搜索引擎原理

2 Lucene

3 Elasticsearch

4 Solr

5 sphinx

golang

1 基本概念

1.1 GOPATH和工作区

  • GOROOT,GOPATH,GOBIN
  • src,bin,pkg
  • go build; go install ; go get;

1.2 命令源码文件

  • 如果一个源码文件声明属于main包，并且包含一个无参数声明且无结果声明的main函数，那么它就是命令源码文件

1.3 库源码文件

  • 库源码文件是不能被直接运行的源码文件，它仅用于存放程序实体，这些程序实体可以被其他代码使用
  • internal
  • 函数导出，访问权限

1.4 变量声明

  • var s string
  • s := "name"
  • 短变量声明

1.5 作用域

  • 包级私有的、模块级私有的和公开的

2 数组切片

  • 在无需扩容时，append函数返回的是指向原底层数组的新切片,而在需要扩容时，append函数返回的是指向新底层数组的新切片。
  • slice扩容 2倍，1.25倍。
  • 底层数组不会被替换，直接生产新的数组

3 链表

  • container/list

4 字典哈希

5 channel

5.0 注意点

  • 通道不能一直阻塞
  • goroutine执行完再退出
  • goroutine泄漏
  • channel关闭
  • goroutine不能打开太多，应该有限制

5.1 通道规则

  • 对于同一个通道，发送操作之间是互斥的，接收操作之间也是互斥的
  • 发送操作和接收操作中对元素值的处理都是不可分割的
  • 发送操作在完全完成之前会被阻塞。接收操作也是如此

5.2 无缓存通道

  • Channels的发送操作将导致发送者goroutine阻塞，直到另一个goroutine在相同的Channels上执行接收操作
  • 接收操作先发生，那么接收者goroutine也将阻塞，直到有另一个goroutine在相同的Channels上执行发送操作

5.3 close

  • 当一个channel被关闭后，再向该channel发送数据将导致panic异常
  • 当一个被关闭的channel中已经发送的数据都被成功接收后，后续的接收操作将不再阻塞，它们会立即返回一个零值
  • 只需要关闭接受者goroutine
  • range是安全接收的，它会判断是否关闭且没有收据接收。

5.4 单方向channel

  • 只有在发送者所在的goroutine才会调用close函数
  • 任何双向channel向单向channel变量的赋值操作都将导致该隐式转换，没有反向转换的语法

5.5 缓存通道

  • 内部缓存队列是满的，那么发送操作将阻塞直到因另一个goroutine执行接收操作
  • channel是空的，接收操作将阻塞直到有另一个goroutine执行发送操作而向队列插入元素。
  • 可以保证go程执行完再退出（？？）

5.6 并发循环

  • 循环时显式的将参数传给go程。
  • wg.wait为什么要在go func(){}中
  • for range channel当channel关闭且流干的时候才退出循环

5.7 select

  • 同时都满足条件，会随机选择一个执行。是不是有bug
  • Loop goto break

5.8 并发的退出

  • 通过close广播，select去接收。

6 基于共享变量的并发

6.1 数据竞争

  • 数据竞争会在两个以上的goroutine并发访问相同的变量且至少其中一个为写操作时发生。
  • 三种方法避免数据竞争：不要去写变量；避免从多个goroutine访问变量；加锁；

6.2 互斥锁

  • sync.Mutex互斥锁

6.3 读写锁

  • sync.RMutex读写锁

6.4 内存同步

  • 内存同步
  • 不使用channel且不使用mutex这样的显式同步操作时，我们就没法保证事件在不同的goroutine中看到的执行顺序是一致的

6.5 初始化

  • sync.once
  • 保证loadIcons的变量能够对所有goroutine可见

6.6 并发的非阻塞缓存

  • close(ch)会广播到每个goroutine
  • 两种方式：加锁；channel ；

NSQ

TODO

YII

《计算机组成原理》

1 计算机概述

1.1 软硬件

  • 软件，硬件
  • 系统软件；应用软件

1.2 层次结构

  • 汇编--机器语言-解释操作系统-微程序解释机器语言-执行机器语言
  • 翻译程序两种：编译程序；解释程序；

1.3 计算机组成

  • 运算器，存储器，控制器，输入输出
  • 指令和数据相同地位存放在存储器，可按地址寻访。
  • 指令和数据由二进制码表示
  • 指令由操作码和地址码组成
  • 指令是顺序存放的
  • 以运算器为中心
  • 现代计算机：MM+CPU+IO

1.4 计算机硬件

  • 数学建模；确定计算方法；编程序
  • 控制器，存储器，运算器，输入，输出设备

项目管理

TODO

资讯&技术资源

1 行业资讯

2 博客

TODO

  • 计算机组成原理
  • 编译原理和技术
  • 操作系统原理与设计
  • 数据结构算法基础
  • 计算机组成原理实验
  • 数据库系统及应用
  • 并行计算
  • 软件工程
  • 计算机导论
  • 计算机网络

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

214 stars

Watchers

10 watching

Forks

67 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages