技术

下一个平台Agent 激发LLM涌现——提示工程 LLM微调理论及实践 大佬沉思 LLM外挂知识库 LLMOps 多模态LLM Python一些比较有意思的库 LLM部分技术源码学习 LangChain源码学习 通用分布式计算引擎Ray Python并发 go依赖注入 go collection gc的基本原理 golang性能分析及优化 数据湖 高性能计算与存储 Linux2.1.13网络源代码学习 《大数据经典论文解读》 三驾马车学习 Spark 内存管理及调优 Yarn学习 从Spark部署模式开始讲源码分析 容器狂占内存资源怎么办? 多角度理解一致性 golang io使用及优化模式 Flink学习 c++学习 学习ebpf go设计哲学 ceph学习 学习mesh kvm虚拟化 学习MQ go编译器以及defer实现 学习go 为什么要有堆栈 汇编语言 计算机组成原理 运行时和库 Prometheus client mysql 事务 mysql 事务的隔离级别 mysql 索引 坏味道 学习分布式 学习网络 学习Linux go堆内存分配 golang 系统调用与阻塞处理 Goroutine 调度过程 重新认识cpu mosn有的没的 负载均衡泛谈 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go channel codereview gc分析 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes扩缩容 神经网络模型优化 直觉上理解深度学习 如何学习机器学习 TIDB源码分析 什么是云原生 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 共识算法 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全访问机制 jvm crash分析 Prometheus 学习 Kubernetes监控 容器日志采集 Kubernetes 控制器模型 容器狂占资源怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes类型系统 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言那些事儿 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 如何分发计算 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记 log4j学习 为什么netty比较难懂? 递归、回溯、动态规划 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 OpenTSDB 入门 spring事务小结 分布式事务 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型和jvm内存布局 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker namespace和cgroup zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 深度学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM执行 git maven/ant/gradle/make使用 再看tcp kv系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go基础 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

架构

大模型推理服务框架 模型服务化(未完成) 大模型RHLF 大模型训练 大模型推理 从Attention到Transformer k8s设备管理 LLM工具栈 ddd从理念到代码 如何应用LLM 小鼠如何驾驭大象(LLM)? 多类型负载协调员Koordinator controller-runtime细节分析 finops学习 kubevela多集群 kubevela中cue的应用 基于k8s的工作流 容器和CPU那些事儿 kubevela源码分析 数据集管理fluid 应用管理平台kubevela karmada支持crd 多集群管理 AutoML和AutoDL 特征平台 实时训练 分布式链路追踪 helm tensorflow原理——python层分析 如何学习tensorflow 数据并行——allreduce 数据并行——ps 机器学习中的python调用c 机器学习训练框架概述 embedding的原理及实践 tensornet源码分析 大模型训练和推理 X的生成——特征工程 tvm tensorflow原理——core层分析 模型演变 《深度学习推荐系统实战》笔记 keras 和 Estimator tensorflow分布式训练 分布式训练的一些问题 基于Volcano的弹性训练 图神经网络 pytorch弹性分布式训练 从混部到统一调度 从RNN到Attention pytorch分布式训练 CNN 《动手学深度学习》笔记 pytorch与线性回归 多活 volcano特性源码分析 推理服务 kubebuilder 学习 mpi 学习pytorch client-go学习 tensorflow学习 提高gpu 利用率 GPU与容器的结合 GPU入门 AI云平台梳理 tf-operator源码分析 k8s批处理调度/Job调度 喜马拉雅容器化实践 Kubernetes 实践 学习rpc BFF openkruise学习 可观察性和监控系统 基于Kubernetes选主及应用 《许式伟的架构课》笔记 Admission Controller 与 Admission Webhook 发布平台系统设计 k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 深入controller openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go informer源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 资源调度泛谈 业务系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 概率论 serverless 泛谈 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 架构大杂烩 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 用户认证问题 资源的分配与回收——池 消息/任务队列

标签

