lucene

lucene3.0中BooleanQuery 实现与或的复合搜索 .
BooleanClause用于表示布尔查询子句关系的类,


括:

BooleanClause.Occur.MUST,

BooleanClause.Occur.MUST_NOT,

BooleanClause.Occur.SHOULD。

 

必须包含,不能包含,可以包含三种.有以下6种组合: 
 
1.MUST和MUST:取得连个查询子句的交集。 
2.MUST和MUST_NOT:表示查询结果中不能包含MUST_NOT所对应得查询子句的检索结果。 
3.SHOULD与MUST_NOT:连用时,功能同MUST和MUST_NOT。
4.SHOULD与MUST连用时,结果为MUST子句的检索结果,但是SHOULD可影响排序。
5.SHOULD与SHOULD:表示“或”关系,最终检索结果为所有检索子句的并集。
6.MUST_NOT和MUST_NOT:无意义,检索无结果。

...

构造出“与”的关系: bquery.Add(query, BooleanClause.Occur.MUST);

构造“或”关系:bquery.Add(query, BooleanClause.Occur.SHOULD);

构造“非”关系:bquery.Add(query, BooleanClause.Occur.MUST_NOT);

...

Field.Store.YES:存储字段值(未分词前的字段值) 

       Field.Store.NO:不存储,存储与索引没有关系 

       Field.Store.COMPRESS:压缩存储,用于长文本或二进制,但性能受损 



       Field.Index.ANALYZED:分词建索引 

       Field.Index.ANALYZED_NO_NORMS:分词建索引,但是Field的值不像通常那样被保存,而是只取一个byte,这样节约存储空间 

       Field.Index.NOT_ANALYZED:不分词且索引 

       Field.Index.NOT_ANALYZED_NO_NORMS:不分词建索引,Field的值去一个byte保存 



       TermVector表示文档的条目(由一个Document和Field定位)和它们在当前文档中所出现的次数 

       Field.TermVector.YES:为每个文档(Document)存储该字段的TermVector 

       Field.TermVector.NO:不存储TermVector 

       Field.TermVector.WITH_POSITIONS:存储位置 

       Field.TermVector.WITH_OFFSETS:存储偏移量 

       Field.TermVector.WITH_POSITIONS_OFFSETS:存储位置和偏移量

...

 Apache Lucene 几种分词系统

1、 StopAnalyzer

StopAnalyzer能过滤词汇中的特定字符串和词汇,并且完成大写转小写的功能。

2、 StandardAnalyzer

StandardAnalyzer根据空格和符号来完成分词,还可以完成数字、字母、E-mail地址、IP地址以及中文字符的分析处理,还可以支持过滤词表,用来代替StopAnalyzer能够实现的过滤功能。

3、 SimpleAnalyzer

SimpleAnalyzer具备基本西文字符词汇分析的分词器,处理词汇单元时,以非字母字符作为分割符号。分词器不能做词汇的过滤,之进行词汇的分析和分割。输出地词汇单元完成小写字符转换,去掉标点符号等分割符。

在全文检索系统开发中,通常用来支持西文符号的处理,不支持中文。由于不完成单词过滤功能,所以不需要过滤词库支持。词汇分割策略上简单,使用非英文字符作为分割符,不需要分词词库的支持。

4、 WhitespaceAnalyzer

WhitespaceAnalyzer使用空格作为间隔符的词汇分割分词器。处理词汇单元的时候,以空格字符作为分割符号。分词器不做词汇过滤,也不进行小写字符转换。

实际中可以用来支持特定环境下的西文符号的处理。由于不完成单词过滤和小写字符转换功能,也不需要过滤词库支持。词汇分割策略上简单使用非英文字符作为分割符,不需要分词词库支持。

5、 KeywordAnalyzer

KeywordAnalyzer把整个输入作为一个单独词汇单元,方便特殊类型的文本进行索引和检索。针对邮政编码,地址等文本信息使用关键词分词器进行索引项建立非常方便。

6、 CJKAnalyzer

CJKAnalyzer内部调用CJKTokenizer分词器,对中文进行分词,同时使用StopFilter过滤器完成过滤功能,可以实现中文的多元切分和停用词过滤。在Lucene3.0版本中已经弃用。

7、 ChineseAnalyzer

ChineseAnalyzer功能与StandardAnalyzer分析器在处理中文是基本一致,都是切分成单个的双字节中文字符。在Lucene3.0版本中已经弃用。

8、 PerFieldAnalyzerWrapper

PerFieldAnalyzerWrapper功能主要用在针对不同的Field采用不同的Analyzer的场合。比如对于文件名,需要使用KeywordAnalyzer,而对于文件内容只使用StandardAnalyzer就可以了。通过addAnalyzer()可以添加分类器。

9、 IKAnalyzer

实现了以词典为基础的正反向全切分,以及正反向最大匹配切分两种方法。IKAnalyzer是第三方实现的分词器,继承自Lucene的Analyzer类,针对中文文本进行处理。

10、JE-Analysis

JE-Analysis是Lucene的中文分词组件,需要下载。

11、 ICTCLAS4J

ictclas4j中文分词系统是sinboy在中科院张华平和刘群老师的研制的FreeICTCLAS的基础上完成的一个java开源分词项目,简化了原分词程序的复杂度,旨在为广大的中文分词爱好者一个更好的学习机会。

12、 Imdict-Chinese-Analyzer

imdict-chinese-analyzer 是 imdict智能词典 的智能中文分词模块,算法基于隐马尔科夫模型(Hidden Markov Model, HMM),是中国科学院计算技术研究所的ictclas中文分词程序的重新实现(基于Java),可以直接为lucene搜索引擎提供简体中文分词支持。

13、 Paoding Analysis

Paoding Analysis中文分词具有极 高效率 和 高扩展性。引入隐喻,采用完全的面向对象设计,构思先进。其效率比较高,在PIII 1G内存个人机器上,1秒可准确分词100万汉字。采用基于不限制个数的词典文件对文章进行有效切分,使能够将对词汇分类定义。能够对未知的词汇进行合理解析。

14、 MMSeg4J

