2024年11月

LiteFlow真的是相见恨晚啊,之前做过的很多系统,都会用各种if else,switch这些来解决不同业务方提出的问题,有时候还要“切一个分支”来搞这些额外的事情,把代码搞得一团糟,毫无可读性而言。如何打破僵局?LiteFlow为解耦逻辑而生,为编排而生,在使用LiteFlow之后,你会发现打造一个低耦合,灵活的系统会变得易如反掌!

另外, LiteFlow 和 Activiti 们并不是同一个东西,而是面向不同的使用场景和需求。LiteFlow 更加轻量灵活,适合需要简单流程管理和动态配置的场景;而 Activiti 则是一个全面的 BPM 引擎,适合需要复杂业务流程管理和任务管理的场景。根据具体业务需求,可以选择合适的工具来实现流程编排。

背景

之前做过一个数据分发系统,需要消费kafka的数据,下游有不同的业务,每个业务可能有共同的地方,也有不同的地方,在经过各类的处理之后,最后数据分发到下游里面去。为了简化代码方便理解,我们定义4个Handler(A、B、C、D),然后有3个不同的业务,需要经过不同的Handler,整个流程如下。

image-20241108000137572

如果要在一个代码实现上诉功能,我们第一反应可能是
责任链设计模式
,每个业务一条链路,在Spring中,类似下面的代码:

public abstract class Handler {
    abstract void handler(Request request);
}

@Component
@Slf4j
public class HandlerA extends Handler{
    @Override
    public void handler(Request request) {
        log.info("处理器1");
    }
}

@Component
@Slf4j
public class HandlerB extends Handler {
    @Override
    public void handler(Request request) {
        log.info("处理器2");
    }
}

@Component
@Slf4j
public class HandlerC extends Handler{
    @Override
    public void handler(Request request) {
        log.info("处理器3");
    }
}
@Component
@Slf4j
public class HandlerD extends Handler{
    @Override
    public void handler(Request request) {
        log.info("处理器4");
    }
}

//然后我们定义一个枚举类,用来配置不同业务需要经历过的处理器。
public enum HandleBuz {
    Business_1(HandlerA,HandlerB),
    Business_2(HandlerB,HandlerC),
    Business_3(HandlerA,HandlerD);
    public final Class<? extends Handler>[] processors;
    public HandleBuz(Class<? extends Handler>[] processors){
        this.processors=processors;
    }    
    public void handle(){
        for (Handler handler : processors) {
            handler.handler(xxx);
        }
    }

}

通过配置责任链,可以灵活地组合处理对象,实现不同的处理流程,并且可以在运行时动态地改变处理的顺序,由于责任链模式遵循
开闭原则
,新的处理者可以随时被加入到责任链中,不需要修改已有代码,提供了良好的扩展性。但实际上面对各种需求的时候,没法做到完全的解耦,比如
对于HandlerA,如果业务1和业务2都有定制化的需求(来自产品提的临时或长期需求)
,此时是应该再HandlerA中用if else解决,还是再额外开个HandlerA_1和HandlerA_2。这类特性需求会非常多,最终把代码可读性变得越来越低。

一、为什么需要流程编排

LiteFlow由Baidu开源,专注于逻辑驱动流程编排,通过组件化方式快速构建和执行业务流程,有效解耦复杂业务逻辑。它以其轻量级、快速、稳定且可编排的特性,在业务流程管理、规则引擎、工作流、订单处理、数据处理、微服务编排以及智能化流程管理等领域都有广泛的应用前景。

img

二、它可以解决什么问题

对大部分不断迭代的代码来说,历史遗留的代码加上需要面对各类各样的需求,代码会变得越来越难维护,甚至变成屎山。我们想着不断的去进行解耦,不断的去进行切割拆分,还要兼顾新需求,就怕蝴蝶效应导致大故障,liteflow能帮我们在解耦上更加清晰一点。
(1)复杂业务流程编排和管理
在一些应用场景中,业务逻辑往往非常复杂,涉及多个步骤的执行,并且这些步骤之间具有复杂的依赖关系。LiteFlow 可以帮助开发者通过配置和代码相结合的方式定义和管理这些流程。
(2)流程动态配置
LiteFlow 允许通过配置文件或者数据库动态修改流程,而无需修改代码。这意味着可以根据不同的业务需求快速调整并发布新的流程,而不需要重新部署应用。
(3)流程节点的复用和解耦
在使用 LiteFlow 时,每个业务步骤都可以定义为一个独立的节点(Node),这些节点可以独立开发、测试和维护,并且可以在多个流程中复用。通过这种方式,可以实现业务逻辑的复用和解耦,提高代码的可维护性。
(4)节点状态和错误处理
LiteFlow 提供了丰富的节点状态管理和错误处理机制,允许开发者在流程执行过程中捕获和处理异常,从而确保系统的稳定性和健壮性。
(5) 高扩展性和自定义能力
LiteFlow 具有高度的扩展性,开发者可以根据自身业务的特殊需求定制节点、组件和插件,从而满足复杂场景的要求。

以下是一些实际使用 LiteFlow 的示例场景:
(1)
订单处理系统
:在电商系统中,订单处理涉及多个步骤,如库存检查、支付处理、订单确认和发货等。LiteFlow 可以帮助将这些步骤分开独立实现,然后通过流程引擎编排执行。
(2)
审批流程
:在企业中,审批流程通常包括多个节点(如申请、审批、复核、归档等),并且这些节点之间可能有条件和依赖关系。LiteFlow 可以帮助动态配置和管理这些流程,提高审批效率。
(3)
营销活动
:在一些营销活动中,不同的活动环节和逻辑可能会因用户行为和外部条件而变化。LiteFlow 可以帮助实现灵活的活动规则配置和执行。