k8s设备管理 多类型负载协调员Koordinator controller-runtime细节分析 finops学习 kubevela多集群 kubevela中cue的应用 基于k8s的工作流 容器和CPU那些事儿 kubevela源码分析 数据集管理fluid 应用管理平台kubevela karmada支持crd 多集群管理 helm 从混部到统一调度 volcano特性源码分析 kubebuilder 学习 client-go学习 tf-operator源码分析 k8s批处理调度/Job调度 喜马拉雅容器化实践 Kubernetes 实践 openkruise学习 基于Kubernetes选主及应用 Admission Controller 与 Admission Webhook k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 深入controller openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go informer源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? Kubernetes events学习及应用 CRI 资源调度泛谈 如何学习Kubernetes 以应用为中心 kubernetes operator kubernetes扩缩容 serverless 泛谈 什么是云原生 自定义CNI IPAM docker和k8s安全访问机制 Kubernetes监控 Kubernetes 控制器模型 Kubernetes资源调度——scheduler Kubernetes类型系统 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 Kubernetes源码分析——从kubectl开始 kubernetes yaml配置 CNI——容器网络是如何打通的 当我在说PaaS时,我在说什么 《深入剖析kubernetes》笔记 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件

go堆内存分配

2020年11月22日

前言

图解 Go GCmutator 申请内存是以应用视角来看问题,我需要的是某一个 struct,某一个 slice 对应的内存,这与从操作系统中获取内存的接口(比如mmap)之间还有一个鸿沟。需要由 allocator 进行映射与转换,将以“块”来看待的内存与以“对象”来看待的内存进行映射。在现代 CPU 上,我们还要考虑内存分配本身的效率问题,应用执行期间小对象会不断地生成与销毁,如果每一次对象的分配与释放都需要与操作系统交互,那么成本是很高的。这需要在应用层设计好内存分配的多级缓存,尽量减少小对象高频创建与销毁时的锁竞争,这个问题在传统的 C/C++ 语言中已经有了解法,那就是 tcmalloc

一文彻底理解Go语言栈内存/堆内存

历史沿革

Go内存管理一文足矣内存分配一般有三种方式:静态存储区(根对象、静态变量、常量)、栈(函数中的临时局部变量)、堆(malloc、new等);一般最常讨论的是栈和堆,栈的特点可以认为是线性内存,管理简单,分配比堆上更快,栈上分配的内存一般不需要程序员关心。因为堆区是多个线程共用的,所以就需要一套机制来进行分配(考虑内存碎片、公平性、冲突解决);

  1. 内存碎片问题。将内存按照块的结构来进行划分,使用链表的方式来管理。
  2. 并发冲突问题。常见的方案是使用锁,但是锁则不可避免的带来性能问题;所以有各种各样的方案兼顾性能和碎片化以及预分配的策略来进行内存分配。

解决思路

  1. 分块
    1. 提前将内存分块
    2. 对象分配:根据对象大小,选择最合适的块返回。
  2. 缓存

简单的内存分配器

如果想在heap上分配更多的空间,只需要请求系统由低像高移动brk指针,并把对应的内存首地址返回,释放内存时,只需要向下移动brk指针即可。在Linux和unix系统中,我们这里就调用sbrk()方法来操纵brk指针:

  1. sbrk(0)获取当前brk的地址
  2. 调用sbrk(x),x为正数时,请求分配x bytes的内存空间,x为负数时,请求释放x bytes的内存空间

假设我们现在申请了两块内存,A/B,B在A的后面,如果这时候用户想将A释放,这时候brk指针在B的末尾处,那么如果简单的移动brk指针,就会对B进行破坏,所以对于A区域,我们不能直接还给操作系统,而是等B也同时被释放时再还给操作系统,同时也可以把A作为一个缓存,等下次有小于等于A区域的内存需要申请时,可以直接使用A内存,也可以将AB进行合并来统一分配。

所以将内存按照块的结构来进行划分,使用链表的方式来管理,那么除了本身用户申请的内存区域外,还需要一些额外的信息来记录块的大小、下一个块的位置,当前块是否在使用。

为了支持多线程并发访问内存,使用全局锁。到目前为止

  1. 通过加锁保证线程安全
  2. 通过链表的方式管理内存块,并解决内存复用问题。
  3. free时,首先要看下需要释放的内存是否在brk的位置,如果是,则直接还给操作系统,如果不是,标记为空闲,以后复用。

