手记-ES基础

(转载请注明作者和出处‘https://fourthringroad.com/’,请勿用于任何商业用途)

基本概念

Document文档

Json 对象,由多个filed字段组成,支持多种数据类型,详见mapping

每个文档有唯一的id标识,可以指定,也可以自动生成。

元数据:_index, _type, _id, _version(每次更新都会增加), _source(原始json数据), _all(整合所有字段,不鼓励),_seq_no, _primary_term;

Index索引

相同结构(Mapping)的文档(Document)的集合;

更好的解释指向一个/多个分片的逻辑命名空间

mapping相当于schema,定义字段名称和类型

Type类型

相当于DB中的table,但是6.0之后就逐渐废弃这个概念了

Node节点

主节点

master节点:专用/非专用

从节点

  • 数据节点:
  • client节点/coordinating节点:处理用户请求,转发,负载均衡

Cluster集群

分片shard

  • es管理文档的集合单元
  • 数据的一部分
  • 一个lucene index
  • 包括多个segment
  • 主分片:数量一旦确定不可修改
  • 副本分片:主分片的拷贝,冗余备份,支持读服务

使用入门

Restful API/Kibana

curl的格式:

curl -XPUT “localhost:9200/index” -H “Content-Type: application/json” -d “{…}”

kibana的交互格式:

PUT localhost:9200/index

{…}

压测工具:esrally

常用操作

创建索引:put /my_index

查看索引:get /_cat/indices

删除索引:delete /my_index

创建文档:

put /my_index/_doc/1 {}

put /my_index/_doc/1/_create -> 存在会报错

post /my_index/_doc {} -》 id自动生成

查询文档:

get /my_index/_doc/1

Get /my_index/_doc/_search?q=last_name:smith -> Query String搜索

Get /my_index/_doc/_search {} -> DSL(domain-specifc language) 搜索

GET /my_index/_count + DSL -> 查询符合文档数

GET /my_index/_search + _source:[“”, “”] ->source过滤只返回感兴趣的字段

批量操作:

post _bulk -> 支持四种类型:index,create update, delete (create只创建,存在报错;index覆盖)

_mget/_msearch

集群健康:get /_cluster/health

Green/yellow/red

_cat API 集合:

update操作:

跟lucene底层类似,update操作是将文档删除,然后新建一个文档。

Update vs Index

当我们需要更新一个文档时,可以自己使用Index操作;当然也可以使用update操作,他们的底层操作是一致的,都需要删除旧文档,索引新文档。但是update的好处是:using update removes some network roundtrips and reduces chances of version conflicts between the GET and the index operation. 另外update一个大文档的部分内容,也可以节省一定的网络流量。

这里有一个ES官方开发给出的回答:

“I’m using the update API only if I have a very very big document to update. That would save a bit of network usage and memory.Otherwise, in 99,9% of the time, I’m only using the index API.”

Update by query

Updates documents that match the specified query. If no query is specified, performs an update on every document in the data stream or index without modifying the source, which is useful for picking up mapping changes.(例如增加一个子字段)

比较常见的用法是结合scripts使用:

// increments the count field for all documents with a user.id of kimchy in my-index-000001
POST my-index-000001/_update_by_query
{
  "script": {
    "source": "ctx._source.count++",
    "lang": "painless"
  },
  "query": {
    "term": {
      "user.id": "kimchy"
    }
  }
}

Reindex vs Snapshot Restore

“If you are doing that using the same elasticsearch major version, I believe that Snapshot/Restore is the fastest safer option.

If you are doing that from a 2.x cluster (which may be started originally with 1.x indices) to a 5.x cluster, I’d probably go to the reindex API road.”

别名-alias

(1)灵活的扩容:推荐每个人为他们的Elasticsearch索引使用别名,因为在未来重建索引的时候,别名会赋予你更多的灵活性。假设一开始创建索引只有一个主分片,之后你又决定为索引扩容。如果为原索引使用的是别名,现在你可以修改别名让其指向额外创建的新索引,而无须修改被搜索的索引之名称(假设一开始你就为搜索使用了别名)。

(2)动态的滚动查询:在实际应用中,我们也不应该向单个索引持续写入数据,知道它的分片巨大无比。巨大的索引会在数据老化后难以删除,以id为单位删除文档不会立即释放空间,删除doc只在lucene分段合并时才会真正从磁盘中删除。即使手工触发分段合并,仍会引起较高的I/O压力,并且可能因为分段巨大导致合并过程中磁盘空间不足(分段大小大于此片可用空间的一半). 因此,另外一个有用的特性是:在不同的索引创建窗口。比如,如果为数据创建了每日索引,你可能期望一个滑动窗口覆盖过去一周的数据,别名就称为last-7-days.然后,每天创建新的每日索引时,将其加入别名,同时删除第8天前的旧索引。这样,对于业务方来说,读取时使用的别名不变,当需要删除数据的时候,可以直接删除整个索引

MappingSchema

指定字段(field)名称,类型,设置倒排索引相关配置。

mapping中字段类型一旦设定,就不能更改了(lucene底层是不支持修改的);如果有需求只能创建新的索引然后reindex;

如果需要扩展一个字段的功能,可以通过增加子字段,然后用update by query api进行更新。

可以通过dynamic:true/false/strict 来设定是否能够动态增加新字段 

Dynamic:true时:动态mapping,es会自动识别类型,例如一个字符串:”username”:”bob”

“username”:{ 
  “type”:”text”,
  “fields”: {
   “keyword”:{ //自动带keyword子字段
    “type”:”keyword”,
    “ignore_above”:256
   }
  }
}

没有分词的字段也是有索引的,所以具备检索能力;

可以通过index:true/false控制一个字段是否索引,不索引的字段不可以搜索。譬如手机号,不希望被搜索;同时也可以节省大量存储空间。

_all字段和copy_to操作:

_all字段由所有字段内容拼接而成,方便统一查询,但是已经被废弃;可以给一个字段加copy_to配置,使得自动将它copy到某一个字段,后者可以扮演类似_all的角色。    

数据类型

  1. 简单数据类型
    • 字符串:text,keyword
    • 数值型:long,integer,short,byte,double,float。。。
    • 布尔:boolean
    • 日期:date
    • 二进制:binary
    • 范围类型:integer_range, float_range, long_range…
  2. 复杂数据类型:
    • 数组:array 
    • 对象:object
    • 嵌套对象:nested object
    • 地理位置:geo_point,geo_shape

多字段特性(multi-fields特性):通过不同的方法索引相同的字段;譬如同时使用keyword和text索引一个字段,这样既可以全文检索,也可以keyword查询

PUT my_index
{
  "mappings": {
    "_doc": {
      "properties": {
        "city": {
          "type": "text",
          "fields": {
            "raw": { 
              "type":  "keyword"
            }
          }
        }
      }
    }
  }
}

可以直接使用city.raw来使用

多字段的另一个应用场景是使用不同的方法分析相同的字段以求获得更好的相关性。

PUT my_index
{
  "mappings": {
    "_doc": {
      "properties": {
        "text": { 
          "type": "text",
          "fields": {
            "english": { 
              "type":     "text",
              "analyzer": "english"
            }
          }
        }
      }
    }
  }
}

Numeric_detection:true 可以开启数字的自动探测(“xx”:”num”),而不是默认的text

Date支持自定义格式的自动探测

动态模版dynamic template

动态模板允许你定义可以用于动态添加的字段的自定义映射,可实现效果例如:

  • 所有的字符串类型都设定称 Keyword,或者关闭 keyword 字段
  • is 开头的字段都设置成 boolean
  • long_ 开头的都设置成 long 类型

匹配方式:

  1. 匹配类型
  2. 匹配名称
  3. 匹配路径(对象结构)
PUT my_index
{
  "mappings": {
    "my_type": {
      "dynamic_templates": [
        {
          "integers": {
            "match_mapping_type": "long",
            "mapping": {
              "type": "integer"
            }
          }
        },
        {
          "strings": {
            "match_mapping_type": "string",
            "mapping": {
              "type": "text",
              "fields": {
                "raw": {
                  "type":  "keyword",
                  "ignore_above": 256
                }
              }
            }
          }
        }
      ]
    }
  }
}

索引模版index template

创建索引时自动生成预定义的mapping和settings

如果index同时命中两个模版order大的会覆盖order小的属性局部覆盖)。