三、LiteFlow改造之后

首先定义并实现一些组件,确保SpringBoot会扫描到这些组件并注册进上下文。

@Slf4j
@LiteflowComponent("a")
public class HandlerA extends NodeComponent {
    @Override
    public void process() throws Exception {
        Customizer contextBean = this.getContextBean(Customizer.class);
    }
}

@Slf4j
@LiteflowComponent("b")
public class HandlerB extends NodeComponent {
    @Override
    public void process() throws Exception {
        Customizer contextBean = this.getContextBean(Customizer.class);
    }
}

@Slf4j
@LiteflowComponent("c")
public class HandlerC extends NodeComponent {
    @Override
    public void process() throws Exception {
        Customizer contextBean = this.getContextBean(Customizer.class);
    }
}

@Slf4j
@LiteflowComponent("d")
public class HandlerD extends NodeComponent {
    @Override
    public void process() throws Exception {
        Customizer contextBean = this.getContextBean(Customizer.class);
    }
}

同时,你得在resources下的
config/flow.el.xml
中定义规则:

<?xml version="1.0" encoding="UTF-8"?>
<flow>
    <chain name="chain1">
        THEN(
        a,b
        );
    </chain>
    <chain name="chain2">
        THEN(
        b,c
        );
    </chain>
    <chain name="chain3">
        THEN(
        a,d
        );
    </chain>
</flow>

最后,在消费kafka的时候,先定义一个ruleChainMap,用来判断根据唯一的id(业务id或者消息id)来判断走哪条chain、哪个组件等,甚至可以定义方法级别的组件。

    private Map<Integer, String> ruleChainMap = new HashMap<>();
    @Resource
    private FlowExecutor flowExecutor;

    @PostConstruct
    private void init() {
        ruleChainMap.put(1, "业务1");
        ruleChainMap.put(2, "业务2");
        ruleChainMap.put(3, "业务3");
    }

    @KafkaListener(topics = "xxxx")
    public void common(List<ConsumerRecord<String, String>> records) {
        for (ConsumerRecord<String, String> record : records) {
            ...
            String chainName = ruleChainMap.get("唯一id(可以是record里的,也可以全局定义的id)");
            LiteflowResponse response = flowExecutor.execute2Resp(chainName, xxx, xxx, new TempContext());
        }
    }

由于篇幅的关系,这里不再讲解怎么传递上下文的关系,可以自己去官网研究一下。另外,上面的例子因为是简化之后的,如果你觉得不够形象,可以看看下面的实际业务。这个如果不使用liteflow,可能就得在主流程代码里增加各种if else,甚至后续改了一小块也不知道对别的地方有没有影响。

image-20241108000231371

总结

后续,如果面对产品经理“来自大领导的一个想法,我不知道后续还会不会一直做下去,反正先做了再说”这类需求,就可以自己定义一个LiteFlow的组件,既不污染主流程的代码,后续下线了删掉即可,赏心悦目。

文档&参考

1.【腾讯文档】业务处理复杂
https://docs.qq.com/flowchart/DZVFURmhCb0JFUHFD
2.【腾讯文档】业务处理复杂2
https://docs.qq.com/flowchart/DZXVOaUV5VGRtc3ZD
3.
一文搞懂设计模式—责任链模式
4.
LiteFlow官网

.NET Conf 2024
是一个面向.NET生态系统社区的大型活动,将于2024年11月12日至14日举行。该活动将通过
YouTube
和Twitch进行现场直播,并在
dotnetconf.net
网站上提供直播流。这是一个免费的虚拟事件,旨在为初学者和学习者提供关于AI、Web开发、移动开发和游戏开发等方面的教育内容。

.NET Conf 以 .NET 团队成员和领导者的主题演讲开始,他们向您展示了 .NET 9 版本最酷的新功能。然后,您将享受一整天的现场演示,其中包括一些构建 .NET 9 的人,他们将深入探讨 .NET Aspire、AI 构建基块、C#、ASP.NET Core、Blazor、.NET MAUI 等的功能。

该活动是现场直播的,因此请务必在活动期间通过提问来与演讲者互动。我们的活动版主将寻找您的问题和评论,以便在现场活动期间分享。有关详细的议程和会议时间,请访问
https://www.dotnetconf.net/agenda
的官方时间表。

活动亮点包括:

  1. .NET 9 的正式发布
    :第一天将正式推出 .NET 9,由 .NET 团队主持的会议将深入介绍新版本的特点和功能。

  2. AI 和 .NET
    :活动还将探索 .NET 开发者如何利用 AI 库和功能构建更智能的应用程序、提高生产力,并提供更好的用户体验。

  3. 社区参与和互动
    :.NET Conf 2024 是一个充满知识、创造力和社区参与的活动,旨在提升开发体验。

  4. 内容记录和分享
    :所有内容都将被录制,并在活动结束后在 YouTube 频道上提供,以便错过直播的人可以观看。

此外,.NET Conf 2024 还设有学生区,这是一个面向初学者的虚拟活动,专家们将在活动中教授如何使用C#和.NET构建令人惊叹的项目。学生区会议将在日本时间11月19日凌晨1点和下午1点通过.NET的YouTube频道举行。