但这个内存分配器也存在几个严重的问题:

  1. 全局锁在高并发场景下会带来严重性能问题
  2. 每次从头遍历也存在一些性能问题
  3. 内存碎片问题,我们内存复用时只是简单的判断块内存是否大于需要的内存区域,如果极端情况下,我们一块空闲内存为1G,而新申请内存为1kb,那就造成严重的碎片浪费
  4. 内存释放存在问题,只会把末尾处的内存还给操作系统,中间的空闲部分则没有机会还给操作系统。

内存分配算法 TCMalloc

主要是以下几个思想:

  1. 划分内存分配粒度,先将内存区域以最小单位定义出来,然后区分对象大小分别对待。小对象分为若干类,使用对应的数据结构来管理,降低内存碎片化。
  2. 垃圾回收及预测优化:释放内存时,能够合并小内存为大内存,根据策略进行缓存,下次可以直接复用提升性能。达到一定条件释放回操作系统,避免长期占用导致内存不足。
  3. 优化多线程下的性能:针对多线程每个线程有自己独立的一段堆内存分配区。线程对这片区域可以无锁访问,提升性能。PS:就像每个线程有一个独立的栈区一样

在 TCMalloc(Thread Cache Memory alloc) 18张图解密新时代内存分配器TCMalloc基本概念

  1. Page,操作系统是按Page管理内存的,,TCMalloc也是这样,只不过TCMalloc里的Page大小与操作系统里的大小并不一定相等,而是倍数关系。
  2. Span 和 SpanList,一组连续的Page被称为Span,持有相同数量Page的Span构成一个双向链表SpanList。Span是TCMalloc中内存管理的基本单位。
  3. Object,一个Span会被按照某个大小拆分为N个Objects,同时这N个Objects构成一个FreeList

TCMalloc三层逻辑架构

  1. ThreadCache:线程缓存。 每个线程各自的Cache,一个Cache包含多个空闲内存块链表,每个链表连接的都是内存块,同一个链表上内存块的大小是相同的。
  2. CentralCache:保存的空闲内存块链表,链表的数量与ThreadCache中链表数量相同,当ThreadCache内存块不足时,可以从CentralCache取,当ThreadCache内存块多时,可以放回CentralCache。由于CentralCache是共享的,所以它的访问是要加锁的。
  3. PageHeap:保存的Span链表,当CentralCache没有内存的时,会从PageHeap取,把1个Span拆成若干内存块,添加到对应大小的链表中,当CentralCache内存多的时候,会放回PageHeap。

go的多级分配

Go 的内存分配器基于 Thread-Cache Malloc (tcmalloc) ,tcmalloc 为每个线程实现了一个本地缓存, 区分了小对象(小于 32kb)和大对象分配两种分配类型,其管理的内存单元称为 span。但与 tcmalloc 存在一定差异

  1. 比TCMalloc更加细致的划分对象等级
  2. 将TCMalloc中针对线程的缓存变更为绑定到逻辑处理器P上的缓存区域。
  3. Go 语言被设计为没有显式的内存分配与释放, 完全依靠编译器与运行时的配合来自动处理,因此也就造就了内存分配器、垃圾回收器两大组件。

我们可以将内存分配的路径与 CPU 的多级缓存作类比,这里 mcache 内部的 tiny 可以类比为 L1 cache,而 alloc 数组中的元素可以类比为 L2 cache,全局的 mheap.mcentral 结构为 L3 cache,mheap.arenas 是 L4,L4 是以页为单位将内存向下派发的,由 pageAlloc 来管理 arena 中的空闲内存。如果 L4 也没法满足我们的内存分配需求,那我们就需要向操作系统去要内存了。

在 Go 语言中,根据对象中是否有指针以及对象的大小,将内存分配过程分为三类:

  1. tiny :size < 16 bytes && has no pointer(noscan); PS:noscan 指对象里不包含指针,所以gc不需要scan它。
  2. small :has pointer(scan)   (size >= 16 bytes && size <= 32 KB);
  3. large :size > 32 KB。
     
L1 mcache.tiny tiny 从此开始
L2 mcache.alloc[] small 从此开始
L3 mcache.central 全局的
L4 mcache.arenas large 直接从此开始,以页为单位将内存向下派发的,由 pageAlloc 来管理 arena 中的空闲内存。