Sample:(下面格式低版本和高本本有所不同)

PUT _template/template_1
{
  "index_patterns": ["te*", "bar*"],
  "template": {
    "settings": {
      "number_of_shards": 1
    },
    "mappings": {
      "_source": {
        "enabled": true
      },
      "properties": {
        "host_name": {
          "type": "keyword"
        },
        "created_at": {
          "type": "date",
          "format": "EEE MMM dd HH:mm:ss Z yyyy"
        }
      }
    },
    "aliases": {
      "mydata": { }
    }
  },
  "priority": 500,
  "composed_of": ["component_template1", "runtime_component_template"], 
  "version": 3,
  "_meta": {
    "description": "my custom"
  }
}

快照原理

https://www.cnblogs.com/dyfblog/p/15220301.html

倒排索引

正排索引:文档ID指向内容;例如书籍的目录-文章名称指向文章内容所在位置

倒排索引:关键词指向文档ID;例如书籍的索引页-关键词指向文章的名称

Sample:
Term/token	doc1	doc2
Bring	y	n
Home	y	y
White	n	y
Fox	y	n

如何构建倒排索引:将文章内容分词,并与文章ID进行关联

搜索引擎的逻辑:

  1. 将搜索key进行分词
  2. 用分词去倒排索引查找文章
  3. 按照关联程度返回给用户

构成

单词词典Term Dictionary

有很多结构适合快速的查询B+tree, HashMap, 单词词典采用FST,类似于字典树trie。提供单词的快速查询,并记录了单词到倒排列表的关联信息

https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

倒排列表Posting List

  • 文档ID
  • 单词频率(TF,Term Frequency)
  • 位置Position:文档分词后的位置
  • 偏移Offset:记录在文档的开始和结束位置,用于高亮

es中每个字段都会有自己的倒排索引

分词

将文本转化为term/token的过程,es中叫Analysis

分词器Analyzer

构成:

  • Character Filter:对原始文本过滤处理,例如去掉html特殊符号
  • Tokenizer:切分单词
  • Token Filter: 对单词处理:譬如转小写,删除/增加等等

可以基于上面三个环节进行自定义分词:

PUT my_index 
{
  “settings”: {
    “analysis”:{
      对三个环节进行自定义或指定一个三方分词器    
    }
  }
}

常用分词器:

  • Standard
  • Simple
  • WhiteSpace
  • Stop
  • IK:中文分词器
    • 支持自定义词库
    • 热更新分词词典
  • 结巴:中文分词器
  • 更高阶的是基于自然语言处理的分词器

分词分析API:Analyze API

可以指定分词器,自定义分词器构成等等

例如:

POST _analyze 
{
  “analyzer”:”standard”,
  “text”:”xxxxx”
}

如何重新索引你的数据

一旦创建索引,就不能修改分析器/改变现有字段,否则会造成已经索引的数据无法正常搜索,需要重新索引数据,有两个方式:

  1. Reindex API
  2. 用scroll API从旧索引批量读取文档,然后使用bulk api重新index所有数据

检索Search

GET /my_index/_search

两种格式

  1. URI search(query string)
  2. Query DSL(body体)

Query DSL

基于json格式定义

GET /my_index/_search
{
  “query”:{
    “term”: xxxxxx
  }
}
  • 查询时加上profile:true 参数可以打印es查询的的过程
  • 查询时加上explain:true 参数可以查看算分的详细内容
  • Validate API 也可以对查询请求进行验证,检查lucene底层执行的语句是什么

相关性算分 :解决返回文档排序

  • 词频:Term Frequency:频率越大,相关性越高
  • 文档频率:Document Frequency:出现文档越少,相关性越高
  • Inverse Document Frequency(IDF): 1/文档频率
  • Filed-length Norm:文档越短,相关性越高

两个模型:

  1. TF/IDF 模型:
    1. 与TF, IDF,成正比,
    1. 文档长度成反比
  2. BM25模型:5.x之后默认的模型
    1. 基于TF/IDF进行了优化

分类

  1. 字段类查询只针对一个字段进行查询
  2. 复合查询针对一个或者多个字段

字段类查询

全文匹配针对text类型的字段进行全文检索需要对插叙语句进行分词

  • Match query
  • Match Phrase Query:在match基础上有term顺序要求
  • Query String Query:多字段,多关键字(支持AND,OR,NOT等语句支持)

单词匹配不分词直接匹配倒排索引

  • Term Query:不对查询语句进行分词;精确查询,适合检索非text类型的字段,比如keyword 、numeric、date;需要注意拿term去查text要尤其注意分词问题
  • Terms Query:针对多个term
  • Range Query:主要这对数字,date

复合查询

  • Constant_score Query:可以实现自定义得分
  • Bool query:包含多个bool子句,每个子句其实就是上面的字段类查询
    • Filter过滤符合条件的文档不计算相关性得分提高查询效率
    • Must:必须符合条件,计算相关性得分
    • Must_not:与filter相反;也不会计算相关性得分,起到一个过滤效果
    • Should: 计算相关性得分

Search的QueryThenFetch过程

  • Query:协调节点收到一个search请求,选择分片,发送search请求;这些分片会返回指定个数(from+size)个文档ID和排序值用于排序,最后综合得到from+size个文档ID
  • Fetch:协调节点接着根据文档的ID向分片发送_mGet请求,获得文档的详细内容;协调节点拼接后返回给用户;

相关性算分问题

同一条文档在不同shard上会得到不同的相关性分数(因为shard之间是独立的,甚至在不同的节点上),有时候会导致一些排序不准确的问题。

Dfs_query_then_fetch可以解决这个问题(拿到所有文档后重新计算分数),但是非常耗费资源。

排序fielddata  doc_values

默认使用相关性算分的结果进行排序,用户也可以用自定义的方式进行排序:

get my_index/_search
{
  “sort”:[
    {“xx_field”:”asc/desc”},
    {“_score”:”asc/desc”},  // 与相关性算分结合 
    {“yy_field”:”asc/desc”},
    ...
  ]
}

多个条件按顺序判断;

这里的field可以是keyword,date,integer等类型,但是如果是text的话会报错:

Fielddata is disabled on text fields by default

原因是text的类型在索引中是以分词形态存在的,只有设置fielddata=true才能够获取到text字段的所有值,缺点是会占用大量的空间。也可以将text字段改成keyword类型。

doc_values是什么:一个列式存储映射