在过去的几个月里,我们的社区成员们一直忙于筹备即将于12月举行的第五届 .NET 中国峰会。我们非常高兴地宣布,活动的官网设计与开发工作正在如火如荼地进行中。在国庆节后的第一天,我们正式启动了活动的序幕,确定了会议的地点和时间,并开始了宣传工作,期待与更多的开发者共同参与这一盛会。

.NET Conf China 2024 是您探索 .NET 生态系统前沿进展的绝佳机会。随着 .NET 9 的发布,我们将展示一系列云原生改进和智能应用程序开发的新功能。这些新特性旨在帮助开发者提高生产力、简化部署流程,并加速人工智能的集成,让开发者能够更高效地构建现代化应用。无论您是经验丰富的开发者,还是刚刚开始您的 .NET 之旅的初学者,本次会议都将为您提供丰富的学习与交流机会。

大会将围绕“
.NET x AI
”这一议程展开,汇聚了众多行业专家和资深开发者,涵盖了 .NET 领域的最新技术动态。无论是核心框架的深入解析,还是跨平台应用开发的实战经验,参会者都能在这里找到丰富的内容与灵感。我们将邀请多位知名讲者分享他们在实际项目中遇到的挑战与解决方案,帮助开发者们更好地理解和应用 .NET 技术。

image

image

image

作者:来自 vivo 互联网存储团队- Wang Yuzhi

本文以一次线上故障为基础介绍了使用 glibc 进行内存管理可能碰到问题,进而对库中内存分配与释放机制进行分析,最后提供了相应问题的解决方案。

一、引言

内存对象的分配与释放一直是后端开发人员代码设计中需要考虑的问题,考虑不周极易造成内存泄漏、内存访问越界等问题。在发生内存异常后,开发人员往往花费大量时间排查用户管理层代码,而忽视了C运行时,库层和操作系统层本身的实现也可能会带来内存问题。本文先以一次线上内存事故引出问题,再逐步介绍 glibc 库的内存布局设计、内存分配、释放逻辑,最后给出相应的解决方案。

二、内存告警事件

在一次线上运维过程中发现服务出现内存告警。

【监控系统-自定义监控-告警-持续告警】

检测规则: xxx内存使用率监测:一般异常(>4096)

集群id:xxx

集群名称: xxxxxx

异常对象(当前值): xx.xx.xx.xx-xxxxxxx(11335)

开始时间: 2023-08-10 17:10:30

告警时间: 2023-08-10 18:20:32

持续时间: 1h10m2s

异常比例: 2.1918 (8/365)

异常级别: 一般

备注:-

随即查看服务相关监控,判断是业务流量激增带来的内存短时间增高,或是发生了内存泄漏。

图片

图片

通过查看 OPS 和服务自身统计的内存监控,发现在告警时间内存在业务流量突增现象,但是内存已经下降到正常值了。然而告警持续到了18:20依然没有恢复,跟监控表现不符,登录机器后发现实例的内存并没有恢复,随即怀疑用户层发生内存泄漏。

经过分析,由于内存统计代码每次调用 new、delete 之后才会对统计值进行增减,而监控中服务统计内存已经下降,说明已经正常调用 delete 进行内存释放,而操作系统层面发现内存依然居高不下,怀疑使用的c运行库 glibc 存在内存释放问题。

三、glibc 内存管理机制

3.1 glibc 简介

glibc 全称为 GUN C Library,是一个开源的标准C库,其对操作系统相关调用进行了封装,提供包括数学、字符串、文件 I/O、内存管理、多线程等方面标准函数和系统调用接口供用户使用。

3.2 内存管理布局

以 Linux 内核 v2.6.7 之后的32位模式下的虚拟内存布局方式为例:

图片

  1. Kernel Space(内核空间)— 存储内核和驱动程序的代码和数据;
  2. Stack(栈区)— 存储程序执行期间的本地变量和函数的参数,从高地址向低地址生长;

  3. Memory Mapping Segment(内存映射区)— 简称为 mmap,用来文件或其他对象映射进内存;

  4. Heap(堆区)— 动态内存分配区域,通过 malloc、new、free 和 delete 等函数管理;

  5. BSS segment(未初始化变量区)— 存储未被初始化的全局变量和静态变量;

  6. DATA segment(数据区)— 存储在源代码中有预定义值的全局变量和静态变量;

  7. TEXT segment(代码区)— 存储只读的程序执行代码,即机器指令。

其中 Heap 和 Mmap 区域是可以提供给用户程序使用的虚拟内存空间。

Heap 操作

操作系统提供了 brk() 函数,c运行时库提供了 sbrk() 函数从 Heap 中申请内存,函数声明如下:

int brk(void *addr);
void *sbrk(intptr_t increment);
  • brk() 通过设置进程堆的结束地址进行内存分配与释放,即可以一次性的分配或释放一整段连续的内存空间。比较适合于一次性分配大块内存的情况,如果设置的结束地址过大或过小会造成内存碎片或内存浪费的问题。

  • sbrk 函数通过传入的 increment 参数决定增加或减少堆空间的大小,可以动态的多次分配或释放空间达到需要多少内存就申请多少内存的效果,有效避免了内存碎片和浪费问题。

Mmap 操作

在 Linux 中提供了 mmap() 和 munmap() 函数操作虚拟内存空间,函数声明如下:

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

其中 mmap 能够将文件或者其他对象映射进内存,munmap 能够删除特定地址区域的内存映射。

3.3 内存分配器

开源社区公开了很多现成的内存分配器,包括 dlmalloc、ptmalloc、jemalloc、tcmalloc......,由于 glibc 用的是 ptmalloc 所以本文只对该内存分配器进行介绍。