arenas 是 Go 向操作系统申请内存时的最小单位,每个 arena 为 64MB 大小,在内存中可以部分连续,但整体是个稀疏结构。单个 arena 会被切分成以 8KB 为单位的 page,一个或多个 page 可以组成一个 mspan,每个 mspan 可以按照 sizeclass 再划分成多个 element。同样大小的 mspan 又分为 scan 和 noscan 两种,分别对应内部有指针的 object 和内部没有指针的 object。

数据结构

普通应用程序是调用 malloc 或者 mmap,向 OS 申请内存;而 Go 程序是通过 Go 运行时申请内存,Go 运行时会向 OS 申请一大块内存,然后自己进行管理。Go 应用程序分配内存时是直接找 Go 运行时,这样 Go 运行时才能对内存空间进行跟踪,最后做好内存垃圾回收的工作。Go 运行时把这个大块内存称为 arena 区域,其中又划分为 8KB 大小页。

在 Go 的内存管理机制中,有几个重要的数据结构需要关注,分别是 mspan、heapArena、mcache、mcentral 以及 mheap。其中,mspan 和 heapArena 维护了 Go 的虚拟内存布局,而 mcache、mcentral 以及 mheap 则构成了 Go 的三层内存管理器。

  1. mheap:分配的堆,在页大小为 8KB 的粒度上进行管理。mheap 在 Go 的运行时里边是只有一个实例的全局变量。对应于 TCMalloc 中的 Page heap 结构
  2. heapArena: 可以管理一个区,这个区的大小一般为 64MB
  3. mcentral:收集了给定大小等级的所有 span,对应于 TCMalloc 中的 Central cache 结构。作用是为mcache提供切分好的mspan资源,每个spanClass对应一个级别的mcentral;
  4. mcache:为 per-P 的缓存。对应于 TCMalloc 中的 Thread cache 结构。mcache 提前从mcentral中获取mspan,后序的分配内存操作就不需要竞争锁。PS:mcentral 和 mcache 都只是 mspan 的容器。
  5. mspan:是 mheap 上管理的一连串的页 ,包含 分配对象的大小规格、占用页的数量等内容。

三级内存管理

  1. 在 Go 的三级内存管理器中,维护的对象都是小于 32KB 的小对象。对于这些小对象,Go 又将其按照大小分成了 67 个类别,称为 spanClass/sizeclass。每一个 spanClass 都用来存储固定大小的对象。
  2. class 为 0 时用来管理大于 32KB 对象的 spanClass

这些数据都是通过在 runtime.mksizeclasses.go 中计算得到的。Go 在分配的时候,是通过控制每个 spanClass 场景下的最大浪费率,来保障堆内存在 GC 时的碎片率的。

type mcache struct {
    // Tiny allocator
	tiny             uintptr    // 指向当前在使用的 16 字节内存块的地址
	tinyoffset       uintptr    // 指新分配微小对象需要的起始偏移
    tinyAllocs       uintptr    // 存放了多少微小对象

	alloc [numSpanClasses]*mspan // spans to allocate from, indexed by spanClass
}

Golang为每个线程分配了span的缓存,即mcache,每个层级的span都会在mcache中保存一份(macache包含所有规格的span),避免多线程申请内存时不断的加锁。当 mcache 没有可用空间时,从 mcentral 的 mspans 列表获取一个新的所需大小规格的 mspan。

type mcentral struct {
    lock      mutex     // 互斥锁
    spanclass spanClass // span class ID
    nonempty  mSpanList // non-empty 指还有空闲块的span列表
    empty     mSpanList // 指没有空闲块的span列表
    nmalloc uint64      // 已累计分配的对象个数

    // 每种集合都存放两个元素,用来区分集合中 mspan 是否被清理过。
    partial [2]spanSet // 包含着空闲空间的 mspan 集合
    full    [2]spanSet // 不包含空闲空间的 span 集合
}

从mcentral数据结构可见,每个mcentral对象只管理特定的class规格的span,事实上每种class都会对应一个mcentral,主要作用是为mcache提供切分好的mspan资源。

Go 使用 mheap 对象管理堆,只有一个全局变量(mheap 也是go gc 工作的地方)。持有虚拟地址空间。mheap 存储了 mcentral 的数组。这个数组包含了各个的 span 规格的 mcentral(mcentral的个数是67x2=134,也是针对有指针和无指针对象分别处理)。由于我们有各个规格的 span 的 mcentral,当一个 mcache 从 mcentral 申请 mspan 时,只需要在独立的 mcentral 级别中使用锁,其它任何 mcache 在同一时间申请不同大小规格的 mspan 互不影响。