为了加快排序、聚合操作,在建立倒排索引的时候,额外增加一个列式存储映射,是一个空间换时间的做法。默认是开启的,对于确定不需要聚合或者排序的字段可以关闭。

  • 在ES保持文档,构建倒排索引的同时doc_values就被生成了, doc_values数据太大时, 它存储在电脑磁盘上.
  • doc_values是列式存储结构, 它擅长做聚合和排序
  • 对于非分词字段, doc_values默认值是true(开启的), 如果确定某字段不参与聚合和排序,可以把该字段的doc_values设为false
  • 例如SessionID, 它是keyword类型, 对它聚合或排序毫无意义, 需要把doc_values设为false, 节约磁盘空间
  • 分词字段不能用doc_values

两种获得field字段值的方式:(本质就是ID-》field信息)

  1. Fielddata, 默认对所有字段都是禁用的,所以text在开启fielddata之后可以获得字段值。在搜索时创建,位于内存之中。
  2. Doc values,除了text类型之外,都默认启用的。会在index文档是时创建,存储在磁盘。

如何开启fielddata:在相应的text字段的mapping中append-> fielddata:true

如何关闭doc values:在non-text字段mapping中append->doc_values:false

关闭之后lucene底层就不会存这个字段了,之后再打开必须要reindex才行

分页 & 遍历

From + size

深度分页问题:如果from=4980,size=20,有五个分片;那么每个分片都需要取5000条数据,并且在协调节点汇总排序,对内存压力非常大;

ES默认有限制深度分页条数为10000;

Scroll

解决深度分页的问题

Get my_index/_search?scroll=10m {size:10} ->返回一个_scroll_id,后序可以迭代_scroll_id,不断的向后查询;

POST _search/scroll 
{
  scroll:10m, //续10分钟
  scroll_id:xxxx
}

原理是创建一个用于查询的快照:

  1. 有有效时间设定
  2. 有翻页数量设定
  3. 不具备搜索实时性,创建快照后的新文档无法查询到
  4. 创建快照会消耗一定时间和资源(尤其是内存)

Search After

解决深度分页的问题

在每次搜索时指定search after = 上次搜索最后一条记录的得分

这样在每一个分片上只需要搜索size条记录,汇总之后在协调节点排序返回

实时性好,但是只能向后翻页

Aggregation-聚合分析统计分析

ES的基本功能是查询检索,在此基础上,还可以进行针对ES查询的的数据结果做统计分析


GET /my_index/_search
{
  “query”:{}
  //聚合分析会对query的结果进行分析
  “aggs”:{
    name
      type
        body //提供这个type需要的参数
      aggs //子聚合分析
  ...
  //可以包含多个上述结构体,即多个聚合查询
    name
      type
        body //提供这个type需要的参数
      aggs //子聚合分析
  }
}

基本类型

  • Metric,指标分析,max,min,avg
  • Bucket:分桶,类似SQL中的GroupBy
  • Pipeline,冠道,基于前序聚合分析结构继续计算
  • Matrix,矩阵分析类型

Metric

  • Min:返回数值类字段最小值
  • Max
  • Avg
  • Sum
  • Cardinality:基数,等同 distinct+count
  • Stats: count,min,max,avg,sum 多个数据集成
  • Extended_stats: Stats的拓展,包括方差,标准差等等信息 
  • Percentiles:百分位数统计,可以统计数据的分布情况
  • Top_hits: 通常配合分桶使用,作为子查询,用于获取桶内顶部size个记录的详细内容

Bucket

按照一定规则分桶

  • Terms:按照keyword分桶(如果是text类型会按照分词进行分桶)
  • Range/data range:0-100,100-200,200-300 。。。等  /按日期分桶 
  •  Histogram/date Histogram:直方图,按照固定单位分割

支持嵌套子查询,即分桶之后再分桶;

也可以Bucket配合Metric嵌套查询;

Pipeline:

在聚合分析的结果之上执行一些操作:

例如,我对数据分桶,然后计算metrics,再对metric进行一些操作。

  • Min_bucket: 求桶的某个指标最小值
  • Max_bucket
  • Avg_bucket
  • Sum_bucket
  • Stats_bucket: 对之前的聚合分析的结果做stat分析
  • Percentiles_bucket
  • Derivative: 按桶的某个指标求导数来分析走向
  • Moving_avg: 移动平均值
  • Cumulative_sum: 累计求和

修改作用范围

  • Filter:过滤掉一部分数据后再做聚合分析
  • Post-Filter:在聚合分析结束后,过滤结果
  • Global:不基于query结果,在全量数据里查询

对桶排序

默认排序是根据桶内的数据量(_count)

Order:

  • 可以按照某个指标进行排序,例如_count
  • 可以按照子聚合中的数值排序

注意:query语句里面对结果是通过sort来进行的

聚合查询底层执行逻辑

ES的聚合查询结果排名可能不是准确的

我们在有的聚合查询时(例如分桶)通常会指定最终返回的数据量:size=xx;es在返回结果时,会按照count(桶中数据量)进行排序,然后返回前size个;

  • 大部分情况是协调节点到每个分片所在节点上分别获得聚合值,再统一在协调节点计算返回给用户的值
  • 因为从每个节点都是按贪心来取数据,比如需要top 3,就从每个shard取top3,再到协调节点进行贪心计算,获得全局top3;所以最终返回的数据不一定准确;解决方案是设定shard_size大于最终需要的数据量;这样协调节点会过量的从每个shard上取得需要的数据,再做排序。
  • 衡量shard_size指标合理性的标准是,每个桶的 doc_count_error_upper_bound 尽可能接近0;

海量数据准确度实时性很难三者都得到满足例如hadoopspark离线计算方案可以处理海量数据准确度高但是实时性差mysql等关系型数据库实时性准确度高但是处理数据量有限es的某些聚合统计就是满足了实时性海量数据但是准确度不能得到满足可以通过调参提高准确度但是实时性也会相应的下降

高级功能ES Scripts

在Elasticsearc中,它使用了一个叫做Painless的语言。它是专门为Elasticsearch而建立的。Painless是一种简单,安全的脚本语言,专为与Elasticsearch一起使用而设计。 它是Elasticsearch的默认脚本语言,可以安全地用于inline和stored脚本。它具有像Groovy那样的语法。自Elasticsearch 6.0以后的版本不再支持Groovy,Javascript及Python语言。

例子:

如何避免了从客户端发起多次查询与写入:

    PUT twitter/_doc/1
    {
      "user" : "双榆树-张三",
      "message" : "今儿天气不错啊,出去转转去",
      "uid" : 2,
      "age" : 20,
      "city" : "北京",
      "province" : "北京",
      "country" : "中国",
      "address" : "中国北京市海淀区",
      "location" : {
        "lat" : "39.970718",
        "lon" : "116.325747"
      }
    }

  //将age修改成30
  POST twitter/_update/1
    {
      "script": {
        "source": "ctx._source.age = 30"
      }
  }

scripts可以被存放于一个集群的状态中。它之后可以通过ID进行调用:

PUT _scripts/add_age
    {
      "script": {
        "lang": "painless",
        "source": "ctx._source.age += params.value"
      }
}
//调用
POST twitter/_update/1
    {
      "script": {
        "id": "add_age",
        "params": {
          "value": 2
        }
      }
    }

分布式架构

TBD 架构图

Cluster State信息

  • node级别state信息
  • index级别state信息,
  • shard级别state信息,

都分别保存在各自独立的目录下,其中index级别的state信息在7.x版本中被合并到node级别state同一个目录下。

ClusterState在每个节点上其实都维护了一份(mem+disk),通过event-driven形式进行更新。

Master 节点

Master节点负责管理Cluster State信息;后者存储在各自节点上,Master维护最新版本并且同步到不同的节点

在云上我们通常会有一个master专用集群,由三个master-eligible节点构成;但是同一时间只会有一个master