3.3.1 Arena(分配区)

堆管理结构如下所示:

struct malloc_state {
 mutex_t mutex;                 /* Serialize access. */
 int flags;                       /* Flags (formerly in max_fast). */
 #if THREAD_STATS
 /* Statistics for locking. Only used if THREAD_STATS is defined. */
 long stat_lock_direct, stat_lock_loop, stat_lock_wait;
 #endif
 mfastbinptr fastbins[NFASTBINS];    /* Fastbins */
 mchunkptr top;
 mchunkptr last_remainder;
 mchunkptr bins[NBINS * 2];
 unsigned int binmap[BINMAPSIZE];   /* Bitmap of bins */
 struct malloc_state *next;           /* Linked list */
 INTERNAL_SIZE_T system_mem;
 INTERNAL_SIZE_T max_system_mem;
 };

ptmalloc 对进程内存是通过一个个的分配区进行管理的,而分配区分为主分配区(arena)和非主分配区(narena),两者区别在于主分配区中可以使用 sbrk 和 mmap 向操作系统申请内存,而非主分配区只能通过 mmap 申请内存。

图片

对于一个进程,只有一个主分配区和若干个非主分配区,主分配区只能由第一个线程来创建持有,其和非主分配区由环形链表的形式相互连接,整个分配区中通过变量互斥锁支持多线程访问。

当一个线程调用 malloc 申请内存时,该线程先查看线程私有变量中是否已经存在一个分配区。如果存在,则对该分配区加锁,加锁成功的话就用该分配区进行内存分配;失败的话则搜索环形链表找一个未加锁的分配区。如果所有分配区都已经加锁,那么 malloc 会开辟一个新的分配区加入环形链表并加锁,用它来分配内存。释放操作同样需要获得锁才能进行。

3.3.2 chunk

ptmalloc 通过 malloc_chunk 来管理内存,定义如下:

struct malloc_chunk { 
  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */ 
  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */ 
   
  struct malloc_chunk* fd;           /* double links -- used only if free. */ 
  struct malloc_chunk* bk; 
   
  /* Only used for large blocks: pointer to next larger size.  */ 
  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */ 
  struct malloc_chunk* bk_nextsize;
};
  • prev_size:存储前一个 chunk 的大小。如果前一个 chunk 没有被使用,则 prev_size 的值表示前一个 chunk 的大小,如果前一 chunk 已被使用,则 prev_size 的值没有意义。

  • size:表示当前 chunk 的大小,包括所请求的有效数据大小,以及堆块头部和尾部的管理信息等附加信息的大小。

  • fd 和 bk:表示 chunk 在空闲链表中的前一个和后一个堆块的指针。如果该 chunk 被占用,则这两个指针没有意义。

  • fd_nextsize 和 bk_nextsize:表示同一空闲链表上下一个堆块的指针。fd_nextsize 指向下一个比当前 chunk 大小大的第一个空闲 chunk , bk_nextszie 指向前一个比当前 chunk 大小小的第一个空闲 chunk,增加这两个字段可以加快遍历空闲 chunk ,并查找满足需要的空闲 chunk 。

使用该数据结构能够更快的在链表中查找到空闲 chunk 并分配。

3.3.3 空闲链表(bins)

在 ptmalloc 中,会将大小相似的 chunk 链接起来,叫做空闲链表(bins),总共有128个 bin 供 ptmalloc 使用。用户调用 free 函数释放内存的时候,ptmalloc 并不会立即将其归还操作系统,而是将其放入 bins 中,这样下次再调用 malloc 函数申请内存的时候,就会从 bins 中取出一块返回,这样就避免了频繁调用系统调用函数,从而降低内存分配的开销。

在 ptmalloc 中,bin主要分为以下四种:

  • fast bin

  • unsorted bin

  • small bin

  • large bin

其中根据 bin 的分类,可以分为 fast bin 和 bins,而 bins 又可以分为 unsorted bin、small bin 以及 large bin 。

图片

  • fast bin

程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后,也许马上就会有另一个小块内存的请求,这样分配器又需要从大的空闲内存中切分出一块,这样无疑是比较低效的,故而, malloc 中在分配过程中引入了 fast bins 。

fast bin 总共有10个,本质上就是10个单链表,每个 fast bin 中所包含的 chunk size 以8字节逐渐递增,即如果第一个 fast bin 中 chunk size 均为16个字节,第二个 fast bin 的 chunk size 为24字节,以此类推,最后一个 fast bin 的 chunk size 为80字节。值得注意的是 fast bin 中 chunk 释放并不会与相邻的空闲 chunk 合并,这是由于 fast bin 设计的初衷就是小内存的快速分配和释放,因此系统将属于 fast bin 的 chunk 的P(未使用标志位)总是设置为1,这样即使当 fast bin 中有某个 chunk 同一个 free chunk 相邻的时候,系统也不会进行自动合并操作。

malloc 操作

在 malloc 申请内存的时候,如果申请的内存大小范围在fast bin 以内,则先在 fast bin 中进行查找,如果 fast bin 中存在空闲 chunk 则返回。否则依次从 small bin、unsorted bin、large bin 中进行查找。

free 操作

先通过 chunksize 函数根据传入的地址指针获取该指针对应的 chunk 的大小;然后根据这个 chunk 大小获取该 chunk 所属的 fast bin,然后再将此 chunk 添加到该 fast bin 的链尾。

  • unsorted bin