mmseg4j 用 Chih-Hao Tsai 的 MMSeg 算法(http://technology.chtsai.org/mmseg/ )实现的中文分词器,并实现 lucene 的 analyzer 和 solr 的TokenizerFactory 以方便在Lucene和Solr中使用。 MMSeg 算法有两种分词方法:Simple和Complex,都是基于正向最大匹配。Complex 加了四个规则过虑。官方说:词语的正确识别率达到了 98.41%。mmseg4j 已经实现了这两种分词算法。

...

using System;
using System.Collections.Generic;
using System.Web.Mvc;
using Lucene.Net.Store;
using Lucene.Net.Analysis;
using Lucene.Net.Analysis.Standard;
using Lucene.Net.Index;
using Lucene.Net.Documents;
using Lucene.Net.Search;
using Lucene.Net.QueryParsers;
using System.Diagnostics;

namespace LuceneNet.Web.Controllers {
    public class HomeController : Controller {
        public ActionResult Index() {
            ViewBag.Message = "欢迎使用 ASP.NET MVC!";
            return View();
        }
        public ActionResult About() {
            return View();
        }
        /// <summary>
        /// 添加索引
        /// </summary>
        /// <returns></returns>
        public ActionResult AddIndex() {
            //为索引存储目录
            string INDEX_STORE_PATH = Server.MapPath("~/SearchIndex");
#if DEBUG
            ///如果存在文件则删除(测试用)
            if (System.IO.Directory.Exists(INDEX_STORE_PATH)) {
                System.IO.Directory.Delete(INDEX_STORE_PATH, true);
            }
#endif
            Directory indexDirectory = FSDirectory.Open(new System.IO.DirectoryInfo(INDEX_STORE_PATH));
            Analyzer analyzer = new StandardAnalyzer(Lucene.Net.Util.Version.LUCENE_29);
            IndexWriter writer = null;

            try {
                //检查索引文件是否存在
                bool iscreate = !Lucene.Net.Index.IndexReader.IndexExists(indexDirectory);
                //如果索引文件不存在则创建索引文件,否则创建索引文件
                writer = new IndexWriter(indexDirectory, analyzer, iscreate, IndexWriter.MaxFieldLength.UNLIMITED);

                //开始添加索引
                foreach (var item in Get()) {
                    Document doc = new Document();
                    doc.Add(new Field("id", item.Id, Field.Store.YES, Field.Index.ANALYZED));//存储,不分词索引
                    doc.Add(new Field("classid", item.ClassId, Field.Store.YES, Field.Index.NOT_ANALYZED));//存储,不分词索引
                    doc.Add(new Field("classname", item.ClassName, Field.Store.YES, Field.Index.ANALYZED));//存储,不分词索引
                    doc.Add(new Field("title", item.Title, Field.Store.YES, Field.Index.ANALYZED));//存储,分词索引
                    doc.Add(new Field("summary", item.Summary, Field.Store.YES, Field.Index.ANALYZED));//存储,分词索引
                    doc.Add(new Field("createtime", item.CreateTime.ToString(), Field.Store.YES, Field.Index.NOT_ANALYZED));//存储,分词索引
                    writer.AddDocument(doc);
                }
                writer.Optimize();
            } catch (Exception) {
                throw;
            } finally {
                if (analyzer != null)
                    analyzer.Close();
                if (writer != null)
                    writer.Close();
                if (indexDirectory != null)
                    indexDirectory.Close();
            }
            return RedirectToAction("index");
        }
        /// <summary>
        /// 搜索
        /// </summary>
        /// <param name="k"></param>
        /// <param name="cid"></param>
        /// <returns></returns>
        public ActionResult Search(string k, string cid) {
            Stopwatch st = new Stopwatch();
            st.Start();//计时开始  
            //为索引存储目录
            string INDEX_STORE_PATH = Server.MapPath("~/SearchIndex");
            var ver = Lucene.Net.Util.Version.LUCENE_29;
            Directory indexDirectory = FSDirectory.Open(new System.IO.DirectoryInfo(INDEX_STORE_PATH));
            Analyzer analyzer = new StandardAnalyzer(ver);
            IndexSearcher searcher = null;
            List<Article> list;
            int recCount = 0;
            try {
                searcher = new IndexSearcher(indexDirectory, true);
                string[] fields = { "title", "summary" };
                BooleanQuery booleanQuery = new BooleanQuery();
                //多字段查询同时搜索title和summary
                MultiFieldQueryParser parser = new MultiFieldQueryParser(ver, fields, analyzer);
                Query query = parser.Parse(k);
                //Query query1 = new QueryParser(ver, "classid", analyzer).Parse("1");

                //TermQuery只能查询不分词的索引(Field.Index.NOT_ANALYZED)
                Query query1 = new TermQuery(new Term("id", "1"));
                //当classname为ANALYZED时搜不到
                // Query query2 = new TermQuery(new Term("classname", "体育新闻"));
                //只有当classname为NOT_ANALYZED才可以搜得到,
                //由此得出TermQuery只能查询不分词的索引(Field.Index.NOT_ANALYZED)的结论
                //但当id为ANALYZED时TermQuery却可以收的到,
                //当搜classname中包含“体”时即Query query2 = new TermQuery(new Term("classname", "体"));
                //当搜classname中包含“育”时即Query query2 = new TermQuery(new Term("classname", "育"));
                //可以搜得到。因此,由此得出,TermQuery搜的是最小单位,由此又得出Lucene是把“体育新闻”拆分成了"体/育/新/闻"四部分
                //听说Lucene分词是按空格分的,那么把“体育新闻”,改成“体育 新闻”后再重新生成索引是不是可以搜的到呢?
                //Query query2 = new TermQuery(new Term("classname", "体育"));
                //但是结果却是搜不到,纳闷...难道Lucene的分词不是这么分而是更复杂?
                //StandardAnalyzer看来是对中文分词不怎么好,当ClassName = "sports news"可以搜sports和news
                //StandardAnalyzer只支持英文的空格分词
                Query query2 = new TermQuery(new Term("classname", k));
                //关于QueryParser的搜索当k为Empty或null时会报错注意处理
                //Query query3 = new QueryParser(ver, "title", analyzer).Parse(k);
                Query query3 = new QueryParser(ver, "title", analyzer).Parse(k);

                Query query4 = new PrefixQuery(new Term("classname", k));
                Query query5 = new QueryParser(ver, "title", analyzer).Parse(k);
                TermRangeQuery query6 = new TermRangeQuery("createtime", "2012-1-3", "2012-5-3", true, true);

                //booleanQuery.Add(query1, BooleanClause.Occur.MUST);
                //booleanQuery.Add(query2, BooleanClause.Occur.MUST);
                //booleanQuery.Add(query3, BooleanClause.Occur.MUST);
                booleanQuery.Add(query4, BooleanClause.Occur.MUST);
                //booleanQuery.Add(query5, BooleanClause.Occur.MUST);
                booleanQuery.Add(query6, BooleanClause.Occur.MUST);
                TopDocs ts = searcher.Search(booleanQuery, null, 100);//执行搜索,获取查询结果集对象

                recCount = ts.totalHits;//获取命中的文档个数
                ScoreDoc[] hits = ts.scoreDocs;//获取命中的文档信息对象
                st.Stop();//计时停止
                ViewBag.EvenTime = string.Format("{0}毫秒,生成的Query语句:{1}", st.ElapsedMilliseconds, booleanQuery.ToString());
                ViewBag.Count = recCount;
                list = new List<Article>();
                foreach (var item in hits) {
                    list.Add(new Article()
                    {
                        Id = searcher.Doc(item.doc).Get("id"),
                        ClassId = searcher.Doc(item.doc).Get("classid"),
                        ClassName = searcher.Doc(item.doc).Get("classname"),
                        Title = searcher.Doc(item.doc).Get("title"),
                        Summary = searcher.Doc(item.doc).Get("summary"),
                        Score = item.score.ToString(),
                        CreateTime = DateTime.Parse(searcher.Doc(item.doc).Get("createtime"))
                    });
                }
            } catch (Exception) {
                throw;
            } finally {
                if (searcher != null) {
                    searcher.Close();
                }
            }

            return View(list);
        }

        public List<Article> Get() {
            List<Article> list = new List<Article>();
            list.Add(new Article() { Id = "1", ClassId = "1", ClassName = "体育新闻", Title = "微软发布MVC4.0了", Summary = "微软发布MVC4.0了,此版本更加强大", CreateTime = DateTime.Parse("2012-2-3") });
            list.Add(new Article() { Id = "2", ClassId = "1", ClassName = "IT新闻", Title = "跟谷歌测试工程师的对话", Summary = "本文主人公Alan是谷歌的一名的软件测试工程师,他的工作对象是谷歌的DoubleClick广告管理系统(Bid Manager),这个系统提供让广告代理商和广告客户在多个广告上进行报价竞标的功能。", CreateTime = DateTime.Parse("2012-3-3") });
            list.Add(new Article() { Id = "3", ClassId = "1", ClassName = "体育 新闻", Title = "好的程序员应该熟悉的几门编程语言", Summary = "如果想成为一个好的程序员,甚至架构师、技术总监等,显然只精通一种编程语言是不够的,还应该在常见领域学会几门编程语言,正如我们要成为高级人才不仅要会中文还要会英文", CreateTime = DateTime.Parse("2012-4-3") });
            list.Add(new Article() { Id = "4", ClassId = "2", ClassName = "娱乐新闻", Title = "Javascript开发《三国志曹操传》-开源讲座(五)-可移动地图的实现", Summary = "这一讲的内容很简单,大家理解起来会更快。因此我只对重点加以分析,其他的就轮到大家思考哦!首先来说,我对游戏开发可以算是不怎么深入,因为现在的程序员爱用canvas,我却就只会拿几个div凑和。", CreateTime = DateTime.Parse("2012-5-3") });
            list.Add(new Article() { Id = "5", ClassId = "2", ClassName = "体育新闻", Title = "Android之BaseExpandableListAdapter使用心得", Summary = " 但是我最近做那个QQ项目是遇到一个问题,如果给这个ExpandableListView添加动态从网上获取的数据呢?前面跟大家分享的时候,是用了静态的数据,很好处理。", CreateTime = DateTime.Parse("2012-6-3") });
            list.Add(new Article() { Id = "6", ClassId = "3", ClassName = "sports news", Title = "对话CSDN蒋涛:微软移动互联网马太效应不可避免,小团队需学会利用平台", Summary = "CSDN是全球最大的中文IT社区,也是雷锋网最重要的合作伙伴之一,自1999年创办至今,有着非常强大的业界影响力和号召力,其专注IT信息传播、技术交流、教育培训和专业技术人才服务,在2012年移动开发者大会即将举办之际,雷锋网对CSDN的掌门人蒋涛做了一次专访,一起探讨移动互联网的新技术浪潮和下一波发展趋势。", CreateTime = DateTime.Parse("2012-7-3") });
            list.Add(new Article() { Id = "7", ClassId = "3", ClassName = "体育新闻", Title = "基于MySQL的分布式事务控制方案", Summary = "基于MySQL的分布式事务控制方案", CreateTime = DateTime.Parse("2012-8-3") });
            list.Add(new Article() { Id = "8", ClassId = "4", ClassName = "sports news", Title = "IOS和Android开发的一些个人感受", Summary = "最近公司的产品 Android版本第二版也算到了收尾,新加了几个功能性模块,我基本也就捡了几个好玩的模块做了下。", CreateTime = DateTime.Parse("2012-9-3") });
            list.Add(new Article() { Id = "9", ClassId = "5", ClassName = "IT资讯", Title = "Google Code的简单使用", Summary = "google code简介:用于管理代码的仓库,反正我是这么理解的。就比我们在公司的时候也会有个用于存放公司代码的主机一样,google同样给我们提供了这样的一个host。这样我们可以在不同电脑不同地方随时的checkout,commit,同时分享我们的项目。", CreateTime = DateTime.Parse("2012-10-3") });
            list.Add(new Article() { Id = "10", ClassId = "33", ClassName = "IT资讯", Title = "谷歌在印度推Gmail免费短信服务", Summary = "歌一直在努力桥接发展中国家功能手机SMS服务和Gmail之间的服务,这不,近日谷歌在印度推出“Gmail SMS”服务,这使得印度的Gmail用户可以从Gmail的窗口发送信息到手机上并且接受聊天信息的回复,目前谷歌的这项服务已经得到印度的八大运营商的支持。", CreateTime = DateTime.Parse("2012-11-3") });
            list.Add(new Article() { Id = "11", ClassId = "11", ClassName = "体育新闻", Title = "鲍尔默:微软新时代 软硬结合“赢”未来", Summary = "微软CEO鲍尔默在年度公开信中表示,微软在未来将紧密结合硬件和软件。鲍尔默认为,这是微软的一个新时代。“我们看到了前所未有的机会,我们对此很兴奋,并且保持着乐观的心态。”", CreateTime = DateTime.Parse("2012-12-3") });
            return list;
        }
    }

    public class Article {
        public string Id { get; set; }
        public string ClassId { get; set; }
        public string ClassName { get; set; }
        public string Title { get; set; }
        public string Summary { get; set; }
        public string Score { get; set; }
        public DateTime CreateTime { get; set; }
    }
}

 

 

 

 

 

 

...

...

发表在 search | lucene已关闭评论

Zookeeper的核心:ZAB原子消息广播协议

 点击查看原图
        ZooKeeper为高可用的一致性协调框架,自然的ZooKeeper也有着一致性算法的实现,ZooKeeper使用的是ZAB协议作为数据一致性的算法,
ZAB(ZooKeeper Atomic Broadcast )
称为:原子消息广播协议;ZAB可以说是在Paxos算法基础上进行了扩展改造而来的,ZAB协议设计了支持崩溃恢复,ZooKeeper使用单一主进程
Leader用于处理客户端所有事务请求,采用ZAB协议将服务器数状态以事务形式广播到所有Follower上;由于事务间可能存在着依赖关系,ZAB
协议保证Leader广播的变更序列被顺序的处理,:一个状态被处理那么它所依赖的状态也已经提前被处理;ZAB协议支持的崩溃恢复可以保证在
Leader进程崩溃的时候可以重新选出Leader并且保证数据的完整性;

  在ZooKeeper中
所有的事务请求都由一个主服务器也就是Leader来处理,其他服务器为Follower,Leader将客户端的事务请求转换为事务Proposal,
并且将Proposal分发给集群中其他所有的Follower,然后Leader等待Follwer反馈,当有
过半数(>=N/2+1)的Follower反馈信息后,Leader将再次向集群内Follower广播Commit信息,Commit为将之前的Proposal提交;

一、协议状态

  ZAB协议中存在着三种状态,每个节点都属于以下三种中的一种:
  1. Looking(发现):系统刚启动时或者Leader崩溃后正处于选举状态
  2. Following(同步):Follower节点所处的状态,Follower与Leader处于数据同步阶段;
  3. Leading(领导):Leader所处状态,当前集群中有一个Leader为主进程;

  ZooKeeper启
动时所有节点初始状态为Looking,这时集群会尝试选举出一个Leader节点,选举出的Leader节点切换为Leading状态;当节点发现集群
中已经选举出Leader则该节点会切换到Following状态,然后和Leader节点保持同步;当Follower节点与Leader失去联系时
Follower节点则会切换到Looking状态,开始新一轮选举;在ZooKeeper的整个生命周期中每个节点都会在Looking、
Following、Leading状态间不断转换;

    点击查看原图

  选举出Leader节
点后ZAB进入原子广播阶段,这时Leader为和自己同步的每个节点Follower创建一个操作序列,一个时期一个Follower只能和一个
Leader保持同步,Leader节点与Follower节点使用心跳检测来感知对方的存在;当Leader节点在超时时间内收到来自Follower
的心跳检测那Follower节点会一直与该节点保持连接;若超时时间内Leader没有接收到来自过半Follower节点的心跳检测或TCP连接断
开,那Leader会结束当前周期的领导,切换到Looking状态,所有Follower节点也会放弃该Leader节点切换到Looking状态,然
后开始新一轮选举;

二、算法阶段

  ZAB协议定义了选举(election)、发现(discovery)、同步(sync)、广播(Broadcast)
个阶段;ZAB选举(election)时当Follower存在ZXID(事务ID)时判断所有Follower节点的事务日志,只有lastZXID
的节点才有资格成为Leader,这种情况下选举出来的Leader总有最新的事务日志,基于这个原因所以ZooKeeper实现的时候把
发现(discovery)与同步(sync)合并为恢复(recovery)阶段;
  1. Election:在Looking状态中选举出Leader节点,Leader的lastZXID总是最新的;
  2. Discovery:Follower节点向准Leader推送FOllOWERINFO,该信息中包含了上一周期的epoch,接受准Leader的NEWLEADER指令,检查newEpoch有效性,准Leader要确保Follower的epoch与ZXID小于或等于自身的;
  3. sync:将Follower与Leader的数据进行同步,由Leader发起同步指令,最总保持集群数据的一致性;
  4. Broadcast:Leader广播Proposal与Commit,Follower接受Proposal与Commit;
  5. Recovery:在Election阶段选举出Leader后本阶段主要工作就是进行数据的同步,使Leader具有highestZXID,集群保持数据的一致性;

  1、选举(Election)
  election阶段必
须确保选出的Leader具有highestZXID,否则在Recovery阶段没法保证数据的一致性,Recovery阶段Leader要求
Follower向自己同步数据没有Follower要求Leader保持数据同步,所有选举出来的Leader要具有最新的ZXID;

  在选举的过程中会对每个Follower节点的ZXID进行对比只有highestZXID的Follower才可能当选Leader;
选举流程:
  1. 每个Follower都向其他节点发送选自身为Leader的Vote投票请求,等待回复;
  2. Follower接受到的Vote如果比自身的大(ZXID更新)时则投票,并更新自身的Vote,否则拒绝投票;
  3. 每个Follower中维护着一个投票记录表,当某个节点收到过半的投票时,结束投票并把该Follower选为Leader,投票结束;

  ZAB协议中使用ZXID作为事务编号,ZXID为64位数字
低32位为一个递增的计数器,每一个客户端的一个事务请求时Leader产生新的事务后该计数器都会加1,高32位为Leader周期epoch编号,当
新选举出一个Leader节点时Leader会取出本地日志中最大事务Proposal的ZXID解析出对应的epoch把该值加1作为新的epoch,
将低32位从0开始生成新的ZXID;ZAB使用epoch来区分不同的Leader周期;

  2、恢复(Recovery)
  在election阶段选举出来的Leader已经具有最新的ZXID,所有本阶段的主要工作是根据Leader的事务日志对Follower节点数据进行更新;
  
Leader:Leader生成新的ZXID与epoch,接收Follower发送过来的FOllOWERINFO(含有当前节点的LastZXID)
然后往Follower发送NEWLEADER;Leader根据Follower发送过来的LastZXID根据数据更新策略向Follower发送更
新指令;

  同步策略:
  1. SNAP:如果Follower数据太老,Leader将发送快照SNAP指令给Follower同步数据;
  2. DIFF:Leader发送从Follolwer.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据;
  3. TRUNC:当Follower.lastZXID比Leader.lastZXID大时,Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令让Follower丢弃该段数据;
  Follower:往
Leader发送FOLLOERINFO指令,Leader拒绝就转到Election阶段;接收Leader的NEWLEADER指令,如果该指令中
epoch比当前Follower的epoch小那么Follower转到Election阶段;Follower还有主要工作是接收SNAP/DIFF
/TRUNC指令同步数据与ZXID,同步成功后回复ACKNETLEADER,然后进入下一阶段;Follower将所有事务都同步完成后Leader
会把该节点添加到可用Follower列表中;

  SNAP与DIFF用于保证集群中Follower节点已经Committed的数据的一致性,TRUNC用于抛弃已经被处理但是没有Committed的数据;

  3、广播(Broadcast)
  客户端提交事务请求时
Leader节点为每一个请求生成一个事务Proposal,将其发送给集群中所有的Follower节点,收到过半Follower的反馈后开始对事务
进行提交,ZAB协议使用了原子广播协议;在ZAB协议中只需要得到过半的Follower节点反馈Ack就可以对事务进行提交,这也导致了Leader
几点崩溃后可能会出现数据不一致的情况,ZAB使用了崩溃恢复来处理数字不一致问题;消息广播使用了TCP协议进行通讯所有保证了接受和发送事务的顺序
性。广播消息时Leader节点为每个事务Proposal分配一个全局递增的ZXID(事务ID),每个事务Proposal都按照ZXID顺序来处
理;

  Leader节点为每一
个Follower节点分配一个队列按事务ZXID顺序放入到队列中,且根据队列的规则FIFO来进行事务的发送。Follower节点收到事务
Proposal后会将该事务以事务日志方式写入到本地磁盘中,成功后反馈Ack消息给Leader节点,Leader在接收到过半Follower节点
的Ack反馈后就会进行事务的提交,以此同时向所有的Follower节点广播Commit消息,Follower节点收到Commit后开始对事务进行
提交;

摘自: http://blog.itpub.net/30316686/viewspace-2106956/

发表在 technologys | Zookeeper的核心:ZAB原子消息广播协议已关闭评论

TcpTimedWaitDelay/MaxUserPort

当TCP连接被关闭时,{ Protocol, Local IP, Local Port, Remote IP, Remote Port}五元组就进入TIME_WAIT状态,默认时间是4分钟。可以通过一组命令看看tcp的连接状态:

netstat -ano>>c:\port.txt

netstat -n | find /C /I "established"
查看连接与内存
ss -s && free -g

本地ip,远程ip,远程端口都是固定的,只有本地端口是变化的,本地端口只能使用1024-5000,因此如果在4分钟内发起了大约4000个连接,这时就会发生异常,下面是使用WCF,客户端的异常:

System.Net.Sockets.SocketException: Only one usage of each socket
address (protocol/network address/port) is normally permitted
192.168.101.5:8888
at System.Net.Sockets.Socket.DoConnect(EndPoint endPointSnapshot, SocketAddress socketAddress)
at System.Net.Sockets.Socket.Connect(EndPoint remoteEP)
at System.ServiceModel.Channels.SocketConnectionInitiator.Connect(Uri uri, TimeSpan timeout)

TcpTimedWaitDelay 描述:
HKEY_LOCAL_MACHINE/SYSTEM/CurrentControlSet/Services/TCPIP/Parameters
确定 TCP/IP 可释放已关闭连接并重用其资源前,必须经过的时间。关闭和释放之间的此时间间隔通称 TIME_WAIT 状态或两倍最大段生命周期(2MSL)状态。
此时间期间,重新打开到客户机和服务器的连接的成本少于建立新连接。
减少此条目的值允许 TCP/IP 更快地释放已关闭的连接,为新连接提供更多资源。
如果运行的应用程序需要快速释放和创建新连接,而且由于 TIME_WAIT 中存在很多连接,导致低吞吐量,则调整此参数。

参考:https://technet.microsoft.com/en-us/library/cc938217.aspx
TYPE:    REG_DWORD   
VALUE:    0x1E 0x12C ( 30–300 seconds )
DEFAULT:    0xF0 ( 240 seconds = 4 minutes )

将此值设置为十进制 30,其为十六进制 0x0000001e。该值将等待时间设置为 30 秒。
建议值:最小值为 0x1E,它将等待时间设置为 30 秒。

MaxUserPort 描述:
HKEY_LOCAL_MACHINE/SYSTEM/CurrentControlSet/Services/TCPIP/Parameters
TYPE:    REG_DWORD   
VALUE:    5,000–65,534 ( port number )
DEFAULT:    5000

确定在应用程序从系统请求可用用户端口时,TCP/IP 可指定的最高端口号。
缺省值:无 建议值:至少十进制 32768。

参考:https://technet.microsoft.com/en-us/library/cc938196.aspx

注意: 如果调整 MaxUserPort 或 TcpTimedWaitDelay 设置,您必须重新启动 Microsoft Windows 以使新设置生效。

使用 Exchange Server 2007 :
建议将 MaxUserPort 值设置为 60000。
如果设置的 MaxUserPort 值低于 60000,服务器可能会显示名称服务提供程序接口 (NSPI) 代理警告,例如事件 9040。

描述:

http://longwhiteclouds.com/2012/03/22/1-million-iops-microsoft-vs-vmware-comparison/

 

Links:

http://www.xiaobo.li/network/572.html

 

发表在 network | TcpTimedWaitDelay/MaxUserPort已关闭评论

PPTP/L2TP over PPPoE的準確MTU/MRU值

Ethernet MinSize = 512bit = 64 Byte
Ethernet MaxSize = 1518 Byte
so Ethernet IP MTU = 1518 - 18 ( 6 SRCMAC+ 6 DSTMAC+ 2 TYPE+ 4 CRC) = 1500 B
so Ethernet IP TCP MSS = 1500 - 40 ( 20 IP_HEADER + 20 TCP_HEADER) = 1460 B
so Ethernet IP UDP MTU/MRU = 1500 - 28 ( 20 IP_HEADER + 8 UDP_HEADER ) = 1472 B
so PPPoE MTU/MRU = 1500 - 8 ( 6 PPPoE_SESSION + 2 PPP_HEADER ) = 1492 B
so TCP over PPPoE MSS = 1492 ( PPPoE MTU/MRU ) - 40 ( 20 IP_HEADER + 20 TCP_HEADER) = 1452
so PPTP MTU/MRU = 1500 - 56 ( 20 IP_HEADER + 20 TCP_HEADER + 12 GRE_HEADER + 4 PPP_HEADER ) = 1444 B
so TCP over PPTP MSS = 1444 ( PPTP MTU/MRU ) - 40 ( 20 IP_HEADER + 20 TCP_HEADER) = 1404
so L2TP MTU/MRU = 1500 - 40 ( 20 IP_HEADER +8 UDP_HEADER + 8 L2TP_HEADER + 4 PPP_HEADER ) = 1460 B
so TCP over L2TP MSS = 1460 ( L2TP MTU/MRU ) - 40 ( 20 IP_HEADER + 20 TCP_HEADER) = 1420 B
so PPTP over PPPoE MTU/MRU = 1492 ( PPPoE MTU/MRU ) - 56 ( 20 IP_HEADER + 20 TCP_HEADER + 12 GRE_HEADER + 4 PPP_HEADER ) = 1436 B
so PPTP over PPTP MTU/MRU = 1444 ( PPTP MTU/MRU ) - 56 ( 20 IP_HEADER + 20 TCP_HEADER + 12 GRE_HEADER + 4 PPP_HEADER ) = 1388 B
so PPTP over L2TP MTU/MRU = 1460 ( L2TP MTU/MRU ) - 56 ( 20 IP_HEADER + 20 TCP_HEADER + 12 GRE_HEADER + 4 PPP_HEADER ) = 1404 B
so L2TP over PPPoE MTU/MRU = 1492 ( PPPoE MTU/MRU ) - 40 ( 20 IP_HEADER +8 UDP_HEADER + 8 L2TP_HEADER + 4 PPP_HEADER ) = 1452 B
so L2TP over PPTP MTU/MRU = 1444 ( PPTP MTU/MRU ) - 40 ( 20 IP_HEADER +8 UDP_HEADER + 8 L2TP_HEADER + 4 PPP_HEADER ) = 1404 B
so L2TP over L2TP MTU/MRU = 1460 ( L2TP MTU/MRU ) - 40 ( 20 IP_HEADER +8 UDP_HEADER + 8 L2TP_HEADER + 4 PPP_HEADER ) = 1420 B

 

PPTP over PPPoE的準確MTU值是 1436,L2TP over PPPoE的準確MTU是1452。別人說的 1400 偏保守了點。

如果你用 ADSL 上網,然後用 PPTP 來翻Wall,那麼,你實際上是 PPP 協議跑在 TCP 協議上再跑在 IP 協議上再跑在
PPP 協議上再跑在 IP 協議上再跑在以太網協議上。1518 字節的最大以太網 frame,扣來扣去,就剩下
1436。同理L2TP跑在PPP鏈路上,扣來扣去也就只剩1452B了,難怪筆者之前VPN上不去網,原來是全把數據包丟掉了。

如果讀者看明白了上面的解釋,那麼考慮你用 pptp 連公司的 vpn,公司又 pppoe(adsl撥號),然後你再 pptp 來翻功夫網,那麼,你的 MTU 只能設為 1518-18-8-56-56=1380 字節。

 

 

 

发表在 technologys | PPTP/L2TP over PPPoE的準確MTU/MRU值已关闭评论

(CORS)Cross-origin resource sharing

How CORS works:

https://upload.wikimedia.org/wikipedia/commons/c/ca/Flowchart_showing_Simple_and_Preflight_XHR.svg

点击查看原图

 

参考:

https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Access_control_CORS

 

 

简单请求:

简单指:

  • 只使用 GET, HEAD 或者 POST 请求方法。如果使用 POST 向服务器端传送数据,则数据类型(Content-Type)只能是 application/x-www-form-urlencoded, multipart/form-data 或 text/plain中的一种。
  • 不会使用自定义请求头(类似于 X-Modified 这种)。

 

GET /resources/public-data/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) 
Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
Referer: http://foo.example/examples/access-control/simpleXSInvocation.html
Origin: http://foo.example


HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 00:23:53 GMT
Server: Apache/2.0.61 
Access-Control-Allow-Origin: *
Keep-Alive: timeout=2, max=100
Connection: Keep-Alive
Transfer-Encoding: chunked
Content-Type: application/xml

 

 

预请求:

OPTIONS /resources/post-here/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) 
Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
Origin: http://foo.example
Access-Control-Request-Method: POST
Access-Control-Request-Headers: X-PINGOTHER


HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 01:15:39 GMT
Server: Apache/2.0.61 (Unix)
Access-Control-Allow-Origin: http://foo.example
Access-Control-Allow-Methods: POST, GET, OPTIONS
Access-Control-Allow-Headers: X-PINGOTHER
Access-Control-Max-Age: 1728000
Vary: Accept-Encoding, Origin
Content-Encoding: gzip
Content-Length: 0
Keep-Alive: timeout=2, max=100
Connection: Keep-Alive
Content-Type: text/plain

POST /resources/post-here/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre)
 Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
X-PINGOTHER: pingpong
Content-Type: text/xml; charset=UTF-8
Referer: http://foo.example/examples/preflightInvocation.html
Content-Length: 55
Origin: http://foo.example
Pragma: no-cache
Cache-Control: no-cache



HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 01:15:40 GMT
Server: Apache/2.0.61 (Unix)
Access-Control-Allow-Origin: http://foo.example
Vary: Accept-Encoding, Origin
Content-Encoding: gzip
Content-Length: 235
Keep-Alive: timeout=2, max=99
Connection: Keep-Alive
Content-Type: text/plain

 

 

附带凭证信息的请求:

var invocation = new XMLHttpRequest();
var url = 'http://bar.other/resources/credentialed-content/';
    
function callOtherDomain(){
  if(invocation) {
    invocation.open('GET', url, true);
    invocation.withCredentials = true;
    invocation.onreadystatechange = handler;
    invocation.send(); 
  }

GET /resources/access-control-with-credentials/ HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) 
Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Connection: keep-alive
Referer: http://foo.example/examples/credential.html
Origin: http://foo.example
Cookie: pageAccess=2


HTTP/1.1 200 OK
Date: Mon, 01 Dec 2008 01:34:52 GMT
Server: Apache/2.0.61 (Unix) PHP/4.4.7 mod_ssl/2.0.61 OpenSSL/0.9.7e 
mod_fastcgi/2.4.2 DAV/2 SVN/1.4.2
X-Powered-By: PHP/5.2.6
Access-Control-Allow-Origin: http://foo.example
Access-Control-Allow-Credentials: true
Cache-Control: no-cache
Pragma: no-cache
Set-Cookie: pageAccess=3; expires=Wed, 31-Dec-2008 01:34:53 GMT
Vary: Accept-Encoding, Origin
Content-Encoding: gzip
Content-Length: 106
Keep-Alive: timeout=2, max=100
Connection: Keep-Alive
Content-Type: text/plain

特别注意: 给一个带有withCredentials的请求发送响应的时候,服务器端必须指定允许请求的域名,不能使用'*'.

.

发表在 http | 标签为 | (CORS)Cross-origin resource sharing已关闭评论

zookeeper

场景一