Master的一致性算法采用的是:2-Phase-Commit算法TBD

Coordinating协调节点

处理用户请求,将请求分发到master/数据节点;

默认每个ES节点都具备扮演协调节点的能力;

云上通常会有专用的协调节点集群,防止数据节点/master节点耗费过多资源在处理网络请求上。Bulk操作,agg操作等都会对coordinating产生压力。也能充分利用专用协调节点的优势。

文档到分片的映射算法

Shard ID= hash(routing_id)%主分片数量 

Routing_id在put请求时,可以人为指定,也可以使用默认值(文档ID);

Shard的底层架构

Shard对应的其实就是Lucene的Index

Lucene文件系统是不可修改的(只能追加和读),所以shard从本质上也是不可修改的;

Page Cache缓存的的利用:

CPU如果要访问外部磁盘上的文件,需要首先将这些文件的内容拷贝到内存中,由于硬件的限制,从磁盘到内存的数据传输速度是很慢的,如果现在物理内存有空余,干嘛不用这些空闲内存来缓存一些磁盘的文件内容呢,这部分用作缓存磁盘文件的内存就叫做page cache. 用户进程启动read()系统调用后,内核会首先查看page cache里有没有用户要读取的文件内容,如果有(cache hit),那就直接读取,没有的话(cache miss)再启动I/O操作从磁盘上读取,然后放到page cache中,下次再访问这部分内容的时候,就又可以cache hit,不用忍受磁盘的龟速了(相比内存慢几个数量级)。

同时因为Lucene文件系统是不可修改的,缓存是不需要更新的;

几个重要节点:

  1. 生成倒排索引文件(segment)
  2. 更新Commit Point文件:segments_N文件
  3. 更新.del文件

Refresh

对应Lucene的flush,将内存中Buffer(lucene中的数据结构)里的数据生成segment,但是不保证落盘;

ES refresh的频率默认是1s;

会更新Commit Point文件:segments_N文件 -> 数据结构SegmentInfos

高版本里面refresh的时机有所改变如果没有搜索并不会保持持续的更新

Flush

对应Lucene的commit,操作系统的fsync;

flush操作包括:refresh,更新commit point, fsync,清除translog

flush时机:Flush happens automatically depending on how many operations get added to the transaction log, how big they are, and when the last flush happened.

Translog- Transaction Log

Changes to Lucene are only persisted to disk during a Lucene commit, which is a relatively expensive operation and so cannot be performed after every index or delete operation. Changes that happen after one commit and before another will be removed from the index by Lucene in the event of process exit or hardware failure.

Lucene commits are too expensive to perform on every individual change, so each shard copy also writes operations into its transaction log known as the translog. All index and delete operations are written to the translog after being processed by the internal Lucene index but before they are acknowledged. In the event of a crash, recent operations that have been acknowledged but not yet included in the last Lucene commit are instead recovered from the translog when the shard recovers.

An Elasticsearch flush is the process of performing a Lucene commit and starting a new translog generation. Flushes are performed automatically in the background in order to make sure the translog does not grow too large, which would make replaying its operations take a considerable amount of time during recovery. The ability to perform a flush manually is also exposed through an API, although this is rarely needed.

写入translog的频率也是可以调整的;默认每一个操作都会写;

删除&更新文档

lucene是不可修改的,底层维护一个.del文件记录所有删除文档的ID,查询结果返回前会利用.del文件内容进行过滤

段合并segment merge

在可以是ES自动触发,也可以是用户手动触发

ES分布式设计关键点

  • 满足CAP理论
  • Meta data的一致性
  • Primary/Replication 分片的一致性
  • Master的选主过程设计
  • Sequence Number设计
  • Primary Term设计
  • Lucene软删除的设计
  • 基于事件驱动的设计思想  
  • 写流程分析    
  • 读流程分析
  • 批量操作分析:  Bulk/mget/msearch
  • 脑裂问题避免 – quorum
  • translog机制
  • Pacific-A算法的应用

ES的一些设计思想

  • 通过分布式保证扩展性,能处理更大量的数据
  • 通过分布式保证系统HA
  • 通过不同角色的专用节点,提高资源使用效率,保证系统的稳定性
  • 通过引入主分片保证数据容量
  • 通过副本分片保证数据的HA

写一致性中的quorum的概念

2.4 version

Write Consistency

To prevent writes from taking place on the “wrong” side of a network partition, by default, index operations only succeed if a quorum (>replicas/2+1) of active shards are available. This default can be overridden on a node-by-node basis using the action.write_consistency setting. To alter this behavior per-operation, the consistency request parameter can be used.

Valid write consistency values are one, quorum, and all.

Note, for the case where the number of replicas is 1 (total of 2 copies of the data), then the default behavior is to succeed if 1 copy (the primary) can perform the write.

The index operation only returns after all active shards within the replication group have indexed the document (sync replication).

Index operation return when all live/active shards have finished indexing, regardless of consistency param. Consistency param may only prevent the operation to start if there are not enough available shards(nodes).

Stackoverflow 文章

There is a write consistency parameter in elasticsearch as well, but it is different compared to how other data storages work, and it is not related to whether replication is sync or async. With the consistency parameter you can control how many copies of the data need to be available in order for a write operation to be permissible. If not enough copies of the data are available the write operation will fail (after waiting for up to 1 minute, interval that you can change through the timeout parameter). This is just a preliminary check to decide whether to accept the operation or not. It doesn’t mean that if the operation fails on a replica it will be rollbacked. In fact, if a write operation fails on a replica but succeeds on a primary, the assumption is that there is something wrong with the replica (or the hardward it’s running on), thus the shard will be marked as failed and recreated on another node. Default value for consistency is quorum, and can also be set to one or all.

5.0及以上:

Active shardsedit

To improve the resiliency of writes to the system, indexing operations can be configured to wait for a certain number of active shard copies before proceeding with the operation. If the requisite number of active shard copies are not available, then the write operation must wait and retry, until either the requisite shard copies have started or a timeout occurs. By default, write operations only wait for the primary shards to be active before proceeding (i.e. wait_for_active_shards=1). This default can be overridden in the index settings dynamically by setting index.write.wait_for_active_shards. To alter this behavior per operation, the wait_for_active_shards request parameter can be used.

Valid values are all or any positive integer up to the total number of configured copies per shard in the index (which is number_of_replicas+1). Specifying a negative value or a number greater than the number of shard copies will throw an error.

For example, suppose we have a cluster of three nodes, A, B, and C and we create an index index with the number of replicas set to 3 (resulting in 4 shard copies, one more copy than there are nodes). If we attempt an indexing operation, by default the operation will only ensure the primary copy of each shard is available before proceeding. This means that even if B and C went down, and A hosted the primary shard copies, the indexing operation would still proceed with only one copy of the data. If wait_for_active_shards is set on the request to 3 (and all 3 nodes are up), then the indexing operation will require 3 active shard copies before proceeding, a requirement which should be met because there are 3 active nodes in the cluster, each one holding a copy of the shard. However, if we set wait_for_active_shards to all (or to 4, which is the same), the indexing operation will not proceed as we do not have all 4 copies of each shard active in the index. The operation will timeout unless a new node is brought up in the cluster to host the fourth copy of the shard.

It is important to note that this setting greatly reduces the chances of the write operation not writing to the requisite number of shard copies, but it does not completely eliminate the possibility, because this check occurs before the write operation commences. Once the write operation is underway, it is still possible for replication to fail on any number of shard copies but still succeed on the primary. The _shards section of the write operation’s response reveals the number of shard copies on which replication succeeded/failed.

