Android-属性服务的设计魅力
本文概要
属性服务不管你有没有用过它、见过它，它都是存在的，并且在Android系统中非常的重要，本文通过故事的方式由浅入深的介绍了属性服务为啥使用共享内存和socket通信作为进程之间的通信方式，同时也由浅入深的介绍了属性服务为了做到更快、更省内存都做了哪些努力。
init进程当老板
告诉大家一个好消息，我init进程开公司了，公司的名字叫Android用户空间有限公司。这消息一出，没有引来大家的掌声，却引来了一些嫉妒者的唏嘘声，有些嫉妒者口无遮拦的说道：“他这么年纪轻轻的当老板，还不是因为人家有个好爹。人家命好啊。”
init老板怒呵道：“我就是靠我爹了咋的，有种你也有个这样的爹啊，最恨你们这些说话不动大脑的家伙了。”
“还有更刺激的消息要刺激你们，我爹swapper进程他也开了一家公司，公司名叫Android系统有限公司。我兄弟kthreadd进程也开了一家公司，公司名叫Android内核空间有限公司。我和我兄弟的公司都归我爹管理。“
属性服务当秘书
init老板心想：虽然我公司刚成立，但是为了长远考虑我得找个秘书来分担我的工作，那该找谁呢？想到了找我的前同事属性服务美女来帮助我。
经过init老板一番忽悠后，属性服务美女答应了init老板的聘请要求。
“那咱们现在立马就开始工作吧，我稍后会把工作内容先告诉你。“
属性服务美女不情愿的说道：”啊！这么急迫吗？连个缓冲的时间都不给我，就立马让我工作，生产队的驴也不能被你这么使唤吧。“
init老板嘿嘿一笑：”首先现在大环境就是这样，大家都非常的卷，咱不卷那别人就会卷死咱们。别看公司刚成立，你可是咱们公司的2号人物，前期吃点苦、受点累非常值得啊。要相信我也要相信你，咱们公司一定会上市的，到那时候你就财富自由了。想想都美好！“
属性服务美女心想：又用这老套的说辞来忽悠我，要不是今年这经济环境不景气，我早就......,诶！还是忍忍吧，先有个工作才能养家糊口啊。属性服务美女坚定的说：”好的老板，为了咱们公司的发展、上市梦，我一定好好干，我把我所有的时间都投入到公司，我把公司当作我的家。
一个需求
init老板对属性服务美女说：”在给你布置工作任务之前，咱们公司的规定你需要先熟知下。首先因为每个员工都是单独的一个进程，为了员工及公司的安全，员工之间是不可以随意沟通的，员工之间确实有沟通的需求，那就只能通过匿名共享内存、socket（管道通信）、signal（信号机制）、信号量、binder通信 这几个进程通信的手段来进行，这个你可千万要记住，后面的工作任务中你要用到。但是你是个特例，你是可以直接与我通信的，因为咱俩都在同一进程。“
属性服务美女想了想：员工与员工之间不可随意沟通，这是啥奇葩规定，美其名曰是为了员工安全，我看其实和流水线工作一样，让员工卖命的工作而已。不过好在我是有特权的，我管不了别人，想想我是一个有特权的员工，生活是多么美好啊！
交代了公司规定后，那我就来给你提个需求，你需要根据这个需求来设计一套系统，需求内容是下面几项：
沟通渠道：解决员工与我沟通的问题，而不是我与员工沟通的问题，现在“上传下达”可以做到，我有啥任务是可以直接交给员工去做的；但 是下面员工有啥述求或工作汇报，我现在是完全不知道的，因此需要建立这么一个沟通渠道。在沟通渠道上传递的数据格式是
key value字典类型的，也可以称这种格式为为属性。有了上面的沟通渠道后，就经常会有员工向我汇报工作，但是我每天处理的事情特别的多，因此需要你来帮我分担下，以后员工找我汇报工作，
要先和你打招呼，我会告诉你哪些工作可以转交给我，哪些工作你自己处理即可。并不是所有员工都可以向我汇报工作，比如只有高级管理者（也是一个进程）才可以汇报，因此需要增加
权限设置。属性存储中心：从名字就可以看出它的作用，它是用来存储key value属性的，存储下来的属性是可以供员工之间共享的，比如员工A存储的属性是 可以供员工B、员工C使用的。权限设置：比如高级别的管理者存储的属性设置了权限的话，没有对应权限的员工是没有办法获取这些信息的。持久化：什么叫持久话呢，大白话就是有些员工希望存储的属性能存储在硬 盘中。沟通渠道和属性存储中心作为咱们公司的基础服务，就像国家修的路和高铁一样，如果基础服务做不到既快又省，那会严重影响咱们公司的效 率，快指的是速度上的快，比如从属性存储中心读取属性要多快就得有多快，没有最快只有更快。省指的是省内存，不能说为了做到快却牺牲了大量的内存，这是不可取的。
上面是整个需求，小属啊你需要认真分析这个需求，根据需求来实现设计这么一套系统。
需求分析
属性服务美女心想：我这刚来，必须把第一枪打的又响又漂亮。init老板提的需求主要就是两大功能：沟通渠道和属性存储中心，我可以这样理解这个需求：首先需要先有沟通渠道，它不单解决员工与init老板沟通的要求，同时它也需要解决员工从属性存储中心取属性的要求。沟通渠道是属性存储中心的基础，因此沟通渠道的快慢决定了属性存储中心的快慢。因此需要先建立一个最快的沟通渠道。
需求中最重要的点就是一定要快，因此除了沟通渠道快之外，属性存储中心也不能掉链子啊，要达到又快又省的目标沟通渠道和属性存储中心都必须是最快的。
属性存储中心到底应该放置在何处的问题，对了应该放置在init老板所处的进程，因为这个进程是整个Android用户空间所有进程中生命周期最长的进程并且没有之一。
最快的沟通渠道
要想建立最快的沟通渠道，有必要听听前辈的经验，因此属性服务美女把匿名共享内存、socket、signal、信号量、binder等一众大佬请了过来，把要做的事情向大佬们交代后，希望各位能提提意见。
匿名共享内存大佬第一个发话：“哈哈，要说快，我还是非常自信的，我肯定是最快的，我敢说第二没人敢说第一。但是我也是有缺点的，咱有一说一万事万物都不可能十全十美，我的缺点就是需要做同步处理”
“同步处理？”属性服务美女有点懵。
“刚好用你的需求来打个比方，你的需求其实就是读写的需求，大体的情况是会有多个线程读同时也会有多个线程写。如果当前都是读操作，那不需要做同步处理，因为没有数据发生变化，并且这也是最快的时候。如果同时存在读写操作，那就需要让所有的读操作先暂停掉，同时也需要让多个写操作暂停，只让其中一个写操作进行。直到所有写操作都执行完，才可以让所有读操作执行，这时候的效率就不敢打包票是最快的了。”
匿名共享内存大佬接着说：“对于你的需求来说，同步处理是最难的事情，因为与进行读写的进程实在太多了。”
“好的我记下了匿名共享内存大佬，如果能把同步处理解决了，您肯定是最好的通信手段”
socket大佬说：“在快方面我没有啥发言权，因为需要经过两次拷贝，这也是导致通信慢的原因，但是我也有我的优点就是是可以传递大数据的，并且可以用来做C/S模式”
“C/S模式就是一个server端可以同时与多个client端进行通信吧“
socket大佬连忙点头说：”对的，你可以好好想想，C/S模式我觉得可以帮上你的忙。“
signal大佬对属性服务美女说：“我确实想帮你，但是我无能为力，因为我有一个很特别的限制一次通信只能传递一个int整数，不好意思啊。”
属性服务美女：“没事，能帮我想办法我已经非常感激你了。”
这时候binder大佬说话了：“我是为安卓而生的，我也是C/S模式，我的通信效率仅次于匿名共享内存，因为仅有一次数据拷贝，其他的优势就不细说了。同时我也是存在一些缺点的，首先进程启动的时候需要创建一定大小的共享内存，其次会至少启动一个binder线程来为通信工作做准备，当通信量非常大的时候就需要创建更多的binder线程。”
binder大佬又接着对属性服务美女说：“我主要应用于数据量大、通信特别频繁的场景。而针对你的需求使用我来解决我觉得是不适合的。首先不管进程到底有没有存储key value数据的需求都需要在进程启动的时候提前创建共享内存，还需要提前初始化binder驱动层，如果系统中有很多的进程根本就没有这种需求是不是内存方面大大的浪费；其次因为是C/S模式，init进程其实是server端，因为整个系统中根本不知道会有多少进程会有通信的需求，万一一下子有非常多的进程来通信，那我到底应该最多创建多少个binder线程呢？创建的多了是浪费，创建少了会引起anr等问题；最后因为我也使用到了内存共享机制，所以我也是需要解决同步问题的。”
“以上是我的分析结果，所以最终到底选择我们哪个来帮助你，需要你结合你的需求、场景来自己仔细的斟酌下。”
属性服务美女琢磨了下binder大佬的话，是的应该结合自己的需求来考虑到底应该选哪个了。
首先signal方式肯定不行，其次binder方式也基本放弃了，那就剩下匿名共享内存和socket了。匿名共享内存确实快，但是如果遇到大量的写操作和读操作，首先同步处理是个最大的问题，如何保证这么多的读写操作准确性呢？并且这种情况下效率明显降低了。
解决同步问题
同步问题不好处理的主要原因是：读写操作都在不同的线程中，所以非常难以做同步。那如果把写操作都放在同一线程中进行，读操作还依然在原先各自的线程中进行，这样是不是就容易处理了，如果用lock来解决同步问题的话，这种情况下是不是顶多只需要一个lock就可以解决问题。对了为了更快，不能用lock来做同步处理，因为lock的效率低下，可以使用原子操作，比如atomic_load_explicit、memory_order_consume、atomic_store_explicit、memory_order_release,关于原子操作就不详细展开介绍了。
怎么才能让所有的写操作收拢到同一个线程呢，办法就是先把它们收拢到同一进程中，进而收拢到同一线程中，收拢到的同一进程就是init进程。
刚解决了一个问题，又来新问题（人生何尝不是这样呢），那怎么样才能让写操作收拢到init进程呢？答案就是socket通信，因为可以用它来做C/S模式，在init进程中启动socket的server端，谁想要与init进程通信那就创建一个socket的client端，server端把所有的写操作都收拢到同一线程中。那就用一张图来总结下我这绝妙的设计吧
欧耶，我都被我的聪明给折服了。让我在细细想想这方案是否靠谱：首先写操作没有那么频繁，并且数据格式是key value的属性，即使两次拷贝也不至于那么慢。其次读操作肯定是最快的因为用的是匿名共享内存，并且读操作的频率会很高。
最快的属性存储中心
属性服务美女乐哈哈的向init老板汇报自己的进度：沟通渠道是如何设计的，都用到了哪些通信手段，沟通渠道绝对是最快的渠道，绝对是遥遥领先的。
init老板听后，为自己有这么一个能干的员工感到无比的高兴。他说：“小属啊！你的专业知识和设计能力真的非常突出。你设计的沟通渠道是如此的快，犹如从绿皮火车换为高铁。关于属性存储中心你计划如何设计呢？”
“属性存储中心，不是存储很简单的key value属性数据吗？我感觉已经很明确了，还需要设计吗？”
“当然需要设计了，并且还需要非常用心的设计，一个优秀的属性存储中心需要满足快、省这俩要求。快就是读取快，咱们的文档中心刚开始的时候数据量少体现不出问题来，如果数据量越来越多，如何能从巨多的数据中依据key值快速的找到对应的value值。省就是省内存。现在没有任何设计，那你计划如何根据key去查找对应value呢？是一个一个的对比查找吗？这肯定是一个非常愚蠢的做法。”
“刚刚在需求分析阶段我还想到了这问题了，刚刚被喜悦冲昏头脑了忘记属性中心的设计了，那我立马好好的设计一番。”
属性服务美女总结了下：其实就是解决如何快速查找的问题，这不涉及到数据结构了吗，有了可以请教数组大佬。
属性服务美女把需求向数组大佬说明了下，数组大佬我现在的一个解法是:使用数组来存放属性数据，在存放的时候key根据音序排列（比如"zygote":"xxx","demo":"xxx"。它们放入数组的顺序是这样的："demo":"xxx","zygote":"xxx"），那就可以使用二分查找可以快速的进行查找了。
数组大佬说：“这样确实可以加快查找的效率，但是有一个问题就是数据的增删效率是非常低下的（比如增加数据，需要先找到key值应该存放的位置，该位置及后面的数据都得往后移动），因此依据这点来看我不建议使用数组来解决此问题。不过我觉得你可以去找HashMap大佬，或许它可以解决你的问题。”
属性服务美女同样把需求向HashMap大佬交代了下，HashMap大佬我有个不成熟的解法，帮我把把脉：存储的数据刚好是key value类型，而您HashMap刚好可以用来存放key value数据，真是天造地设的一对啊。并且您可以根据key快速的找到对应的value值；并且增删操作的效率也高（不像数组那样效率低下）真的是太完美了，我觉得完全不需要做多余的设计，直接使用您HashMap就可以解决我的问题。
“no no no，小美女可别高兴的太早了，不是我给你泼冷水，是这样的我也存在一些问题：首先是扩容，如果存放不下数据时，就需要扩容，扩容可是没有那么简单的；其次是由于我结合了数组和链表两种数据结构，当存在大量的key值的hash值存在一样的时候，整个查找效率会明显降低；最后数据量大的时候会有内存浪费的情况。因此当数据量大的时候使用HashMap会存在内存浪费和查找效率低下的问题，这需要你自己来综合考虑下。”
天呢，我又一次受到了打击，该咋办呢！淡定越是这个时候越需要冷静，这才是真正展示我能力的时候。靠人不如靠自己，更何况我在数据结构方面也有深厚的功底，那我就自己来设计了。
刚开始一上来就想着用什么样的数据结构这是一个错误的方向，应该先设定好属性key的格式，进而再依据key的格式来决定使用哪些数据结构。
需求中有这么一些关键信息：传递的属性数据有可能会有权限方面的设置，并且init老板也有要求哪些属性会交给它处理。
如果需要满足上面的需求，其中一个做法就是依据属性的key值，比如key值是以com开头的认定为需要进行权限校验，以control开头的认定为需要交给init老板处理，这也是最简单的做法。另外以com或者control开头的关键字最后和后面的字符用分隔符分割开，比如用“.”分割开，最好凡是单词之间都用分隔符分割开，这样就可以依据分割符来做更多的事情，并且也易读。那最终key的格式是这样的xxx.xxx.xxx，比如com.aa.bb。
属性服务美女惊叹到：“这个格式是不是特别的眼熟啊，没错和域名格式是一样的。那接下来就该琢磨琢磨用啥数据结构来存储key了。”
可以使用链表来存储，每个分隔符分割出的关键字是一个节点，分割符分割的下个关键字节点是上个关键字节点的孩子节点，节点的结构如下：
struct node {
//以分隔符进行分割的下个关键字是当前节点的child
struct node * child;
//当前节点若存在value，则value就代表key对应的value
char value[];
//关键字
char name[];
}
比如 "com.aa.bb":"demo" 对应的链表结构如下：
进阶
那如果有"com.aa.bb":"demo"，"com.aa.cc":"hello"，"com.bb.dd":"world" 这三个属性值，那如果按上面的链表结构是如下样子：
属性服务美女问道：“不知道大家有没有发现上图的问题，问题就是内存浪费，多个相同的节点没有共用同一节点，当数据量特别大的时候，这就是大大的浪费啊！其次是查找慢，因为这些链表之间即使有共同的节点但是它们都是单独的存在，完全使用不到数据结构里面的各种查找算法,作为一个优秀的、追求完美的的开发设计者，怎能容忍这问题呢”
可以把节点node的child改为children，children代表子节点数组（如下面伪代码）这样就可以解决共用相同node节点的问题了。
struct node {
//children代表当前节点的所有子节点，n代表数组长度
struct node children[n];
//当前节点若存在value，则value就代表key对应的value
char value[];
//关键字
char name[];
}
稍等等，属性美女突然意识到一个问题：children是一个数组，数组的大小应该设置为多少呢？申请的多了，浪费内存，少了可能会涉及扩容的问题。并且增删操作并不是数组的优势。所以这不能用数组。
那就用二叉树吧，二叉树还可以结合二分查找算法加快查找效率，依据二叉树定义的结构如下：
struct node {
//children指向所有的孩子节点
struct node *children;
//left、right分别代表与当前节点同级的节点，也就是当前节点的兄弟节点
struct node *left;
struct node *right;
//当前节点若存在value，则value就代表key对应的value
char value[];
//关键字
char name[];
}
那用上面的结构来看下"com.aa.bb":"comaabb"，"net.bb":"netbb"的结构图吧
com节点和net节点被认为是同一辈分的，因此它们是兄弟关系，aa节点是com节点的子节点，同理bb节点是aa节点的子节点。
为了加快查找节点的效率，可以这样设计left和right节点：left节点存放的是比当前节点name长度小或相等的节点，right节点存放的大于当前节点name长度的节点，比如："com.aa"，"a.b"，“hello.c" 这三个key，com的left节点存放的是a节点，com的right节点存放的是hello节点，这样就可以加快查找效率了。
为了加深大家的理解，来看下"com.aa.bb":"comaabb"，"com.aa.cc":"comaacc"，"com.bb.dd":"combbdd"，"net.aa.bb":"netaabb"，"com.eee.ff":"comeeeff"，"com.eee.ff.ggg":"comeeeffggg" 这些属性的结构图：
总结
属性存储中心利用属性的key设计为域名的格式，既可以做权限的控制，也可以根据前缀来划分出各种不同类别的属性（比如control类型的，sys系统类型的），最关键的利用链表、二叉树来存储key value属性，可以达到节省内存、加快查找效率，同时增删也用到了链表的优势
属性美女感叹到：我又一次被自己的优秀设计给惊艳到了，我真是太有才了。
注：上面伪代码与Android源代码的对应关系
node结构对应prop_btnode结构的value对应prop_info
没有最快只有更快
属性服务美女把当前的进展汇报给了init老板，init老板对属性美女一顿夸奖后，又给她提了一个要求，他觉得还是有优化的空间，他觉得还能再快。
属性美女深思后，终于找到了可以优化的点：现在的设计是只申请了一块大的共享内存，各种属性数据都存储在这块内存中，首先的一个问题是发生读写同步的概率就会非常大（即使写的key value和当前读的key没有多大联系）这会降低读的效率；其次有的进程其实只关心一小部分key value数据，但是一下子就mmap了一大块共享内存，这是大大的浪费啊。
没事，继续接着优化，可以采用分组的方式，把大块的共享内存分为多个小的共享内存，把key值相关的的属性放在同一共享内存中，依此进程就可以根据自己关心的key值，来mmap一小块共享内存即可。下图展示了key值与共享内存的关系
会把找不到组织的key值会加入到default这个共享内存中。
注：
这部分内容对应Android源码中的prop_area、ContextNode的概念。
源码中根据key查找value的过程是：根据对应的key值可以找到对应的ContextNode,进而根据ContextNode找到对应的prop_area，prop_area中会找到prop_bt,prop_bt找到对应key的prop_info,最终从prop_info中找到value值。
成果
属性服务美女拿着自己优秀的设计成果给了init老板，把这套系统设计的是多么的快、多么的省内存、多么的优雅都一五一十的给老板讲清楚了。init老板高兴的说：“小属啊，你这套系统设计的真是棒啊，我非常认可你的专业技能，对了这套优秀的系统应该有个名字，既然你是设计者那就以你的名字命名吧，就叫属性服务系统吧。“
属性服务美女听到这套系统能以自己的名字命名，抑制不住的兴奋油然而生。
”还有凡是收到sys、control开头的属性都需要交给我来处理。还有还可以制定一些不同类型的属性，比如以ro开头的就认为是只读的属性，是不可以被重新写的。属性服务系统应该在init进程启动的时候就要启动，提前把磁盘中存储的属性读取到内存中。以后属性服务系统的事情就统统交给你来处理了，一定要好好干啊“
”好的老板，谢谢老板对我的肯定，我会加倍努力工作的。“