有这样一个场景:
统中有大约100w的用户,每个用户平
均有3个邮箱账号,每隔5分钟,每个邮箱账需要收取100封邮件,最多3亿份邮件需要下载到服务器中(不含附件和正文)。用20台机器划分计算的压力,从
多个不同的网路出口进行访问外网,计算的压力得到缓解,那么每台机器的计算压力也不会很大了。

        通过我们的讨论和以往的经验判断在这场景中可以实现并行计算,但我们还期望能对并行计算的节点进行动态的添加/删除,做到在线更新并行计算的数目并且不会影响计算单元中的其他计算节点,但是有4个问题需要解决,否则会出现一些严重的问题:

  1. 20台机器同时工作时,有一台机器down掉了,其他机器怎么进行接管计算任务,否则有些用户的业务不会被处理,造成用户服务终断。
  2. 随着用户数量增加,添加机器是可以解决计算的瓶颈,但需要重启所有计算节点,如果需要,那么将会造成整个系统的不可用。
  3. 用户数量增加或者减少,计算节点中的机器会出现有的机器资源使用率繁忙,有的却空闲,因为计算节点不知道彼此的运行负载状态。
  4. 怎么去通知每个节点彼此的负载状态,怎么保证通知每个计算节点方式的可靠性和实时性。

        先不说那么多专业名词,白话来说我们需要的是:1记录状态,2事件通知 ,3可靠稳定的中央调度器,4易上手、管理简单。

        采用Zookeeper完全可以解决我们的问题,分布式计算中的协调员,观察者,分布式锁 
都可以作为zookeeper的关键词,在系统中利用Zookeeper来处理事件通知,队列,优先队列,锁,共享锁等功能,利用这些特色在分布式计算中
发挥重要的作用。

场景二 

        假
设我们我们有个20个搜索引擎的服务器(每个负责总索引中的一部分的搜索任务)和一个总服务器(负责向这20个搜索引擎的服务器发出搜索请求并合并
结果集),一个备用的总服务器(负责当总服务器宕机时替换总服务器),一个web的
cgi(向总服务器发出搜索请求).搜索引擎的服务器中的15个服务器现在提供搜索服务,5个服务器正在生成索引.这20个搜索引擎的服务器经常要让正在

提供搜索服务的服务器停止提供服务开始生成索引,或生成索引的服务器已经把索引生成完成可以搜索提供服务了.使用Zookeeper可以保证总服务器自动

感知有多少提供搜索引擎的服务器并向这些服务器发出搜索请求,备用的总服务器宕机时自动启用备用的总服务器,web的cgi能够自动地获知总服务器的网络
地址变化.这些又如何做到呢?

 

1. 提供搜索引擎的服务器都在Zookeeper中创建znode,zk.create("/search/nodes/node1",

"hostname".getBytes(), Ids.OPEN_ACL_UNSAFE, CreateFlags.EPHEMERAL);

2.总服务器可以从Zookeeper中获取一个znode的子节点的列表,zk.getChildren("/search/nodes", true);

3.总服务器遍历这些子节点,并获取子节点的数据生成提供搜索引擎的服务器列表.

4.当总服务器接收到子节点改变的事件信息,重新返回第二步.

5.总服务器在Zookeeper中创建节点,zk.create("/search/master", "hostname".getBytes(), Ids.OPEN_ACL_UNSAFE, CreateFlags.EPHEMERAL);

6.备用的总服务器监控Zookeeper中的"/search/master"节点.当这个znode的节点数据改变时,把自己启动变成总服务器,并把自己的网络地址数据放进这个节点.

7.web的cgi从Zookeeper中"/search/master"节点获取总服务器的网络地址数据并向其发送搜索请求.

8.web的cgi监控Zookeeper中的"/search/master"节点,当这个znode的节点数据改变时,从这个节点获取总服务器的网络地址数据,并改变当前的总服务器的网络地址.

        在
我的测试中:一个Zookeeper的集群中,3个Zookeeper节点.一个leader,两个follower的情况下,停掉leader,然后两
个follower选举出一个leader.获取的数据不变.我想Zookeeper能够帮助Hadoop做到:

 

        Hadoop,使用Zookeeper的事件处理确保整个集群只有一个NameNode,存储配置信息等.

        HBase,使用Zookeeper的事件处理确保整个集群只有一个HMaster,察觉HRegionServer联机和宕机,存储访问控制列表等.

 zookeeper是什么

        官方说辞:Zookeeper 分布式服务框架是Apache Hadoop 的一个子项目,它主要是用来解决分布式应用中经常遇到的一些数据管理问题,如:统一命名服务、状态同步服务、集群管理、分布式应用配置项的管理等。

好抽象,我们改变一下方式,先看看它都提供了哪些功能,然后再看看使用它的这些功能能做点什么。

 zookeeper提供了什么

简单的说,zookeeper=文件系统+通知机制。

1、 文件系统

Zookeeper维护一个类似文件系统的数据结构:

                                                          点击查看原图

 

        每个子目录项如 NameService 都被称作为 znode,和文件系统一样,我们能够自由的增加、删除znode,在一个znode下增加、删除子znode,唯一的不同在于znode是可以存储数据的。

有四种类型的znode:

1、PERSISTENT-持久化目录节点

客户端与zookeeper断开连接后,该节点依旧存在

2、 PERSISTENT_SEQUENTIAL-持久化顺序编号目录节点

客户端与zookeeper断开连接后,该节点依旧存在,只是Zookeeper给该节点名称进行顺序编号

3、EPHEMERAL-临时目录节点

客户端与zookeeper断开连接后,该节点被删除

4、EPHEMERAL_SEQUENTIAL-临时顺序编号目录节点

客户端与zookeeper断开连接后,该节点被删除,只是Zookeeper给该节点名称进行顺序编号

 

2、 通知机制

        客户端注册监听它关心的目录节点,当目录节点发生变化(数据改变、被删除、子目录节点增加删除)时,zookeeper会通知客户端。 

就这么简单,下面我们看看能做点什么呢?

 

我们能用zookeeper做什么

1、 命名服务

        这个似乎最简单,在zookeeper的文件系统里创建一个目录,即有唯一的path。在我们使用tborg无法确定上游程序的部署机器时即可与下游程序约定好path,通过path即能互相探索发现,不见不散了。

 

2、 配置管理

        程
序总是需要配置的,如果程序分散部署在多台机器上,要逐个改变配置就变得困难。好吧,现在把这些配置全部放到zookeeper上去,保存在
Zookeeper 的某个目录节点中,然后所有相关应用程序对这个目录节点进行监听,一旦配置信息发生变化,每个应用程序就会收到 Zookeeper
的通知,然后从 Zookeeper 获取新的配置信息应用到系统中就好。

                                         点击查看原图

 

3、 集群管理

所谓集群管理无在乎两点:是否有机器退出和加入、选举master。

        对
于第一点,所有机器约定在父目录GroupMembers下创建临时目录节点,然后监听父目录节点的子节点变化消息。一旦有机器挂掉,该机器与
zookeeper的连接断开,其所创建的临时目录节点被删除,所有其他机器都收到通知:某个兄弟目录被删除,于是,所有人都知道:它上船了。新机器加入
也是类似,所有机器收到通知:新兄弟目录加入,highcount又有了。

        对于第二点,我们稍微改变一下,所有机器创建临时顺序编号目录节点,每次选取编号最小的机器作为master就好。

                                 点击查看原图

 

4、  分布式锁

        有了zookeeper的一致性文件系统,锁的问题变得容易。锁服务可以分为两类,一个是保持独占,另一个是控制时序。

        对
于第一类,我们将zookeeper上的一个znode看作是一把锁,通过createznode的方式来实现。所有客户端都去创建
/distribute_lock
节点,最终成功创建的那个客户端也即拥有了这把锁。厕所有言:来也冲冲,去也冲冲,用完删除掉自己创建的distribute_lock
节点就释放出锁。

        对于第二类, /distribute_lock 已经预先存在,所有客户端在它下面创建临时顺序编号目录节点,和选master一样,编号最小的获得锁,用完删除,依次方便。

                                         点击查看原图

5、队列管理

两种类型的队列:

1、 同步队列,当一个队列的成员都聚齐时,这个队列才可用,否则一直等待所有成员到达。

2、队列按照 FIFO 方式进行入队和出队操作。

第一类,在约定目录下创建临时目录节点,监听节点数目是否是我们要求的数目。

第二类,和分布式锁服务中的控制时序场景基本原理一致,入列有编号,出列按编号。                 

         终于了解完我们能用zookeeper做什么了,可是作为一个程序员,我们总是想狂热了解zookeeper是如何做到这一点的,单点维护一个文件系统没有什么难度,可是如果是一个集群维护一个文件系统保持数据的一致性就非常困难了。

 

分布式与数据复制

Zookeeper作为一个集群提供一致的数据服务,自然,它要在所有机器间做数据复制。数据复制的好处:

1、 容错

一个节点出错,不致于让整个系统停止工作,别的节点可以接管它的工作;

2、提高系统的扩展能力

把负载分布到多个节点上,或者增加节点来提高系统的负载能力;

3、提高性能

让客户端本地访问就近的节点,提高用户访问速度。

 

从客户端读写访问的透明度来看,数据复制集群系统分下面两种:

1、写主(WriteMaster)

对数据的修改提交给指定的节点。读无此限制,可以读取任何一个节点。这种情况下客户端需要对读与写进行区别,俗称读写分离;

2、写任意(Write Any)

对数据的修改可提交给任意的节点,跟读一样。这种情况下,客户端对集群节点的角色与变化透明。

 

        对
zookeeper来说,它采用的方式是写任意。通过增加机器,它的读吞吐能力和响应能力扩展性非常好,而写,随着机器的增多吞吐能力肯定下降(这
也是它建立observer的原因),而响应能力则取决于具体实现方式,是延迟复制保持最终一致性,还是立即复制快速响应。

我们关注的重点还是在如何保证数据在集群所有机器的一致性,这就涉及到paxos算法。

 

数据一致性与paxos算法

        据说Paxos算法的难理解与算法的知名度一样令人敬仰,所以我们先看如何保持数据的一致性,这里有个原则就是:

在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。

        Paxos
算法解决的什么问题呢,解决的就是保证每个节点执行相同的操作序列。好吧,这还不简单,master维护一个全局写队列,所有写操作都必须
放入这个队列编号,那么无论我们写多少个节点,只要写操作是按编号来的,就能保证一致性。没错,就是这样,可是如果master挂了呢。

        Paxos
算法通过投票来对写操作进行全局编号,同一时刻,只有一个写操作被批准,同时并发的写操作要去争取选票,只有获得过半数选票的写操作才会被
批准(所以永远只会有一个写操作得到批准),其他的写操作竞争失败只好再发起一轮投票,就这样,在日复一日年复一年的投票中,所有写操作都被严格编号排
序。编号严格递增,当一个节点接受了一个编号为100的写操作,之后又接受到编号为99的写操作(因为网络延迟等很多不可预见原因),它马上能意识到自己
数据不一致了,自动停止对外服务并重启同步过程。任何一个节点挂掉都不会影响整个集群的数据一致性(总2n+1台,除非挂掉大于n台)。

总结

        Zookeeper
作为 Hadoop 项目中的一个子项目,是 Hadoop 集群管理的一个必不可少的模块,它主要用来控制集群中的数据,如它管理 Hadoop
集群中的 NameNode,还有 Hbase 中 Master Election、Server 之间状态同步等。

 

Zookeeper工作原理

        ZooKeeper
是一个分布式的,开放源码的分布式应用程序协调服务,它包含一个简单的原语集,分布式应用程序可以基于它实现同步服务,配置维护和
命名服务等。Zookeeper是hadoop的一个子项目,其发展历程无需赘述。在分布式应用中,由于工程师不能很好地使用锁机制,以及基于消息的协调

机制不适合在某些应用中使用,因此需要有一种可靠的、可扩展的、分布式的、可配置的协调机制来统一系统的状态。Zookeeper的目的就在于此。本文简
单分析zookeeper的工作原理,对于如何使用zookeeper不是本文讨论的重点。

Zookeeper的基本概念

1.1 角色

Zookeeper中的角色主要有以下三类,如下表所示:

                         点击查看原图

系统模型如图所示:

                         点击查看原图
        

1.2 设计目的

1.最终一致性:client不论连接到哪个Server,展示给它都是同一个视图,这是zookeeper最重要的性能。

2 .可靠性:具有简单、健壮、良好的性能,如果消息m被到一台服务器接受,那么它将被所有的服务器接受。

3 .实时性:Zookeeper保证客户端将在一个时间间隔范围内获得服务器的更新信息,或者服务器失效的信息。但由于网络延时等原因,Zookeeper不能保证两个客户端能同时得到刚更新的数据,如果需要最新数据,应该在读数据之前调用sync()接口。

4 .等待无关(wait-free):慢的或者失效的client不得干预快速的client的请求,使得每个client都能有效的等待。

5.原子性:更新只能成功或者失败,没有中间状态。

6 .顺序性:包括全局有序和偏序两种:全局有序是指如果在一台服务器上消息a在消息b前发布,则在所有Server上消息a都将在消息b前被发布;偏序是指如果一个消息b在消息a后被同一个发送者发布,a必将排在b前面。

 ZooKeeper的工作原理

        Zookeeper
的核心是原子广播,这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。Zab协议有两种模式,它们分
别是恢复模式(选主)和广播模式(同步)。当服务启动或者在领导者崩溃后,Zab就进入了恢复模式,当领导者被选举出来,且大多数Server完成了和
leader的状态同步以后,恢复模式就结束了。状态同步保证了leader和Server具有相同的系统状态。

        为
