高性能计算
2021-07-29 15:27:15 2 举报AI智能生成
高性能计算所涉及的所有知识 涵盖算法、Linux、方法论
作者其他创作
大纲/内容
预加载
时空局部性原理
冷不命中
padding
伪共享
覆盖不命中
MESI
缓存行一致性协议
什么是缓存行
L1
全关联
L2 L3
组关联
类型
缓存行
为什么
怎么升级
锁升级
Monitor对象
Wait/notify
CountDownLutch
Condition
ReadWriteLock
ReentryLock
JUC
Park
unsafe库
轻量级锁
重量级锁
Synchronized
线程同步技术
java
CAS
多线程编程
CPU多核构架
高精度计算
jmm规范
c/c++
go
happens-before
分支预测
java中表示强制同步工作空间与堆中的共享变量
C/C++表示禁止编译器重排
LOCK指令——原子指令
volatile
乱序执行
利用冗余的资源进行高效的运算
超线程\\超标量
流水线模型
静态编译
动态编译
编译
动态链接
静态链接
链接
进程的创建
OS
程序的加载
程序的执行
ELF
可执行文件格式
程序是怎么运行的
早期多任务程序支持
分段
段式与页式
提高CPU访问内存的性能
为什么要内存对齐
子主题 1
编译器怎么对齐内存的
内存对齐
缓存
算法的基础
递归
冯诺依曼瓶颈
著名的金字塔模型
CPU内存模型
CPU
段
页目录
多级页表
页表
虚拟内存管理
为什么能够提高效率？
内存映射mmap
内存管理
进程的切换原理
进程调度
硬盘
块设备
网络套接字文件
终端
外设啥的
字符设备
打开的文件
文件系统
锁
信号
静态链接库
二进制可执行文件
代码段（加载）
全局变量
字符串
静态变量
数据段（加载）
进程动态内存空间
堆（运行时）
自动回收
局部变量
线程
栈（运行时）
动态链接的原理
动态链接库
库函数
共享内存（加载）
虚拟内存空间
寄存器
系统调用
内核栈
task_struct
进程的构造
陷入内核
返回用户态
进程管理
文件系统可以随意的挂在到任何的目录资源上
文件系统跟路径分离
操作文件的各种方法
注册文件系统
不对应到块设备驱动就是内存文件系统取决于继承的op操作
内存文件系统成为可能
不同文件系统实现自己的inodeopiblock的组织
不同文件系统通过统一的vfs做到机制策略分离
良好的面向对象实践
Linux万物皆文件
每次加载一个块4K
利用时空局部性原理加快系统访问速度与吞吐
inode索引区
数据区
格式化块设备
建立索引
如何快速定位块
分块管理
虚拟文件系统
CPU原子操作
信号量
每个进程都有信号队列
异常
父子进程通信
CS程序的调度
网络程序通信
进程通信的手段
管道
RPC
共享内存
进程通信
系统库共享
将Linux内核看做一个整体
包管理工具
系统工具
依赖配置
编程语言库
将不同Linux的差异屏蔽
配置文件
程序
将应用程序的context打包
相当于在不同电脑上插入不同的CD来播放不同格式的音乐
操作系统对进程的裁剪与限制
UTS
USER
Mount
进程之间互相ps不到了
PID
Network
隔离
NameSpace
内存
CPU节点使用
磁盘
资源限制
cgroup
技术
容器原理
进程列表、线程列表、父子关系、CPU占用、用户态内核态占用等
top
虚拟内存监控上下文切换
vmstat
详细看某个进程的资源使用
pidstat
iostat
perf
工具的使用
开销小
只有线程的上下文要保存
发生在一个线程中
内核空间对所有进程一致
发生在内核中
中断切换
开销大
进程的所有资源都要切换、保存
进程切换
要切换寄存器栈空间等
开销中等偏小
虚拟内存不用切TLB不用刷
发生在同一个虚拟地址空间
线程切换
时间片用完
内存不足
资源用完
sleep
被强占
切换时机
上线文切换
Linux性能调优
操作系统
TCP/IP状态转移
tcpdump
wireshark
7-4层的抓包工具
检测工具的使用
Time_wait过多？
怎么标志一个数据包是否完毕
粘包问题
滑动窗口算法
....
TCP是流式算法
常见的问题
三次握手四次挥手
内核中的队列
0拷贝技术
内核态到用户态的copy
一个可能的是TCP/IP协议栈用户态移动
多路复用解决10k问题，那么1000k？
epoll
内核实现细节
没有copy
不占用内核资源，程序更稳定
用户态协议栈实现？
原理
解决的问题
HTTP2.0
TCP/IP协议
多线程 vs 单线程
红黑树
nginx
redis
中间件
多路复用
算法
7层 4层负载
硬件负载
F5
工具
负载均衡原理
阻塞调用
非阻塞调用
调用函数read write等是否能麻烦返回不切换进程
同步IO
异步IO
数据从内核拷贝到用户态是否是异步的
考虑两个同步与异步
两个syscall
然后调用read取
select、epoll阻塞
批处理，一次等待一批
阻塞IO
一个syscall
内核处理数据+拷贝数据一直等
古老
阻塞调用阻塞IO
做Polling，看看内核完成没，如果完成则继续往下走
事件到来后，还得去内核取数据
信号驱动
调用以后立即返回事件通知后，数据已经到了用户态
非阻塞
纯异步IO
网络模型
网络程序设计
底层技术
参数设置
并行的GC
管理大内存才有用
0卡顿的zgc
不同GC算法的区别
垃圾标记算法
jvm分代模型
JVM调优
一堆工具
hashset
hashtable
ConcurrentHashTable
Hash
Java的数据结构线程安全问题要注意
forkjoin
线程池
AOP
IOC
一堆组件
框架
Spring
JVM
协议标准
标准的队列具有高可靠性
可靠性好
客户端多
广播
topic
routekey
基于Exchange与Queue模型
Rabbitmq
基于文件的日志系统
基于日志文件的队列
kafka
kafka的变种
Rocketmq
Azure MQ
微软的队列
MSMQ
MQ
mq的协议
mq
pb等等
grpc
RPC框架
外存数据结构
多叉树
B+ tree
索引原理
磁盘IO分析
执行策略分析
分库分表策略
集群
SQL调优
Mysql
用得少
文档型
MongoDB
logn的增删查改
分值排序topN
logn的取范围
zset
bitmap
Stream
轻量级
sub-pub
服务外-数据缓存层数据结构服务器
redisson
分布式锁
哨兵模式
集群模式
bin log
aof文件
日志
hyper loglog等概率算法
算法模块
内存操作：快速
部署方便，单线程处理核心逻辑，快速简单
存储、检索规模大，且不占业务内存
提供丰富的进程类数据结构实现
但是不擅长需要做backup
可持久化
客户端支持丰富
优点
没必要，否则灵活性查
没有分片机制
分布式集群扩展能力不好
一般后面会有mysql
本来就是用作高并发，这块程序补偿
掉电后恢复慢，准确性不高
可靠性不好
缺点
特点
Redis数据库服务器
数据索引、大数据查询
大规模日志
solr也行
数据库的全文索引
文档型数据库
Elastic search
数据类
docker
K8s
部署工具
常见的中间件
联想LSC2.0OD算法设计
移动飞信高性能网关设计
案例
高并发程序设计
内存管控技术
没有测试不能优化
UT
保证系统交互在优化前后一致
E2E
保证系统的稳定性
调查系统性能问题的根本原因
认清系统边界，避免破坏性优化
如果系统在持续更新如何优化？
永远要有B计划兜底
保证系统的可用性
实施性能改进
保证系统的运行性能
遗留系统的优化
关键功能有有效且完备的测试覆盖
统一的批处理框架
统一的缓存处理框架
统一的RPC框架
统一的队列服务封装
统一的日志框架
统一的配置框架
构架师设计框架
实现一个功能只有一种方式
不同的中间件有不同的特点
最终一致性
并发高的事务补偿机制
事务兜底
要并发高，事务性就会差
数据库是AC系统可以合理使用
保证事务性，就会损失吞吐量
规划IO是个平衡的过程不存在万全的方案
对IO的合理规划
类比到操作系统设计
业务往往多变，底层的能力往往不变
IO
底层能力往往不变对开发者进行屏蔽
对变化与不变进行规划与解耦
分层构架设计
高并发系统构架设计原则
注重构架的设计
新系统性能保证
高性能分布式系统设计原理
code review
性能优化原则宣贯
性能retro
分布式数据收集
Big Data
分布式数据存储
Gfs
分布式计算框架
Map-Reduce
google的三篇论文
Docker
容器技术
大量进程/线程的管控调度
分布式部署
分布式系统的来源，能解决什么问题
服务越多，装填越难预测
配置信息多，难维护
运维困难
服务之间的依赖复杂
部署困难
Spring Cloud
依赖多，链路长
日志多难排查
日志服务不稳定，bug难复现
日志服务
bug难排查
分布式系统缺点
执行文件小，启动内存占用小
小
启动快速，部署快速，服务依赖少
快
自动化运维
扩展性好
编排容易
灵
好的分布式服务特点
统一的服务发现
带存储，稳定重试容易，可靠
Mq
管道模型
性能好，不稳定
网络
子弹模型
序列化反序列化速度
编程友好
协议数据格式矛盾
统一的RPC调用方式
高效的RPC框架
统一的配置获取
统一的配置推送
配置服务
ELK
稳定的日志框架
关键设计点
开箱即用？
bug链太长，debug痛苦
依赖是bug的根源
重新造轮子是大公司提高稳定性的一个手段
KISS原则
减少服务的依赖可以提高服务的稳定性
一个系统零件越多越脆弱，怎么控制bug？
系统出了问题，怎么能够快速定位与排查？
怎么测试一个分布式系统？
开发与维护一个分布式系统比单体要难得多！
技术水平与能力是限制分布式系统研发的重要因素
业务层DDD
功能层按照性能点切分
如何切分服务？
走一步看一步不过过度与过早的设计
细胞分裂模式
分层构建是构建分布式系统的有效手段
一些经验
设计原则
设计原则宣贯
跟敏捷配套的活动设计
原则：性能优化活动处理的是人与机器之间交互
优化之前补全UT
data race
多线程并发场景
缓存失效更新问题
事务补偿方案？
事务机制
优化之后加UT
优化之前先把事情做对，不要做过早优化
超算
用容量更大速度更快的计算机
map reduce
分布式并行计算
加快CPU运行指令的速度
算法降阶打击
加缓存
减少问题的计算规模
优化只有两种
最稳定的程序要求程序员对每一行代码都熟悉到字节的程度
对底层的持续学习了解更多知识越能做出正确的判断
行动指引
方法论
单向
双向
队列
查询O(n)
插入更新删除O(1)
在编程时，链表性能较差不容易命中CPU缓存
性能
链表
hash table
堆 heap
查询O(1)
插入删除更新O(n)
性能较好，容易命中CPU缓存建议多用
数组
数据结构的基石
是否有线性的扩容能力
多线程情况下的表现
稳定性
增删查改的时间复杂性
时间复杂度
数据规模的增长特性
空间复杂度
对范围的支持
为什么redis要用跳表实现zset？
红黑树 vs SkipList
当数据持续增长扩容问题实现的难度多线程下的稳定性
为什么Linux内核的查找表不用HashMap？
红黑树 vs HashMap java
工程难度
评估一个数据结构的性能
可以用于流式计算增 删 查 logn
优先级队列
堆
基于链表+索引
跳表
动态数据结构
hashTable
ArrayList
静态数据结构
为什么说红黑树比Hashmap更适合做性能可靠性较高的工程
不能忽略工程化难度
得先排序
二分法
静态性能好扩容性能差
HashTable
平均性能不行
二叉查找树BST
增 删 查都是O(logn)
稳定可靠
容易编码实现好测试
稳定可靠，动态性能好
空间复杂度高于红黑树
语言库函数支持较少
跳表 SkipList
查找表
分类
数据结构
渐进上界
大O是同阶或者渐进上界小o是绝对渐进上界
大O 小o
同阶
西塔
渐进下界
大-同阶或者渐进下界小-绝对渐进下界
大欧米伽 小欧米伽
函数的渐进界
组合问题规划问题
指数 阶乘
KMP
字符串匹配问题
查找、匹配
多项式级别
排序
最长子序列等问题
分治查找
线性对数
线性
二分搜索
对数互联网级
算法的降阶过程
如何计算一个算法的时间复杂度
衡量算法的时间复杂度
快速排序、堆排序
关键点在于考虑子问题合并时是否是O(n)
各种查找问题分析问题都可以考虑
分治策略
N+1只有在N算完才能得出最优解
多阶段最值问题
递推方程的证明与推算
子问题具有传递性
递归树有重复子问题
往往面对的问题是一个指数或者阶乘问题
存在重复子问题计算
0-1背包
高阶的背包
背包问题
最优组合
规划问题
判定问题
问题域
指数
看看是否有DP的特性
估算原始问题的工作量
蛮力算法解析
本质是缓存的思想
相同的子问题只要算一次就行
从递归树上可以发现重复子问题，并用表记录结果
画出递归树
递归求解
得出递推方程
解法
常见的50个可以用DP解的问题
最值问题处理降阶利器
动态规划策略
huffman编码
单源最短路径问题
形式很简单 好实现 但是难点在于证明
贪心策略
可以用来做降阶的初步评估算法建议在做算法优化时，一定要实现蛮力算法对问题有个清晰的认识，然后优化
蛮力算法
8皇后
路径探索
#我来讲一个算法设计的故事博客大赛
算法工程实践如何面对现实中的算法设计问题
图+倒排序索引
LSC OD商业项目
约束满足问题
回溯算法
算法设计技术
算法设计
特点——判断不存在问题可以节约内存如果K个key都在bitmap中不能说明一定存在但是如果不在bitmap中一定不满足。
达到n（目标空间）>m（数组长度）时可以达到判断目标是否存在的效果
用多个hash函数对目标计算形成多个hash值
基础是bitmap
布隆过滤器
包括虚拟节点的建立
集群的扩容缩小数据搬迁的数量
一致性hash
搜索引擎框动态提示功能
多模的形式敏感词过滤
动态匹配字符串
缺点是：内存占用大弥补是缩点
Trie tree
分词、自然语言
Lucence
Elastic Search
Solar
模糊搜索的解决方案
倒排序索引
mysql的索引调优
多叉树+二分搜索
结合磁盘读取数据的特性将二叉树的性能在外存上做了优化
B+ Tree
流量控制
排序合并多个流
logn的时间找到TopK
处理动态带权重排序问题
分治算法的典型
可以求 逆序对数量
比快排的空间复杂度高
堆排序
参考:#换个角度彻底理解红黑树
2-3树的变种
易于实现
性能卓越 时间 logn空间m^2(n是层数)
范围搜索的性能更好
性能跟红黑树相当
redis的zset实现
网络流
二分图
配对问题
最短路径
地图
排课、编译顺序
拓扑顺序
面向对象IDE处理对象、方法、变量的关系
基于图的倒排序索引
动态规划
联想OD算法
案例：
对象关系研究
描述的是事物之间的复杂关系
栈
深度优先
广度优先
图的遍历
邻接矩阵
邻接表
图的构建
图
一些有用的算法与数据结构
链表与数组的融合
LinkedHashMap
在数据量不大的情况下充分利用CPU内存模型来加快处理
时空局部性
压缩列表
分析redis的源码可以了解更多工程实践的例子
redis宝库
一些工程实践的例子
指数及其以上规模为不可解
多项式级别是可解
可计算性问题
证明了一个其他都能证明
NPC是什么
NP--N问题是什么？
这个问题呢？
人工智能？
所有现实的问题都能计算吗
vs经典计算机
量子计算机是什么？
是否所有命题都能证明的通用证明是否存在
解决希尔伯特23个问题中的一个
图论的贡献
奠定了计算机由CPU与内存组成缺一不可
存储程序型计算机发明者
冯诺依曼的贡献
计算机与数学之间关系的桥梁
提出了衡量算法快慢的一般方法
高德纳的贡献
计算理论
HPCTO B/C 高性能计算
0 条评论
回复 删除
下一页