是 bins 的缓冲区,顾名思义,unsorted bin 中的 chunk 无序,这种设计能够让 glibc 的 malloc 机制有第二次机会重新利用最近释放的 chunk 从而加快内存分配的时间。

与 fast bin 不同,unsorted bin 采用的是 FIFO 的方式。

malloc 操作

当需要的内存大小大于 fast bin 的最大大小,则先在 unsorted 中寻找,如果找到了合适的 chunk 则直接返回,否则继续在 small bin 和l arge bin中搜索。

free 操作

当释放的内存大小大于fast bin的最大大小,则将释放的 chunk 写入 unsorted bin。

  • small bin

大小小于512字节的 chunk 被称为 small chunk,而保存 small chunks 的 bin 被称为 small bin。62个 small bin 中,每个相邻的的 small bin 之间相差8字节,同一个 small bin 中的 chunk 拥有相同大小。

small bin 指向的是包含空闲区块的双向循环链表。内存分配和释放逻辑如下:

malloc 操作

当需要的内存不存在于 fast bin 和 unsorted bin 中,并且大小小于512字节,则在 small bin 中进行查找,如果找到了合适的 chunk 则直接返回。

free 操作

free 一个 chunk 时会检查该 chunk 相邻的 chunk 是否空闲,如果空闲则需要先合并,然后将合并的 chunk 先从所属的链表中删除然后合并成一个新的 chunk,新的 chunk 会被添加在 unsorted bin 链表的前端。

  • large bin

大小大于等于512字节的 chunk 被称为 large chunk,而保存 large chunks 的 bin 被称为 large bin。large bins 中每一个 bin 分别包含了一个给定范围内的 chunk,其中的 chunk 按大小递减排序,大小相同则按照最近使用时间排列。63 large bin 中的每一个都与 small bin 的操作方式大致相同,但不是存储固定大小的块,而是存储大小范围内的块。每个 large bin 的大小范围都设计为不与 small bin  的块大小或其他large bin 的范围重叠。

malloc 操作

首先确定用户请求的大小属于哪一个 large bin,然后判断该 large bin 中最大的 chunk 的 size 是否大于用户请求的 size。如果大于,就从尾开始遍历该 large bin,找到第一个 size 相等或接近的 chunk,分配给用户。如果该 chunk 大于用户请求的 size 的话,就将该 chunk 拆分为两个 chunk:前者返回给用户,且 size 等同于用户请求的 size;剩余的部分做为一个新的 chunk 添加到 unsorted bin 中。

free 操作

large bin 的 fee 操作与 small bin 一致,此处不再赘述。

3.3.4 特殊 chunk

  • top chunk

top chunk 是堆最上面的一段空间,它不属于任何 bin,当所有的 bin 都无法满足分配要求时,就要从这块区域里来分配,分配的空间返回给用户,剩余部分形成新的 top chunk,如果 top chunk 的空间也不满足用户的请求,就要使用 brk 或者 mmap 来向系统申请更多的堆空间(主分配区使用 brk、sbrk,非主分配区使用 mmap)。

  • mmaped chunk

当分配的内存非常大(大于分配阀值,默认128K)的时候需要被 mmap 映射,则会放到 mmaped chunk 上,释放 mmaped chunk 上的内存的时候会将内存直接交还给操作系统。(chunk 中的M标志位置1)

  • last remainder chunk

如果用户申请的 size 属于 small bin 的,但是又不能精确匹配的情况下,这时候采用最佳匹配(比如申请128字节,但是对应的bin是空,只有256字节的 bin 非空,这时候就要从256字节的 bin 上分配),这样会 split chunk 成两部分,一部分返给用户,另一部分形成 last remainder chunk,插入到 unsorted bin 中。

3.3.5 hunk 的合并与切分

  • 合并

当 chunk 释放时,如果前后两个相邻的 chunk 均空闲,则会与前后两个相邻 chunk 合并,随后将合并结果放入 unsorted bin 中。

  • 切分

当需要分配的内存小于待分配的 chunk 块,则会将待分配 chunk 块切割成两个 chunk 块,其中一个 chunk 块大小等同于用户需要分配内存的大小。需要注意的是分裂后的两个 chunk 必须均大于 chunk 的最小大小,否则不会进行拆分。

3.4 内存分配

内存分配流程可以分为三步:

第一步:根据用户请求大小转换为实际需要分配 chunk 空间的大小;

第二步:在 bins 中搜索还没有归还给操作系统的 chunk 块,具体流程如下图所示。

图片

  • 如果所需分配的 chunk 大小小于等于 max_fast (fast bins 中要求的最大 chunk 大小,默认为64B),则尝试在 fast bins 中获取 chunk,如果获取 chunk 则返回。否则进入下一步。
  • 判断所需大小是否可能处于 small bins 中,即判断 chunk_size < 512B是否成立。如果 chunk 大小处在 small bins 中则在 small bins 中搜索合适的 chunk,即找到合适的 small bin,然后从该 bin 的尾部摘取一个满足大小要求的 chunk 返回。如果 small bins 中无法找到合适的 chunk 则进入下一步。

  • 到这一步说明待分配的内存块要么是一个大的 chunk,要么只是没有在 small bin 中找到。分配器先在 fast bin 中尝试合并 chunk,并将 chunk 写入 unsorted chunk 中,此时再遍历 unsorted chunk 如果能够找到合适的 chunk 则按需将该 chunk 切分(可能不需要),将生成的 chunk 中其中一个放入 small bins 或者 large bins 中,另一个与待分配内存块相同大小的 chunk 则返回。

  • 在 large bins 中搜索合适的 chunk,如果能够找到则将该 chunk 切分成需要分配的内存大小,另一部分则继续写入 bins 中。如果无法找到合适的 chunk,则进入下一步。

  • 尝试从 top chunk 中分配一块内存给用户,剩下一部分生成新的 top chunk 。