了保证事务的顺序一致性,zookeeper采用了递增的事务id号(zxid)来标识事务。所有的提议(proposal)都在被提出的时候加上
了zxid。实现中zxid是一个64位的数字,它高32位是epoch用来标识leader关系是否改变,每次一个leader被选出来,它都会有一个
新的epoch,标识当前属于那个leader的统治时期。低32位用于递增计数。

每个Server在工作过程中有三种状态:

  • LOOKING:当前Server不知道leader是谁,正在搜寻
  • LEADING:当前Server即为选举出来的leader
  • FOLLOWING:leader已经选举出来,当前Server与之同步

2.1 选主流程

 
   
当leader崩溃或者leader失去大多数的follower,这时候zk进入恢复模式,恢复模式需要重新选举出一个新的leader,让所有的
Server都恢复到一个正确的状态。Zk的选举算法有两种:一种是基于basic paxos实现的,另外一种是基于fast
paxos算法实现的。系统默认的选举算法为fast paxos。先介绍basic paxos流程:

        1 .选举线程由当前Server发起选举的线程担任,其主要功能是对投票结果进行统计,并选出推荐的Server;

        2 .选举线程首先向所有Server发起一次询问(包括自己);

        3

.选举线程收到回复后,验证是否是自己发起的询问(验证zxid是否一致),然后获取对方的id(myid),并存储到当前询问对象列表中,最后获取对方
提议的leader相关信息(        id,zxid),并将这些信息存储到当次选举的投票记录表中;

        4.  收到所有Server回复以后,就计算出zxid最大的那个Server,并将这个Server相关信息设置成下一次要投票的Server;

        5.
 线程将当前zxid最大的Server设置为当前Server要推荐的Leader,如果此时获胜的Server获得n/2 +
1的Server票数,
设置当前推荐的leader为获胜的Server,将根据获胜的Server相关信息设置自己的状态,否则,继续这个过程,直到leader被选举出来。

    通过流程分析我们可以得出:要使Leader获得多数Server的支持,则Server总数必须是奇数2n+1,且存活的Server的数目不得少于n+1.

    每个Server启动后都会重复以上流程。在恢复模式下,如果是刚从崩溃状态恢复的或者刚启动的server还会从磁盘快照中恢复数据和会话信息,zk会记录事务日志并定期进行快照,方便在恢复时进行状态恢复。选主的具体流程图如下所示:

                                         点击查看原图

 
    fast
paxos流程是在选举过程中,某Server首先向所有Server提议自己要成为leader,当其它Server收到提议以后,解决epoch和
zxid的冲突,并接受对方的提议,然后向对方发送接受提议完成的消息,重复这个流程,最后一定能选举出Leader。其流程图如下所示:

                         点击查看原图

2.2 同步流程

选完leader以后,zk就进入状态同步过程。

        1. leader等待server连接;

        2 .Follower连接leader,将最大的zxid发送给leader;

        3 .Leader根据follower的zxid确定同步点;

        4 .完成同步后通知follower 已经成为uptodate状态;

        5 .Follower收到uptodate消息后,又可以重新接受client的请求进行服务了。

流程图如下所示:

                                 点击查看原图

2.3 工作流程

2.3.1 Leader工作流程

Leader主要有三个功能:

        1 .恢复数据;

        2 .维持与Learner的心跳,接收Learner请求并判断Learner的请求消息类型;

        3 .Learner的消息类型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息,根据不同的消息类型,进行不同的处理。

        PING
消息是指Learner的心跳信息;REQUEST消息是Follower发送的提议信息,包括写请求及同步请求;ACK消息是
Follower的对提议的回复,超过半数的Follower通过,则commit该提议;REVALIDATE消息是用来延长SESSION有效时间。

Leader的工作流程简图如下所示,在实际实现中,流程要比下图复杂得多,启动了三个线程来实现功能。

                                 点击查看原图

2.3.2 Follower工作流程

Follower主要有四个功能:

        1. 向Leader发送请求(PING消息、REQUEST消息、ACK消息、REVALIDATE消息);

        2 .接收Leader消息并进行处理;

        3 .接收Client的请求,如果为写请求,发送给Leader进行投票;

        4 .返回Client结果。

Follower的消息循环处理如下几种来自Leader的消息:

        1 .PING消息: 心跳消息;

        2 .PROPOSAL消息:Leader发起的提案,要求Follower投票;

        3 .COMMIT消息:服务器端最新一次提案的信息;

        4 .UPTODATE消息:表明同步完成;

        5 .REVALIDATE消息:根据Leader的REVALIDATE结果,关闭待revalidate的session还是允许其接受消息;

        6 .SYNC消息:返回SYNC结果到客户端,这个消息最初由客户端发起,用来强制得到最新的更新。

Follower的工作流程简图如下所示,在实际实现中,Follower是通过5个线程来实现功能的。

                         点击查看原图

对于observer的流程不再叙述,observer流程和Follower的唯一不同的地方就是observer不会参加leader发起的投票。

  

附录:

ZooKeeper典型使用场景一览

        ZooKeeper
是一个高可用的分布式数据管理与系统协调框架。基于对Paxos算法的实现,使该框架保证了分布式环境中数据的强一致性,也正是基
于这样的特性,使得zookeeper能够应用于很多场景。网上对zk的使用场景也有不少介绍,本文将结合作者身边的项目例子,系统的对zk的使用场景进
行归类介绍。
值得注意的是,zk并不是生来就为这些场景设计,都是后来众多开发者根据框架的特性,摸索出来的典型使用方法。因此,也非常欢迎你分享你在ZK使用上的奇
技淫巧。

        

场景类别

典型场景描述(ZK特性,使用方法)

应用中的具体使用

数据发布与订阅

发布与订阅即所谓的配置管理,顾名思义就是将数据发布到zk节点上,供订阅者动态获取数据,实现配置信息的集中式管理和动态更新。例如全局的配置信息,地址列表等就非常适合使用。

1. 索引信息和集群中机器节点状态存放在zk的一些指定节点,供各个客户端订阅使用。2. 系统日志(经过处理后的)存储,这些日志通常2-3天后被清除。

 

3. 应用中用到的一些配置信息集中管理,在应用启动的时候主动来获取一次,并且在节点上注册一个Watcher,以后每次配置有更新,实时通知到应用,获取最新配置信息。

4. 业务逻辑中需要用到的一些全局变量,比如一些消息中间件的消息队列通常有个offset,这个offset存放在zk上,这样集群中每个发送者都能知道当前的发送进度。

5. 系统中有些信息需要动态获取,并且还会存在人工手动去修改这个信息。以前通常是暴露出接口,例如JMX接口,有了zk后,只要将这些信息存放到zk节点上即可。

Name Service

这个主要是作为分布式命名服务,通过调用zk的create node api,能够很容易创建一个全局唯一的path,这个path就可以作为一个名称。

 

分布通知/协调

ZooKeeper

中特有watcher注册与异步通知机制,能够很好的实现分布式环境下不同系统之间的通知与协调,实现对数据变更的实时处理。使用方法通常是不同系统都对

ZK上同一个znode进行注册,监听znode的变化(包括znode本身内容及子节点的),其中一个系统update了znode,那么另一个系统能
够收到通知,并作出相应处理。

1.
另一种心跳检测机制:检测系统和被检测系统之间并不直接关联起来,而是通过zk上某个节点关联,大大减少系统耦合。2.
另一种系统调度模式:某系统有控制台和推送系统两部分组成,控制台的职责是控制推送系统进行相应的推送工作。管理人员在控制台作的一些操作,实际上是修改
了ZK上某些节点的状态,而zk就把这些变化通知给他们注册Watcher的客户端,即推送系统,于是,作出相应的推送任务。

 

3. 另一种工作汇报模式:一些类似于任务分发系统,子任务启动后,到zk来注册一个临时节点,并且定时将自己的进度进行汇报(将进度写回这个临时节点),这样任务管理者就能够实时知道任务进度。

总之,使用zookeeper来进行分布式通知和协调能够大大降低系统之间的耦合。

分布式锁

分布式锁,这个主要得益于ZooKeeper为我们保证了数据的强一致性,即用户只要完全相信每时每刻,zk集群中任意节点(一个zk server)上的相同znode的数据是一定是相同的。锁服务可以分为两类,一个是保持独占,另一个是控制时序。

 

谓保持独占,就是所有试图来获取这个锁的客户端,最终只有一个可以成功获得这把锁。通常的做法是把zk上的一个znode看作是一把锁,通过create
znode的方式来实现。所有客户端都去创建 /distribute_lock 节点,最终成功创建的那个客户端也即拥有了这把锁。


制时序,就是所有视图来获取这个锁的客户端,最终都是会被安排执行,只是有个全局时序了。做法和上面基本类似,只是这里
/distribute_lock
已经预先存在,客户端在它下面创建临时有序节点(这个可以通过节点的属性控制:CreateMode.EPHEMERAL_SEQUENTIAL来指
定)。Zk的父节点(/distribute_lock)维持一份sequence,保证子节点创建的时序性,从而也形成了每个客户端的全局时序。

 

集群管理

1. 集群机器

控:这通常用于那种对集群中机器状态,机器在线率有较高要求的场景,能够快速对集群中机器变化作出响应。这样的场景中,往往有一个监控系统,实时检测集群
机器是否存活。过去的做法通常是:监控系统通过某种手段(比如ping)定时检测每个机器,或者每个机器自己定时向监控系统汇报“我还活着”。
这种做法可行,但是存在两个比较明显的问题:1. 集群中机器有变动的时候,牵连修改的东西比较多。2. 有一定的延时。

 


用ZooKeeper有两个特性,就可以实时另一种集群机器存活性监控系统:a. 客户端在节点 x 上注册一个Watcher,那么如果
x 的子节点变化了,会通知该客户端。b. 创建EPHEMERAL类型的节点,一旦客户端和服务器的会话结束或过期,那么该节点就会消失。


如,监控系统在 /clusterServers 节点上注册一个Watcher,以后每动态加机器,那么就往 /clusterServers
下创建一个 EPHEMERAL类型的节点:/clusterServers/{hostname}.
这样,监控系统就能够实时知道机器的增减情况,至于后续处理就是监控系统的业务了。

2. Master选举则是zookeeper中最为经典的使用场景了。

分布式环境中,相同的业务应用分布在不同的机器上,有些业务逻辑(例如一些耗时的计算,网络I/O处理),往往只需要让整个集群中的某一台机器进行执行,
其余机器可以共享这个结果,这样可以大大减少重复劳动,提高性能,于是这个master选举便是这种场景下的碰到的主要问题。

利用ZooKeeper的强一致性,能够保证在分布式高并发情况下节点创建的全局唯一性,即:同时有多个客户端请求创建 /currentMaster 节点,最终一定只有一个客户端请求能够创建成功。

利用这个特性,就能很轻易的在分布式环境中进行集群选取了。

另外,这种场景演化一下,就是动态Master选举。这就要用到 EPHEMERAL_SEQUENTIAL类型节点的特性了。

文中提到,所有客户端创建请求,最终只有一个能够创建成功。在这里稍微变化下,就是允许所有请求都能够创建成功,但是得有个创建顺序,于是所有的请求最终
在ZK上创建结果的一种可能情况是这样: /currentMaster/{sessionId}-1
, /currentMaster/{sessionId}-2 , /currentMaster/{sessionId}-3 …..
每次选取序列号最小的那个机器作为Master,如果这个机器挂了,由于他创建的节点会马上小时,那么之后最小的那个机器就是Master了。

1.

在搜索系统中,如果集群中每个机器都生成一份全量索引,不仅耗时,而且不能保证彼此之间索引数据一致。因此让集群中的Master来进行全量索引的生成,
然后同步到集群中其它机器。2.
另外,Master选举的容灾措施是,可以随时进行手动指定master,就是说应用在zk在无法获取master信息时,可以通过比如http方式,向
一个地方获取master。

分布式队列

队列方面,我目前感觉有两种,一种是常规的先进先出队列,另一种是要等到队列成员聚齐之后的才统一按序执行。对于第二种先进先出队列,和分布式锁服务中的控制时序场景基本原理一致,这里不再赘述。

 


二种队列其实是在FIFO队列的基础上作了一个增强。通常可以在 /queue 这个znode下预先建立一个/queue/num
节点,并且赋值为n(或者直接给/queue赋值n),表示队列大小,之后每次有队列成员加入后,就判断下是否已经到达队列大小,决定是否可以开始执行
了。这种用法的典型场景是,分布式环境中,一个大任务Task
A,需要在很多子任务完成(或条件就绪)情况下才能进行。这个时候,凡是其中一个子任务完成(就绪),那么就去 /taskList
下建立自己的临时时序节点(CreateMode.EPHEMERAL_SEQUENTIAL),当 /taskList
发现自己下面的子节点满足指定个数,就可以进行下一步按序进行处理了。

 

 
参考: 

