adoryn
TA的个人档案
adoryn个人页面-阿里云开发者社区
文章
97
问答
0
个人介绍
暂无个人介绍
擅长的技术
- 高分内容
- 最新动态
- 文章
- 问答
-
发表了文章 2018-06-24
生活随笔：第一次见家长注意事项
快要见家长了，赶紧补一波注意事项~~~ 男生版 1、去女友家拜访，到她家附近时不可以再挽着她的手，因为她的邻居会品头论足一番。 2、进家后，不要对她太随便、太亲热，她的家人在观察着你的一举一动，以免给人留下不好的印象。 3、不可不时看手表，否则她的家人会认为你不愿意呆在她家。 4、离去时不可一踏出门就露出松懈姿态，因为背后她的家人们还在观察你。 5、还应注意一点，去女友家做正式拜访的前一天，一定要洗澡，更衣，要做到干净、整洁，切不可邋里邋遢，既不尊重对方，又给人留下不好的第一印象。最重要的是全身都散发出干净的清洁感，如肩膀上有头屑最让人恶心。男人通常都是以外表取胜，因为父母的眼睛很容易往细处看：干净、整齐的头发、胡子，衬衣领口和袖口洁净，指甲修理整齐、干净，长裤笔挺，干净的袜子的鞋。 初登恋人家门，就像参加一场考试，既要注意服饰仪表，又要为应答交谈作好必要的准备。 这可从四个方面进行： 一是稳定情绪，自信真诚恳切，落落大方，肯定受欢迎；虚伪做作，扭扭捏捏，必然被嫌弃。有了自信心，紧张的心情便会慢慢平静。 二是了解情况。询问恋爱对象，了解其家庭成员，父母的职业，文化，兴趣，经历，性格等，知道越详细越好。情况熟悉，才能先有准备，交谈时也能有的放矢。 三是初拟内容。想想对方会提出些什么问题。在这种场合下，未来的岳父母常会问问你的家庭，工作，爱好等，自己可做些准备。 四是适当准备礼物，初次去对方家里做客，适当送些礼物给对方的父母，很有必要，这不仅表明你对长辈的尊敬，更表明你的诚意，一般来说，对方父母是会接受的，但应注意，送的礼品不宜太贵重，否则起点太高，以后恐怕你难以为继。 初次见面，双方难免感到拘束。寒暄之后，常会冷场。这时就要引出话题。一种方法是就地取材。仔细观察墙壁，窗台，桌子等，墙上的名人字画，窗台上的菊花，桌上的各种小摆设，都可借来入话。因为它们往往体现了主人的情趣爱好，能使主人讲出许多愉快的话来。另一种方法是避生就熟。引出话题要避开对方感到陌生的事，从对方最熟悉的入手，可以谈谈新闻，聊聊天气。 对方父母提问时，要会叙述说明，态度要恭敬，声音略低一些，柔和些。把话一句句，一层层说清楚，谈话时一定彬彬有礼。长辈夸奖年轻人时，总爱说：“这孩子很懂事！”一般长辈衡量青年好坏的标准，除了天生的外貌和本人的才能外，就看他是否“懂事”，也就是是否能通晓情理。在与对方父母交谈时，你一定要注意礼貌问题，要做到谦虚恭敬，善解人意。 初登恋人家门，应忌讳四个方面： 一忌油嘴猾舌。 说话要朴实，说心里话，如一池清水，清澈见底；不做作，不油滑。 二忌自我吹嘘。 要懂得：不表示自己聪明，就是聪明；不夸张自己的美德，就是美德。 三忌胆小怯羞。 要明白：越怕讲错，就越会讲错话；不怕讲错，反倒会使言谈顺畅。胆小，拘谨，害羞，是初登恋人家门交谈时的大忌。 四忌粗言劣语。 语言必须文明，不礼貌的口头禅，习惯语等，一定要戒除。 对方父母请你家宴，说明他们对你有了初步好感，你切不可得意忘形，露出“野性”。由于来做客赴宴是“醉翁之意不在酒”，切莫贪杯，喝个酩酊大醉，美好姻缘可能会因你一醉方休而毁于一旦。 男生拜见女方家长的注意事项 第一次上对方的门，新人心里必定紧张，说什么做什么，多少有点手足无措。希望这篇攻略能为新人们整理出一点头绪，让新人们在准备时有的放矢。 在见女方父母之前，请男孩子们一定好好整理一下自己。如果在女方家里见面，那么整齐的休闲装就可以了。如果是约在酒店或者茶社见面，那最好还是穿正式的西装+皮鞋。 切记，男孩们要把自己收拾的干净利索，这样能讨父母辈的喜欢。指甲缝不要有污垢、皮鞋要擦亮、头发整齐最好不要用发胶、胡子刮干净。要让女方父母觉得，这个男人很得体，把自己的女儿交给他能放心。 拜见家长怎么穿不适宜 不要在未来的岳父岳母面前表现你的小个性了，艺术家那样的披肩长发啦，络腮胡子啦，各种放荡不羁啦，请收敛起来吧，这只能给你减分。夏天的凉拖短裤，冬天挂满泥的球鞋和满是褶皱的裤子，还是早点换了吧。有汗脚的男孩，也要前期做好准备，不要穿不透气的鞋子，换双新袜子，不要让破洞在换鞋后暴露出来。 拜见家长怎么送礼物适宜 送礼物是个大学问，现在已经不再是水果点心的年代了。在挑选礼物的时候，要跟女友商量着来，有没有对方父母一直想买但没有机会去买的东西。送这样的礼物，会让长辈觉得这孩子很贴心。像是茶叶、羊毛披肩这样既实用又有面子的礼物，再好不过了。 拜见家长怎么送礼物不适宜 礼物很重要，价格也很关键。我恰恰不赞同送过于贵重的礼物，毕竟是第一次见面，太贵重的礼物会让对方父母觉得你是不是故意在显示有钱呢，又或者不懂得节俭，这样怎么能过日子呢。 有些爸爸喜欢抽烟，很多男孩子会带上好烟，其实小编不觉得这样的礼物好，因为对健康没有好处。 拜见家长怎么称呼适宜 得体的礼貌，在初次见面中很重要。可以事先问问对方父母的出生年份，决定称呼叔叔阿姨还是伯父伯母，这样比统称叔叔阿姨更得体一些。跟女方父母交流时要带“您”。 拜见家长怎么称呼不适宜 想象不出该是有多没有规矩的孩子，才能称呼对方父母除了“叔叔阿姨伯父伯母”之外的称谓了。 拜见家长怎么聊适宜 谈话时，语速要适中。长辈问什么就答什么，如果稍微有点冷场，男孩子可以主动引起一些话题，可以从对方父母的爱好展开话题，但态度要谦虚谨慎，大方得体，不要滔滔不绝。 拜见家长怎么聊不适宜 在具体聊天的过程中，请新人注意一些禁忌。 1、如果对方父母有身体不好的，请不要聊健康。 2、不要涉及地方家里的私事，比如退休工资啦，以前的单位啦。 3、不要滔滔不绝，那样会让人觉得特别不稳重，爱显示自己。遇上本身低调的父母，会觉得这个小伙子有点夸夸其谈。 4、不要谈及财产之类比较敏感的话题，即使你家里物质条件好，也要低调。 男方第一次去女方家相关事项： 1、时间——最好是一天之中的上午，千万别晚上去(当然这得看你未来的岳父母的意识)这是一般的礼节，以示尊重，并暗示你是一个勤奋之人，因我的父母皆是大家族出来的，特别讲这个。 2、送礼——男方第一次去女方家总不能空手而去，总会想买点礼物，这是很多男孩子好面子才这样想，但是究竟要买什么也拿不定主意。这个礼物不要太多，但是一定要买。要买好看的，拿得出手的，不一定要很实用(因为在他们心理，你毕竟还是“外人”，所以一定要体面)。 3、礼貌——上一辈的人对这个看得是比较重的，第一次去女方家之前，男方可以先问问你女朋友她们那里有没有什么特殊的礼节，如没有特别的,则和长辈的交往中保持谦虚的态度可谓是最大的礼节吧，进女方家门时，男方嘴口一定要甜，比如微笑的问叔叔阿姨你好，这是初次登门给人的第一印象(很关键的)。 4、言谈——在女方家人面前，男孩子要面带微笑，多听少说，认真聆听老人的言谈、并及时应和，说话时大方自然,但不可以得意忘形，保持诚恳、实诚的本色，也许你有些事情还没想好,如大人们问起也许不知怎么回答,那就照实回答,比胡谄强多了，老人往往要的是感觉，也给你的女友一种姿态，你接纳她并会善待她的父母。”多谢””不客气””你们别忙乎，我来”要常挂在嘴边，多说关心的话。 5、话题——避开一些双方敏感的话题，多询问一些女友小时候的事，这是每个父母百说不厌的经典话题，尤其是值得夸耀的事，可问一些细节。当他们的思维跟你转的时候，就减轻了对你的注意力，同时他们会认为你关心他们的女儿。 6、衣着——男方第一见女方家长，衣服不必刻意讲究有多华丽，只要整洁、干净，就行，但不要太随便，还有就是头发一定要干净。 7、神态举止——自然、轻松、愉快。最好用几句简短的话，表明你对将来的打算，并征求他们的意见。对他们的回答哪怕有异议，也点头，微笑，以后再说，不要破坏此次的气氛。做些力所能及的小事吧，也许他们不会让你做，但态度是另外一回事。 8、其他——第一次会面的时间最好不要太长，最好不要住在女方家里，有的家庭很忌讳这个，速战速决，见好就撤，以便为下次会面留下良好的期待。多注意观察，比如看见家里长了花草，就装作很感兴趣可以询问饲养花草的方法，要是看见有什么古董之类的陈设，可以赞美一番。总之就是要抓住岳父母的爱好，他会很有兴趣，觉得你是同道中人。 女生版 其实见家长这事是个说大也大说小也小的事，如果真的因为见家长这事最后两个人掰了，那只能说明两个问题： 第一，你的情商实在让人捉急。 第二，男朋友家里人不同意。 女孩子见家长的话一定会担心他家里人会在怎么想啊，是不是同意啊，喜不喜欢我之类的问题自我烦恼，更有些想事情多的妹纸还会想到婆媳矛盾问题啊巴拉巴拉的。 其实见家长这事，我们要两看，第一呢，让男朋友家里人看一下你，心里有个数，毕竟男朋友的妈妈是我们最大的情敌么。其次，你也可以借机看看男朋友家里的状态，看看他们家是否和谐啊，家里是准婆婆说了算还是公公，家庭气氛怎么样啊等等，如果考察出问题，果断解决也是极好的。闲话不多说，总结下我生活中关于见家长的攻略。 见家长呢，不一定是一定要结婚了才见的，哪怕是在恋爱中也是可以去见家长的。这表明了你的另一半对你的认同以及希望跟你长久发展的愿望。我曾经听过一个男孩子说一直没有勇气带女朋友回家，他觉得很恐怖。所以你的另一半想带你见家长，那么妹纸们，偷笑吧，嘻嘻。笑过之后就要开始准备了。 我把整个过程分为三个阶段：事前、事中和事后三部分。 一、事前：见家长前的准备工作要做好 知己知彼百战百胜 在知道要去后，首先做好信息收集的工作。问问他家爸爸妈妈的一些喜好啊，平时的兴趣啊什么的，这些一定要问清楚。一方面，方便准备给对方父母的礼物。另一方面，可以很靠谱的跟长辈们聊天。不过，这没有那么简单，是个男友九个会跟你说，我也不知道要买什么。放心吧，我爸爸妈妈人很好的。 一般的对话是这样的： 女：去你家买点什么啊？你妈妈喜欢什么啊？ 男：我也不知道，你自己看着办吧。 女：化妆品？你妈妈用什么的？ 男：不知道…… 反正，就是男朋友一般是不会给你合适的建议的。因为你们的立场是不同，他回去只是回家，爸爸妈妈是自己的亲人，而我们是去见外人，出发点都不一样想问题的角度一定没办法相同。因此，如果你的男朋友能给你靠谱的建议，那我恭喜你呀。如果不能，咱们也要自力更生。 问清楚对方父母的职业、家庭状态（退休了没有啊）、业余爱好、家里都有什么人啊。这次去见面都有哪些人啊等等。 问问对方家里有什么家庭礼仪需要遵守啊。比如有的地方吃饭是必须要端着碗吃，有的地方吃饭绝对不能把碗端起来等等，这些习俗挺琐碎的，也很重要啊，细节决定一切啊。 去对方家一定要提前准备礼物。告诫妹纸们，千万不要空手去，一定不要。虽说空手对方不会说什么，但是真的从礼数上讲真的不好。一般你带着东西去，对方会跟你客气客气：哎呀，来吃个饭还带什么东西呀。下次来就不要带了……哎呀，这多不好意思啊……一般都会这样，看到了“下次”么，如果你不带东西去，那么连听到这句话的机会都被你丢了，多可惜啊。 关于礼物的选择： 水果类。原则是不买那些太普通的，买好吃好看的，又不太重的。水果是第一次见面最稳妥的选择，就是说你拿不准要买什么的时候，或者这次见面是家庭式的，那么买水果不会惊艳，但绝不失礼。 保健品类。这类也是送长辈很不错的选择，一般我会买钙片、维生素或者蛋白粉之类的保健品作为第一次见面的见面礼，不分男女都可以用，还能把对方的爷爷奶奶也送到，简单又实用。 食品类。这类的话最好能跟特定的节日联系起来，比如中秋节，送个月饼啊什么的。 特产类。这是很讨巧的一类礼物，比如我会买点珍珠粉、海边的特产送过去，大方又拿得出手，就说是特产让对方尝鲜。 其他。比如给对方妈妈可以买护肤品、衣服、包、香水什么的。给对方爸爸的话买茶叶、工艺品之类的（我不太会给男生买东西，尤其是长辈，这个我也在学习和总结中呢）。 个人形象塑造。 这个也是需要事前好好想好的。其实很多人都知道要得体大方，简单化妆、淡妆就可以。但是具体的话，我的建议是风格上可以根据个人气质进行选择，但可以在服饰的配色上往偏暖的色调上靠、简单的风格就好。妆容的话淡妆就可以了，标准就是让人看着舒服就好，不用刻意凹造型。 二、事中：眼观六路，耳听八方 事前的成功就等于见家长成功了一半，另一半就要靠自己在现场的掌控了。 都说妈妈是你最大的情敌，这话我特别认同。所有的妈妈在见女朋友的时候心里都会有一个疑问，她能对我儿子好吗？ 因此，你做所有事情都要围绕着这句话来，用行动和言语告诉他的妈妈，能。 1、聊天：回答 对方肯定会各种夸自己儿子好。这个时候你就颔首微笑，适时点头，顺着话头也各种明着暗着的夸。一定要笑哦，这是超级加分项。 会说自己老公和家庭。我功力不是很够，很多时候也不能完全分析出来应该怎么应对，但是这种情况总归是要告诉你我们家里很好很和谐。我们也吵架也有不好的时候两人包容就过来了。潜台词就是告诉你一些生活和婚姻的道理。你一定要及时的说，阿姨说的太对了，我也是这么觉得。应该向你们学习之类的，一定要说的及时而真诚啊。 问你和你家庭的情况。这个因人而异，不刻意欺骗，但也挑好的说，别实在的都一咕噜都说了。多留点话题吧，来日方长呢。 2、聊天：发问 问问健康啊，日常生活之类的。 问问男朋友小时候啊什么的，尽量把气氛搞得轻松加愉快。 问问喜好之类的。 问问对方一些生活技能。 3、聊天：夸 夸对方年轻、漂亮、气质、有文化等等 夸手艺啊生活技能高啊之类的 夸男朋友好啊，夸对方教育的好啊等等 聊天的时候，要先少说话，多观察。了解清楚对方父母是话多的还是话少的人之后再确定自己怎么去应对比较稳妥。实在不知道要说什么就多笑多点头多认同，这是真理。如果在吃饭，没话说的时候就给一家人添茶倒水。或者说“阿姨多吃点，这个好吃”之类的。反正别冷场就好。 如果对基本礼仪不熟悉，那么自己去百度下，别失礼就ok了。 4、做事 记得之前看过一个帖子，说不要第一次去男方家太殷勤，不然以后结婚没有地位什么的。我不太赞同那篇文章里的观点。 我还是觉得去对方家，对方款待你，人家家人辛辛苦苦的给你做了饭，你去人家家洗个碗怎么了？不应该吗？ 大多数时候你说帮忙做个饭、洗个碗，是个态度问题。对方通常不会让你做，就让你出去客厅做着了，但是这话你一定要说，哪怕真让你打个下手择个菜、端个碗的也没什么啊。告诫姑娘们，去男朋友家提前做好做家务的准备吧，生活永远比想象来的丰富，下一秒会发生什么难说。 三、事后 收尾工作要做好啊，不然就虎头蛇尾了。 通常我会给对方家里发个语音道谢。主要的内容包括，谢谢对方的款待或者邀请，其次呢表达一下今天吃的很开心、聊天很投机之类的、最后可以邀请对方一起吃个饭啊或者下次一起出去玩之类的话。这叫礼尚往来，有来有往。一方面放对方了解了你的态度，还顺便约了下一次的见面，一举两得，又不花费什么成本何乐不为。 ps：还有呢，现在是移动互联网时代了么，对方服务如果微信神马的用的，那么就果断扫一扫，或者回去之后问男友要上对方服父母的微信号，没事去点个赞什么的。这是我最近得出的心得。 ps：其实再详细的攻略都涵盖不了生活。攻略不是教你虚伪，也不是教你敷衍，恰恰是告诉你用真心实意去对待，但是要有智慧的善良和善真诚的对待一些重要的事情。我最后祝每个妹纸都能够获得自己想要的幸福~ 第一次拜见家长补充攻略 【写在前面】 相信今年春节一定有不少人们都借着春节的春风见了双方家长，哈哈，感觉一定“很好”吧。初登恋人家门，就像参加一场考试，既要注意服饰仪表，又要小心言谈举止。虽然现在是婚恋自由的年代，但家长的意见也值得参考，因此，我觉得，做好一些准备，给长辈留下美好的第一印象很有必要。细节决定成败，我下面来奉献自己的第一次拜见家长的攻略，让我们从打扮、语言、神情、动作各个击破吧！ 【穿着要得体】 俗话说的好，人靠衣装马靠鞍。见面的第一印象，都是从穿着上体现的。想要TA的家人看你顺眼，你也要迎合TA家人的口味。所以在见家长之前，一定要和TA沟通好，问清TA家人的接受程度在做穿着上的考虑。 如果对方父母思想保守，或有宗教信仰，那你就选择简单、干净的衣服，让那些破洞牛仔裤、金属T恤、超短裙待在衣柜里吧。 如果对方父母时尚前卫，思想开明，那就如自己喜欢的那样(但也不要太随意，运动裤和睡衣通常都不是一个好主意)。 如果对方家境殷实，可选择质地好的高档服装。小贴士：男生一定要打理好自己的小细节。例如，出行前去理发，把胡子刮干净，注意鼻部卫生（嘎嘎），换上一双干净的袜子等。如果穿了衬衫，应不时查看一下领口和袖口有没有脏污，长途旅行很难保证服饰的干净，所以，最好穿深色的衣服或者备一套新装。 【礼物：合意加上心意】 我觉得，送礼物给长辈，合适的才是好的，也最能体现送礼人的心意。拜访对方父母前，可先了解清楚对方家人的兴趣爱好。我有一个女同事讲他第一次到男朋友家时，送了一套钓鱼杂志和一袋外国品种的玫瑰种子。原来，她了解到，男友的父亲是钓鱼爱好者，想在年底续订来年的杂志，而母亲则喜欢园艺，很想种一些稀有花卉。根据这些线索，女同事挑选到了让未来公婆爱不释手的见面礼。小熊觉得说，如果没有好的切入点的话，就选择一些应季的实用品。像现在这个季节送羊绒衫、羊毛围巾、呢帽、保暖内衣、保暖小家电等都是不错的选择。小贴士：值得注意的是，如果要把保健品当作礼物，最好提前了解对方父母的健康状况，以免弄巧成拙。 【说话，要有礼貌】 我第一次见家长的时候，非常的紧张，因为之前一点心理准备都没有，是妈妈把我“骗”过去的。快见到男朋友家长之前，妈妈就对我说，如果你害怕说错话，一言不发，别人会觉得你性格内向，不容易相处。但是，你若不管别人说什么都滔滔不绝地抢话，也不会受欢迎。那我们究竟应该怎么做呢？小熊经过一段时间的总结后就明白了，当对方父母提问时，态度要恭敬，声音略低一些，柔和些。把话一句句，一层层说清楚。当长辈想要插话的时候，你要虚心倾听。当然初次见面，双方难免感到拘束。寒暄之后，常会冷场。找到共同点，这些初步的了解将能派上用场。 父母对运动感兴趣么？如果你们有相同的运动爱好，这将是个很好的话题。 地域渊源。你或你的家人，是否和对方父母来自同一个地方？有无类似的生活经历？ 就地取材。仔细观察墙壁、窗台、桌子等，墙上的名人字画，窗台上的花卉，桌上的各种小摆设，都可借来入话。因为它们往往体现了主人的情趣爱好，能使主人讲出许多愉快的话来。当然，也可以从对方最熟悉的入手，可以谈谈新闻，聊聊天气。 【吃饭，注意用餐礼仪】 我在这里特别提醒，对方父母请你家宴，说明他们对你有了初步好感，你切不可得意忘形，这很有可能是一次非常近距离的接触。因为从饭局能看出一个人的许多品性和性格，孰优孰劣一目了然。比如，女生吃饭要细嚼慢咽、夹菜不能满盘乱翻。咀嚼的时候，更不要吧嗒吧嗒。另外切记，当你在席间满口塞满饭菜，还滔滔不绝讲话的时候，你的形象分已经被减去好多。男生，你无论多饿，还是一口口慢慢吃。不要给自己堆好一大碗饭菜，然后埋头猛往嘴巴里面填。这样的行为，会显得你很粗俗。 吃饭过程还要给家长多端茶倒水，男生要给女友夹菜，这些细节，家长都会看在眼里的。 小贴士：由于来赴宴是“醉翁之意不在酒”，切莫贪杯，喝个酩酊大醉，美好姻缘可能会因你一醉方休而毁于一旦。小熊有一个老家的表哥就是因为贪杯，经不住女方家人的轮番劝酒，自己的酒量又有限，知道自己酒量有限还充面子海喝，结果喝得自己都不知道怎么回家的。没过两天，女方那边带话过来就把这门亲事给吹了。
-
发表了文章 2018-06-19
对蚂蚁金服面试中几个题目的浅析
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/zhaobryant/article/details/80738819 本文对今天蚂蚁金服面试中的几个问题进行简单阐述分析，望批评指正。 搜索DAG问题 问题描述：给定一个图，寻找出里面所有的有向无环图（DAG）。 问题分析： 有向无环图 在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。 解题思路 给定一个图，如下： 该图包括多个DAG有向无环图。 于是，对于整个算法，我们使用两个阶段来完成： 第一阶段：计算每个节点到其他节点的有向路径。为了防止成环，我们需要在合并时进行成环检测。 代码如下： public class GraphDAGFinder { private Map<Node, NodeDAGList> nodeDAGListMap = new HashMap<>(); public void findAllDAGinGraph(Set<Node> graphNodes) { for (Node node : graphNodes) { NodeDAGList dagList = this.findAllDAGbyNode(node); System.out.println("NODE [" + node.getId() + "] DAGS = "); for (NodeDAGItem item : dagList.getAllDagItems()) { item.printDAG(); } System.out.println("-------------------------------"); } } private NodeDAGList findAllDAGbyNode(Node n) { NodeDAGList dagList = this.nodeDAGListMap.get(n); if (dagList != null) return dagList; dagList = new NodeDAGList(); NodeDAGItem item = new NodeDAGItem(); item.addNode(n); dagList.addNodeDAGItem(item); if (n.getNextHops().isEmpty()) { return dagList; } for (Node nd : n.getNextHops()) { NodeDAGList tmplist = this.findAllDAGbyNode(nd); for (NodeDAGItem tmpit : tmplist.getAllDagItems()) { if (tmpit.hasNode(n)) continue; NodeDAGItem itm = tmpit.copyDAG(); itm.addNode(n); dagList.addNodeDAGItem(itm); } } this.nodeDAGListMap.put(n, dagList); return dagList; } } 第二阶段：路径合并成图。有了每个节点到其他节点的路径，我们可以对其所有路径进行合并，合并的规则是节点顺序不能交叉，否则会导致成环。在这里，为了合并路径，需要对不同的路径进行组合，然后再合并。 组合的代码如下，主要是寻找出对应路径集合的ID组合： private static Set<List<Integer>> computeCombs(List<Integer> idxs) { Set<List<Integer>> combinations = new HashSet<>(); List<Integer> comb = new ArrayList<>(); for (int i = 1; i < idxs.size(); i++) { getNCombs(nodes, 0, i, comb, combinations); } return combinations; } private static void getNCombs(List<Integer> idxs, int index, int len, List<Integer> comb, Set<List<Integer>> combinations) { if (len == 0) { combinations.add(comb); return; } if (index == idxs.size()) return; comb.add(idxs.get(index)); getNCombs(idxs, index + 1, len - 1, comb, combinations); comb.remove(idxs.get(index)); getNCombs(idxs, index + 1, len, comb, combinations); } 合并流程如下： 从源节点开始，所有路径向后遍历，直到出现交叉，此时，选择某一分支停止向后遍历。以此类推，直到所有分支全部停止或遍历完成。 这里的合并可能有多个结果，统一存储。 最后的结果如下所示： 后续工作 对于整个问题，我们这里采用了两阶段的处理过程，能够得到结果，但是对于大规模节点图，仍然存在时间复杂度较高的问题。因此，后续工作可以围绕如何进一步降低搜索空间的方式来进行进一步的优化。比如，换一个维度，从边入手，而不是从节点入手；又如，使用回溯非递归+全局变量存储的方式来代替现有的递归方案，从而进一步减少栈溢出错误；再如，查阅论文文献，参考别人的算法，理解吃透优化。 脑裂问题 摘自CSDN博客： 在高可用HA系统中，当联系两个节点的心跳线断开时，原本为一个整体的动作协调的HA系统，就会分裂成为两个独立的个体。这时，由于两个节点相互失去了联系，都以为是对方出现了故障，两个节点上的HA软件就会像裂脑人一样，争夺共享资源，争相提供应用服务，这个时候就会出现严重后果： 共享资源被瓜分，两个节点的服务都起不来； 两个节点的服务都起来了，但同时读写共享资源，导致数据损坏。 一般来说，脑裂问题产生的原因主要包括下面几个： 高可用服务器之间的心跳线发生故障，导致无法正常通信； 高可用服务器开启了iptables防火墙，阻挡了心跳消息传输； 高可用服务器上网卡地址等信息配置不正确，导致发送心跳消息失败。 可以认为，在集群或者主备模式下，由于网络原因导致节点之间不可达，此时，每个网络分区就会自主选择出master节点，从而造成原来的集群存在多个master节点。这些master节点会争夺共享资源，从而导致系统出现服务不可用或资源损坏等问题。 解决方案： 添加冗余的心跳线，如双心跳线，尽量减少“脑裂”的发生几率。 设置仲裁机制，当心跳线完全断开时，两个节点相互ping一下参考IP，不通则表示断点就出在本端，此时可自动重启，从而彻底释放可能还占用的共享资源。 增加节点至奇数个，通过raft或paxos协议来进行投票选举主节点。
-
发表了文章 2018-06-03
Linux epoll模型详解及源码分析
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/zhaobryant/article/details/80557262 一、epoll简介 epoll是当前在Linux下开发大规模并发网络程序的热门选择，epoll在Linux2.6内核中正式引入，和select相似，都是IO多路复用（IO multiplexing）技术。 按照man手册的说法，epoll是为处理大批量句柄而做了改进的poll。 Linux下有以下几个经典的服务器模型： 1、PPC模型和TPC模型 PPC（Process Per Connection）模型和TPC（Thread Per Connection）模型的设计思想类似，就是给每一个到来的连接都分配一个独立的进程或者线程来服务。对于这两种模型，其需要耗费较大的时间和空间资源。当管理连接数较多时，进程或线程的切换开销较大。因此，这类模型能接受的最大连接数都不会高，一般都在几百个左右。 2、select模型 对于select模型，其主要有以下几个特点： 最大并发数限制：由于一个进程所打开的fd（文件描述符）是有限制的，由FD_SETSIZE设置，默认值是1024/2048，因此，select模型的最大并发数就被限制了。 效率问题：每次进行select调用都会线性扫描全部的fd集合。这样，效率就会呈现线性下降。 内核/用户空间内存拷贝问题：select在解决将fd消息传递给用户空间时采用了内存拷贝的方式。这样，其处理效率不高。 3、poll模型 对于poll模型，其虽然解决了select最大并发数的限制，但依然没有解决掉select的效率问题和内存拷贝问题。 4、epoll模型 对比于其他模型，epoll做了如下改进： 支持一个进程打开较大数目的文件描述符（fd） select模型对一个进程所打开的文件描述符是有一定限制的，其由FD_SETSIZE设置，默认为1024/2048。这对于那些需要支持上万连接数目的高并发服务器来说显然太少了，这个时候，可以选择两种方案：一是可以选择修改FD_SETSIZE宏然后重新编译内核，不过这样做也会带来网络效率的下降；二是可以选择多进程的解决方案（传统的Apache方案），不过虽然Linux中创建线程的代价比较小，但仍然是不可忽视的，加上进程间数据同步远不及线程间同步的高效，所以也不是一种完美的方案。 但是，epoll则没有对描述符数目的限制，它所支持的文件描述符上限是整个系统最大可以打开的文件数目，例如，在1GB内存的机器上，这个限制大概为10万左右。 IO效率不会随文件描述符（fd）的增加而线性下降 传统的select/poll的一个致命弱点就是当你拥有一个很大的socket集合时，不过任一时间只有部分socket是活跃的，select/poll每次调用都会线性扫描整个socket集合，这将导致IO处理效率呈现线性下降。 但是，epoll不存在这个问题，它只会对活跃的socket进行操作，这是因为在内核实现中，epoll是根据每个fd上面的callback函数实现的。因此，只有活跃的socket才会主动去调用callback函数，其他idle状态socket则不会。在这一点上，epoll实现了一个伪AIO，其内部推动力在内核。 在一些benchmark中，如果所有的socket基本上都是活跃的，如高速LAN环境，epoll并不比select/poll效率高，相反，过多使用epoll_ctl，其效率反而还有稍微下降。但是，一旦使用idle connections模拟WAN环境，epoll的效率就远在select/poll之上了。 使用mmap加速内核与用户空间的消息传递 无论是select，poll还是epoll，它们都需要内核把fd消息通知给用户空间。因此，如何避免不必要的内存拷贝就很重要了。对于该问题，epoll通过内核与用户空间mmap同一块内存来实现。 内核微调 这一点其实不算epoll的优点了，而是整个Linux平台的优点，Linux赋予开发者微调内核的能力。比如，内核TCP/IP协议栈使用内存池管理sk_buff结构，那么，可以在运行期间动态调整这个内存池大小（skb_head_pool）来提高性能，该参数可以通过使用echo xxxx > /proc/sys/net/core/hot_list_length来完成。再如，可以尝试使用最新的NAPI网卡驱动架构来处理数据包数量巨大但数据包本身很小的特殊场景。 二、epoll API epoll只有epoll_create、epoll_ctl和epoll_wait这三个系统调用。其定义如下： #include <sys/epoll.h> int epoll_create(int size); int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout); 1、epoll_create #include <sys/epoll.h> int epoll_create(int size); 可以调用epoll_create方法创建一个epoll的句柄。 需要注意的是，当创建好epoll句柄后，它就会占用一个fd值。在使用完epoll后，必须调用close函数进行关闭，否则可能导致fd被耗尽。 2、epoll_ctl #include <sys/epoll.h> int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); epoll的事件注册函数，它不同于select是在监听事件时告诉内核要监听什么类型的事件，而是通过epoll_ctl注册要监听的事件类型。 第一个参数epfd：epoll_create函数的返回值。 第二个参数events：表示动作类型。有三个宏来表示： * EPOLL_CTL_ADD：注册新的fd到epfd中； * EPOLL_CTL_MOD：修改已经注册的fd的监听事件； * EPOLL_CTL_DEL：从epfd中删除一个fd。 第三个参数fd：需要监听的fd。 第四个参数event：告诉内核需要监听什么事件。 struct epoll_event结构如下所示： // 保存触发事件的某个文件描述符相关的数据 typedef union epoll_data { void *ptr; int fd; __uint32_t u32; __uint64_t u64; } epoll_data_t; // 感兴趣的事件和被触发的事件 struct epoll_event { __uint32_t events; // Epoll events epoll_data_t data; // User data variable }; 如上所示，对于Epoll Events，其可以是以下几个宏的集合： EPOLLIN：表示对应的文件描述符可读（包括对端Socket）； EPOLLOUT：表示对应的文件描述符可写； EPOLLPRI：表示对应的文件描述符有紧急数据可读（带外数据）； EPOLLERR：表示对应的文件描述符发生错误； EPOLLHUP：表示对应的文件描述符被挂断； EPOLLET：将EPOLL设为边缘触发（Edge Triggered），这是相对于水平触发（Level Triggered）而言的。 EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket，需要再次 3、epoll_wait #include <sys/epoll.h> int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout); 收集在epoll监控的事件中已经发生的事件。参数events是分配好的epoll_event结构体数组，epoll将会把发生的事件赋值到events数组中（events不可以是空指针，内核只负责把数据赋值到这个event数组中，不会去帮助我们在用户态分配内存）。maxevents告诉内核这个events数组有多大，这个maxevents的值不能大于创建epoll_create时的size。参数timeout是超时时间（毫秒）。如果函数调用成功，则返回对应IO上已准备好的文件描述符数目，如果返回0则表示已经超时。 三、epoll工作模式 1. LT模式（Level Triggered，水平触发） 该模式是epoll的缺省工作模式，其同时支持阻塞和非阻塞socket。内核会告诉开发者一个文件描述符是否就绪，如果开发者不采取任何操作，内核仍会一直通知。 2. ET模式（Edge Triggered，边缘触发） 该模式是一种高速处理模式，当且仅当状态发生变化时才会获得通知。在该模式下，其假定开发者在接收到一次通知后，会完整地处理该事件，因此内核将不再通知这一事件。注意，缓冲区中还有未处理的数据不能说是状态变化，因此，在ET模式下，开发者如果只读取了一部分数据，其将再也得不到通知了。正确的做法是，开发者自己确认读完了所有的字节（一直调用read/write直到出错EAGAGIN为止）。 Nginx默认采用的就是ET（边缘触发）。 四、epoll高效性探讨 epoll的高效性主要体现在以下三个方面： （1）select/poll每次调用都要传递所要监控的所有fd给select/poll系统调用，这意味着每次调用select/poll时都要将fd列表从用户空间拷贝到内核，当fd数目很多时，这会造成性能低效。对于epoll_wait，每次调用epoll_wait时，其不需要将fd列表传递给内核，epoll_ctl不需要每次都拷贝所有的fd列表，只需要进行增量式操作。因此，在调用epoll_create函数之后，内核已经在内核开始准备数据结构用于存放需要监控的fd了。其后，每次epoll_ctl只是对这个数据结构进行简单的维护操作即可。 （2）内核使用slab机制，为epoll提供了快速的数据结构。在内核里，一切都是文件。因此，epoll向内核注册了一个文件系统，用于存储所有被监控的fd。当调用epoll_create时，就会在这个虚拟的epoll文件系统中创建一个file节点。epoll在被内核初始化时，同时会分配出epoll自己的内核告诉cache区，用于存放每个我们希望监控的fd。这些fd会以红黑树的形式保存在内核cache里，以支持快速查找、插入和删除。这个内核高速cache，就是建立连续的物理内存页，然后在之上建立slab层，简单的说，就是物理上分配好想要的size的内存对象，每次使用时都使用空闲的已分配好的对象。 （3）当调用epoll_ctl往epfd注册百万个fd时，epoll_wait仍然能够快速返回，并有效地将发生的事件fd返回给用户。原因在于，当我们调用epoll_create时，内核除了帮我们在epoll文件系统新建file节点，同时在内核cache创建红黑树用于存储以后由epoll_ctl传入的fd外，还会再建立一个list链表，用于存储准备就绪的事件。当调用epoll_wait时，仅仅观察这个list链表中有无数据即可。如果list链表中有数据，则返回这个链表中的所有元素；如果list链表中没有数据，则sleep然后等到timeout超时返回。所以，epoll_wait非常高效，而且，通常情况下，即使我们需要监控百万计的fd，但大多数情况下，一次也只返回少量准备就绪的fd而已。因此，每次调用epoll_wait，其仅需要从内核态复制少量的fd到用户空间而已。那么，这个准备就绪的list链表是怎么维护的呢？过程如下：当我们执行epoll_ctl时，除了把fd放入到epoll文件系统里file对象对应的红黑树之外，还会给内核中断处理程序注册一个回调函数，其告诉内核，如果这个fd的中断到了，就把它放到准备就绪的list链表中。 如此，一棵红黑树、一张准备就绪的fd链表以及少量的内核cache，就帮我们解决了高并发下fd的处理问题。 总结一下： 执行epoll_create时，创建了红黑树和就绪list链表； 执行epoll_ctl时，如果增加fd，则检查在红黑树中是否存在，存在则立即返回，不存在则添加到红黑树中，然后向内核注册回调函数，用于当中断事件到来时向准备就绪的list链表中插入数据。 执行epoll_wait时立即返回准备就绪链表里的数据即可。 五、epoll源码分析 eventpoll_init过程： static int __init eventpoll_init(void) { int error; init_MUTEX(&epsem); /* Initialize the structure used to perform safe poll wait head wake ups */ ep_poll_safewake_init(&psw); /* Allocates slab cache used to allocate "struct epitem" items */ epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem), 0, SLAB_HWCACHE_ALIGN|EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); /* Allocates slab cache used to allocate "struct eppoll_entry" */ pwq_cache = kmem_cache_create("eventpoll_pwq", sizeof(struct eppoll_entry), 0, EPI_SLAB_DEBUG|SLAB_PANIC, NULL, NULL); /* * Register the virtual file system that will be the source of inodes * for the eventpoll files */ error = register_filesystem(&eventpoll_fs_type); if (error) goto epanic; /* Mount the above commented virtual file system */ eventpoll_mnt = kern_mount(&eventpoll_fs_type); error = PTR_ERR(eventpoll_mnt); if (IS_ERR(eventpoll_mnt)) goto epanic; DNPRINTK(3, (KERN_INFO "[%p] eventpoll: successfully initialized.\n", current)); return 0; epanic: panic("eventpoll_init() failed\n"); } 其中，epoll用slab分配器kmem_cache_create分配内存用于存放struct epitem和struct eppoll_entry。 当向系统中添加一个fd时，就会创建一个epitem结构体，这是内核管理epoll的基本数据结构： /* * Each file descriptor added to the eventpoll interface will * have an entry of this type linked to the hash. */ struct epitem { /* RB-Tree node used to link this structure to the eventpoll rb-tree */ struct rb_node rbn; // 用于主结构管理的红黑树 /* List header used to link this structure to the eventpoll ready list */ struct list_head rdllink; // 事件就绪队列 /* The file descriptor information this item refers to */ struct epoll_filefd ffd; // 用于主结构中的链表 /* Number of active wait queue attached to poll operations */ int nwait; // 事件个数 /* List containing poll wait queues */ struct list_head pwqlist; // 双向链表，保存着被监控文件的等待队列 /* The "container" of this item */ struct eventpoll *ep; // 该项属于哪个主结构体 /* The structure that describe the interested events and the source fd */ struct epoll_event event; // 注册的感兴趣的时间 /* * Used to keep track of the usage count of the structure. This avoids * that the structure will desappear from underneath our processing. */ atomic_t usecnt; /* List header used to link this item to the "struct file" items list */ struct list_head fllink; /* List header used to link the item to the transfer list */ struct list_head txlink; /* * This is used during the collection/transfer of events to userspace * to pin items empty events set. */ unsigned int revents; }; 对于每个epfd，其对应的数据结构为： /* * This structure is stored inside the "private_data" member of the file * structure and rapresent the main data sructure for the eventpoll * interface. */ struct eventpoll { /* Protect the this structure access */ rwlock_t lock; /* * This semaphore is used to ensure that files are not removed * while epoll is using them. This is read-held during the event * collection loop and it is write-held during the file cleanup * path, the epoll file exit code and the ctl operations. */ struct rw_semaphore sem; /* Wait queue used by sys_epoll_wait() */ wait_queue_head_t wq; /* Wait queue used by file->poll() */ wait_queue_head_t poll_wait; /* List of ready file descriptors */ struct list_head rdllist; // 准备就绪的事件链表 /* RB-Tree root used to store monitored fd structs */ struct rb_root rbr; // 用于管理所有fd的红黑树（根节点） }; eventpoll在epoll_create时创建： /* * It opens an eventpoll file descriptor by suggesting a storage of "size" * file descriptors. The size parameter is just an hint about how to size * data structures. It won't prevent the user to store more than "size" * file descriptors inside the epoll interface. It is the kernel part of * the userspace epoll_create(2). */ asmlinkage long sys_epoll_create(int size) { int error, fd; struct eventpoll *ep; struct inode *inode; struct file *file; DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_create(%d)\n", current, size)); /* * Sanity check on the size parameter, and create the internal data * structure ( "struct eventpoll" ). */ error = -EINVAL; if (size <= 0 || (error = ep_alloc(&ep)) != 0) // ep_alloc为eventpoll分配内存并初始化 goto eexit_1; /* * Creates all the items needed to setup an eventpoll file. That is, * a file structure, and inode and a free file descriptor. */ error = ep_getfd(&fd, &inode, &file, ep); // 创建于eventpoll相关的数据结构，包括file、inode和fd等信息 if (error) goto eexit_2; DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_create(%d) = %d\n", current, size, fd)); return fd; eexit_2: ep_free(ep); kfree(ep); eexit_1: DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_create(%d) = %d\n", current, size, error)); return error; } 如上，内核中维护了一棵红黑树，大致结构如下： 下面是epoll_ctl函数过程： /* * The following function implements the controller interface for * the eventpoll file that enables the insertion/removal/change of * file descriptors inside the interest set. It represents * the kernel part of the user space epoll_ctl(2). */ asmlinkage long sys_epoll_ctl(int epfd, int op, int fd, struct epoll_event __user *event) { int error; struct file *file, *tfile; struct eventpoll *ep; struct epitem *epi; struct epoll_event epds; DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p)\n", current, epfd, op, fd, event)); error = -EFAULT; if (ep_op_hash_event(op) && copy_from_user(&epds, event, sizeof(struct epoll_event))) goto eexit_1; /* Get the "struct file *" for the eventpoll file */ error = -EBADF; file = fget(epfd); // 获取epfd对应的文件 if (!file) goto eexit_1; /* Get the "struct file *" for the target file */ tfile = fget(fd); // 获取fd对应的文件 if (!tfile) goto eexit_2; /* The target file descriptor must support poll */ error = -EPERM; if (!tfile->f_op || !tfile->f_op->poll) goto eexit_3; /* * We have to check that the file structure underneath the file descriptor * the user passed to us _is_ an eventpoll file. And also we do not permit * adding an epoll file descriptor inside itself. */ error = -EINVAL; if (file == tfile || !is_file_epoll(file)) goto eexit_3; /* * At this point it is safe to assume that the "private_data" contains * our own data structure. */ ep = file->private_data; down_write(&ep->sem); /* Try to lookup the file inside our hash table */ epi = ep_find(ep, tfile, fd); // 在哈希表中查询，防止重复添加 error = -EINVAL; switch (op) { case EPOLL_CTL_ADD: // 添加节点，调用ep_insert函数 if (!epi) { epds.events |= POLLERR | POLLHUP; error = ep_insert(ep, &epds, tfile, fd); } else error = -EEXIST; break; case EPOLL_CTL_DEL: // 删除节点，调用ep_remove函数 if (epi) error = ep_remove(ep, epi); else error = -ENOENT; break; case EPOLL_CTL_MOD: // 修改节点，调用ep_modify函数 if (epi) { epds.events |= POLLERR | POLLHUP; error = ep_modify(ep, epi, &epds); } else error = -ENOENT; break; } /* * The function ep_find() increments the usage count of the structure * so, if this is not NULL, we need to release it. */ if (epi) ep_release_epitem(epi); up_write(&ep->sem); eexit_3: fput(tfile); eexit_2: fput(file); eexit_1: DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p) = %d\n", current, epfd, op, fd, event, error)); return error; } 对于ep_insert函数，基本代码如下： static int ep_insert(struct eventpoll *ep, struct epoll_event *event, struct file *tfile, int fd) { int error, revents, pwake = 0; unsigned long flags; struct epitem *epi; struct ep_pqueue epq; error = -ENOMEM; // 分配一个epitem结构体来保存每个加入的fd if (!(epi = kmem_cache_alloc(epi_cache, SLAB_KERNEL))) goto eexit_1; /* Item initialization follow here ... */ // 初始化结构体 ep_rb_initnode(&epi->rbn); INIT_LIST_HEAD(&epi->rdllink); INIT_LIST_HEAD(&epi->fllink); INIT_LIST_HEAD(&epi->txlink); INIT_LIST_HEAD(&epi->pwqlist); epi->ep = ep; ep_set_ffd(&epi->ffd, tfile, fd); epi->event = *event; atomic_set(&epi->usecnt, 1); epi->nwait = 0; /* Initialize the poll table using the queue callback */ epq.epi = epi; // 安装poll回调函数 init_poll_funcptr(&epq.pt, ep_ptable_queue_proc); /* * Attach the item to the poll hooks and get current event bits. * We can safely use the file* here because its usage count has * been increased by the caller of this function. */ // 将当前item添加至poll hook中，然后获取当前event位 revents = tfile->f_op->poll(tfile, &epq.pt); /* * We have to check if something went wrong during the poll wait queue * install process. Namely an allocation for a wait queue failed due * high memory pressure. */ if (epi->nwait < 0) goto eexit_2; /* Add the current item to the list of active epoll hook for this file */ spin_lock(&tfile->f_ep_lock); list_add_tail(&epi->fllink, &tfile->f_ep_links); spin_unlock(&tfile->f_ep_lock); /* We have to drop the new item inside our item list to keep track of it */ write_lock_irqsave(&ep->lock, flags); /* Add the current item to the rb-tree */ ep_rbtree_insert(ep, epi); /* If the file is already "ready" we drop it inside the ready list */ if ((revents & event->events) && !ep_is_linked(&epi->rdllink)) { list_add_tail(&epi->rdllink, &ep->rdllist); /* Notify waiting tasks that events are available */ if (waitqueue_active(&ep->wq)) wake_up(&ep->wq); if (waitqueue_active(&ep->poll_wait)) pwake++; } write_unlock_irqrestore(&ep->lock, flags); /* We have to call this outside the lock */ if (pwake) ep_poll_safewake(&psw, &ep->poll_wait); DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_insert(%p, %p, %d)\n", current, ep, tfile, fd)); return 0; eexit_2: ep_unregister_pollwait(ep, epi); /* * We need to do this because an event could have been arrived on some * allocated wait queue. */ write_lock_irqsave(&ep->lock, flags); if (ep_is_linked(&epi->rdllink)) ep_list_del(&epi->rdllink); write_unlock_irqrestore(&ep->lock, flags); kmem_cache_free(epi_cache, epi); eexit_1: return error; } 其中，init_poll_funcptr和tfile->f_op->poll将ep_ptable_queue_proc注册到epq.pt中的qproc中。 ep_ptable_queue_proc函数设置了等待队列的ep_poll_callback回调函数。在设备硬件数据到来时，硬件中断函数唤醒该等待队列上等待的进程时，会调用唤醒函数ep_poll_callback。 ep_poll_callback函数主要的功能是将被监视文件的等待事件就绪时，将文件对应的epitem实例添加到就绪队列中，当用户调用epoll_wait时，内核会将就绪队列中的事件报告给用户。 epoll_wait的实现如下： /* * Implement the event wait interface for the eventpoll file. It is the kernel * part of the user space epoll_wait(2). */ asmlinkage long sys_epoll_wait(int epfd, struct epoll_event __user *events, int maxevents, int timeout) { int error; struct file *file; struct eventpoll *ep; DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_wait(%d, %p, %d, %d)\n", current, epfd, events, maxevents, timeout)); /* The maximum number of event must be greater than zero */ if (maxevents <= 0 || maxevents > MAX_EVENTS) // 检查maxevents参数 return -EINVAL; /* Verify that the area passed by the user is writeable */ // 检查用户空间传入的events指向的内存是否可写 if (!access_ok(VERIFY_WRITE, events, maxevents * sizeof(struct epoll_event))) { error = -EFAULT; goto eexit_1; } /* Get the "struct file *" for the eventpoll file */ error = -EBADF; file = fget(epfd); // 获取epfd对应的eventpoll文件的file实例，file结构是在epoll_create中创建的 if (!file) goto eexit_1; /* * We have to check that the file structure underneath the fd * the user passed to us _is_ an eventpoll file. */ error = -EINVAL; if (!is_file_epoll(file)) goto eexit_2; /* * At this point it is safe to assume that the "private_data" contains * our own data structure. */ ep = file->private_data; /* Time to fish for events ... */ // 核心处理函数 error = ep_poll(ep, events, maxevents, timeout); eexit_2: fput(file); eexit_1: DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_wait(%d, %p, %d, %d) = %d\n", current, epfd, events, maxevents, timeout, error)); return error; } 其中，调用ep_poll函数，具体流程如下： static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, int maxevents, long timeout) { int res, eavail; unsigned long flags; long jtimeout; wait_queue_t wait; /* * Calculate the timeout by checking for the "infinite" value ( -1 ) * and the overflow condition. The passed timeout is in milliseconds, * that why (t * HZ) / 1000. */ jtimeout = (timeout < 0 || timeout >= EP_MAX_MSTIMEO) ? MAX_SCHEDULE_TIMEOUT : (timeout * HZ + 999) / 1000; retry: write_lock_irqsave(&ep->lock, flags); res = 0; if (list_empty(&ep->rdllist)) { /* * We don't have any available event to return to the caller. * We need to sleep here, and we will be wake up by * ep_poll_callback() when events will become available. */ init_waitqueue_entry(&wait, current); add_wait_queue(&ep->wq, &wait); for (;;) { /* * We don't want to sleep if the ep_poll_callback() sends us * a wakeup in between. That's why we set the task state * to TASK_INTERRUPTIBLE before doing the checks. */ set_current_state(TASK_INTERRUPTIBLE); if (!list_empty(&ep->rdllist) || !jtimeout) break; if (signal_pending(current)) { res = -EINTR; break; } write_unlock_irqrestore(&ep->lock, flags); jtimeout = schedule_timeout(jtimeout); write_lock_irqsave(&ep->lock, flags); } remove_wait_queue(&ep->wq, &wait); set_current_state(TASK_RUNNING); } /* Is it worth to try to dig for events ? */ eavail = !list_empty(&ep->rdllist); write_unlock_irqrestore(&ep->lock, flags); /* * Try to transfer events to user space. In case we get 0 events and * there's still timeout left over, we go trying again in search of * more luck. */ if (!res && eavail && !(res = ep_events_transfer(ep, events, maxevents)) && jtimeout) goto retry; return res; } ep_send_events函数用于向用户空间发送就绪事件。ep_send_events函数将用户传入的内存简单封装到ep_send_events_data结构中，然后调用ep_scan_ready_list将就绪队列中的事件传入用户空间的内存。 六、参考 Epoll详解及源码分析——CSDN博客
-
发表了文章 2018-06-03
TCP TIME_WAIT状态解析及问题解决
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/zhaobryant/article/details/80557158 一、TCP四次挥手过程 TCP在建立连接时需要握手，同理，在关闭连接的时候也需要握手。 具体如下所示： 由于TCP连接是双向的，所以在关闭连接的时候，两个方向各自都需要关闭。先发FIN包的一方执行的是主动关闭，后发送FIN包的一方执行的是被动关闭。主动关闭的一方会进入TIME_WAIT状态，并且在此状态停留2MSL时长。 对于MSL，其指的是报文段的最大生存时间。如果报文段在网络中活动了MSL时间，还没有被接收，那么就会被丢弃。关于MSL的大小，RFC 793协议中给出的建议是2分钟，不过Linux中，通常是半分钟。 对于TIME_WAIT状态，有下图： 我们关注几个概念： TIME_WAIT的产生条件：主动关闭方在发送四次挥手的最后一个ACK后会变为TIME_WAIT状态，持续时间为2MSL（Linux中一个MSL是30秒，是不可配置的）。 TIME_WAIT持续两个MSL的作用：首先，可靠安全地关闭TCP连接。比如网络拥塞，如果主动关闭方最后一个ACK没有被被动关闭方接收到，这时被动关闭方会对FIN进行超时重传，在这时尚未关闭的TIME_WAIT就会把这些尾巴问题处理掉，不至于对新连接及其他服务产生影响。其次，防止由于没有持续TIME_WAIT时间导致的新的TCP连接建立起来，延迟的FIN重传包会干扰新的连接。 TIME_WAIT占用的资源：少量内存（大概4K）和一个文件描述符fd。 TIME_WAIT关闭的危害：首先，当网络情况不好时，如果主动方无TIME_WAIT等待，关闭前个连接后，主动方与被动方又建立起新的TCP连接，这时被动方重传或延时过来的FIN包到达后会直接影响新的TCP连接；其次，当网络情况不好时，同时没有TIME_WAIT等待时，关闭连接后无新连接，那么当接收到被动方重传或延迟的FIN包后，会给被动方回送一个RST包，可能会影响被动方其他的服务连接。 TCP: time wait bucket table overflow产生原因及影响：原因是当TIME_WAIT数超过了Linux系统的TW数量的阈值。危害是超过阈值后，系统会把多余的TIME_WAIT Socket删除掉，并且显示警告信息。如果是NAT网络且又存在大量访问时，会产生各种连接不稳定断开的情况。 二、相关参数优化调整 1. tcp_tw_recycle 顾名思义就是回收TIME_WAIT连接。可以说这个内核参数已经变成了处理TIME_WAIT的万金油，如果你在网络上搜索TIME_WAIT的解决方案，十有八九会推荐设置它，不过这里隐藏着一个不易察觉的陷阱：当多个客户端通过NAT方式联网并与服务端交互时，服务端看到的是同一个IP，也就是说对服务端而言这些客户端实际上等同于一个，由于这些客户端的时间戳可能存在差异，所以从服务端的视角看，便可能出现时间戳错乱的现象，进而直接导致时间戳小的数据包被丢弃。参考：tcp_tw_recycle和tcp_timestamps导致connect失败问题。 tcp_tw_recycle = 0 备注：建议不要开启该选项，现在互联网NAT使用很多，可能导致无法进行三次握手。 开启后在3.5*RTO（RTO时间是根据RTT时间计算而来）内回收TIME_WAIT，并60s内同一源ip主机的socket connect请求中的timestamp必须是递增的，对于服务端，同一个源ip可能会是NAT后很多机器，这些机器timestamp递增性无可保证，服务器会拒绝非递增请求连接，直接导致不能三次握手。 2. tcp_tw_reuse 顾名思义就是复用TIME_WAIT连接。当创建新连接的时候，如果可能的话会考虑复用相应的TIME_WAIT连接。通常认为tcp_tw_reuse比tcp_tw_recycle安全一些，这是因为一来TIME_WAIT创建时间必须超过一秒才可能会被复用；二来只有连接的时间戳是递增的时候才会被复用。官方文档里是这样说的：如果从协议视角看它是安全的，那么就可以使用。这简直就是外交辞令啊！按我的看法，如果网络比较稳定，比如都是内网连接，那么就可以尝试使用。 不过需要注意的是在哪里使用，既然我们要复用连接，那么当然应该在连接的发起方使用，而不能在被连接方使用。举例来说：客户端向服务端发起HTTP请求，服务端响应后主动关闭连接，于是TIME_WAIT便留在了服务端，此类情况使用tcp_tw_reuse是无效的，因为服务端是被连接方，所以不存在复用连接一说。让我们延伸一点来看，比如说服务端是PHP，它查询另一个MySQL服务端，然后主动断开连接，于是TIME_WAIT就落在了PHP一侧，此类情况下使用tcp_tw_reuse是有效的，因为此时PHP相对于MySQL而言是客户端，它是连接的发起方，所以可以复用连接。 说明：如果使用tcp_tw_reuse，请激活tcp_timestamps，否则无效。 tcp_timestamps = 1 tcp_tw_reuse = 1 3. tcp_max_tw_buckets 顾名思义就是控制TIME_WAIT总数。官网文档说这个选项只是为了阻止一些简单的DoS攻击，平常不要人为的降低它。如果缩小了它，那么系统会将多余的TIME_WAIT删除掉，日志里会显示：TCP: time wait bucket table overflow。 需要提醒大家的是物极必反，曾经看到有人把「tcp_max_tw_buckets」设置成0，也就是说完全抛弃TIME_WAIT，这就有些冒险了，用一句围棋谚语来说：入界宜缓。 当出现TCP: time wait bucket table overflow时，尽量调大下面参数： tcp_max_tw_buckets = 256000 三、总结 有时候，如果我们换个角度去看问题，往往能得到四两拨千斤的效果。前面提到的例子：客户端向服务端发起HTTP请求，服务端响应后主动关闭连接，于是TIME_WAIT便留在了服务端。这里的关键在于主动关闭连接的是服务端！在关闭TCP连接的时候，先出手的一方注定逃不开TIME_WAIT的宿命，套用一句歌词：把我的悲伤留给自己，你的美丽让你带走。如果客户端可控的话，那么在服务端打开KeepAlive，尽可能不让服务端主动关闭连接，而让客户端主动关闭连接，如此一来问题便迎刃而解了。 四、补充 RST简介： 在TCP协议中，RST表示复位，用来关闭异常连接。发送RST包关闭连接时，不必等到缓冲区的数据包都发送出去，直接丢弃缓存区的数据包而发送RST包。接收端在接收到RST包后，不必发送ACK包来确认。 出现RST的几种情况： 端口未打开：客户端连接服务器程序未打开的端口。当客户端向服务器的某个端口发送SYN请求后，但是服务器上并没有打开该端口，因此其会向客户端发送RST。但是，并不是所有的操作系统都会发送RST给客户端，win7就会直接忽略该SYN报文。 在一个已关闭的socket上收到数据：如果某个socket已经关闭，但是依然接收数据，那么也会产生RST。 接收缓冲区还存在数据时，关闭连接：在请求方请求数据，未处理完缓冲区中的所有数据，就请求关闭连接时，请求方不会如预期的发送FIN包，进入4路关闭逻辑，而是可能会直接发送一个RST包强制完成连接的关闭。 参考：https://my.oschina.net/costaxu/blog/127394 参考文献 http://blog.csdn.net/dog250/article/details/13760985 http://blog.sina.com.cn/s/blog_781b0c850100znjd.html https://huoding.com/2013/12/31/316 http://benpaozhe.blog.51cto.com/10239098/1767612
-
发表了文章 2018-06-03
架构文摘：消息队列设计精要
消息队列已经逐渐成为企业IT系统内部通信的核心手段。它具有低耦合、可靠投递、广播、流量控制、最终一致性等一系列功能，成为异步RPC的主要手段之一。 当今市面上有很多主流的消息中间件，如老牌的ActiveMQ、RabbitMQ，炙手可热的Kafka，阿里巴巴自主开发的Notify、MetaQ、RocketMQ等。 本文不会一一介绍这些消息队列的所有特性，而是探讨一下自主开发设计一个消息队列时，你需要思考和设计的重要方面。过程中我们会参考这些成熟消息队列的很多重要思想。 本文首先会阐述什么时候你需要一个消息队列，然后以Push模型为主，从零开始分析设计一个消息队列时需要考虑到的问题，如RPC、高可用、顺序和重复消息、可靠投递、消费关系解析等。同时，我们也会分析以Kafka为代表的Pull模型所具备的优点。最后是一些高级主题，如用批量/异步提高性能、Pull模型的系统设计理念、存储子系统的设计、流量控制的设计、公平调度的实现等。 一、何时需要消息队列 当你需要使用消息队列时，首先需要考虑它的必要性。可以使用mq的场景有很多，最常用的几种，是做业务解耦/最终一致性/广播/错峰流控等。反之，如果需要强一致性，关注业务逻辑的处理结果，则RPC显得更为合适。 1、解耦 解耦是消息队列要解决的最本质问题。所谓解耦，简单点将就是一个事务，只关心核心流程。而需要依赖其他系统但不那么重要的事情，有通知即可，无需等待结果。换句话说，基于消息的模型，关心的是“通知”，而非“处理”。 比如在美团旅游，我们有一个产品中心，产品中心上游对接的是主站、移动后台、旅游供应链等各个数据源；下游对接的是筛选系统、API系统等展示系统。当上游的数据发生变更的时候，如果不使用消息系统，势必要调用我们的接口来更新数据，就特别依赖产品中心接口的稳定性和处理能力。但其实，作为旅游的产品中心，也许只有对于旅游自建供应链，产品中心更新成功才是他们关心的事情。而对于团购等外部系统，产品中心更新成功也好、失败也罢，并不是他们的职责所在。他们只需要保证在信息变更的时候通知到我们就好了。 而我们的下游，可能有更新索引、刷新缓存等一系列需求。对于产品中心来说，这也不是我们的职责所在。说白了，如果他们定时来拉取数据，也能保证数据的更新，只是实时性没有那么强。但使用接口方式去更新他们的数据，显然对于产品中心来说太过于“重量级”了，只需要发布一个产品ID变更的通知，由下游系统来处理，可能更为合理。 再举一个例子，对于我们的订单系统，订单最终支付成功之后可能需要给用户发送短信积分什么的，但其实这已经不是我们系统的核心流程了。如果外部系统速度偏慢（比如短信网关速度不好），那么主流程的时间会加长很多，用户肯定不希望点击支付过好几分钟才看到结果。那么我们只需要通知短信系统“我们支付成功了”，不一定非要等待它处理完成。 2、最终一致性 最终一致性指的是两个系统的状态保持一致，要么都成功，要么都失败。当然有时间限制，理论上越快越好，但实际上存在各种异常的情况下，可能会有一定的延迟达到最终一致性，但最后两个系统的状态是一样的。 业界有一些为“最终一致性”而生的消息队列，如Notify（阿里）、QMQ（去哪儿）等，其设计初衷，就是为了交易系统中的高可靠通知。 以一个银行的转账过程来理解最终一致性，转账的需求很简单，如果A系统扣钱成功，则B系统加钱一定成功。反之则一起回滚，像什么都没发生一样。 然而，这个过程中存在很多可能的意外： A扣钱成功，调用B加钱接口失败。 A扣钱成功，调用B加钱接口虽然成功，但获取最终结果时网络异常引起超时。 A扣钱成功，B加钱失败，A想回滚扣的钱，但A机器down机。 可见，想把这件看似简单的事真正做成，真的不容易。所有跨VM的一致性问题，从技术的角度通用的解决方案是： 强一致性，分布式事务，但落地太难且成本太高。 最终一致性，主要是用“记录”和“补偿”的方式。在做所有的不确定的事情之前，先把事情记录下来，然后去做不确定的事情，结果可能是：成功、失败或是不确定，“不确定”（例如超时等）可以等价为失败。成功就可以把记录的东西清理掉了，对于失败和不确定，可以依靠定时任务等方式把所有失败的事情重新再做一遍，直到成功为止。 回到刚才的例子，系统在A扣钱成功的情况下，把要给B“通知”这件事记录备案（为了保证最高的可靠性可以把通知B系统加钱和扣钱成功这两件事维护在一个本地事务里），通知成功则删除这条记录，通知失败或不确定则依靠定时任务补偿性地通知我们，直到我们把状态更新成正确的为止。 整个这个模型依然可以基于RPC来做，但可以抽象成一个统一的模型，基于消息队列来做一个“企业总线”。 具体来说，本地事务维护业务变化和通知消息，一起落地（失败则一起回滚），然后RPC到达broker，在broker成功落地后，RPC返回成功，本地消息可以删除。否则本地消息一直靠定时任务轮询不断重发，这样就保证了消息可靠落地broker。 Broker往Consumer发送消息的过程类似，一直发送消息，直到Consumer发送消费成功确认。 我们先不理会重复消息的问题，通过两次消息落地加补偿，下游是一定可以收到消息的。然后依赖状态机版本号等方式做判重，更新自己的业务，就实现了最终一致性。 最终一致性不是消息队列的必备特性，但确实可以依靠消息队列来做最终一致性的事情。另外，所有不保证100%不丢消息的消息队列，理论上无法实现最终一致性。好吧，应该说理论上的100%，排除系统严重故障和bug。 像Kafka一类的设计，在设计层面上就有丢消息的可能（比如定时刷盘，如果掉电就会丢消息）。哪怕只丢千分之一的消息，业务也必须用其他的手段来保证结果正确。 3、广播 消息队列的基本功能之一是进行广播。如果没有消息队列，每当一个新的业务方接入，我们都要联调一次新接口。有了消息队列，我们只需要关心消息是否送达了队列，至于谁希望订阅，是下游的事情，无疑极大地减少了开发和联调的工作量。 比如本文开始提到的产品中心发布产品变更的消息，以及景点库很多去重更新的消息，可能“关心”方有很多个，但产品中心和景点库只需要发布变更消息即可，谁关心谁接入。 4、错峰与流控 试想上下游对于事情的处理能力是不同的。比如，Web前端每秒承受上千万的请求，并不是什么神奇的事情，只需要加多一点机器，再搭建一些LVS负载均衡设备和Nginx等即可。但数据库的处理能力却十分有限，即使使用SSD加分库分表，单机的处理能力仍然在万级。由于成本的考虑，我们不能奢求数据库的机器数量追上前端。 这种问题同样存在于系统和系统之间，如短信系统可能由于短板效应，速度卡在网关上（每秒几百次请求），跟前端的并发量不是一个数量级。但用户晚上个半分钟左右收到短信，一般是不会有太大问题的。如果没有消息队列，两个系统之间通过协商、滑动窗口等复杂的方案也不是说不能实现。但系统复杂性指数级增长，势必在上游或者下游做存储，并且要处理定时、拥塞等一系列问题。而且每当有处理能力有差距的时候，都需要单独开发一套逻辑来维护这套逻辑。所以，利用中间系统转储两个系统的通信内容，并在下游系统有能力处理这些消息的时候，再处理这些消息，是一套相对较通用的方式。 总而言之，消息队列不是万能的。对于需要强事务保证而且延迟敏感的，RPC是优于消息队列的。 对于一些无关痛痒，或者对于别人非常重要但是对于自己不是那么关心的事情，可以利用消息队列去做。 支持最终一致性的消息队列，能够用来处理延迟不那么敏感的“分布式事务”场景，而且相对于笨重的分布式事务，可能是更优的处理方式。 当上下游系统处理能力存在差距的时候，利用消息队列做一个通用的“漏斗”。在下游有能力处理的时候，再进行分发。 如果下游有很多系统关心你的系统发出的通知的时候，果断地使用消息队列吧。 二、如何设计一个消息队列 1、综述 我们现在明确了消息队列的使用场景，下一步就是如何设计实现一个消息队列了。 基于消息的系统模型，不一定需要Broker(消息队列服务端)。市面上的的Akka（actor模型）、ZeroMQ等，其实都是基于消息的系统设计范式，但是没有Broker。 我们之所以要设计一个消息队列，并且配备broker，无外乎要做两件事情： 消息的转储，在更合适的时间点投递，或者通过一系列手段辅助消息最终能送达消费者。 规范一种范式和通用的模式，以满足解耦、最终一致性、错峰等需求。 掰开了揉碎了看，最简单的消息队列可以做成一个消息转发器，把一次RPC做成两次RPC。发送者把消息投递到服务端（以下简称Broker），服务端再将消息转发一手到接收端，就是这么简单。 一般来讲，设计消息队列的整体思路是先build一个整体的数据流,例如producer发送给broker,broker发送给consumer,consumer回复消费确认，broker删除/备份消息等。 利用RPC将数据流串起来，然后考虑RPC的高可用性，尽量做到无状态，方便水平扩展。 之后考虑如何承载消息堆积，然后在合适的时机投递消息，而处理堆积的最佳方式，就是存储，存储的选型需要综合考虑性能/可靠性和开发维护成本等诸多因素。 为了实现广播功能，我们必须要维护消费关系，可以利用zookeeper/config server等保存消费关系。 在完成了上述几个功能后，消息队列基本就实现了。然后我们可以考虑一些高级特性，如可靠投递，事务特性，性能优化等。 下面我们会以设计消息队列时重点考虑的模块为主线，穿插灌输一些消息队列的特性实现方法，来具体分析设计实现一个消息队列时的方方面面。 2、实现队列基本功能 RPC通信协议 刚才讲到，所谓消息队列，无外乎两次RPC加一次转储，当然需要消费端最终做消费确认的情况是三次RPC。既然是RPC，就必然牵扯出一系列话题，什么负载均衡啊、服务发现啊、通信协议啊、序列化协议啊，等等。在这一块，我的强烈建议是不要重复造轮子。利用公司现有的RPC框架：Thrift也好，Dubbo也好，或者是其他自定义的框架也好。因为消息队列的RPC，和普通的RPC没有本质区别。当然了，自主利用Memchached或者Redis协议重新写一套RPC框架并非不可（如MetaQ使用了自己封装的Gecko NIO框架，Kafka也用了类似的协议）。但实现成本和难度无疑倍增。排除对效率的极端要求，都可以使用现成的RPC框架。 简单来讲，服务端提供两个RPC服务，一个用来接收消息，一个用来确认消息收到。并且做到不管哪个server收到消息和确认消息，结果一致即可。当然这中间可能还涉及跨IDC的服务的问题。这里和RPC的原则是一致的，尽量优先选择本机房投递。你可能会问，如果producer和consumer本身就在两个机房了，怎么办？首先，broker必须保证感知的到所有consumer的存在。其次，producer尽量选择就近的机房就好了。 高可用 其实所有的高可用，是依赖于RPC和存储的高可用来做的。先来看RPC的高可用，美团的基于MTThrift的RPC框架，阿里的Dubbo等，其本身就具有服务自动发现，负载均衡等功能。而消息队列的高可用，只要保证broker接受消息和确认消息的接口是幂等的，并且consumer的几台机器处理消息是幂等的，这样就把消息队列的可用性，转交给RPC框架来处理了。 那么怎么保证幂等呢？最简单的方式莫过于共享存储。broker多机器共享一个DB或者一个分布式文件/kv系统，则处理消息自然是幂等的。就算有单点故障，其他节点可以立刻顶上。另外failover可以依赖定时任务的补偿，这是消息队列本身天然就可以支持的功能。存储系统本身的可用性我们不需要操太多心，放心大胆的交给DBA们吧！ 对于不共享存储的队列，如Kafka使用分区加主备模式，就略微麻烦一些。需要保证每一个分区内的高可用性，也就是每一个分区至少要有一个主备且需要做数据的同步，关于这块HA的细节，可以参考下篇pull模型消息系统设计。 服务端承载消息堆积的能力 消息到达服务端如果不经过任何处理就到接收者了，broker就失去了它的意义。为了满足我们错峰/流控/最终可达等一系列需求，把消息存储下来，然后选择时机投递就显得是顺理成章的了。 只是这个存储可以做成很多方式。比如存储在内存里，存储在分布式kv系统里，存储在磁盘里，存储在数据库里等等。但归结起来，主要有持久化和非持久化两种。 持久化的形式能更大程度地保证消息的可靠性（如断电等不可抗外力），并且理论上能承载更大限度的消息堆积（外存的空间远大于内存）。 但并不是每种消息都需要持久化存储。很多消息对于投递性能的要求大于可靠性的要求，且数量极大（如日志）。这时候，消息不落地直接暂存内存，尝试几次failover，最终投递出去也未尝不可。 市面上的消息队列普遍两种形式都支持。当然具体的场景还要具体结合公司的业务来看。 存储子系统的选择 我们来看看如果需要数据落地的情况下各种存储子系统的选择。理论上，从速度来看，文件系统>分布式KV（持久化）>分布式文件系统>数据库，而可靠性却截然相反。还是要从支持的业务场景出发作出最合理的选择，如果你们的消息队列是用来支持支付/交易等对可靠性要求非常高，但对性能和量的要求没有这么高，而且没有时间精力专门做文件存储系统的研究，DB是最好的选择。 但是DB受制于IOPS，如果要求单broker 5位数以上的QPS性能，基于文件的存储是比较好的解决方案。整体上可以采用数据文件+索引文件的方式处理，具体这块的设计比较复杂。 分布式KV（如MongoDB，HBase）等，或者持久化的Redis，由于其编程接口较友好，性能也比较可观，如果在可靠性要求不是那么高的场景，也不失为一个不错的选择。 消费关系解析 现在我们的消息队列初步具备了转储消息的能力。下面一个重要的事情就是解析发送接收关系，进行正确的消息投递了。 市面上的消息队列定义了一堆让人晕头转向的名词，如JMS 规范中的Topic/Queue，Kafka里面的Topic/Partition/ConsumerGroup，RabbitMQ里面的Exchange等等。抛开现象看本质，无外乎是单播与广播的区别。所谓单播，就是点到点；而广播，是一点对多点。当然，对于互联网的大部分应用来说，组间广播、组内单播是最常见的情形。 消息需要通知到多个业务集群，而一个业务集群内有很多台机器，只要一台机器消费这个消息就可以了。 当然这不是绝对的，很多时候组内的广播也是有适用场景的，如本地缓存的更新等等。另外，消费关系除了组内组间，可能会有多级树状关系。这种情况太过于复杂，一般不列入考虑范围。所以，一般比较通用的设计是支持组间广播，不同的组注册不同的订阅。组内的不同机器，如果注册一个相同的ID，则单播；如果注册不同的ID(如IP地址+端口)，则广播。 至于广播关系的维护，一般由于消息队列本身都是集群，所以都维护在公共存储上，如config server、zookeeper等。维护广播关系所要做的事情基本是一致的: 发送关系的维护。 发送关系变更时的通知。 3、队列高级特性设计 上面都是些消息队列基本功能的实现，下面来看一些关于消息队列特性相关的内容，不管可靠投递/消息丢失与重复以及事务乃至于性能，不是每个消息队列都会照顾到，所以要依照业务的需求，来仔细衡量各种特性实现的成本，利弊，最终做出最为合理的设计。 可靠投递（最终一致性） 这是个激动人心的话题，完全不丢消息，究竟可不可能？答案是，完全可能，前提是消息可能会重复，并且，在异常情况下，要接受消息的延迟。 方案说简单也简单，就是每当要发生不可靠的事情（RPC等）之前，先将消息落地，然后发送。当失败或者不知道成功失败（比如超时）时，消息状态是待发送，定时任务不停轮询所有待发送消息，最终一定可以送达。 具体来说： Producer往Broker发送消息之前，需要做一次落地。 请求到server后，server确保数据落地后再告诉客户端发送成功。 支持广播的消息队列需要对每个待发送的endpoint，持久化一个发送状态，直到所有endpoint状态都OK才可删除消息。 对于各种不确定（超时、宕机、消息没有送达、送达后数据没落地、数据落地了回复没收到），其实对于发送方来说，都是一件事情，就是消息没有送达。 重推消息所面临的问题就是消息重复。重复和丢失就像两个噩梦，你必须要面对一个。好在消息重复还有处理的机会，消息丢失再想找回就难了。 Anyway，作为一个成熟的消息队列，应该尽量在各个环节减少重复投递的可能性，不能因为重复有解决方案就放纵的乱投递。 最后说一句，不是所有的系统都要求最终一致性或者可靠投递，比如一个论坛系统、一个招聘系统。一个重复的简历或话题被发布，可能比丢失了一个发布显得更让用户无法接受。不断重复一句话，任何基础组件要服务于业务场景。 消费确认 当broker把消息投递给消费者后，消费者可以立即响应我收到了这个消息。但收到了这个消息只是第一步，我能不能处理这个消息却不一定。或许因为消费能力的问题，系统的负荷已经不能处理这个消息；或者是刚才状态机里面提到的消息不是我想要接收的消息，主动要求重发。 把消息的送达和消息的处理分开，这样才真正的实现了消息队列的本质-解耦。所以，允许消费者主动进行消费确认是必要的。当然，对于没有特殊逻辑的消息，默认Auto Ack也是可以的，但一定要允许消费方主动ack。 对于正确消费ack的，没什么特殊的。但是对于reject和error，需要特别说明。reject这件事情，往往业务方是无法感知到的，系统的流量和健康状况的评估，以及处理能力的评估是一件非常复杂的事情。举个极端的例子，收到一个消息开始build索引，可能这个消息要处理半个小时，但消息量却是非常的小。所以reject这块建议做成滑动窗口/线程池类似的模型来控制，消费能力不匹配的时候，直接拒绝，过一段时间重发，减少业务的负担。 但业务出错这件事情是只有业务方自己知道的，就像上文提到的状态机等等。这时应该允许业务方主动ack error，并可以与broker约定下次投递的时间。 重复消息和顺序消息 上文谈到重复消息是不可能100%避免的，除非可以允许丢失，那么，顺序消息能否100%满足呢? 答案是可以，但条件更为苛刻： 允许消息丢失。 从发送方到服务方到接受者都是单点单线程。 所以绝对的顺序消息基本上是不能实现的，当然在METAQ/Kafka等pull模型的消息队列中，单线程生产/消费，排除消息丢失，也是一种顺序消息的解决方案。 一般来讲，一个主流消息队列的设计范式里，应该是不丢消息的前提下，尽量减少重复消息，不保证消息的投递顺序。 谈到重复消息，主要是两个话题： 如何鉴别消息重复，并幂等的处理重复消息。 一个消息队列如何尽量减少重复消息的投递。 先来看看第一个话题，每一个消息应该有它的唯一身份。不管是业务方自定义的，还是根据IP/PID/时间戳生成的MessageId，如果有地方记录这个MessageId，消息到来是能够进行比对就能完成重复的鉴定。数据库的唯一键/bloom filter/分布式KV中的key，都是不错的选择。由于消息不能被永久存储，所以理论上都存在消息从持久化存储移除的瞬间上游还在投递的可能（上游因种种原因投递失败，不停重试，都到了下游清理消息的时间）。这种事情都是异常情况下才会发生的，毕竟是小众情况。两分钟消息都还没送达，多送一次又能怎样呢？幂等的处理消息是一门艺术，因为种种原因重复消息或者错乱的消息还是来到了，说两种通用的解决方案： 版本号。 状态机。 版本号 举个简单的例子，一个产品的状态有上线/下线状态。如果消息1是下线，消息2是上线。不巧消息1判重失败，被投递了两次，且第二次发生在2之后，如果不做重复性判断，显然最终状态是错误的。但是，如果每个消息自带一个版本号。上游发送的时候，标记消息1版本号是1，消息2版本号是2。如果再发送下线消息，则版本号标记为3。下游对于每次消息的处理，同时维护一个版本号。 每次只接受比当前版本号大的消息。初始版本为0，当消息1到达时，将版本号更新为1。消息2到来时，因为版本号>1.可以接收，同时更新版本号为2.当另一条下线消息到来时，如果版本号是3.则是真实的下线消息。如果是1，则是重复投递的消息。如果业务方只关心消息重复不重复，那么问题就已经解决了。但很多时候另一个头疼的问题来了，就是消息顺序如果和想象的顺序不一致。比如应该的顺序是12，到来的顺序是21。则最后会发生状态错误。 参考TCP/IP协议，如果想让乱序的消息最后能够正确的被组织，那么就应该只接收比当前版本号大一的消息。并且在一个session周期内要一直保存各个消息的版本号。 如果到来的顺序是21，则先把2存起来，待1到来后，先处理1，再处理2，这样重复性和顺序性要求就都达到了。 状态机 基于版本号来处理重复和顺序消息听起来是个不错的主意，但凡事总有瑕疵。使用版本号的最大问题是： 对发送方必须要求消息带业务版本号。 下游必须存储消息的版本号，对于要严格保证顺序的。 还不能只存储最新的版本号的消息，要把乱序到来的消息都存储起来。而且必须要对此做出处理。试想一个永不过期的”session”，比如一个物品的状态，会不停流转于上下线。那么中间环节的所有存储就必须保留，直到在某个版本号之前的版本一个不丢的到来，成本太高。 就刚才的场景看，如果消息没有版本号，该怎么解决呢？业务方只需要自己维护一个状态机，定义各种状态的流转关系。例如，”下线”状态只允许接收”上线”消息，“上线”状态只能接收“下线消息”，如果上线收到上线消息，或者下线收到下线消息，在消息不丢失和上游业务正确的前提下。要么是消息发重了，要么是顺序到达反了。这时消费者只需要把“我不能处理这个消息”告诉投递者，要求投递者过一段时间重发即可。而且重发一定要有次数限制，比如5次，避免死循环，就解决了。 举例子说明，假设产品本身状态是下线，1是上线消息，2是下线消息，3是上线消息，正常情况下，消息应该的到来顺序是123，但实际情况下收到的消息状态变成了3123。 那么下游收到3消息的时候，判断状态机流转是下线->上线，可以接收消息。然后收到消息1，发现是上线->上线，拒绝接收，要求重发。然后收到消息2，状态是上线->下线，于是接收这个消息。此时无论重发的消息1或者3到来，还是可以接收。另外的重发，在一定次数拒绝后停止重发，业务正确。 中间件对于重复消息的处理 回归到消息队列的话题来讲。上述通用的版本号/状态机/ID判重解决方案里，哪些是消息队列该做的、哪些是消息队列不该做业务方处理的呢？其实这里没有一个完全严格的定义，但回到我们的出发点，我们保证不丢失消息的情况下尽量少重复消息，消费顺序不保证。那么重复消息下和乱序消息下业务的正确，应该是由消费方保证的，我们要做的是减少消息发送的重复。 我们无法定义业务方的业务版本号/状态机，如果API里强制需要指定版本号，则显得过于绑架客户了。况且，在消费方维护这么多状态，就涉及到一个消费方的消息落地/多机间的同步消费状态问题，复杂度指数级上升，而且只能解决部分问题。 减少重复消息的关键步骤： broker记录MessageId，直到投递成功后清除，重复的ID到来不做处理，这样只要发送者在清除周期内能够感知到消息投递成功，就基本不会在server端产生重复消息。 对于server投递到consumer的消息，由于不确定对端是在处理过程中还是消息发送丢失的情况下，有必要记录下投递的IP地址。决定重发之前询问这个IP，消息处理成功了吗？如果询问无果，再重发。 4、事务 持久性是事务的一个特性，然而只满足持久性却不一定能满足事务的特性。还是拿扣钱/加钱的例子讲。满足事务的一致性特征，则必须要么都不进行，要么都能成功。 解决方案从大方向上有两种： 两阶段提交，分布式事务。 本地事务，本地落地，补偿发送。 分布式事务存在的最大问题是成本太高，两阶段提交协议，对于仲裁down机或者单点故障，几乎是一个无解的黑洞。对于交易密集型或者I/O密集型的应用，没有办法承受这么高的网络延迟，系统复杂性。并且成熟的分布式事务一定构建与比较靠谱的商用DB和商用中间件上，成本也太高。 那如何使用本地事务解决分布式事务的问题呢？以本地和业务在一个数据库实例中建表为例子，与扣钱的业务操作同一个事务里，将消息插入本地数据库。如果消息入库失败，则业务回滚；如果消息入库成功，事务提交。然后发送消息（注意这里可以实时发送，不需要等定时任务检出，以提高消息实时性）。以后的问题就是前文的最终一致性问题所提到的了，只要消息没有发送成功，就一直靠定时任务重试。这里有一个关键的点，本地事务做的，是业务落地和消息落地的事务，而不是业务落地和RPC成功的事务。这里很多人容易混淆，如果是后者，无疑是事务嵌套RPC，是大忌，会有长事务死锁等各种风险。而消息只要成功落地，很大程度上就没有丢失的风险（磁盘物理损坏除外）。而消息只要投递到服务端确认后本地才做删除，就完成了producer->broker的可靠投递，并且当消息存储异常时，业务也是可以回滚的。 本地事务存在两个最大的使用障碍： 配置较为复杂，“绑架”业务方，必须本地数据库实例提供一个库表。 对于消息延迟高敏感的业务不适用。 话说回来，不是每个业务都需要强事务的。扣钱和加钱需要事务保证，但下单和生成短信却不需要事务，不能因为要求发短信的消息存储投递失败而要求下单业务回滚。所以，一个完整的消息队列应该定义清楚自己可以投递的消息类型，如事务型消息，本地非持久型消息，以及服务端不落地的非可靠消息等。对不同的业务场景做不同的选择。另外事务的使用应该尽量低成本、透明化，可以依托于现有的成熟框架，如Spring的声明式事务做扩展。业务方只需要使用@Transactional标签即可。 5、性能相关 异步/同步 首先澄清一个概念，异步，同步和oneway是三件事。异步，归根结底你还是需要关心结果的，但可能不是当时的时间点关心，可以用轮询或者回调等方式处理结果；同步是需要当时关心的结果的；而oneway是发出去就不管死活的方式，这种对于某些完全对可靠性没有要求的场景还是适用的，但不是我们重点讨论的范畴。 回归来看，任何的RPC都是存在客户端异步与服务端异步的，而且是可以任意组合的：客户端同步对服务端异步，客户端异步对服务端异步，客户端同步对服务端同步，客户端异步对服务端同步。对于客户端来说，同步与异步主要是拿到一个Result，还是Future(Listenable)的区别。实现方式可以是线程池，NIO或者其他事件机制，这里先不展开讲。服务端异步可能稍微难理解一点，这个是需要RPC协议支持的。参考servlet 3.0规范，服务端可以吐一个future给客户端，并且在future done的时候通知客户端。 整个过程可以参考下面的代码： 客户端同步服务端异步。 Future<Result> future = request(server);//server立刻返回future synchronized(future){ while(!future.isDone()){ future.wait();//server处理结束后会notify这个future，并修改isdone标志 } } return future.get(); 客户端同步服务端同步。 Result result = request(server); 客户端异步服务端同步(这里用线程池的方式)。 Future<Result> future = executor.submit(new Callable(){public void call<Result>(){ result = request(server); }}) return future; 客户端异步服务端异步。 Future<Result> future = request(server);//server立刻返回future return future 上面说了这么多，其实是想让大家脱离两个误区： RPC只有客户端能做异步，服务端不能。 异步只能通过线程池。 那么，服务端使用异步最大的好处是什么呢？说到底，是解放了线程和I/O。试想服务端有一堆I/O等待处理，如果每个请求都需要同步响应，每条消息都需要结果立刻返回，那么就几乎没法做I/O合并 （当然接口可以设计成batch的，但可能batch发过来的仍然数量较少）。而如果用异步的方式返回给客户端future，就可以有机会进行I/O的合并，把几个批次发过来的消息一起落地（这种合并对于MySQL等允许batch insert的数据库效果尤其明显），并且彻底释放了线程。不至于说来多少请求开多少线程，能够支持的并发量直线提高。 来看第二个误区，返回future的方式不一定只有线程池。换句话说，可以在线程池里面进行同步操作，也可以进行异步操作，也可以不使用线程池使用异步操作（NIO、事件）。 回到消息队列的议题上，我们当然不希望消息的发送阻塞主流程（前面提到了，server端如果使用异步模型，则可能因消息合并带来一定程度上的消息延迟），所以可以先使用线程池提交一个发送请求，主流程继续往下走。但是线程池中的请求关心结果吗？Of course，必须等待服务端消息成功落地，才算是消息发送成功。所以这里的模型，准确地说事客户端半同步半异步（使用线程池不阻塞主流程，但线程池中的任务需要等待server端的返回），server端是纯异步。客户端的线程池wait在server端吐回的future上，直到server端处理完毕，才解除阻塞继续进行。 总结一句，同步能够保证结果，异步能够保证效率，要合理的结合才能做到最好的效率。 批量 谈到批量就不得不提生产者消费者模型。但生产者消费者模型中最大的痛点是：消费者到底应该何时进行消费。大处着眼来看，消费动作都是事件驱动的。主要事件包括： 攒够了一定数量。 到达了一定时间。 队列里有新的数据到来。 对于及时性要求高的数据，可用采用方式3来完成，比如客户端向服务端投递数据。只要队列有数据，就把队列中的所有数据刷出，否则将自己挂起，等待新数据的到来。 在第一次把队列数据往外刷的过程中，又积攒了一部分数据，第二次又可以形成一个批量。伪代码如下: Executor executor = Executors.newFixedThreadPool(4); final BlockingQueue<Message> queue = new ArrayBlockingQueue<>(); private Runnable task = new Runnable({//这里由于共享队列，Runnable可以复用，故做成全局的 public void run(){ List<Message> messages = new ArrayList<>(20); queue.drainTo(messages，20); doSend(messages);//阻塞，在这个过程中会有新的消息到来，如果4个线程都占满，队列就有机会囤新的消息 } }); public void send(Message message){ queue.offer(message); executor.submit(task) } 这种方式是消息延迟和批量的一个比较好的平衡，但优先响应低延迟。延迟的最高程度由上一次发送的等待时间决定。但可能造成的问题是发送过快的话批量的大小不够满足性能的极致。 Executor executor = Executors.newFixedThreadPool(4); final BlockingQueue<Message> queue = new ArrayBlockingQueue<>(); volatile long last = System.currentMills(); Executors.newSingleThreadScheduledExecutor().submit(new Runnable(){ flush(); }，500，500，TimeUnits.MILLS); private Runnable task = new Runnable({//这里由于共享队列，Runnable可以复用，顾做成全局的。 public void run(){ List<Message> messages = new ArrayList<>(20); queue.drainTo(messages，20); doSend(messages);//阻塞，在这个过程中会有新的消息到来，如果4个线程都占满，队列就有机会屯新的消息。 } }); public void send(Message message){ last = System.currentMills(); queue.offer(message); flush(); } private void flush(){ if(queue.size>200||System.currentMills()-last>200){ executor.submit(task) } } 相反对于可以用适量的延迟来换取高性能的场景来说，用定时/定量二选一的方式可能会更为理想，既到达一定数量才发送，但如果数量一直达不到，也不能干等，有一个时间上限。 具体说来，在上文的submit之前，多判断一个时间和数量，并且Runnable内部维护一个定时器，避免没有新任务到来时旧的任务永远没有机会触发发送条件。对于server端的数据落地，使用这种方式就非常方便。 最后啰嗦几句，曾经有人问我，为什么网络请求小包合并成大包会提高性能？主要原因有两个： 减少无谓的请求头，如果你每个请求只有几字节，而头却有几十字节，无疑效率非常低下。 减少回复的ack包个数。把请求合并后，ack包数量必然减少，确认和重发的成本就会降低。 5、push还是pull 上文提到的消息队列，大多是针对push模型的设计。现在市面上有很多经典的也比较成熟的pull模型的消息队列，如Kafka、MetaQ等。这跟JMS中传统的push方式有很大的区别，可谓另辟蹊径。 我们简要分析下push和pull模型各自存在的利弊。 慢消费 慢消费无疑是push模型最大的致命伤，穿成流水线来看，如果消费者的速度比发送者的速度慢很多，势必造成消息在broker的堆积。假设这些消息都是有用的无法丢弃的，消息就要一直在broker端保存。当然这还不是最致命的，最致命的是broker给consumer推送一堆consumer无法处理的消息，consumer不是reject就是error，然后来回踢皮球。 反观pull模式，consumer可以按需消费，不用担心自己处理不了的消息来骚扰自己，而broker堆积消息也会相对简单，无需记录每一个要发送消息的状态，只需要维护所有消息的队列和偏移量就可以了。所以对于建立索引等慢消费，消息量有限且到来的速度不均匀的情况，pull模式比较合适。 消息延迟与忙等 这是pull模式最大的短板。由于主动权在消费方，消费方无法准确地决定何时去拉取最新的消息。如果一次pull取到消息了还可以继续去pull，如果没有pull取到则需要等待一段时间重新pull。 但等待多久就很难判定了。你可能会说，我可以有xx动态pull取时间调整算法，但问题的本质在于，有没有消息到来这件事情决定权不在消费方。也许1分钟内连续来了1000条消息，然后半个小时没有新消息产生，可能你的算法算出下次最有可能到来的时间点是31分钟之后，或者60分钟之后，结果下条消息10分钟后到了，是不是很让人沮丧？ 当然也不是说延迟就没有解决方案了，业界较成熟的做法是从短时间开始（不会对broker有太大负担），然后指数级增长等待。比如开始等5ms，然后10ms，然后20ms，然后40ms……直到有消息到来，然后再回到5ms。即使这样，依然存在延迟问题：假设40ms到80ms之间的50ms消息到来，消息就延迟了30ms，而且对于半个小时来一次的消息，这些开销就是白白浪费的。 在阿里的RocketMq里，有一种优化的做法-长轮询，来平衡推拉模型各自的缺点。基本思路是:消费者如果尝试拉取失败，不是直接return,而是把连接挂在那里wait,服务端如果有新的消息到来，把连接notify起来，这也是不错的思路。但海量的长连接block对系统的开销还是不容小觑的，还是要合理的评估时间间隔，给wait加一个时间上限比较好~ 顺序消息 如果push模式的消息队列，支持分区，单分区只支持一个消费者消费，并且消费者只有确认一个消息消费后才能push送另外一个消息，还要发送者保证全局顺序唯一，听起来也能做顺序消息，但成本太高了，尤其是必须每个消息消费确认后才能发下一条消息，这对于本身堆积能力和慢消费就是瓶颈的push模式的消息队列，简直是一场灾难。 反观pull模式，如果想做到全局顺序消息，就相对容易很多： producer对应partition，并且单线程。 consumer对应partition，消费确认（或批量确认），继续消费即可。 所以对于日志push送这种最好全局有序，但允许出现小误差的场景，pull模式非常合适。如果你不想看到通篇乱套的日志~~ Anyway，需要顺序消息的场景还是比较有限的而且成本太高，请慎重考虑。 三、总结 本文从为何使用消息队列开始讲起，然后主要介绍了如何从零开始设计一个消息队列，包括RPC、事务、最终一致性、广播、消息确认等关键问题。并对消息队列的push、pull模型做了简要分析，最后从批量和异步角度，分析了消息队列性能优化的思路。下篇会着重介绍一些高级话题，如存储系统的设计、流控和错峰的设计、公平调度等。希望通过这些，让大家对消息队列有个提纲挈领的整体认识，并给自主开发消息队列提供思路。另外，本文主要是源自自己在开发消息队列中的思考和读源码时的体会，比较不”官方”，也难免会存在一些漏洞，欢迎大家多多交流。
滑动查看更多
暂无更多信息
-
发表了文章
2014-08-13
数据处理实战：对ChiMerge问题的分析与实现
-
发表了文章
2014-08-25
经典文摘：Linux/Unix设计思想
-
发表了文章
2014-09-05
Linux命令行参数解析
-
发表了文章
2014-10-14
运维调试记录：SSH无法连接到远端Ubuntu
-
发表了文章
2014-11-21
Git常用命令集录
-
发表了文章
2014-12-18
操作系统中堆和栈详解
-
发表了文章
2014-12-18
C语言中宏与内联函数解析
-
发表了文章
2015-01-14
技术原理：Python中range和xrange对比
-
发表了文章
2015-01-21
运维调试记录：QSqlDatabase: QMYSQL driver not loaded
-
发表了文章
2015-03-03
运维调试记录：Win7中文件或目录损坏且无法读取
-
发表了文章
2015-04-01
技术原理：C语言中函数指针数组浅析
-
发表了文章
2015-04-22
运维调试记录：无法远程连接MySQL数据库
-
发表了文章
2015-04-24
运维调试记录：Mininet: Cannot find required executable controller
-
发表了文章
2015-05-05
运维调试记录：Ubuntu启动到字符界面和图形界面
-
发表了文章
2015-05-05
运维调试记录：Ubuntu16.04安装MySQL和Python库MySQLdb步骤
-
发表了文章
2015-05-05
Linux中Ctrl+C,Ctrl+Z,Ctrl+D说明
-
发表了文章
2016-01-27
PyProjects：Python项目大集合
-
发表了文章
2016-02-19
深入理解Netfilter和iptables
-
发表了文章
2016-02-21
C语言中柔性数组解析
-
发表了文章
2016-04-01
GDB程序调试工具参考知识
滑动查看更多
暂无更多信息