怎样设计一个内存池，减少内存碎片？

一般工程里不推荐你写，因为你费力写一个出来99%可能性没有内置的好，且内存出bug难调试
一定要设计的话，你也可以当个玩具写写玩玩：
1 实现教科书上的内存分配器：
做一个链表指向空闲内存，分配就是取出一块来，改写链表，返回，释放就是放回到链表里面，并做好归并。注意做好标记和保护，避免二次释放，还可以花点力气在如何查找最适合大小的内存快的搜索上，减少内存碎片，有空你了还可以把链表换成伙伴算法，写着玩嘛。
2 实现固定内存分配器：
即实现一个 FreeList，每个 FreeList 用于分配固定大小的内存块，比如用于分配 32字节对象的固定内存分配器，之类的。每个固定内存分配器里面有两个链表，OpenList 用于存储未分配的空闲对象，CloseList用于存储已分配的内存对象，那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户，释放又是从 CloseList 移回到 OpenList。分配时如果不够，那么就需要增长 OpenList：申请一个大一点的内存块，切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候，统一把先前向系统申请的内存块全部还给系统。
3 实现 FreeList 池：
在你实现了 FreeList的基础上，按照不同对象大小（8字节，16字节，32，64，128，256，512，1K。。。64K），构造十多个固定内存分配器，分配内存时根据内存大小查表，决定到底由哪个分配器负责，分配后要在头部的 header 处（ptr[-sizeof(char)]处）写上 cookie，表示又哪个分配器分配的，这样释放时候你才能正确归还。如果大于64K，则直接用系统的 malloc作为分配，如此以浪费内存为代价你得到了一个分配时间近似O（1）的内存分配器，差不多实现了一个 memcached 的 slab 内存管理器了，但是先别得意。此 slab 非彼 slab（sunos/solaris/linux kernel 的 slab）。这说白了还是一个弱智的 freelist 无法归还内存给 *** 作系统，某个 FreeList 如果高峰期占用了大量内存即使后面不用，也无法支援到其他内存不够的 FreeList，所以我们做的这个和 memcached 类似的分配器其实是比较残缺的，你还需要往下继续优化。
4 实现正统的 slab （非memcached的伪 slab）代替 FreeList：
这时候你需要阅读一下论文了，现代内存分配技术的基础，如何管理 slab 上的对象，如何进行地址管理，如何管理不同 slab 的生命周期，如何将内存回收给系统。然后开始实现一个类似的东西，文章上传统的 slab 的各种基础概念虽然今天没有改变，但是所用到的数据结构和控制方法其实已经有很多更好的方法了，你可以边实现边思考下，实在不行还可以参考 kernel 源码嘛。但是有很多事情应用程序做不了，有很多实现你是不能照搬的，比如页面提供器，可以提供连续线性地址的页面，再比如说 kernel 本身记录着每个页面对应的 slab，你查找 slab 时，系统其实是根据线性地址移位得到页面编号，然后查表得到的，而你应用程序不可能这么干，你还得做一些额外的体系来解决这些问题，还需要写一些额外的 cookie 来做标记。做好内存收缩工作，内存不够时先收缩所有分配器的 slab，再尝试重新分配。再做好内存回收工作，多余的内存，一段时间不使用可以还给 *** 作系统。
5 实现混合分配策略：
你实现了上面很多常见的算法后，该具体阅读各种内存分配器的代码了，这些都是经过实践检验的，比如 libc 的内存分配器，或者参考有自带内存管理的各种开源项目，比如 python 源码，做点实验对比他们的优劣，然后根据分配对象的大小采用不同的分配策略，区别对待各种情况。试验的差不多了就得引入多线程支持了，将你的锁改小。注意很多系统层的线程安全策略你是没法弄的，比如 *** 作系统可以关中断，短时间内禁止本cpu发生任务切换，这点应用程序就很麻烦了，还得用更小的锁来代替。当锁已经小到不能再小，也可以选择引入 STM 来代替各种链表的锁。
6 实现 Per-CPU Cache：
现代内存分配器，在多核下的一个重要优化就是给多核增加 cache，为了进一步避免多线程锁竞争，需要引入 Per-CPU Cache 了。分配内存先找到对应线程所在的cpu，从该cpu上对应的 cache 里分配，cache 不够了就一次性从你底层的内存分配器里多分配几个对象进来填充 cache，释放时也是先放回 cache，cache里面如果对象太多，就做一次收缩，把内存换个底层分配器，让其他 cpu 的cache有机会利用。这样针对很多短生命周期的频繁的分配、释放，其实都是在 cache 里完成的，没有锁竞争，同时cache分配逻辑简单，速度更快。 *** 作系统里面的代码经常是直接读取当前的cpu是哪个，而应用层实现你可以用 thread local storage 来代替，目前这些东西在 crt的 malloc 里还暂时支持不到位（不排除未来版本会增加），可以更多参考 tc/jemalloc。
7 实现地址着色:
现代内存分配器必须多考虑总线压力，在很多机型上，如果内存访问集中在某条 cache line相同的偏移上，会给总线带来额外的负担和压力。比如你经常要分配一个 FILE 对象，而每个 FILE对象使用时会比较集中的访问 int FILE::flag; 这个成员变量，如果你的页面提供器提供的页面地址是按照 4K对齐的，那么很可能多个 FILE对象的 flag 成员所处的 cache line 偏移地址是相同的，大量访问这些相同的偏移地址会给总线带来很大负担，这时候你需要给每个对象额外增加一些偏移，让他们能够均匀的分布在线性地址对应的cache line 偏移上，消减总线冲突的开销。
8 优化缓存竞争：
多核时代，很多单核时代的代码都需要针对性的优化改写，最基本的一条就是 cache 竞争，这是比前面锁竞争更恶劣的情况：如果两个cpu同时访问相同的 cache-line 或者物理页面，那么 cpu 之间为了保证内存一致性会做很多的通信工作，比如那个cpu0需要用到这段内存，发现cpu1也在用，那么需要通知cpu1，将cpu1 L1-L2缓存里面的数据写回该物理内存，并且释放控制权，这时cpu0取得了控制权才能继续 *** 作，期间cpu0-cpu1之间的通信协议是比较复杂的，代价也是比较大的，cache竞争比锁竞争恶劣不少。为了避免 cache 竞争，需要比先前Per-CPU cache 更彻底的 Per-CPU Page 机制来解决，直接让不同的cpu使用不同的页面进行二次分配，彻底避免 cache 竞争。具体应用层的做法也是利用线性地址来判断所属页面（因为物理页面映射到进程地址也是4k对齐的），同时继续使用 thread local storage 或者用系统提供的 api 读取当前属于哪个 cpu 来实现。为了避免核太多每个核占据大量的页面带来的不必要的浪费，你可以参考下 Linux 最新的 slub 内存分配算法，但是 slub 也有未尽之处，好几个 linux 发行版在实践中发现 slub 还是存在一些问题的（非bug，而是机制），所以大部分发行版默认都是关闭 slub 的，虽然，你还是可以借鉴测试一下。
9 调试和折腾：
继续参考各种现代内存分配器，取长补短，然后给你的分配器添加一些便于调试的机制，方便诊断各种问题。在你借鉴了很多开源项目，自己也做了一些所谓的优化，折腾了那么久以后，你或许以为你的分配器可以同各种开源分配器一战了，测试效果好像也挺好的，先别急，继续观察内存利用率，向 *** 作系统申请/归还内存的频率等一系列容易被人忽视的指标是否相同。同时更换你的测试用例，看看更多的情况下，是否结果还和先前一样？这些都差不多的时候，你发现没有个一两年的大规模持续使用，你很难发现一些潜在的隐患和bug，可能你觉得没问题的代码，跑了两年后都会继续报bug，这很正常，多点耐心，兴许第三年以后就比较稳定了呢？