http://zookeeper.apache.org/
http://blog.csdn.net/cutesource/article/details/5822459
http://blog.csdn.net/pwlazy/article/details/8080626
http://nileader.blog.51cto.com/1381108/795265
http://nileader.blog.51cto.com/1381108/926753
http://nileader.blog.51cto.com/1381108/795230
http://netcome.iteye.com/blog/1474255
 

发表在 technologys | zookeeper已关闭评论

ZooKeeper 数据流动图


ZooKeeper的基本原理

ZooKeeper是以Fast Paxos算法为基础的,通过选举产生一个leader,只有leader才能提交propose,具体算法可见Fast Paxos

 

2)ZooKeeper的基本运转流程

ZooKeeper主要存在以下两个流程:

  • 选举Leader
  • 同步数据

选举Leader过程中算法有很多,但要达到的选举标准是一致的:

  • Leader要具有最高的zxid 
  • 集群中大多数的机器得到响应并follow选出的Leader

下图为ZooKeeper数据流动图,比较直观地描述了ZooKeeper是如何同步数据的:

 

点击查看原图

 

参考:

http://zookeeper.apache.org/doc/trunk/zookeeperOver.html

 

 

发表在 technologys | ZooKeeper 数据流动图已关闭评论

2016年续费的27家机构

资料备份供自身查询,资料来源:

中国人民银行公告〔2016〕第17号

http://c.m.163.com/news/a/BU9GAJHN00097U7R.html?spss=newsapp&spsw=1

 

点击查看原图点击查看原图点击查看原图

发表在 article | 2016年续费的27家机构已关闭评论

10大基础算法

一:快速排序算法

 

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤:

1 从数列中挑出一个元素,称为 “基准”(pivot),

2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去

点击查看原图


参考:

快速排序

https://zh.wikipedia.org/zh-hant/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#C.23 

二:堆排序算法

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤:

  1. 创建一个堆H[0..n-1]
  2. 把堆首(最大值)和堆尾互换

3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4. 重复步骤2,直到堆的尺寸为1

点击查看原图


参考:

堆排序

 

三:归并排序

归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法步骤:

1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素直接复制到合并序列尾

点击查看原图

 

参考:

归并排序

 

四:二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜
素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组
为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半,时间复杂度为
Ο(logn) 。

 

详细介绍:二分查找算法

 

五:BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分
析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂
度,五位算法作者做了精妙的处理。

算法步骤:

1. 将n个元素每5个一组,分成n/5(上界)组。

2. 取出每一组的中位数,任意排序方法,比如插入排序。

3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

5. 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。

终止条件:n=1时,返回的即是i小元素。


参考:

寻找最小(最大)的k个数

线性查找相关算法


六:DFS(深度优先搜索)

深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分
支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发
现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤:

1. 访问顶点v;

2. 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

3. 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

上述描述可能比较抽象,举个实例:

DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,… 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

 

参考:深度优先搜索

 

七:BFS(广度优先搜索)

广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤:

1. 首先将根节点放入队列中。

2. 从队列中取出第一个节点,并检验它是否为目标。

  • 如果找到目标,则结束搜寻并回传结果。
  • 否则将它所有尚未检验过的直接子节点加入队列中。

3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4. 重复步骤2。

点击查看原图

参考:广度优先搜索

 

八:Dijkstra算法

戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图 G,以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(uv) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合,而边的权重则由权重函数 wE → [0, ∞] 定义。因此,w(uv) 就是从顶点 u 到顶点 v 的非负权重(weight)。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重,就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t,Dijkstra 算法可以找到 s 到 t的最低权重路径(例如,最短路径)。这个算法也可以在一个图中,找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。

算法步骤:

1. 初始时令 S={V0},T={其余顶点},T中顶点对应的距离值

若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>,d(V0,Vi)为∞

2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S

3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值

重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止

点击查看原图

 

参考:Dijkstra算法

九:动态规划算法

动态规划(Dynamic programming)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多
子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个
子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

算法步骤:

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。
动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是
在表格中简单地查看一下结果,从而获得较高的效率

 

参考:

从全球导航到输入法:谈谈动态规划

动态规划

 

十:朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,
如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

 

参考:

贝叶斯网络

朴素贝叶斯分类算法

 

 

 

发表在 technologys | 10大基础算法已关闭评论

OSI 模型与 TCP/IP

以下是 维基百科 中关于OSI 模型的说明:

开放式系统互联通信参考模型(英语:Open System Interconnection Reference Model,ISO/IEC 7498-1),简称为OSI模型(OSI model),一种概念模型,由国际标准化组织(ISO)提出,一个试图使各种计算机在世界范围内互连为网络的标准框架。


而 TCP/IP 协议可以看做是对 OSI 模型的一种简化(以下内容来自 维基百科):

它将软件通信过程抽象化为四个抽象层,采取协议堆叠的方式,分别实作出不同通信协议。协议套组下的各种协议,依其功能不同,被分别归属到这四个阶层之中7,常被视为是简化的七层OSI模型。



一张图详细介绍了 TCP/IP 协议族中的各个协议在 OSI模型 中的分布,一图胜千言(下图来自 科来):
点击查看原图

TCP/IP 协议和 OSI 模型的内容,在互联网上有很多。我没有必要再次介绍它们。在这里,我们只需要知道,HTTP、WebSocket 等协议都是处于 OSI 模型的最高层: 应用层 。而 IP 协议工作在网络层(第3层),TCP 协议工作在传输层(第4层)。

至于 OSI 模型的各个层次都有什么系统和它们对应,这里有篇很好的文章可以满足大家的求知欲:OSI七层模型详解

发表在 network | 标签为 , | OSI 模型与 TCP/IP已关闭评论

Authorization

授权模块代码片段:

