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