关于lucene

lucene文件类型

Name	Extension	Brief Description
Segment Info	.si	segment的元数据文件
Compound File	.cfs, .cfe	一个segment包含了如下表的各个文件,为减少打开文件的数量,在segment小的时候,segment的所有文件内容都保存在cfs文件中,cfe文件保存了lucene各文件在cfs文件的位置信息
Fields	.fnm	保存了fields的相关信息
Field Index	.fdx	正排存储文件的元数据信息
Field Data	.fdt	存储了正排存储数据,写入的原文存储在这
Term Dictionary	.tim	倒排索引的元数据信息
Term Index	.tip	倒排索引文件,存储了所有的倒排索引数据
Frequencies	.doc	保存了每个term的doc id列表和term在doc中的词频
Positions	.pos	Stores position information about where a term occurs in the index
全文索引的字段,会有该文件,保存了term在doc中的位置
Payloads	.pay	Stores additional per-position metadata information such as character offsets and user payloads
全文索引的字段,使用了一些像payloads的高级特性会有该文件,保存了term在doc中的一些高级特性
Norms	.nvd, .nvm	文件保存索引字段加权数据
Per-Document Values	.dvd, .dvm	lucene的docvalues文件,即数据的列式存储,用作聚合和排序
Term Vector Data	.tvx, .tvd, .tvf	Stores offset into the document data file
保存索引字段的矢量信息,用在对term进行高亮,计算文本相关性中使用
Live Documents	.liv	记录了segment中删除的doc

lucene中的数据类型

我理解lucene中的数据类型跟es中的数据类型是有映射关系:

https://lucene.apache.org/core/7_3_1/core/index.html?org/apache/lucene/document/FieldType.html

  • BinaryDocValuesField
  • BinaryPoint
  • DateTools
  • Document
  • DocumentStoredFieldVisitor
  • DoubleDocValuesField
  • DoublePoint
  • DoubleRange
  • Field
  • FieldType
  • FloatDocValuesField
  • FloatPoint
  • FloatRange
  • IntPoint
  • IntRange
  • LongPoint
  • LongRange
  • NumericDocValuesField
  • SortedDocValuesField
  • SortedNumericDocValuesField
  • SortedSetDocValuesField
  • StoredField
  • StringField
  • TextField

功能细节

磁盘水位保护

  1. Low watermark:85不分配
  2. High watermart:90 reroute
  3. 95-> readonly

控制面功能

  • 功能类似:kibana/cerebro
  • 集群状态查看
  • 索引状态查看
  • 分片大小及分布查看
  • 模版管理
  • snapshot管理
  • settings管理
  • mapping管理
  • alias管理
  • analyze工具
  • 智能诊断工具
  • 监控面板

FAQ

ES存在脏读吗读未提交)?

不存在;可能存在读取primary的数据还没有同步到replica,但是ES底层lucene是不可修改的文件系统,不存在回滚,并且ES是非实时系统,所以不存在脏读的问题。

文章

一致性分析:

https://www.alibabacloud.com/blog/elasticsearch-distributed-consistency-principles-analysis-3—data_594360

ES底层数据存储:

https://elasticsearch.cn/article/6178

Lucene 操作:

https://www.baeldung.com/lucene

发表在 ElasticSearch | 5条评论

计算机网络

最近无事,翻了翻计算机网络,好多年不看都忘了,温故知新吧。

 

概述

计算机网络=计算机技术+通信技术

消息发送过程:

信源-》发送设备-》信道-》接收设备-》信宿

网络的发展由初期的:

主机+通信链路(光线,铜缆,无线)

发展成为

主机+交换网络(交换节点:交换机/路由器)

因特网:全球最大的网联网络

网络协议

计算机网络中数据交换的规则,规范了网络中所有信息的发送和接受过程

三个要素:

  • 语法(格式)
  • 语义(控制信息及意义)
  • 时序(顺序)

几乎所有的网络协议都是以RFC(Request for Comments)文档存在,由IETF进行管理。

计算机网络结构

  • 网络边缘:主机(端系统)
    • Client/Server模型
    • Peer-Peer p2p模型
  • 接入网络:
    • 电话网络/DSL/电缆网络/电视网络/频分多路复用 -(个人接入)
    • 端系统直连以太网交换机 – (机构接入)
    • 无线接入:通过基站
      • 无线局域网wlan
      • 广域网接入(电信运营商)
  • 网络核心:ISP路由器网络
  • 功能:路由+转发

  • IXP: Internet Exchange Point
  • CPN:Content Provider Networks, e.g. Google

数据交换

电路交换

建立连接,独占链路(带宽)

多路复用技术(共享信道):

  • 频分
  • 时分
  • 波分(光的频分复用-在光纤传输)
  • 码分

报文交换

信息整体一次性转发到下一个节点

分组交换

报文分拆出来的一系列小数据包(加上头部信息),包含了报文拆分/重组的过程

交换方式:存储+转发(也是路由器的工作方式)

采用“统计”时分多路复用技术

可能出现的问题:拥塞(congestion),分组延迟或者丢失,需要协议处理:

  • 可靠数据传输
  • 拥塞控制

网络性能指标

数据传输速率

Bit rate

带宽

  • 高/低频率之差(HZ)
  • 数字信道的最高传输速率(bps)

延迟latency

  • 节点处理延迟:差错控制,确定输出链路
  • 排队延迟
  • 传输延迟:分组长度/链路传输速率
  • 传播延迟:在介质中

传播时延是汽车在高速上跑的时间,传输时延是通过收费站的时间

RTT

往返时延

分组丢失丢包率

吞吐量/throughput

单位时间内通过网络某个点的数据量:b/s, kb/s, Mb/s

  • 即时吞吐量
  • 平均吞吐量

 

 

计算机网络体系结构

含义

  • 每层遵循某些网络协议来完成本层的功能
  • 是功能层面的抽象
  • 上层调用下层服务,下层向上层提供服务
  • 分层太多,会造成流程过长,效率过低
  • 层与层之间(服务与服务之间)是透明的,实现不可知
  • 层与层之间通过接口进行交互

OSI参考模型reference model

  • 应用层:HTTP(web), FTP(文件传输), SMTP(邮件)
  • 表示层:
    • 编码,加密,压缩数据
  • 会话层:薄,会话层与表示层通常会直接放到应用层中
  • 传输层
    • 段segment
    • 把会话层完整的报文拆分成段进行传输(TCP拆:MSS 最大报文段长度 (Maxium Segment Size):指明数据字段的最大长度,数据字段的长度加上 TCP 首部的长度才等于整个 TCP 报文段的长度。UDP不拆)
    • 报文的分段与重组
    • 端到端,进程到进程的连接控制:建立,维护,拆除
  • —-分割线—- 端系统有7层,路由器有3层(下面)
  • 网络层
    • 包Packet
    • 负责源主机到目的主机数据分组交付
    • 寻址:全网唯一的地址,例如IP
    • 路由Routing:分组转发
  • 数据链路层
    • 帧Frame
    • 物理寻址-物理链路直接相连的两节点的传输
  • 物理层
    • 具体bit的传输

网络传输过程

目的:实现异构网络的互联互通

数据封装(加头,加尾)目的:增加控制信息

  • 地址
  • 差错检测编码
  • 优先级,服务质量

TCP/IP参考模型

 

应用层

网络应用的体系结构

  • C/S
  • P2P
  • 混合结构-Napster
    • 文件传输:使用P2P结构
    • 文件搜索采用C/S