/// <summary>
    /// HTTP模块默认授权配置
    /// </summary>
    public class Authorization
    {
        Dictionary<string, string> users;
        bool hasValidate;

        /// <summary>
        /// 获取用户总数
        /// </summary>
        public int UserCount
        {
            get
            {
                return this.users.Count;
            }
        }

        /// <summary>
        /// 是否具有验证项
        /// </summary>
        public bool HasValidate
        {
            get { return this.hasValidate; }
        }

        internal Authorization()
        {
            this.users = new Dictionary<string, string>();
            this.LoadUsers("Authorization");
            this.hasValidate = this.users.Count > 0;
        }

        /// <summary>
        /// Authorization
        /// </summary>
        /// <param name="sectionName">配置节名称</param>
        public Authorization(string sectionName)
        {
            if ("Authorization".Equals(sectionName, StringComparison.OrdinalIgnoreCase))
                throw new ArgumentOutOfRangeException("sectionName", "no allows you to define Authorization");

            this.users = new Dictionary<string, string>();
            this.LoadUsers(sectionName);
            this.hasValidate = this.users.Count > 0;
        }

        private void LoadUsers(string sectionName)
        {
            var section = System.Configuration.ConfigurationManager.GetSection(sectionName) as IDictionary;
            if (section != null)
            {
                var enumerator = section.GetEnumerator();
                while (enumerator.MoveNext())
                {
                    this.users.Add(Convert.ToString(enumerator.Key), Convert.ToString(enumerator.Value));
                }
            }
        }

        /// <summary>
        /// 检验是否合法
        /// </summary>
        /// <param name="username"></param>
        /// <param name="password"></param>
        /// <returns>true 通过 / false 不通过</returns>
        public bool Validate(string username, string password)
        {
            if (this.hasValidate == false)
            {
                //不需要认证
                return true;
            }

            var sourcePassword = "";
            return this.users.TryGetValue(username, out sourcePassword) && sourcePassword.Equals(password);
        }

 

 

发表在 C# Code | Authorization已关闭评论

CommandLine Parse Code Fragment

Command Line Parse Code Fragment

 

internal class CommandLine
    {
        /// <summary>
        /// get process command line info
        /// </summary>
        /// <param name="processId"></param>
        /// <returns>command line info, array length is 2, ex: ["C:\Windows\system32\svchost.exe","-k LocalService"]</returns>
        public static String[] GetCommandLineInfo(int processId)
        {
            String[] info = new string[2];
            info[0] = "";
            info[1] = "";
            //
            var commandLine = Wmi.GetCommandLine(processId);
            if (commandLine != "")
            {
                info = ParseCommandLine(commandLine);
            }
            return info;
        }

        /// <summary>
        /// get process command line info
        /// </summary>
        /// <param name="commandLine"></param>
        /// <returns>command line info, array length is 2, ex: ["C:\Windows\system32\svchost.exe","-k LocalService"]</returns>
        public static string[] ParseCommandLine(string commandLine)
        {
            string[] info = new String[2];

            //C:\Windows\system32\svchost.exe -k LocalService
            //"C:\Program Files (x86)\Avira\AntiVir Desktop\avgnt.exe" /min

            if (commandLine[0] == '"')
            {
                int end = commandLine.IndexOf('"', 1);
                if (end == -1)
                {
                    info[0] = commandLine;
                    info[1] = "";
                }
                else if (end + 1 < commandLine.Length)
                {
                    info[0] = commandLine.Substring(1, end + 1);
                    info[1] = commandLine.Substring(end + 1).TrimStart(' ');
                }
                else
                {
                    info[0] = commandLine;
                    info[1] = "";
                }
            }
            else
            {
                int pos = commandLine.IndexOf(' ');
                if (pos == -1)
                {
                    info[0] = commandLine;
                    info[1] = "";
                }
                else if (pos + 1 < commandLine.Length)
                {
                    info[0] = commandLine.Substring(0, pos);
                    info[1] = commandLine.Substring(pos + 1).TrimStart(' ');
                }
                else
                {
                    info[0] = commandLine;
                    info[1] = "";
                }
            }

            return info;
        }
    }

 

 

.

发表在 C# Code | CommandLine Parse Code Fragment已关闭评论

Quartz Misfire处理规则

调度(scheduleJob)或恢复调度(resumeTrigger,resumeJob)后不同的misfire对应的处理规则


CronTrigger

withMisfireHandlingInstructionDoNothing
——不触发立即执行
——等待下次Cron触发频率到达时刻开始按照Cron频率依次执行

withMisfireHandlingInstructionIgnoreMisfires
——以错过的第一个频率时间立刻开始执行
——重做错过的所有频率周期后
——当下一次触发频率发生时间大于当前时间后,再按照正常的Cron频率依次执行

withMisfireHandlingInstructionFireAndProceed
——以当前时间为触发频率立刻触发一次执行
——然后按照Cron频率依次执行


SimpleTrigger

withMisfireHandlingInstructionFireNow
——以当前时间为触发频率立即触发执行
——执行至FinalTIme的剩余周期次数
——以调度或恢复调度的时刻为基准的周期频率,FinalTime根据剩余次数和当前时间计算得到
——调整后的FinalTime会略大于根据starttime计算的到的FinalTime值

withMisfireHandlingInstructionIgnoreMisfires

——以错过的第一个频率时间立刻开始执行
——重做错过的所有频率周期
——当下一次触发频率发生时间大于当前时间以后,按照Interval的依次执行剩下的频率
——共执行RepeatCount+1次

withMisfireHandlingInstructionNextWithExistingCount
——不触发立即执行
——等待下次触发频率周期时刻,执行至FinalTime的剩余周期次数
——以startTime为基准计算周期频率,并得到FinalTime
——即使中间出现pause,resume以后保持FinalTime时间不变

withMisfireHandlingInstructionNowWithExistingCount
——以当前时间为触发频率立即触发执行
——执行至FinalTIme的剩余周期次数
——以调度或恢复调度的时刻为基准的周期频率,FinalTime根据剩余次数和当前时间计算得到
——调整后的FinalTime会略大于根据starttime计算的到的FinalTime值

withMisfireHandlingInstructionNextWithRemainingCount
——不触发立即执行
——等待下次触发频率周期时刻,执行至FinalTime的剩余周期次数
——以startTime为基准计算周期频率,并得到FinalTime
——即使中间出现pause,resume以后保持FinalTime时间不变

withMisfireHandlingInstructionNowWithRemainingCount
——以当前时间为触发频率立即触发执行
——执行至FinalTIme的剩余周期次数
——以调度或恢复调度的时刻为基准的周期频率,FinalTime根据剩余次数和当前时间计算得到

——调整后的FinalTime会略大于根据starttime计算的到的FinalTime值

MISFIRE_INSTRUCTION_RESCHEDULE_NOW_WITH_REMAINING_REPEAT_COUNT
——此指令导致trigger忘记原始设置的starttime和repeat-count
——触发器的repeat-count将被设置为剩余的次数

——这样会导致后面无法获得原始设定的starttime和repeat-count值


发表在 technologys | 标签为 , | Quartz Misfire处理规则已关闭评论

Adf.Smtp

配置描述:

默认实例可通过Smtp.Config,  Global.Config, AppSetting 配置

优先级以 AppSetting->Global.Config->Smtp.Config

 

配置项:

 

SmtpEnabled:    是否启用 ,必需,值为 true/false

SmtpHost:    主机地址,例: smtp.mail.com,非必需

SmtpPort:    端口,非必需, 默认为 25

SmtpAccount:    在配置了SmtpHost时,登录主机的帐号,非必需

SmtpPassword:    在配置了SmtpHost时,登录主机的帐号,非必需

SmtpSender:    默认的邮件发送者地址,与SmtpSenderRandomDomain互斥,非必需

SmtpName:    默认的发送者显示名称,非必需

SmtpSSLEnabled:    是否启用SSL登录,默认false,非必需

SmtpSenderRandomDomain:    默认随机产生邮件发送地址的域名部份与SmtpSender互斥,非必需

 

注:以上SmtpSender / SmtpSenderRandomDomain必需配置或在应用程式中设置一个

 

配置示例:

Smtp.config

<?xml version="1.0" encoding="utf-8"?>
<configuration>

  <!-- 是否启用 -->
  <item name="SmtpEnabled" value="true"/>
  <!-- 发送主机 -->
  <item name="SmtpHost" value="smtp.mymail.com" />
  <!-- 发送端口 -->
  <item name="SmtpPort" value="25" />
  <!-- 登录主机的帐户 -->
  <item name="SmtpAccount" value="" />
  <!-- 登录主机的帐户名 -->
  <item name="SmtpPassword" value="" />
  <!-- 邮件默认发送者, 此配置与SmtpSenderRandomDomain互斥 -->
  <item name="SmtpSender" value="" />
  <!-- 邮件默认发送显示名 -->
  <item name="SmtpName" value="" />
  <!-- 是否启动SSL连接-->
  <item name="SmtpSSLEnabled" value="" />
  <!-- 默认邮件发送使用的随机发送地址域名部份,为空时不启用, 此配置与SmtpSender互斥 -->
  <item name="SmtpSenderRandomDomain" value="" />


</configuration>

 

 

 

 .

发表在 adf | 标签为 | Adf.Smtp已关闭评论

MySQL大数据场景的优化和运维之道

前言

MySQL数据库大家应该都很熟悉,而且随着前几年的阿里的去IOE,MySQL逐渐引起更多人的重视。

MySQL历史

  • 1979年,Monty Widenius写了最初的版本,96年发布1.0

  • 1995-2000年,MySQL AB成立,引入BDB

  • 2000年4月,集成MyISAM和replication

  • 2001年,Heikki Tuuri向MySQL建议集成InnoDB

  • 2003发布5.0,提供了视图、存储过程等功能

  • 2008年,MySQL AB被Sun收购,09年推出5.1

  • 2009年4月,Oracle收购Sun,2010年12月推出5.5

  • 2013年2月推出5.6 GA,5.7开发中

MySQL的优点

  • 使用简单

  • 开源免费

  • 扩展性“好”,在一定阶段扩展性好

  • 社区活跃

  • 性能可以满足互联网存储和性能需求,离不开硬件支持

上面这几个因素也是大多数公司选择考虑MySQL的原因。不过MySQL本身存在的问题和限制也很多,有些问题点也经常被其他数据库吐槽或鄙视

MySQL存在的问题

  • 优化器对复杂SQL支持不好

  • 对SQL标准支持不好

  • 大规模集群方案不成熟,主要指中间件

  • ID生成器,全局自增ID

  • 异步逻辑复制,数据安全性问题

  • Online DDL

  • HA方案不完善

  • 备份和恢复方案还是比较复杂,需要依赖外部组件

  • 展现给用户信息过少,排查问题困难

  • 众多分支,让人难以选择


到了刚才讲的MySQL的优势和劣势,可以看到MySQL面临的问题还是远大于它的优势的,很多问题也是我们实际需要在运维中优化解决的,这也是
MySQL
DBA的一方面价值所在。并且MySQL的不断发展也离不开社区支持,比如Google最早提交的半同步patch,后来也合并到官方主线。
Facebook Twitter等也都开源了内部使用MySQL分支版本,包含了他们内部使用的patch和特性。

数据库开发规范

数据库开发规范定义:开发规范是针对内部开发的一系列建议或规则, 由DBA制定(如果有DBA的话)。

开发规范本身也包含几部分:基本命名和约束规范,字段设计规范,索引规范,使用规范。

规范存在意义

  • 保证线上数据库schema规范

  • 减少出问题概率

  • 方便自动化管理

  • 规范需要长期坚持,对开发和DBA是一个双赢的事情

想想没有开发规范,有的开发写出各种全表扫描的SQL语句或者各种奇葩SQL语句,我们之前就看过开发写的SQL 可以打印出好几页纸。这种造成业务本身不稳定,也会让DBA天天忙于各种救火。

基本命名和约束规范

  • 表字符集选择UTF8 ,如果需要存储emoj表情,需要使用UTF8mb4(MySQL 5.5.3以后支持)

  • 存储引擎使用InnoDB

  • 变长字符串尽量使用varchar varbinary

  • 不在数据库中存储图片、文件等

  • 单表数据量控制在1亿以下

  • 库名、表名、字段名不使用保留字

  • 库名、表名、字段名、索引名使用小写字母,以下划线分割 ,需要见名知意

  • 库表名不要设计过长,尽可能用最少的字符表达出表的用途

字段规范

  • 所有字段均定义为NOT NULL ,除非你真的想存Null

  • 字段类型在满足需求条件下越小越好,使用UNSIGNED存储非负整数 ,实际使用时候存储负数场景不多

  • 使用TIMESTAMP存储时间

  • 使用varchar存储变长字符串 ,当然要注意varchar(M)里的M指的是字符数不是字节数;使用UNSIGNED INT存储IPv4 地址而不是CHAR(15) ,这种方式只能存储IPv4,存储不了IPv6

  • 使用DECIMAL存储精确浮点数,用float有的时候会有问题

  • 少用blob text

关于为什么定义不使用Null的原因

* 1.浪费存储空间,因为InnoDB需要有额外一个字节存储

* 2.表内默认值Null过多会影响优化器选择执行计划

关于使用datatime和timestamp,现在在5.6.4之后又有了变化,使用二者存储在存储空间上大差距越来越小 ,并且本身datatime存储范围就比timestamp大很多,timestamp只能存储到2038年

点击查看原图

索引规范

  • 单个索引字段数不超过5,单表索引数量不超过5,索引设计遵循B+ Tree索引最左前缀匹配原则

  • 选择区分度高的列作为索引

  • 建立的索引能覆盖80%主要的查询,不求全,解决问题的主要矛盾

  • DML和order by和group by字段要建立合适的索引

  • 避免索引的隐式转换

  • 避免冗余索引

关于索引规范,一定要记住索引这个东西是一把双刃剑,在加速读的同时也引入了很多额外的写入和锁,降低写入能力,这也是为什么要控制索引数原因。之前看到过不少人给表里每个字段都建了索引,其实对查询可能起不到什么作用。

冗余索引例子

  • idx_abc(a,b,c)

  • idx_a(a) 冗余

  • idx_ab(a,b) 冗余

隐式转换例子

字段:remark varchar(50) NOT Null

MySQL>SELECT id, gift_code FROM gift WHERE deal_id = 640 AND remark=115127; 1 row in set (0.14 sec)

MySQL>SELECT id, gift_code FROM pool_gift WHEREdeal_id = 640 AND remark=‘115127’; 1 row in set (0.005 sec)

字段定义为varchar,但传入的值是个int,就会导致全表扫描,要求程序端要做好类型检查

SQL类规范

  • 尽量不使用存储过程、触发器、函数等

  • 避免使用大表的JOIN,MySQL优化器对join优化策略过于简单

  • 避免在数据库中进行数学运算和其他大量计算任务

  • SQL合并,主要是指的DML时候多个value合并,减少和数据库交互

  • 合理的分页,尤其大分页

  • UPDATE、DELETE语句不使用LIMIT ,容易造成主从不一致

数据库运维规范

运维规范主要内容

  • SQL审核,DDL审核和操作时间,尤其是OnlineDDL

  • 高危操作检查,Drop前做好数据备份

  • 权限控制和审计

  • 日志分析,主要是指的MySQL慢日志和错误日志

  • 高可用方案

  • 数据备份方案

版本选择

  • MySQL社区版,用户群体最大

  • MySQL企业版,收费

  • Percona Server版,新特性多

  • MariaDB版,国内用户不多

建议选择优先级为:MySQL社区版 > Percona Server > MariaDB > MySQL 企业版

不过现在如果大家使用RDS服务,基本还以社区版为主

Online DDL问题

原生MySQL执行DDL时需要锁表,且锁表期间业务是无法写入数据的,对服务影响很大,MySQL对这方面的支持是比较差的。大表做DDL对DBA来说是很痛苦的,相信很多人经历过。如何做到Online DDL呢,是不是就无解了呢?当然不是!

点击查看原图

上面表格里提到的 Facebook OSC和5.6 OSC也是目前两种比较靠谱的方案

MySQL 5.6的OSC方案还是解决不了DDL的时候到从库延时的问题,所以现在建议使用Facebook OSC这种思路更优雅

下图是Facebook OSC的思路

点击查看原图

后来Percona公司根据Facebook OSC思路,用perl重写了一版,就是我们现在用得很多的pt-online-schema-change,软件本身非常成熟,支持目前主流版本。

使用pt-online-schema-change的优点有:

  • 1.无阻塞写入

  • 2.完善的条件检测和延时负载策略控制

值得一提的是,腾讯互娱的DBA在内部分支上也实现了Online DDL,之前测试过确实不错,速度快,原理是通过修改InnoDB存储格式来实现。

使用pt-online-schema-change的限制有:

  • 改表时间会比较长(相比直接alter table改表)

  • 修改的表需要有唯一键或主键

  • 在同一端口上的并发修改不能太多

可用性

关于可用性,我们今天分享一种无缝切主库方案,可以用于日常切换,使用思路也比较简单

在正常条件下如何无缝去做主库切换,核心思路是让新主库和从库停在相同位置,主要依赖slave start until 语句,结合双主结构,考虑自增问题。

点击查看原图

MySQL集群方案:

  • 集群方案主要是如何组织MySQL实例的方案

  • 主流方案核心依然采用的是MySQL原生的复制方案

  • 原生主从同步肯定存在着性能和安全性问题

MySQL半同步复制:

现在也有一些理论上可用性更高的其它方案

  • Percona XtraDB Cluster(没有足够的把控力度,不建议上)

  • MySQL Cluster(有官方支持,不过实际用的不多)

点击查看原图

红框内是目前大家使用比较多的部署结构和方案。当然异常层面的HA也有很多第三方工具支持,比如MHA、MMM等,推荐使用MHA

sharding拆分问题

  • Sharding is very complex, so itʼs best not to shard until itʼs obvious that you will actually need to!

  • sharding是按照一定规则数据重新分布的方式

  • 主要解决单机写入压力过大和容量问题

  • 主要有垂直拆分和水平拆分两种方式

  • 拆分要适度,切勿过度拆分

  • 有中间层控制拆分逻辑最好,否则拆分过细管理成本会很高

曾经管理的单表最大60亿+,单表数据文件大小1TB+,人有时候就要懒一些

点击查看原图

上图是水平拆分和垂直拆分的示意图

数据库备份

首先要保证的,最核心的是数据库数据安全性。数据安全都保障不了的情况下谈其他的指标(如性能等),其实意义就不大了。

备份的意义是什么呢?

  • 数据恢复!

  • 数据恢复!

  • 数据恢复!

目前备份方式的几个纬度:

  • 全量备份 VS 增量备份

  • 热备 VS 冷备

  • 物理备份 VS 逻辑备份

  • 延时备份

  • 全量binlog备份

建议方式:

  • 热备+物理备份

  • 核心业务:延时备份+逻辑备份

  • 全量binlog备份

借用一下某大型互联网公司做的备份系统数据:一年7000+次扩容,一年12+次数据恢复,日志量每天3TB,数据总量2PB,每天备份数据量百TB级,全年备份36万次,备份成功了99.9%。

主要做的几点:

  • 备份策略集中式调度管理

  • xtrabackup热备

  • 备份结果统计分析

  • 备份数据一致性校验

  • 采用分布式文件系统存储备份

备份系统采用分布式文件系统原因:

  • 解决存储分配的问题

  • 解决存储NFS备份效率低下问题

  • 存储集中式管理

  • 数据可靠性更好

使用分布式文件系统优化点:

* Pbzip压缩,降低多副本存储带来的存储成本,降低网络带宽消耗

* 元数据节点HA,提高备份集群的可用性

* erasure code方案调研

数据恢复方案


前的MySQL数据恢复方案主要还是基于备份来恢复,可见备份的重要性。比如我今天下午15点删除了线上一张表,该如何恢复呢?首先确认删除语句,然后用
备份扩容实例启动,假设备份时间点是凌晨3点,就还需要把凌晨3点到现在关于这个表的binlog导出来,然后应用到新扩容的实例上,确认好恢复的时间
点,然后把删除表的数据导出来应用到线上。

性能优化

复制优化

MySQL复制:

  • 是MySQL应用得最普遍的应用技术,扩展成本低

  • 逻辑复制

  • 单线程问题,从库延时问题

  • 可以做备份或读复制

问题很多,但是能解决基本问题

点击查看原图

上图是MySQL复制原理图,红框内就是MySQL一直被人诟病的单线程问题

单线程问题也是MySQL主从延时的一个重要原因,单线程解决方案:

  • 官方5.6+多线程方案

  • Tungsten为代表的第三方并行复制工具

  • sharding

点击查看原图

上图是MySQL5.6 目前实现的并行复制原理图,是基于库级别的复制,所以如果你只有一个库,使用这个意义不大

当然MySQL也认识到5.6这种并行的瓶颈所在,所以在5.7引入了另外一种并行复制方式,基于logical timestamp的并行复制,并行复制不再受限于库的个数,效率会大大提升

点击查看原图

上图是5.7的logical timestamp的复制原理图

刚才我也提到MySQL原来只支持异步复制,这种数据安全性是非常差的,所以后来引入了半同步复制,从5.5开始支持

点击查看原图

上图是原生异步复制和半同步复制的区别。可以看到半同步通过从库返回ACK这种方式确认从库收到数据,数据安全性大大提高

在5.7之后,半同步也可以配置你指定多个从库参与半同步复制,之前版本都是默认一个从库

对于半同步复制效率问题有一个小的优化,就是使用5.6+的mysqlbinlog以daemon方式作为从库,同步效率会好很多

关于更安全的复制,MySQL 5.7也是有方案的,方案名叫Group replication 官方多主方案,基于Corosync实现

点击查看原图

主从延时问题

原因:一般都会做读写分离,其实从库压力反而比主库大/从库读写压力大非常容易导致延时。

解决方案:

  • 首先定位延时瓶颈

  • 如果是IO压力,可以通过升级硬件解决,比如替换SSD等

  • 如果IO和CPU都不是瓶颈,非常有可能是SQL单线程问题,解决方案可以考虑刚才提到的并行复制方案

  • 如果还有问题,可以考虑sharding拆分方案

提到延时不得不提到很坑人的Seconds behind master,使用过MySQL的应该很熟悉

这个值的源码里算法

long time_diff= ((long)(time(0) – mi->rli.last_master_timestamp) – mi->clock_diff_with_master);

Secondsbehindmaster来判断延时不可靠,在网络抖动或者一些特殊参数配置情况下,会造成这个值是0但其实延时很大了。通过heartbeat表插入时间戳这种机制判断延时是更靠谱的

复制注意点:

  • Binlog格式,建议都采用row格式,数据一致性更好

  • Replication filter应用

主从数据一致性问题:

  • row格式下的数据恢复问题

InnoDB优化

成熟开源事务存储引擎,支持ACID,支持事务四个隔离级别,更好的数据安全性,高性能高并发,MVCC,细粒度锁,支持O_DIRECT。

主要优化参数:

  • innodbfileper_table =1

  • innodbbufferpool_size,根据数据量和内存合理设置

  • innodbflushlog_attrxcommit= 0 1 2

  • innodblogfile_size,可以设置大一些

  • innodbpagesize

  • Innodbflushmethod = o_direct

  • innodbundodirectory 放到高速设备(5.6+)

  • innodbbufferpool_dump

  • atshutdown ,bufferpool dump (5.6+)

    点击查看原图

 

上图是5.5 4G的redo log和5.6 设置大于4G redo log文件性能对比,可以看到稳定性更好了。innodblogfile_size设置还是很有意义的

InnoDB比较好的特性:

  • Bufferpool预热和动态调整大小,动态调整大小需要5.7支持

  • Page size自定义调整,适应目前硬件

  • InnoDB压缩,大大降低数据容量,一般可以压缩50%,节省存储空间和IO,用CPU换空间

  • Transportable tablespaces,迁移ibd文件,用于快速单表恢复

  • Memcached API,full text,GIS等

InnoDB在SSD上的优化:

  • 在5.5以上,提高innodbwriteiothreads和innodbreadiothreads

  • innodbiocapacity需要调大

  • 日志文件和redo放到机械硬盘,undo放到SSD,建议这样,但必要性不大

  • atomic write,不需要Double Write Buffer

  • InnoDB压缩

  • 单机多实例

也要搞清楚InnoDB哪些文件是顺序读写,哪些是随机读写

随机读写:

  • datadir

  • innodbdata file_path

  • innodbundo directory

顺序读写:

  • innodbloggrouphomedir

  • log-bin

InnoDB VS MyISAM:

  • 数据安全性至关重要,InnoDB完胜,曾经遇到过一次90G的MyISAM表repair,花了两天时间,如果在线上几乎不可忍受

  • 并发度高

  • MySQL 5.5默认引擎改为InnoDB,标志着MyISAM时代的落幕

TokuDB:

  • 支持事务 ACID 特性,支持多版本控制(MVCC)

  • 基于Fractal Tree Index,非常适合写入密集场景

  • 高压缩比,原生支持Online DDL

  • 主流分支都支持,收费转开源 。目前可以和InnoDB媲美的存储引擎

目前主流使用TokuDB主要是看中了它的高压缩比,Tokudb有三种压缩方式:quicklz、zlib、lzma,压缩比依次更高。现在很多使用zabbix的后端数据表都采用的TokuDB,写入性能好,压缩比高。

下图是我之前做的测试对比和InnoDB

点击查看原图

点击查看原图

上图是sysbench测试的和InnoDB性能对比图,可以看到TokuDB在测试过程中写入稳定性是非常好的。

tokudb存在的问题:

  • 官方分支还没很好的支持

  • 热备方案问题,目前只有企业版才有

  • 还是有bug的,版本更新比较快,不建议在核心业务上用

比如我们之前遇到过一个问题:TokuDB的内部状态显示上一次完成的checkpoint时间是“Jul 17 12:04:11 2014”,距离当时发现现在都快5个月了,结果堆积了大量redo log不能删除,后来只能重启实例,结果重启还花了七八个小时

MySQL优化相关的case

Query cache,MySQL内置的查询加速缓存,理念是好的,但设计不够合理,有点out。

锁的粒度非常大MySQL 5.6默认已经关闭

When the query cache helps, it can help a lot. When it hurts, it can hurt a lot.明显前半句已经没有太大用处,在高并发下非常容易遇到瓶颈。

关于事务隔离级别 ,InnoDB默认隔离级别是可重复读级别,当然InnoDB虽然是设置的可重复读,但是也是解决了幻读的,建议改成读已提交级别,可以满足大多数场景需求,有利于更高的并发,修改transaction-isolation。

点击查看原图

点击查看原图

上图是一个比较经典的死锁case,有兴趣可以测试下

关于SSD

关于SSD,还是提一下吧。某知名大V说过“最近10年对数据库性能影响最大的是闪存”,稳定性和性能可靠性已经得到大规模验证,多块SATA SSD做Raid5,推荐使用。采用PCIe SSD,主流云平台都提供SSD云硬盘支持。

最后说一下大家关注的单表60亿记录问题,表里数据也是线上比较核心的。

先说下当时情况,表结构比较简单,都是bigint这种整型,索引比较多,应该有2-3个,单表行数60亿+,单表容量1.2TB左右,当然内部肯定是有碎片的。

形成原因:历史遗留问题,按照我们前面讲的开发规范,这个应该早拆分了,当然不拆有几个原因:

  1. 性能未遇到瓶颈 ,主要原因

  2. DBA比较“懒“

  3. 想看看InnoDB的极限,挑战一下。不过风险也是很大的,想想如果在一个1.2TB表上加个字段加个索引,那感觉绝对酸爽。还有就是单表恢复的问题,恢复时间不可控。

我们后续做的优化 ,采用了刚才提到的TokuDB,单表容量在InnoDB下1TB+,使用Tokudb的lzma压缩到80GB,压缩效果非常好。这样也解决了单表过大恢复时间问题,也支持online DDL,基本达到我们预期。

今天讲的主要针对MySQL本身优化和规范性质的东西,还有一些比较好的运维经验,希望大家能有所收获。今天这些内容是为后续数据库做平台化的基础。我今天分享就到这里,谢谢大家。

QA

Q1:use schema;select * from table; 和select * from schema.table;两种写法有什么不一样吗?会对主从同步有影响吗?

对于主从复制来说执行效率上差别不大,不过在使用replication filter时候这种情况需要小心,应该要使用ReplicateWildIgnoreTable这种参数,如果不使用带wildignore,第一种方式会有问题,过滤不起作用。

Q2:对于用于MySQL的ssd,测试方式和ssd的参数配置方面,有没有好的建议?主要针对ssd的配置哈

关于SATA SSD配置参数,建议使用Raid5,想更保险使用Raid50,更土豪使用Raid 10

点击查看原图

上图是主要的参数优化,性能提升最大的是第一个修改调度算法的

Q3:数据库规范已制定好,如何保证开发人员必须按照规范来开发?

关于数据库规范实施问题,也是有两个方面吧,第一、定期给开发培训开发规范,让开发能更了解。第二、还是在流程上规范,比如把我们日常通用的建表和字段策略固化到程序,做成自动化审核系统。这两方面结合 效果会比较好。

Q4:如何最大限度提高innodb的命中率?

这个问题前提是你的数据要有热点,读写热点要有交集,否则命中率很难提高。在有热点的前提下,也要求你的你的内存要足够大,能够存更多的热点数据。尽量不要做一些可能污染bufferpool的操作,比如全表扫描这种。

Q5:主从复制的情况下,如果有CAS这样的需求,是不是只能强制连主库?因为有延迟的存在,如果读写不在一起的话,会有脏数据。

如果有CAS需求,确实还是直接读主库好一些,因为异步复制还是会有延迟的。只要SQL优化的比较好,读写都在主库也是没什么问题的。

Q6:关于开发规范,是否有必要买国标?

这个国标是什么东西,不太了解。不过从字面看,国标应该也是偏学术方面的,在具体工程实施时候未必能用好。

Q7:主从集群能不能再细化一点那?不知道这样问合适不?

看具体哪方面吧。主从集群每个小集群一般都是采用一主多从方式,每个小集群对应特定的一组业务。然后监控备份和HA都是在每个小集群实现。

Q8:如何跟踪数据库table某个字段值发生变化?

追踪字段值变化可以通过分析row格式binlog好一些。比如以前同事就是通过自己开发的工具来解析row格式binlog,跟踪数据行变化。

Q9:对超大表水平拆分,在使用MySQL中间件方面有什么建议和经验分享?

对于超大表水平拆分,在中间件上经验不是很多,早期人肉搞过几次。也使用过自己研发的数据库中间件,不过线上应用的规模不大。关于目前众多的开源中间件里,360的atlas是目前还不错的,他们公司内部应用的比较多。

Q10:我们用的MySQL proxy做读负载,但是少量数据压力下并没有负载,请问有这回事吗?

少量数据压力下,并没有负载 ,这个没测试过,不好评价

Q11:对于binlog格式,为什么只推荐row,而不用网上大部分文章推荐的Mix ?

这个主要是考虑数据复制的可靠性,row更好。mixed含义是指如果有一些容易导致主从不一致的SQL ,比如包含UUID函数的这种,转换为row。既然要革命,就搞的彻底一些。这种mix的中间状态最坑人了。

Q12: 读写分离,一般是在程序里做,还是用proxy ,用proxy的话一般用哪个?

这个还是独立写程序好一些,与程序解耦方便后期维护。proxy国内目前开源的比较多,选择也要慎重。

Q13: 我想问一下关于mysql线程池相关的问题,什么情况下适合使用线程池,相关的参数应该如何配置,老师有这方面的最佳实践没有?

线程池这个我也没测试过。从原理上来说,短链接更适合用线程池方式,减少建立连接的消耗。这个方面的最佳配置,我还没测试过,后面测试有进展可以再聊聊。

Q14: 误删数据这种,数据恢复流程是怎么样的(从库也被同步删除的情况)?


你删除数据的情况,如果只是一张表,单表在几GB或几十GB。如果能有延时备份,对于数据恢复速度是很有好处的。恢复流程可以参考我刚才分享的部分。目前
的MySQL数据恢复方案主要还是基于备份来恢复
,可见备份的重要性。比如我今天下午15点删除了线上一张表,该如何恢复呢。首先确认删除语句,然后用备份扩容实例启动,假设备份时间点是凌晨3点。就还
需要把凌晨3点到现在关于这个表的binlog导出来,然后应用到新扩容的实例上。确认好恢复的时间点,然后把删除表的数据导出来应用到线上。

Q15: 关于备份,binlog备份自然不用说了,物理备份有很多方式,有没有推荐的一种,逻辑备份在量大的时候恢复速度比较慢,一般用在什么场景?

物理备份采用xtrabackup热备方案比较好。逻辑备份一般用在单表恢复效果会非常好。比如你删了一个2G表,但你总数据量2T,用物理备份就会要慢了,逻辑备份就非常有用了

 

 

 

 

摘自:http://sanwen8.cn/p/10913Vm.html

发表在 db | 标签为 | MySQL大数据场景的优化和运维之道已关闭评论