当 mcentral 列表为空时,mcentral 从 mheap 获取一系列页用于需要的大小规格的 span。

type mheap struct {
    lock      mutex
    spans []*mspan
    bitmap        uintptr 	//指向bitmap首地址,bitmap是从高地址向低地址增长的
    arena_start   uintptr		//指示arena区首地址
    arena_used    uintptr		//指示arena区已使用地址位置
    central [67*2]struct {
        mcentral mcentral
        pad      [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
    }
}

虚拟内存布局 ==> 从对象到页

操作系统是按page管理内存的,同样Go语言也是也是按page管理内存的,1page为8KB,保证了和操作系统一致。page由 page allocator 管理,pageAlloc在 Go 语言中迭代了多个版本,从简单的 freelist 结构,到 treap 结构,再到现在最新版本的 radix 结构,它的查找时间复杂度也从 O(N) -> O(log(n)) -> O(1)。

从os 拿到的页内存按块管理,空闲块一般由空闲链表来管理:维护一个类似链表的数据结构。当用户程序申请内存时,空闲链表分配器会依次遍历空闲的内存块,找到足够大的内存,然后申请新的资源并修改链表。因为分配内存时需要遍历链表,所以它的时间复杂度就是 O(n),为了提高效率,将内存分割成多个链表,每个链表中的内存块大小相同(不同链表不同),申请内存时先找到满足条件的链表,再从链表中选择合适的内存块,减少了需要遍历的内存块数量

Go 的内存管理基本单元是 mspan,每个 mspan 中会维护着一块连续的虚拟内存空间,内存的起始地址由 startAddr 来记录。每个 mspan 存储的内存空间大小都是内存页的整数倍,由 npages 来保存。Go 的内存页大小设置的是 8KB。

type mspan struct {
    next *mspan             // next span in list, or nil if none
    prev *mspan             // previous span in list, or nil if none
    startAddr uintptr       // address of first byte of span aka s.base()
    npages    uintptr       // number of pages in span
    spanclass   spanClass     // size class and noscan (uint8)
    ...
    allocBits  *gcBits          // 从 mspan 里分配 element ,就是将 mspan 对应 allocBits 中的对应 bit 位置一
	gcmarkBits *gcBits          // 实现 span 的颜色标记
}

9张图轻松吃透Go内存管理单元Go是按页page8KB为最小单位分配内存的吗?当然不是,如果这样的话会导致内存使用率不高。Go内存管理单元mspan通常由N个且连续的page组成,会把mspan再拆解为更小粒度的单位object。object和object之间构成一个链表(FreeList),object的具体大小由sizeclass决定,mspan结构体上维护一个sizeclass的字段(实际叫spanclass)。PS:mspan通常由N个且连续的page组成,所以可以视为一段连续内存,内部又按统一大小的object 分配,所以可以认为:mspan是 npages 整存,object 零取。

所谓申请内存,是申请 size 大小的内存,参数是size。 ThreadCache 和 TransferCacheManager 维护了 特定几个大小的 object,要做的事情就是个根据size 快速从合适的链表选择空闲内存块/object。

mspan 关键字段

  1. next、prev、list, mspan之间可以构成链表
  2. startAddr,mspan内存的开始位置,N个连续page内存的开始位置
  3. npages,mspan由几page组成
  4. freeindex,空闲object链表的开始位置
  5. nelems,一共有多少个object
  6. spanclass,决定object的大小、以及当前mspan是否需要垃圾回收扫描
  7. allocBits,从 mspan 里分配 element 时,我们只要将 mspan 中对应该 element 位置的 bit 位置一就可以了,其实就是将 mspan 对应 allocBits 中的对应 bit 位置一。

heapArena 的结构相当于 Go 的一个内存块,在 x86-64 架构下的 Linux 系统上,一个 heapArena 维护的内存空间大小是 64MB。该结构中存放了 ArenaSize/PageSize 长度的 mspan 数组,heapArena 结构的 spans 变量,用来精确管理每一个内存页。而整个 arena 内存空间的基址则存放在 zeroedBase 中。heapArena 结构的部分定义如下:

type heapArena struct {
    ...
    spans [pagesPerArena]*mspan
    zeroedBase uintptr
}

Go 整体的虚拟内存布局是存放在 mheap 中的一个 heapArena 的二维数组。定义如下:

type mheap struct {
    ...
    arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
}

对于 x86-64 架构下的 Linux 系统,第一维数组长度是 1,而第二维数组长度是 4194304。这样每个 heapArena 管理的内存大小是 64MB,由此可以算出 Go 的整个堆空间最多可以管理 256TB 的大小。

分配过程

分配内存始终是从 P 上运行一个协程开始的

  1. 根据分配对象的大小,选用不同的结构做分配。包括 3 种情况:
    1. 小于 16B 的用 mcache 中的 tiny 分配器分配;
    2. 大于 32KB 的对象直接使用堆区分配;
    3. 16B 和 32KB 之间的对象用 mspan 分配。
  2. 现在我们假定分配对象大小在 16B 和 32KB 之间。在 mcache 中找到合适的 mspan 结构,如果找到了就直接用它给对象分配内存。
  3. 我们这里假定此时没有在 mcache 中找到合适的 mspan。需要到 mcentral 结构中查找到一个 mspan 结构并返回。虽然 mcentral 结构对 mspan 的大小和是否空闲进行了分类管理,但是它对所有的 P 都是共享的,所以每个 P 访问 mcentral 结构都要加锁。
  4. 假定 Go 运行时在进行了一些扫描回收操作之后,在 mcentral 结构还是没有找到合适的 mspan。Go 运行时就会建立一个新的 mspan,并找到 heapArea 分配相应的页面,把页面地址和数量写入 mspan 中。然后,把 mspan 插入 mcentral 结构中,返回的同时将 mspan 插入 mcache 中。最后用这个新的 mspan 分配对象,返回对象地址。

源码分析

字节跳动 Go 语言面试高频题 01:内存分配

分配路径:g ==> m ==> p ==> mcache ==> mspan ==> memory block ==> return pointer.

type p struct {
	id          int32
	mcache      *mcache
	pcache      pageCache 
	...
}

go 内存分配器细节补充

// go:noinline
func smallAllocation() *smallStruct {
    return &smallStruct{}
}
// &smallStruct{} 对应汇编代码
LEAQ    type."".smallStruct(SB), AX
MOVQ    AX, (SP)
PCDATA  $1, $0
CALL    runtime.newobject(SB)

堆上所有的对象都会通过调用 runtime.newobject 函数分配内存,runtime.newobject 就是内存分配的核心入口,该函数会调用 runtime.mallocgc 分配指定大小的内存空间。


if size <= maxSmallSize {
    if noscan && size < maxTinySize {
      // 微小对象分配   ==> 会被放到 spanClass 为 2 的 mspan 中
    } else {
      // 小对象分配     ==> 依次向三级内存管理器请求内存
    }
} else {
  // 大对象分配 ==> Go 并不会走上述的三次内存管理器,而是直接通过调用 mcache.allocLarge 来分配大内存。
}
// src/runtime/malloc.go
func newobject(typ *_type) unsafe.Pointer {
	return mallocgc(typ.size, typ, true)
}
// Allocate an object of size bytes.
// Small objects are allocated from the per-P cache's free lists.
// Large objects (> 32 kB) are allocated straight from the heap.
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    ...
    mp := acquirem()
    var c *mcache
	if mp.p != 0 {
		c = mp.p.ptr().mcache       // 获取当前的 G所属的P
	} else {
		c = mcache0
    }
    var span *mspan
    if size <= maxSmallSize {
        if noscan && size < maxTinySize {   // Tiny allocator.
            ...
            span = c.alloc[tinySpanClass]
            v := nextFreeFast(span)
            x = unsafe.Pointer(v)
            ...
        }else{
            ...
            span = c.alloc[spc]
            v := nextFreeFast(span)
            x = unsafe.Pointer(v)
            ...
        }
    }else{
        ...
        span = largeAlloc(size, needzero, noscan)
        x = unsafe.Pointer(span.base())
        ...
    }
}