应用进程间通信

同一主机内部进程间通信:由操作系统提供支持

不同主机间进程间通信:消息交换

套接字Socket

对(传输层+网络层+数据链路层+物理层)的抽象;操作系统提供,保障应用层进程通信的API

进程寻址

协议+IP+端口号

TCP 192.168.0.100:49225 -> 202.109.23.45:52234

应用层协议

  • 公开协议:由RFC定义
  • 私有协议:P2P文件传输协议

应用层对传输层的服务质量需求

消息交换:由传输层及以下完成

  • 数据丢失率/可靠性
  • 时延
  • 带宽

不同的传输层协议提供的服务质量是不同的例如,TCP vs UDP

TCP UDP
面向连接 无连接
可靠传输 不可靠传输
流程控制
拥塞控制

Http连接类型

  • 短连接
    • HTTP 1.0
    • TCP连接传输一个对象
  • 长连接
    • HTTP1.1
    • TCP连接传输多个对象(重复利用)

HTTP消息体

Request:

  • Request Line 请求行(get,put,del,post)
  • Header
  • Body

Response

  • Status line
  • Header
  • Body

Cookie/Session技术

HTTP协议是无状态的

Client端(浏览器) Server端
Cookie:存有sessionID/UserUUID 等信息,会随着请求一同发送给server 能提取cookie中的信息Session:早期在内存,或者数据库中进行存储,现在一般有专门的session集群(memcached之类的内存数据库)

Email

应用层协议:SMTP

SMTP是‘客户端<–>邮件服务器<–>邮件服务器’传递消息所用的协议

邮件下载协议还有POP3,IMAP,HTTP等都可以支持

注意:HTTP,POP3,SMTP等都是针对ASCII文本的传输协议,如果要传输二进制,需要BASE64编码为字符型数据

MIME:多用途互联网邮件拓展,对原协议的拓展,使得支持非ASCII字符文本,譬如二进制,声音,图像,控制字符等等

DNS

功能:

  • 域名解析:A (Address) 记录是用来指定主机名(或域名)对应的IP地址记录
  • 主机别名:CNAME;别名记录。这种记录允许您将多个名字映射到另外一个域名。通常用于同时提供WWW和MAIL服务的计算机。例如,有一台计算机名为“host.mydomain.com”(A记录)。它同时提供WWW和MAIL服务,为了便于用户访问服务。可以为该计算机设置两个别名(CNAME):WWW和MAIL。这两个别名的全称就 http://www.mydomain.com/和“mail.mydomain.com”。实际上他们都指向 “host.mydomain.com”。
  • 负载均衡

 

P2P架构文件分发)-复杂难以管理

特点

  • 没有服务器
  • 任意节点之间可以通信
  • 阶段性接入Internet
  • 动态IP地址

应用

  • 文件共享:迅雷,电驴
  • 即时消息:QQ(可以p2p,也可以通过服务器中转)

BitTorrentBT协议

  • 文件划分成256KB的Chunk
  • 节点加入torrent,想tracker注册,获得清单,并建立某些连接
  • 下载,也上传

P2P系统的索引如何存储?

 

Socket套接字编程

有很多种网络程序的开发方式,socket是其中一种

socket是位于应用层和传输层之间的网络程序设计接口,隐藏了传输层及以下的细节,为应用进程间通信提供抽象机制。

特点

  • 支持多种协议簇
  • 多种操作系统支持
  • 支持C/S,p2p等通信模型

标识套接字:与定位进程的方式一样-IP地址+端口号

操作系统内部如何管理套接字:

Socket Descriptor,套接字描述符,指向一个数据结构,类似PCB,存储套接字信息;UNIX对其与文件相同管理,但是windows不同

Socket编程可以指定底层使用协议:TCP,UDP,IP,ICMP,IGMP等等

要注意的是的是TCP和UDP的拆包/粘包问题:

UDP是否会发生粘包或拆包的现象呢?答案是不会。UDP是基于报文发送的,从UDP的帧结构可以看出,在UDP首部采用了16bit来指示UDP数据报文的长度,因此在应用层能很好的将不同的数据报文区分开,从而避免粘包和拆包的问题。而TCP是基于字节流的,虽然应用层和TCP传输层之间的数据交互是大小不等的数据块,但是TCP把这些数据块仅仅看成一连串无结构的字节流,没有边界;另外从TCP的帧结构也可以看出,在TCP的首部没有表示数据长度的字段,基于上面两点,在使用TCP传输数据时,才有粘包或者拆包现象发生的可能。

 

常用API

  1. Socket()创建套接字,返回描述符
  2. Close()
  3. Bind()绑定本地IP+Port
  4. Listen()把套接字置于监听状态(服务器段)
  5. Connect()用于客户端进行连接建立
    1. TCP客户端:建立tcp连接
    1. UDP客户端:指定服务器端点地址
  6. Accept():服务器端阻塞,从处于监听状态的套接字SD的客户连接请求队列中取出排在第一个的请求,并创建一个新的套接字来与客户建立连接

注意注意区分NIO的问题NIO是解决多个套接字阻塞的问题

  • Send(),sendTo()UDP
  • Recv(),recvFrom()UDP

注意:用户发送是不提供port,则会使用协议名的默认端口,例如HTTP-》80,HTTPS-》443

 

 

传输层

为进程之间提供传输服务

应用层 data
传输层 TCP -》 segment / UDP -》 datagram
网络层 packet
数据链路层 frame
物理层 bit

传输层关心IP+端口号,网络层只关心IP

  • UDP的socket用二元组标识
  • TCP的socket用四元组标识

UDP特点

Best Effort服务模型,只做了错误校验(校验和checksum)

优势:

  • latency低:不需要建立连接
  • 模型简单:无需维护连接
  • 头部开销少
  • 无拥塞控制

如何可靠数据传输

三个关键点

  1. 数据不错
  2. 数据不丢
  3. 顺序不乱

想要实现数据可靠传输,对应用层来讲,下层传输信道必须是可靠的;但是现实是传输层下层信道是不可靠的,所以传输层就需要维护相对复杂的逻辑来实现

这就需要借助可靠数据传输协议

协议设计借助了FSM(Finite State Machine):状态机

State1 ———-event/action——-> State2

RDT(reliable data transfer)1.0: 底层信道可靠(不丢,不错)

RDT2.0:底层信道可能会有位错误(bitflip)

  • 利用校验和检测位错误
  • 引入确认机制:ACK/NAK(控制消息)
  • 引入重传机制:发送方收到NAK则重新传输

RDT2.0是一个停-等协议,即发送方发送完会等待控制消息的返回

RDT2.1:ACK/NAK被破坏怎么办?

  • ACK/NAK 具备校验和,检测到坏掉,一律重传
  • 给消息增加SN,丢弃重复分组

RDT2.2:无NAK协议

  • 接收方通过ACK告知最后一个正确接收的分组即可。

RDT3.0:信道可能会发生数据丢失

  • 通过定时器(timer)引入正确的等待时间

流水线机制与滑动窗口协议

上述的RDT协议可以保证数据不错,不丢,不乱,但是因为是一个停-等协议,效率非常低,性能很差。

流水线机制

各个分组依次发送出去,等待response(ack)

  • 需要更大的序列号
  • 端系统更大的缓存(分组)

滑动窗口协议

 

TCP协议

特点

  • 可靠,有序
  • 综合流水线和两种滑动窗口的的特性,窗口尺寸会随着拥塞程度和流量大小而变化
  • 实现了流量控制+拥塞控制
  • 面向连接
  • 全双工