memcached 是一套分布式的快取系统，当初是Danga Interactive为了LiveJournal所发展的，但被许多软件（如MediaWiki）所使用。这是一套开放源代码软件，以BSD license授权协议发布。[1]
memcached 仅支持一些非常简单的命令 比如get（获取某个键值） set（用来设定或保存一个缓存）；
其本身是缓存服务器，但本身无法决定缓存任何数据，其缓存机制依赖于服务端和客户端两者必不可少（存储是由服务端进行存储，但存储什么是由客户端进行决定的）
因此客户端要自己提供缓存的键名以及时长、标志位、整个数据大小等等
例如：只存储hello 但只存储60秒
set key 5 60 hello
并告知服务器端，这样存储过了60秒后，由服务端进行清除数据
但是其工作机制非常独特，其缓存功能是基于Lazy模型的：
只要空间未满则不清理
那么问题来了：如果空间过小，而需缓存的内容过大的话，那么导致缓存抖动非常严重，存完即清理其次再去缓存这样会导致命中率下降，而毫无意义
有些时候，有些数据管理不善有可能导致缓存崩溃等
如果memcached崩溃仅导致业务层的影响，最多是速度降低 而不会导致数据层
memcached 如何实现缓存的
memcached 通过内存进行缓存数据，但并不实现持久缓存
存数数据的下限：
最小为48字节
最大不能超过1MB
但存储的数据大小有可能不一致，比如：
indexhtml10k
testjpg34k
那memcached如何在内存中管理缓存数据
假如我们分别存储不同大小的数据以上为例
很显然只要分配一个足够大的空间就可以了，但是在内存中去找对应的数据我们必须要有对应的缓存对象的边界（起始存储位地址和结束存储位地址）将其当做独立的单位来管理
等其缓存失效了，空间会被腾出，时间久了可能会带来碎片，因为存储的都是非常小的数据单元，按理说如果再想高速利用则会困难，所以在这种机制下memcached的存储数据 查询数据等 *** 作都是非常缓慢的
由此，不停快速基于内存的申请、释放反复 *** 作，这种释放本身也消耗大量的资源和时间
因此我们需要一种高效的机制来解决内存的创建和释放的问题
对于memcached来讲首要必须解决这类内存碎片问题，不然由于内存的碎片导致进程运行的非常缓慢
在linux内核中引入了两种机制避免内存碎片
1buddy system 伙伴系统
为了实现整个内存中以页面方式管理内存的时候有足够大的连续内存空间可用的，在物理内存中，事实上内存的管理和分配在内核级别通常以页面方式分配和使用的
通常是4k大小一个页面，buddy就是为了将这些零碎的、空闲的合并成一个连续的大的内存空间，这样就避免了页面之间产生碎片的，因此，其主要目的是为了避免内存外碎片
2slab allocator slab 分配器
实现将存储小于页面单位的非常小的数据内存结构的时候之前事先分配并随时等待有需求的进程或要存储的对象使用，当我们使用之后它也不会自动消毁结构而是随时重复使用
避免内存内部碎片
最新版本的memcached使用的是增长因子（growth factor）来明确定义起始点开始依次增长
比如：
我们定义增长因子为其2倍
我们存储一个单位为48bytes,那么会分配其482 = 96bytes
如果增长因子为11倍
那么48+4811
一旦存储空间满了，则会清理，没有存满则不会清理数据