第三步:如果 top chunk 依然无法满足分配请求,通过 sbrk 或 mmap 增加 top chunk 的大小并分配内存给用户。

3.5 内存释放

图片

  1. 判断当前 chunk 是否是 mmap 映射区域映射的内存,如果是则直接使用 munmap 释放这块内存映射(内存映射的内存能够通过标记进行识别);
  2. 判断 chunk 是否与 top chunk 相邻,如果相邻则直接与 top chunk 合并;

  3. 如果 chunk 的大小大于 max_fast(64B),则将其放入 unsorted bin,

    并检查是否有合并,如果能够合并则将 chunk 合并后根据大小加入合适的 bin 中;

  4. 如果 chunk 的大小小于

    max_fast(64B),则直接放入 fast bin 中,如果没有合并情况则 free 内存。如果在当前 chunk 相邻的 chunk 空闲,则触发合并,并将合并后的结果写入 unsorted bin 中,此时如果合并后的结果大于 max_fast(64B),则触发整个 fast bins 的合并操作,此时 fast bins 将会被遍历,将所有相邻的空闲 chunk 进行合并,然后将合并后的 chunk 写入 unsorted bin 中,fast bin 此时会变为空。如果合并后的 chunk 与 top chunk 相邻则会合并到 top chunk 中;

  5. 如果 top chunk 大小大于 mmap 收缩阈值(默认128KB),如果是,则对于主分配区则会试图归还 top chunk 中一部分给操作系统,此时 free 结束。

3.6 内存碎片

图片

按照 glibc 的内存分配策略,我们考虑下如下场景:

  1. 假设 brk 起始地址为512k

  2. malloc 40k 内存,即 chunk A,brk = 512k + 40k = 552k

  3. malloc 50k 内存,即 chunk B,brk = 552k + 50k = 602k

  4. malloc 60k 内存,即 chunk C,brk = 602k + 60k = 662k

  5. free chunk A。

此时 chunk A 为空闲块,但是如果 chunk C 和 chunk B 一直不释放无法直接通过移动brk指针来释放 chunk A 的内存,必须等待 chunk B 和 chunk C 释放才能和 top chunk 合并并将内存归还给操作系统。

四、问题分析与解决

通过前面的内存分配器运行原理能够很容易得出原因,由于程序中连续调用 free/delete 释放内存仅仅只是将内存写入内存分配器的 bins 中,并没有将其归还给操作系统,所以会出现疑似内存未回收的情况。并且如果每次 delete 的内存都不与 top chunk 相邻,会导致 chunk 块长时间留在空闲链表中无法合并到 top chunk,从而出现内存无法释放给操作系统的现象。

4.1 优化办法

  1. 通过限制服务端内存最大大小能够有效避免内存被c运行库撑的太高,导致服务器 OOM 的情况。

  2. c运行库替换成 jemalloc,jemalloc 与 glibc 的实现方式不同,能够更快将内存归还给操作系统。

4.2 效果对比测试

为了验证优化后的内存使用效果,编写测试代码,模拟线上 pipline 模式下的3000万次连续请求,对比请求过程中的内存峰值、连接断开后的内存使用状况:

  • glibc内存分配器

内存峰值

图片

连接断开后内存占用

图片

  • jemalloc内存分配器

内存峰值

图片

连接断开后内存占用

图片

根据测试结果,jemalloc 相较于 glibc 释放空闲内存速度快12%。

参考链接:

  1. https://www.gnu.org/software/libc/manual/html_node/

  2. https://github.com/hustfisher/ptmalloc/blob/master/README

  3. https://stackoverflow.com/questions/13480235/libc-memory-management

  4. https://zhuanlan.zhihu.com/p/637659294

1. 前言

本篇我们讲解
2个月搞定计算机二级C语言
——真题10

真题10-程序评分

2. 程序填空题

2.1 题目要求

真题10-程序填空

2.2 提供的代码

#include  <stdio.h>
#pragma warning (disable:4996)
double  fun(double x[], int n)
{
	int i, k = 0;
	double avg = 0.0, sum = 0.0;
	for (i = 0; i < n; i++)
		avg += x[i];
	/**********************found***********************/
	avg /= ____(1)____;
	for (i = 0; i < n; i++)
		if (x[i] > avg)
		{
			/**********************found***********************/
			____(2)____ += x[i];
			k++;
		}
	/**********************found***********************/
	return  ____(3)____;
}
main()
{
	double score[12] = { 50,60,70,80,90,100,55,65,75,85,95,99 };
	double aa;
	aa = fun(score, 12);
	printf("%f\n", aa);
}

2.3 解题思路

第(1)处填空:

在这条语句之前,程序使用
for
循环将所有学生的成绩加到了变量
avg
中,这里我们要实现的是求平均成绩,所以需要使用
avg
除学生的数量
n
,即可得到所有学生的平均成绩,并赋值给
avg

其中
avg /= n;
等价于
avg = avg / n;

avg /= n;

第(2)处填空:

经过
if (x[i] > avg)
判断,进来以后的
x[i]
都是大于平均成绩
avg
的,这里要执行的是将符合条件的
x[i]
累加至
sum
(程序已给出),并且每次使
k++
以便于后续求平均值。