段结构:

TCP快速重传机制

  • timeout发生,其值将被重新设置(X2)
  • sender收到关于一个segment的3个ack,则假定其已经丢失,fast fail,不在等待timeout了

TPC流量控制

防止接收方Buffer溢出-》速度匹配

receiver在seg头中RCV window告知可用Buffer,sender限制自己的发送window尺寸。

TCP连接管理

为什么要三次握手

第 1 次握手

Client 什么都无法无法确认。虽然自己发送了 syn 数据,但是只要没收到 Server 端的 syn/ack 数据都无法确认自己的发送是否正常。

Server 确认:自己接收正常,对方发送正常

第 2 次握手

Client 确认:自己发送正常、接收正常,对方发送正常、接收正常。Client 确认状态完成

Server 依旧只能确认:对方发送正常,自己接收正常。

第 3 次握手

Client 确认状态在第 2 次握手时已完成。

Server 确认:自己发送正常,接收正常,对方发送正常、接收正常。

 

TCP拥塞控制

拥塞控制是网络十大问题之一,可靠数据传输也是。

成因:

  • 带宽有限
  • 网络设备缓存有限

危害

  • 分组丢失
  • 延迟增大
  • 大量重复传输浪费资源

解决方案:

  • 端到端的拥塞控制:网络层不参与,端系统观察loss和delay来进行控制(TCP采用)
  • 网络辅助的拥塞控制:路由器向发送发显式的反馈网络拥塞信息,发送方来调整速率例(ATM网络)

Congestion Window:发送但是未确认的byte窗口;或者解释为:拥塞窗口的大小取决于网络的拥塞程度,并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口。如果再考虑到接收方的接收能力,那么发送窗口还可能小于拥塞窗口。

Loss事件:timeout或者3个重复的ACK-》降低发送速率

拥塞窗口与发送速率成正比,如何调整窗口(速率)呢?

TCP拆包/粘包问题

这篇文章讲的非常通俗易懂:https://zhuanlan.zhihu.com/p/359177898

https://cloud.tencent.com/developer/article/1430021

出现粘包问题后需要工程师介入,不同的框架其实有不同的解决方案;

发表在 Uncategorized | 127条评论

算法温习

参加工作已经4年,最近跳槽一看算法,基本上忘干净了,又找个教程温习一下,随手记一点笔记方便之后使用

关于为什么要学习算法

再次学习算法,对为什么要学习算法有了一些深层次的理解。

狭义的讲,学习算法其本质是学习并熟悉背后的常用模式,工作中遇到问题可以去尝试套用这些模式。因为遇到一个基础问题,想要短时间自己去从0去设计一个新的模式,同时性能还要非常优秀,几乎是不可能的。

广义的讲,是学习计算机的编程思维。能解决问题的逻辑抽象有很多种,但是有的是易于用编程实现的,譬如回溯算法,就能够用递归非常容易的实现,算法可以帮助我们习惯从代码实现的角度去思考一个问题。

基础

常数操作

与数据量无关的操作,统计时间复杂度的基本单位;当然不同的常数操作时间有所差别,譬如乘法和按位与;

时间复杂度

常数操作的数量,通常表示为:O(高阶项)

时间复杂度只是估计值,最好的测量方式是实际运行来比较运行时间。

  1. 平均
  2. 最好
  3. 最坏

空间复杂度

需要的额外辅助空间;O(1)指只是需要常数数量的额外空间

位运算

与/或/非/异或 操作是提取某些位的重要方法

不需要额外空间实现数组交换

有一种取巧的方式通过异或运算(^):相同为0,不同为1

不过只能在数组指向不同对象时使用,否则会清零。

异或满足交换律和结合律

a^a=0; 0^a=a;

异或这个特征可以用在一些算法之中

对数器

通过随机样本产生器产生数据,然后检测某一个优化算法和已知正确的算法的结果是否一致;大量的测试可以

递归操作

当一个问题可以被拆解成相同子问题,且当其规模小到一定程度时就可以得到解决(边界),就可以采用递归操作处理;

java里面递归实现的基础是:栈帧

递归操作的时间复杂度可以用master公式来求,比较复杂。

排序算法

十大经典排序算法:https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

选择排序

O(n^2), O(1)

冒泡排序

O(n^2), O(1)

插入排序 

插入排序和选择排序,冒泡排序的时间复杂度有一个区别,数据状况会影响它常数操作的总数,也就是影响时间复杂度估算。

最坏情况时间复杂度:O(n^2)

最好情况是:O(n)

通常定义时间复杂度是按照最差情况来计算O(n^2)

归并排序

利用了递归的思想

时间复杂度三个都是O(N*logN)

空间复杂度O(N)

归并排序为什么时间性能比前三者好因为前三个排序有大量的比较而很多比较关系在使用之后就被抛弃了这样就出现了浪费有效利用这些关系避免重复比较就能提升性能。   

归并变形数组小和问题

数组中左边比当前数小的数累加叫数组的小和。[1,3,4,2,5] -> 16

得出O(N*logN)复杂度的计算方法

类似:逆序对问题。

快速排序

1.0算法以最后一个数作为标准,大于的放前面,小于的放后面。然后递归这个过程。

2.0算法:1.0基础上,对等值区域避免排序

3.0算法:划分值如果很居中则算法时间复杂度较低;故随机选一个数作为标准

时间复杂度最坏O(n^2),最好/平均:O(nlogn):好情况每次递归都平分数组,一共需要递归logn次,每次需要n时间,复杂度为O(n*logn),最坏情况每次都把数组分成1和n-1,一共需要递归n次,每次需要n时间,总体复杂度为O(n^2)。平均总体时间复杂度为O(nlogn)。

空间复杂度 O(logn):每次递归需要的空间是固定的,总体空间复杂度即为递归层数,因此平均/最好空间复杂度为O(logn),最坏空间复杂度为O(n)

堆排序

就是完全二叉树,通常用数组实现

数组如何映射到堆:i 位置(下标)

  • 左孩子:2*i+1
  • 右孩子:2*i+2
  • 父:(i-1)/2

堆结构:

  • 大根堆:每一颗子树,根是最大值
  • 小根堆:每一颗子树,根是最小值

两个最重要的操作

  • 如何构成:不断根父节点比较并交换,直到比根节点小
  • 大根堆pop最大值:把数组最后一个数放到根节点,并调整堆结构

维护堆结构的时间复杂度非常低:O(logn)

排序时间复杂度O(nlogn)

  1. 先构造堆
    1. 一个一个加进来
    1. 如果用户直接提供了一个完全二叉树,可以从叶子节点开始,依次进行每棵树的堆化
  2. 再从根不断取值 

空间复杂度:O(1)

小根堆/大根堆在java里面就是优先级队列:PriorityQueue(默认小根堆)

计数排序

不基于比较的排序:计数排序不是比较排序,排序的速度快于任何比较排序算法

数组下标表示值,数组值表示值等于‘下标’的数据的数量。

通过这个数组,可以很简单的还原排序后的原数组

时间复杂度:O(n)

缺点:受限于数据的特点

基数排序

基数排序是一种非比较型整数排序算法,也使用了桶概念其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

几进制就可以准备几个桶

桶排序

  • 基数排序:根据键值的每位数字来分配桶;
  • 计数排序:每个桶只存储单一键值;
  • 桶排序:每个桶存储一定范围的数值;

排序稳定性 

排序完,值相同的数,相对位置是不变的,那么就是存在稳定性的。