一 下载需要的源码包
所有安装包均选用最新的。
1 下载libevent2022
点击红色部分下载
下载memcached1424
点击红色部分，下载最新版本
下载php扩展memcache308
选择需要的版本
二 安装详细步骤
首先将以上三个软件包下载到/tmp目录下
1 安装libevent
cd /tmp #首先进入到该下载包的目录
tar zxvf libevent-2022-stabletargz #解压包cd libevent-2022-stable #进入到解压的目录/configure --prefix=/usr/local #编译前配置，生成Makefile文件，路径可自行更改make; make install #编译+安装
1
测试是否安装成功
看到这些信息，表示成功啦
2 安装memcached
cd /tmp #首先进入到该下载包的目录
tar zxvf memcached-1424targz #解压包
cd memcached-1424 #进入到解压的目录
/configure –with-libevent=/usr/local #编译前配置，生成Makefile文件，路径必须与libevent中一致make; make install #编译+安装
1
测试是否安装成功
表示成功的信息
通过以上 *** 作，就完成了memcached服务器的安装。特别的简单吧！现在就来搞一搞memcache的php扩展安装吧3 安装扩展
cd /tmp #首先进入到该下载包的目录
tar zxvf memcache-308tgz #解压包
cd memcache-308 #进入到解压的目录
/opt/lampp/bin/phpize #动态为php添加扩展。phpize路径可能不一致，请根据自己的实际情况/configure –enable-memcache –with-php-config=/opt/lampp/bin/php-config –with-zlib-dir #php-config请根据自己环境情况填写make; make install #编译+安装
1
完成以上步骤时，心情愉悦的点击了enter，准备喝口水潇洒一下，结果出现了一下错误(这也是我写这篇博客的原因，要不都懒得记录了)错误信息
看了下代码错误信息，说是zlibh找不到。找不到就给他安一个嘛。真是的安装zlib
下载zlib-128targz
下载地址：>windows下网站开启memcache的方法是设置调用方法：
Memcached 是memcache的运行服务端，核心文件，Memcached基于一个存储键/值对的hashmap，其守护进程（daemon ）是用C写的，但是客户端可以用任何语言来编写，并通过memcached协议与守护进程通信。
作用：Memcached基本只占用内存资源。能够很好弥补对于高频繁调用，却不经常变更的资源。
web中的memcache的实现方法：
/
缓存类
/
public class MemCachedCtl {
protected static MemCachedClient mcc = new MemCachedClient();// 创建全局的唯一实例
protected static MemCachedCtl memCached = new MemCachedCtl();
//配置信息
private static String[] servers = { "127001:11211" };
private static Integer[] weights = { 3 };
private static int initialConnections = 10;
private static int minSpareConnections = 5;
private static int maxSpareConnections = 50;
private static long maxIdleTime = 1000 60 30;
private static long maxBusyTime = 1000 60 5;
private static long maintThreadSleep = 1000 5;
private static int socketTimeOut = 1000 3;
private static boolean nagleAlg = false;

/
不允许通过构造方法创建实例
/
protected MemCachedCtl() {

}

/
获取唯一实例
/
public static MemCachedCtl getInstance() {
return memCached;
}

/
初始化基本信息
/
public void init(){
if(initConfig())
initPool();
}

/
初始化配置信息
/
private boolean initConfig(){
//TODO 初始化配置文件
return true;
}

/
memcache服务器初始化连接池
/
private void initPool(){
SockIOPool pool = SockIOPoolgetInstance();// 获取socke连接池的实例对象
poolsetServers(servers);// 设置服务器信息
poolsetWeights(weights);//设置权重

poolsetInitConn( initialConnections );// 设置初始连接数
poolsetMinConn( minSpareConnections );//设置最小连接数
poolsetMaxConn( maxSpareConnections );//设置最大连接数
poolsetMaxIdle( maxIdleTime );//设置最大处理时间
poolsetMaxBusyTime( maxBusyTime );
poolsetMaintSleep( maintThreadSleep );// 设置主线程的等待时间
poolsetSocketTO( socketTimeOut ); //设置连接超时时间
poolsetNagle( nagleAlg );
poolsetHashingAlg( SockIOPoolNEW_COMPAT_HASH );
poolsetAliveCheck( true );
poolinitialize();
}

/
判断key是否存在
/
public boolean keyExists(String key){
return mcckeyExists(key);
}

/
缓存一个对象
/
public synchronized boolean add(String key, Object value) {
return mccadd(key, value);
}

/
缓存一个对象(日期)
/
public synchronized boolean add(String key, Object value, Date expiry) {
return mccadd(key, value, expiry);
}

/
缓存一个对象(hashCode码)
/
public synchronized boolean add(String key,Object value,Integer hashCode){
return mccadd(key, value, hashCode);
}

/
缓存一个对象
/
public synchronized boolean set(String key, Object value) {
return mccset(key, value);
}

/
缓存一个对象(日期)
/
public synchronized boolean set(String key, Object value, Date expiry) {
return mccset(key, value, expiry);
}

/
缓存一个对象(hashCode码)
/
public synchronized boolean set(String key,Object value,Integer hashCode){
return mccset(key, value, hashCode);
}

/
删除一个缓存对象
/
public synchronized boolean delete(String key) {
return mccdelete(key);
}

/
删除一个缓存对象(日期)
/
public synchronized boolean delete(String key, Object value, Date expiry) {
return mccdelete(key, expiry);
}

/
删除一个缓存对象(hashCode码)
/
public synchronized boolean delete(String key,Integer hashCode,Date expiry){
return mccdelete(key, hashCode, expiry);
}

/
删除全部服务器上的缓存对象
/
public synchronized boolean flushAll() {
return mccflushAll();
}

/
删除指定服务器上的缓存对象
/
public synchronized boolean flushAll(String[] servers) {
return mccflushAll(servers);
}

/
替换原有的缓存(更新缓存)
/
public synchronized boolean replace(String key, Object value) {
return mccreplace(key, value);
}

/
替换原有的缓存(更新缓存)
/
public synchronized boolean replace(String key, Object value, Date expiry) {
return mccreplace(key, value, expiry);
}

/
替换原有的缓存(更新缓存)
/
public synchronized boolean replace(String key, Object value, Integer hashCode) {
return mccreplace(key, value, hashCode);
}

/
替换原有的缓存(更新缓存)
/
public synchronized boolean replace(String key, Object value,Date expiry, Integer hashCode){
return mccreplace(key, value, expiry, hashCode);
}

/
返回全部服务器状态
/
public Map stats(){
return mccstats();
}

/
返回指定服务器状态
/
public Map stats(String[] servers){
return mccstats(servers);
}

/
根据指定KEY获得缓存
/
public Object get(String key) {
return mccget(key);
}

/
根据指定KEY,HASHCODE获得缓存
/
public Object get(String key,Integer hashCode) {
return mccget(key,hashCode);
}

/
根据指定KEY,HASHCODE,状态值 获得缓存
/
public Object get(String key,Integer hashCode,boolean asString) {
return mccget(key,hashCode,asString);
}
/
测试方法
这里真实调用的时候换成自己的场景使用。
/
public static void main(String[] args) {
MemCachedCtl cache = MemCachedCtlgetInstance();
cacheinit();
// cacheadd("helloworld_key", "helloworld_value");
cacheset("helloworld_key", "helloworld_value");
Systemoutprint("返回结果: " + cacheget("helloworld_key"));
}
}

---