逃逸分析

逃逸分析:分析代码中指针的作用域:指针在何处可以访问。大致思路

  1. 从对象分配处出发,沿着控制流,观察对象的数据流
  2. 若发现指针p 当前作用域s:
    1. 作为参数传递给其它函数
    2. 传递给全局变量
    3. 传递给其它goroutine
    4. 传递给已逃逸的指针指向的对象
  3. 则指针p 指向的对象地址逃逸出s,反之则没有逃逸出s。

Go 垃圾回收器指南在深入研究GC之前,让我们首先讨论一下不需要由GC管理的内存。例如,存储在局部变量中的非指针Go语言的值可能根本不会被Go语言的GC管理,Go语言会安排内存的分配,并将其绑定到创建它的词法作用域中。一般来说,这比依赖GC更有效率,因为Go语言编译器能够预先确定何时释放内存,并发出清理内存的机器指令。通常,我们把这种为Go语言的值分配内存的方式称为“栈分配”,因为空间存储在goroutine栈中。如果Go语言的值不能以这种方式分配内存,则Go语言编译器无法确定它的生存期,那么这些值就被称为“逃逸到堆”(所有go 有一个词儿叫逃逸分析)。“堆”可以被认为是内存分配的一个大杂烩,Go语言的值需要被放置在堆的某个地方。在堆上分配内存的操作通常称为“动态内存分配”,因为编译器和运行库都很少会对如何使用内存以及何时可以清理内存做出假设。这就是GC的用武之地:它是一个专门标识和清理动态内存分配的系统。Go语言的值需要逃逸到堆中的原因有很多。

  1. 一个原因可能是其大小是动态确定的。例如,考虑一个切片的支持数组,它的初始大小由一个变量而不是一个常量确定。
  2. 请注意,逃逸到堆也必须是可传递的:如果一个Go值的引用被写入到另一个已经被确定为逃逸的Go值中,那么这个值也必须逃逸。