sum += x[i];

第(3)处填空:

这里我们需要返回的是高于平均成绩的学生成绩的平均值,其中
sum
为高于平均成绩的学生总成绩,
k
为高于平均成绩的学生人数,用
sum / k
即可得到高于平均成绩的学生成绩的平均值。

return  (sum / k);

2.4 代码实现

填写完整的代码:

#include  <stdio.h>
#pragma warning (disable:4996)
double  fun(double x[], int n)
{
	int i, k = 0;
	double avg = 0.0, sum = 0.0;
	for (i = 0; i < n; i++)
		avg += x[i];
	/**********************found***********************/
	avg /= n;
	for (i = 0; i < n; i++)
		if (x[i] > avg)
		{
			/**********************found***********************/
			sum += x[i];
			k++;
		}
	/**********************found***********************/
	return  (sum / k);
}
main()
{
	double score[12] = { 50,60,70,80,90,100,55,65,75,85,95,99 };
	double aa;
	aa = fun(score, 12);
	printf("%f\n", aa);
}

提示:为确保代码正常运行,请在题库编程环境的对应题目中进行测试和运行。

3. 程序修改题

3.1 题目要求

真题10-程序修改

3.2 提供的代码

#include <stdio.h>
void  fun(char* s)
{
    int  i, j;
    for (i = 0, j = 0; s[i] != '\0'; i++)
        if (s[i] >= '0' && s[i] <= '9')
            /**********found**********/
            s[j] = s[i];
    /**********found**********/
    s[j] = "\0";
}
main()
{
    char  item[80];
    printf("\nEnter a string  :  "); gets(item);
    printf("\n\nThe  string  is  : \"%s\"\n", item);
    fun(item);
    printf("\n\nThe string of changing is  : \"%s\"\n", item);
    getchar();
}

3.3 解题思路

第(1)处修改:

这里需要将取出的数字字符形成新的字符串,并取代原字符串。

只使用
s[j]
是不行的,因为在程序中
j
始终没有改变值,一直为 0,导致每次的数字字符都会存储到
s[0]
的地址中,并没有形成新的字符串,所以我们要在这里让
j++
,从而改变存储的地址。

s[j++]=s[i];

第(2)处修改:

""
是用来表示字符串的,而这里的
s[j]
只能存储单个字符,所以需要使用
''
来括起来。

这里给
s[j]
赋值
'\0'
是应为字符串是以
'\0'
作为结尾的。

s[j]='\0';

3.4 代码实现

修改后的代码:

#include <stdio.h>
void  fun(char  *s)
{  int  i,j;
   for(i=0,j=0; s[i]!='\0'; i++)
        if(s[i]>='0' && s[i]<='9')
/**********found**********/
            s[j++]=s[i];
/**********found**********/
        s[j]='\0';
}
main()
{  char  item[80];
   printf("\nEnter a string  :  ");gets(item);
   printf("\n\nThe  string  is  : \"%s\"\n",item);
   fun(item);
   printf("\n\nThe string of changing is  : \"%s\"\n",item );
  getchar();
}

提示:为确保代码正常运行,请在题库编程环境的对应题目中进行测试和运行。

4. 程序设计题

4.1 题目要求

真题10-程序设计

4.2 提供的代码

#include <stdio.h>
#include <string.h>

void  fun(char* s, char  t[])
{



}

main()
{
    char   s[100], t[100]; void NONO();
    printf("\nPlease enter string S:"); scanf("%s", s);
    fun(s, t);
    printf("\nThe result is: %s\n", t);
    NONO();
    getchar();
}

void NONO()
{/* 本函数用于打开文件,输入数据,调用函数,输出数据,关闭文件。 */
    char s[100], t[100];
    FILE* rf, * wf;
    int i;

    rf = fopen("in.dat", "r");
    wf = fopen("out.dat", "w");
    for (i = 0; i < 10; i++) {
        fscanf(rf, "%s", s);
        fun(s, t);
        fprintf(wf, "%s\n", t);
    }
    fclose(rf);
    fclose(wf);
}

4.3 解题思路

这道题其实蛮容易的,无非就是遍历数组,再加个奇偶数的判断。

奇偶数判断前面也讲过,这里简单提一下:一个数除 2 取余等于 0,则为偶数,等于 1 则为奇数。

在函数开头要先将
t
所指的数组清空,然会遍历指针
s
所指的字符串,判断 ASCII 值为偶数则存到
t
中,其中
t[j++]
的作用和上一题一样。

题目要求将奇数的字符删除后,将剩余的字符放入
t
,实质就是把偶数的字符放入
t
,可以直接对偶数的字符操作,减少程序的复杂度。

4.4 代码实现

填写完整的代码:

#include <stdio.h>
#include <string.h>

void  fun(char* s, char  t[])
{
    int i = 0,j = 0;

    for (i = 0; i < (sizeof(t) / sizeof(t[0])); i++)	// 清空数组 t,防止出现垃圾值
    {
        t[i] = 0;
    }

    for (i = 0; i < strlen(s); i++)
    {
        if ((s[i] % 2) == 0)	// 等于 0 说明是 ASCII值为偶数
        {
            t[j++] = s[i];		// 保存到 t 所指的数组中
        }
    }
}

main()
{
    char   s[100], t[100]; void NONO();
    printf("\nPlease enter string S:"); scanf("%s", s);
    fun(s, t);
    printf("\nThe result is: %s\n", t);
    NONO();
    getchar();
}