目前没有找到复杂度O(nLogn)/O(1)/稳定的排序算法

综合排序

将几个排序结合起来,发挥各自的优势。

Arrays.sort():

如果是基础类型,那么就是使用快排;

如果不是基础类型,就使用归并排序(为了保证稳定性)

查找算法

顺序查找

O(n)

二分法

时间复杂度:O(logn)

哈希表

HashSet & HashMap底层结构是一样的,区别就是是否有伴随数据value

CRUD的时间复杂度是O(1)

放入哈希表的东西,如果不是基础类型就是引用传递,即存储对象的地址。

有序表

TreeSet & TreeMap:底层结构是一样的,区别就是是否有伴随数据value

与哈希表区别:有序表把key按照顺序组织起来

性能上差于哈希表:O(logn)

操作:

  • Hashset/map的操作
  • firstKey
  • lastKey
  • floorKey
  • ceilingKey

红黑树,AVL树,size-balance-tree等都是有序表结构,只是底层实现不同。

自定义类型需要提供比较器

单链表/双链表 

反转单/双向链表

快慢指针

判断两个链表相交的节点 

判断有环无环/求环的第一个节点也是利用快慢指针

Java LinkedList(链表) 类似于 ArrayList,是一种常用的数据容器。

与 ArrayList 相比,LinkedList 的增加和删除的操作效率更高,而查找和修改的操作效率较低。

以下情况使用 ArrayList :

  • 频繁访问列表中的某一个元素。
  • 只需要在列表末尾进行添加和删除元素操作。

以下情况使用 LinkedList :

  • 你需要通过循环迭代来访问列表中的某些元素。
  • 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

LinkedList实现了Queue接口

二叉树  

用递归和非递归实现二叉树的前序中序后序的遍历

深度优先(前中后序就是深度优先)

广度(宽度优先)优先遍历:使用队列

求最大层宽度;(hash表法和指针计数法

判断搜索二叉树

每一颗子树; 左树节点《自己《右树节点

可通过中序遍历判断是否是搜索二叉树

可以通过树形动态规划分治分成左右子树通过递归来求解

判断完全二叉树

从左到右依次变满

按宽度遍历:

  • 有右孩子,没有左孩子,return false
  • 第一个叶子节点之后所有节点必须是叶子结点

判断满二叉树

判断层数与节点个数关系

可以通过树形动态规划分治分成左右子树通过递归来求解

判断平衡二叉树 

任何子树,左树和右树的高度差不超过1

可以通过树形动态规划分治分成左右子树通过递归来求解

二叉树的序列化/反序列化

例如:以中序遍历序列化,就用中序遍历反序列化

也可以用分治来做序列化

通过队列实现反序列化+分治 

并查集

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的的树根,就能确定它在哪个集合里。

表示方式

  • 邻接表
    • A:B,C
    • B:A
    • C:A,D
    • D:C
  • 邻接矩阵
    • 可以用数值表示距离/权重
  • 对象结构:
    • 图=点集+边集

分类:有向图/无向图

构成:点,边

图的深度优先遍历dft

利用栈实现

图的广度优先遍历bft

利用队列实现

拓扑排序算法

有向无环图排序-例如任务执行顺序,包依赖解析顺序等问题

算法:优先处理入度为零的点

K(Kruskal)算法生成最小生成树

要求无向图

最小生成树:图里面保留尽可能少数量的边来保证连通性,并保证权值的和是最小的

按权值从小到大依次连接,如果加上某一条边会形成环,则跳过它。

  • 可以自己通过为点设定连通集合实现
  • 更简单是通过并查集来实现

P(prim)排序算法生成最小生成树

要求无向图

Dijkstra算法求最短路径

Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法,时间复杂度 O(n2)

如何加速:通过自己实现堆来对源代码进行加速 

前缀树

https://zhuanlan.zhihu.com/p/28891541

通过字符串序列构造树 abc bcd abe afg -> tree

用途:存储字符串,非常方便查询

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

思想

递推

一种计算机算法

递归

与递推相对应

动态规划

https://cloud.tencent.com/developer/article/1817113

思路:

  • 穷举分析
  • 确定边界
  • 找出规律,确定最优子结构
  • 写出状态转移方程

一道动态规划问题,其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

分治vs动态规划

  • 共同点:两者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小的子问题,然后将子问题的解合并,最终得到答案。
  • 不同点:分治法将分解后的子问题看成相互独立的,通常用递归来做。动态规划将分解后的子问题理解为相互间有联系,有重叠部分,需要记忆,通常用迭代来做。

递推vs动态规划

  • 递推 是一种计算机算法,通常用来将一个递推函数 转化成一个线性或多项式时间(取决于递推函数的参数个数)的求解程序。
  • 动态规划 是一个运筹学算法,通常可以用来将一个满足特定条件的决策最优化问题 转化成一个递推函数。

写动态规划的思路

  1. 写递归版本的代码来处理问题
  2. 记忆化搜索-》用缓存结构避免重复计算,记一下中间的一些计算结果,以便重复利用
  3. 通过多位表结构来存储中间的一些计算结果:二维数组+状态转移方程(可变参数的数量决定了是几维表通常是二维表避免不必要的变量)

如何使得动态规划能够优于暴力递归?

有重复计算的部分一定要将值存储下来时间复杂度会优化很多

分治法(Divide and Conquer)

将问题拆分成类似的小规模问题,通常采用递归方式处理

  • 归并排序
  • 快排
  • 汉诺塔问题
  • 逆序一个stack,使用递归不用额外数据结构 

回溯深度优先

回溯算法,又称为“试探法”。解决问题时,每进行一步,都是抱着试试看的态度,如果发现当前选择并不是最好的,或者这么走下去肯定达不到目标,立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯算法。

回溯与递归

回溯是可以通过递归实现的,当然也可以通过栈;

回溯最重要的一步是:还原数据

例子

打印一个字符串的所有子字符串

打印一个字符串的所有排列组合-》更进一步,如何去重?-递归过程中剪枝去掉对一些分支的探索

分支限界广度优先

分支限界法(branch and bound method)是求解纯整数规划或混合整数规划问题的经典方法,在上世纪六十年代由Land Doig和Dakin等人提出。这种方法灵活且便于用计算机求解,目前已经成功运用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。算法基本思想如下:

以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树

分支限界法中,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,其中导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中

然后从活结点表中取下一结点成为当前扩展结点

重复上述结点扩展过程,直至到找到所需的解或活结点表为空时为止

贪心

贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法

需要证明:局部最优-》全局最优 这个其实是难点;往往确认了某种局部最优的方法可以带来全局最优之后,代码实现是非常简单的,但是确定“某种局部最优的方法可以带来全局最优”这个理论是正确的,才是最复杂的点。这个是数学层面的东西更多了。

有的问题用贪心并不能获得全局最优解答,例如背包问题:

https://blog.csdn.net/qq_16234613/article/details/52235082

贪心算法经常会用到排序/大小根堆因为贪心往往是优先选择某一个极端值

例题:

哈夫曼编码问题

使用小根堆进行处理:

https://blog.csdn.net/xiangjunyes/article/details/106026830

最难的是证明算法(策略);代码实现并不复杂;

经典问题

N皇后问题

N*N的棋盘上,摆放N个皇后,任何两个不在同一行,列,斜线上。有多少种摆法。

暴力递归采用深度优先遍历的方法 –》   也是回溯算法

时间复杂度O(pow(n,n)) -》 能够优化常数时间:用位运算进行加速,优化十分明显 

发表在 Uncategorized | 38条评论