传统意义上的栈被 Go 的运行时霸占,不开放给用户态代码;而传统意义上的堆内存,又被 Go 运行时划分为了两个部分,

  1. 一个是 Go 运行时自身所需的堆内存,即堆外内存;
  2. 另一部分则用于 Go 用户态代码所使用的堆内存,也叫做 Go 堆。 Go 堆负责了用户态对象的存放以及 goroutine 的执行栈。

有关go内存是在堆上分配的,还是在栈上分配的,这个是在编译过程中,通过逃逸分析来确定的,其主体思想是(实际更复杂):假设有变量v,及指向v的指针p,如果p的生命周期大于v的生命周期,则v的内存要在堆上分配。我们可以使用 go build -gcflags="-m" 来观察逃逸分析的结果

package main
func main() {
    var m = make([]int, 10240)
    println(m[0])
}

$ go build -gcflags="-m" xx.go
xx.go: can inline main
xx.go: make([]int, 10240) escapes to heap

若对象被分配在栈上,它的管理成本就比较低,我们通过挪动栈顶寄存器就可以实现对象的分配和释放。若对象被分配在堆上,我们就要经历层层的内存申请过程。但这些流程对用户都是透明的。一切抽象皆有成本,这个成本要么花在编译期,要么花在运行期。mutator需要在堆上申请内存时,会由编译器帮程序员自动调用 runtime.newobject,这时 allocator 会使用 mmap 这个系统调用从操作系统中申请内存,若 allocator 发现之前申请的内存还有富余,会从本地预先分配的数据结构中划分出一块内存,并把它以指针的形式返回给应用。在内存分配的过程中,allocator 要负责维护内存管理对应的数据结构。而 collector 要扫描的就是 allocator 管理的这些数据结构,应用不再使用的部分便应该被回收,通过 madvise 这个系统调用返还给操作系统。

内存模型/happen-before

Go 开发要了解的 1 个内存模型细节The Go memory model specifies the conditions under which reads of a variable in one goroutine can be guaranteed to observe values produced by writes to the same variable in a different goroutine. Go 内存模型规定了:“在一个 goroutine 中读取一个变量时,可以保证观察到不同 goroutine 中对同一变量的写入所产生的值” 的条件。PS: 也是约定了一些规则,与java类似

其它

go 的对象和 java 对象不同,go 对象没有对象头,对象的内存表示 就是各个字段依次排列(加上对齐),事实上 Go 可以用 unsafe 包去直接操作内存,当然这是不推荐的。垃圾回收用位图表示内存状况。反射取的参数是 interface{}interface{} 里会持有类型,不需要对象头。