void NONO()
{/* 本函数用于打开文件,输入数据,调用函数,输出数据,关闭文件。 */
    char s[100], t[100];
    FILE* rf, * wf;
    int i;

    rf = fopen("in.dat", "r");
    wf = fopen("out.dat", "w");
    for (i = 0; i < 10; i++) {
        fscanf(rf, "%s", s);
        fun(s, t);
        fprintf(wf, "%s\n", t);
    }
    fclose(rf);
    fclose(wf);
}

提示:为确保代码正常运行,请在题库编程环境的对应题目中进行测试和运行。

5. 后记

本篇博客到这就结束了,如果您有疑问或建议欢迎您在留言区留言。

来源:晓飞的算法工程笔记 公众号,转载请注明出处

论文: Online Learning via Memory: Retrieval-Augmented Detector Adaptation

创新点


提出一种通过检索增强分类过程的创新在线学习框架
RAC
,与传统的基于离线训练/微调的方法相比,具有以下优点:

  1. 在线和持续学习能力。
  2. 最少的标注需求。
  3. 对视觉领域适应的计算无需求。

内容概述


目标检测器已经从闭集模型演变为开放世界模型,但将这些模型应用于新领域往往会导致较差的检测性能。为此,论文提出了一种新颖的方法,可以在线调整任何现成的目标检测模型,以适应新的领域,而无需重新训练检测器模型。

受到人类快速学习新主题(例如,记忆)方式的启发,论文允许检测器在测试时从记忆中查找相似的物体概念。这是通过一种检索增强分类(
RAC
)模块与一个可以灵活更新新领域知识的记忆库来实现的。

对各种现成的开放集检测器和闭集检测器进行了实验。仅使用一个小型记忆库(例如,每类
10
张图像)并且无需训练,
RAC
显著优于基线,在将检测器适应新的领域方面表现突出。

检索增强的检测器适应


在线学习框架由以下主要模块组成:

  1. 一个可在线更新的记忆库,其中包含用于提供在线适应新概念的目标领域图像
  2. 一个来自现成模型的物体(前景)提议模型,可以是开放世界检测器、在具有不同本体的相似领域数据上训练的任何检测器,或者简单的区域提议网络(
    RPN
    )。
  3. 一个上下文检索模块,用于将记忆库中的图像上下文与推理图像关联。
  4. 一个实例检索模块,用于将提议的物体实例与检索到的相似上下文中的实例关联。

对于查询图像,上下文级
RAC
首先从记忆库中选择相似的上下文图像。然后基于查询图像中的物体提议,对每个提议,实例级
RAC
在选定的相似上下文图像中执行实例匹配。最后,每个提议根据来自检索实例的投票分配一个类别。

物体(前景)提议模型

采用预训练的检测器作为物体提议网络,用于定位子任务,并专注于解决新概念分类子任务。

提议网络可以有多种形式,例如现成的开放集检测器、在不同数据集上训练的检测器(例如,具有不同本体的检测器),或者简单的区域提议网络(
RPN
),只要它能够提供有意义的前景提议。即使是没有任何语义能力的二元
RPN
网络,也可以使其具备分类能力。

记忆库

RAC
仅需最少量的数据来构建记忆库,例如每个类别
10
张图像,这些图像可在在线学习环境中由最终用户轻松标注。为了构建一个高效的记忆库,论文提出了一种无监督的图像选择方法,利用图像级特征聚类来最大化覆盖率以及最小化标注工作。

  • 无监督种子图像聚类

使用强大的图像特征提取主干(例如
CLIP
)从未标注的目标域图像中提取嵌入,这些嵌入随后根据用户标注的图像数量进行聚类(例如,使用
k-means
),形成目标数量的聚类。每个聚类中的中心图像是由用户标注的,代表了多样化和具有代表性的场景。该方法能够通过每个类别仅标注
10
张图像就实现良好的检测性能。

检索增强(
RAC
)模块

通过在记忆库中存储标注的种子对象和图像,检索增强模块可以使物体检测器通过将目标检测到的提议与种子对象匹配来获得新的语义分类能力。

物体匹配的一个重大挑战是目标域中存在外观相似的不同类别的物体。为了解决这些混淆问题,论文构建了一个多阶段的上下文匹配过程。第一阶段,上下文检索,通过过滤掉无关场景(例如,过滤掉船只的海事场景)来缩小搜索范围。第二阶段,实例检索,则是在上下文匹配的图像中进行。通过同时考虑实例外观和上下文,该方法最大限度地减少了分类混淆并提高了检索准确性。

对于检索增强模型,强大的特征提取器是必要的。然而,它并不需要在目标域上进行训练即可实现良好的语义分类准确性。因此,任何强大的预训练特征提取器,例如
DINOV2

CLIP
,都可以以无训练的方式使用,或者在提供的记忆库上进行微调以获得最佳性能。

具体来说,在第一阶段进行图像级语义匹配,使用现成的
CLIP
模型来提取图像级特征,然后计算查询图像与记忆库图像之间的相似性。在第二阶段进行实例级匹配,从图像级匹配结果中选择前 k 张图像(k=
20
,
50
,
100
),使用现成或微调的
CLIP
模型提取边界框级特征,然后计算实例之间的相似性选择的前 k 张图像。因此,最终的实例分类结果是边界框级匹配和全局上下文匹配的结合,有效地减少了外观引起的混淆。

主要实验




如果本文对你有帮助,麻烦点个赞或在看呗~
更多内容请关注 微信公众号【晓飞的算法工程笔记】

work-life balance.