Algorithm

Valid Parentheses

判断只由小中大括号( ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’ ),是否符合以下条件:

  • 必须以相同类型的括号关闭。
  • 关闭的顺序必须和打开的一致。

空字符串认为是有效的。

经过前几次的学习,最开始不会想到暴力破解法了,想到了用栈来解决这个问题,FILO。

Details

Runtime: 3 ms, faster than 74.38% of Java online submissions for Valid Parentheses.

Memory Usage: 36.7 MB, less than 36.06% of Java online submissions for Valid

及格线上,代码结构依旧不是很规整。参考官方的解决方案。带来的思考:

我的答案中,提出了一个 filter的方法,其实我也注意到了,这个问题其实关键在于这个判断怎么去写,官网中用Map来制定规则,而且是以结尾的括号为key,开始的括号为value,很精髓。

Review

文章来源耗子叔、极客时间左耳听风专栏79讲推荐文章

另外,也推荐一下 JVM Anatomy Park JVM解剖公园,这是一个系列的文章,每篇文章都不长,但是都很精彩,带你一点一点地把 JVM 中的一些技术解开。

极客时间版权所有: https://time.geekbang.org/column/article/10216

Q:什么是 Large Pages? 什么是 Transparent Huge Pages? 对我们有什么帮助呢。

Theory

如今Virtual memory已被广为接受了,如今已经很少有人会去直接接触物理内存的操作,取而代之的是,没一个进程都有自己的虚拟内存,与实际的无力内存相映射。也就是两个进程的虚拟内存地址可能相同,但是映射的物理内存是唯一的。当进程访问这个虚拟地址时,某些处理机制会将虚拟地址转换为实际的物理地址。

操作系统维护page table,硬件通过page table walk来转换地址。以页的粒度进行地址转换是比较容易的。但是当每次内存访问都需要进行地址转换时,这就不是很划算了。因此更小的转换机制Translation Lookaside Buffer(TLB)应运而生。TLB 通常都很小,少于100条记录,因为它需要比 L1 cache 更快。TLB 以及页表移动的不命中,将带来昂贵的时间消耗。

虽然我们不能把 TLB 做大,但是我们可以把页变大,大多数的硬件支持 4K 大小的基本页,以及 2M/4M/1G 的大页。larger pages 覆盖内容相同的区域,减少page table walk以提高效率。

  • Hugetlbfs: 占用部分系统内存,将其暴露为虚拟文件系统,让应用程序从其中 mmap(2)。这种特有的接口需要应用程序和操作系统协同配置。这是一种“要么全部,要么是要么都没有”的方式:hugetlbfs不能被正常的进程使用。
  • Transparent Huge Pages (THP): 这种方式对于应用程序来说是透明的,使得应用程序可以像平常那样操作内存。理想情况下,应用程序不需要进行任何改动,我们将会看到应用程序从已知的THP中受益是可得的。在实践中,在一些特殊情况下的内存、时间开销也是不容忽视的,如:为一些小的内容分配整个 large pageTHP有时需要整理内存随便以分配页面。还在这有一个折中的方案:madvise(2) 方法让Linux系统知道应用程序在哪里使用THP

OpenJDK两种方式都支持:

原文作者执行后的示例:

1
2
3
4
5
$ java -XX:+PrintFlagsFinal 2>&1 | grep Huge
bool UseHugeTLBFS = false {product} {default}
bool UseTransparentHugePages = false {product} {default}
$ java -XX:+PrintFlagsFinal 2>&1 | grep LargePage
bool UseLargePages = false {pd product} {default}

我自己在我的mac上执行没有 UseTransparentHugePages这项,在Centos7上是有的。

mac 上的 Java 版本:

1
2
3
java version "1.8.0_171"
Java(TM) SE Runtime Environment (build 1.8.0_171-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.171-b11, mixed mode)

Centos 7 上的 Java 版本:

1
2
3
java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)

-XX:+UseHugeTLBFS 映射 Java 堆到 hugetlbfs,应该单独编写。

-XX+UseTransparent仅 Java heap 通过 madvise -s使用 THP。我们知道 Java heap 一般都很大、大部分都是连续的。最有可能最大程度的从 large pages 中受益。

-XX:+UseLargepages是一个通用的配置,Linux 中,这个指令默认开启的是 hugetlbfs 而不是 THP,应该是因为 历史原因,毕竟 hugetlbfs 更早出现。

一些应用在启用 large pages 后性能下降。原文笔者的直觉是 THP 对于大多数短生命周期的应用,内存整理的时间相对于应用程序较短的生命周期相比更明显。

Experiment

同样我们还要使用JMH(JAVA MICROBENCHMARK HARNESS)来进行实验。有点本命工具的意思😄。

实验材料 :Aliyun ESC 下的 Centos 7 1核 2G 。

我们通过随机访问不同大小的 byte[] 数组,来观测结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ByteArrayTouch {

@Param(...)
int size;

byte[] mem;

@Setup
public void setup() {
mem = new byte[size];
}

@Benchmark
public byte test() {
return mem[ThreadLocalRandom.current().nextInt(size)];
}
}

完整代码

我们知道随着数组的增大,系统性能开始受到L1、L2、L3缓存未命中的影响等等,通常我们忽略 TLB 不命中的影响。细说Cache-L1/L2/L3/TLB

测试前我们需要确定使用多大的堆内存,在我的机器上,L3 缓存有 8M(mac 中使用 sysctl hw查看,Linux 使用 lscpu), 100M 的数组足以满足条件,通过 -Xmx1G -Xms1G分配 1G 内存足够了(我自己设置的256m)。这也为我们分配 hugetlbfs 提供了指导。

同时,确保如下参数已经设置:

1
2
3
4
5
6
# HugeTLBFS should allocate 1000*2M pages:
sudo sysctl -w vm.nr_hugepages=1000

# THP to "madvise" only (some distros have an opinion about defaults):
echo madvise | sudo tee /sys/kernel/mm/transparent_hugepage/enabled
echo madvise | sudo tee /sys/kernel/mm/transparent_hugepage/defrag

通过 madvise 使用 THP,因为它可以让我们选择性内存可以受益的特定部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# BaseLine
Benchmark (size) Mode Cnt Score Error Units
ByteArrayTouch.test 1000 avgt 15 11.866 ± 1.455 ns/op
ByteArrayTouch.test 10000 avgt 15 11.574 ± 1.546 ns/op
ByteArrayTouch.test 1000000 avgt 15 15.395 ± 2.052 ns/op
ByteArrayTouch.test 10000000 avgt 15 63.419 ± 8.201 ns/op
ByteArrayTouch.test 100000000 avgt 15 81.424 ± 9.635 ns/op
# -XX:+UseTransparentHugePages
Benchmark (size) Mode Cnt Score Error Units
ByteArrayTouch.test 1000 avgt 15 11.275 ± 1.332 ns/op
ByteArrayTouch.test 10000 avgt 15 11.463 ± 1.563 ns/op
ByteArrayTouch.test 1000000 avgt 15 15.767 ± 1.927 ns/op
ByteArrayTouch.test 10000000 avgt 15 63.799 ± 7.880 ns/op
ByteArrayTouch.test 100000000 avgt 15 81.149 ± 12.851 ns/op
# -XX:+UseHugeTLBFS
Benchmark (size) Mode Cnt Score Error Units
ByteArrayTouch.test 1000 avgt 15 11.584 ± 1.343 ns/op
ByteArrayTouch.test 10000 avgt 15 11.685 ± 1.267 ns/op
ByteArrayTouch.test 1000000 avgt 15 15.260 ± 1.831 ns/op
ByteArrayTouch.test 10000000 avgt 15 58.797 ± 7.765 ns/op
ByteArrayTouch.test 100000000 avgt 15 80.017 ± 10.773 ns/op

综上一些总结:

  1. 在数组较小的情况下,缓存和 TLB 都表现良好,同默认设置下跑出来的结果基本无异。
  2. 随着数组的增大,缓存不命中成为影响性能的主要因素,三种场景的耗时都有所增加。
  3. 随着数组的增大,TLB 未命中也有了影响,通过设置大页有所提升。
  4. UseTHPUseHTLBS 带来的提升基本一致,因为它们对于应用程序来说,提供的功能是一样的。

为了验证 TLB 不命中的假设,我们可以通过硬件计数器来观察,JMH 的 -prof perfnorm可以使执行标准化。

这个实验也没跑通,本来想纠结一下了,综合考虑暂时pass,留给以后的自己

直接引用原文的实验数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
Benchmark                                (size)  Mode  Cnt    Score    Error  Units

# Baseline
ByteArrayTouch.test 100000000 avgt 15 33.575 ± 2.161 ns/op
ByteArrayTouch.test:cycles 100000000 avgt 3 123.207 ± 73.725 #/op
ByteArrayTouch.test:dTLB-load-misses 100000000 avgt 3 1.017 ± 0.244 #/op // !!!
ByteArrayTouch.test:dTLB-loads 100000000 avgt 3 17.388 ± 1.195 #/op

# -XX:+UseTransparentHugePages
ByteArrayTouch.test 100000000 avgt 15 28.730 ± 0.124 ns/op
ByteArrayTouch.test:cycles 100000000 avgt 3 105.249 ± 6.232 #/op
ByteArrayTouch.test:dTLB-load-misses 100000000 avgt 3 ≈ 10⁻³ #/op
ByteArrayTouch.test:dTLB-loads 100000000 avgt 3 17.488 ± 1.278 #/op

结合数据,可以看出,基准测试中,每次都会操作 dTLB-load-misses ,但是启动了 THP 之后却很少。

开启 THP 碎片整理,分配和访问时,碎片整理会带来而外的成本。将这些成本转移到 JVM 启动,将避免在应用运行时出现意外的延迟问题。你可以通过设置 -XX:AlwaysPreTouch 让 JVM 在启动时访问 java heap 中的每个单独的 page。不管怎么样,预访问对于 larger heaps 来说是一种好的策略。

-XX:+UseTransparentHugePages 事实上让 -XX:+AlwaysPreTouch更快,因为 JVM 知道以什么规模去访问堆。进程关闭后释放内存也会更快,这种优势一直延续到并行释放补丁发行版内核。

使用 4TB 的堆:

1
2
3
4
5
6
7
8
9
$ time java -Xms4T -Xmx4T -XX:-UseTransparentHugePages -XX:+AlwaysPreTouch
real 13m58.167s
user 43m37.519s
sys 1011m25.740s

$ time java -Xms4T -Xmx4T -XX:+UseTransparentHugePages -XX:+AlwaysPreTouch
real 2m14.758s
user 1m56.488s
sys 73m59.046s

提交和释放 4TB 的内存确实需要点时间。

Observations

Large pages 是一个提高我们的应用程序性能的小技巧。Linux 内核中透明大页很容易使用,JVM 配置透明页也很简单。所以,当你的应用有很大的数据量以及堆内存时,启用 large pages 是一个不错的选择。

Tips

1
2
3
4
5
# 创建用户可以使用ssh登录,但只有只读权限可以浏览下载部分文件无法写和修改
useradd -d /home/be-web -m be-web
passwd be-web
chown -R be-web:be-web /mnt/logs
chmod 760 /mnt/logs

Share

what

ElasticSearch 是一个基于 Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。 ElasticSearch是用Java开发的,并作为Apache许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索、稳定、可靠、快速、安装使用方便。

学习资源,感谢《龙果学院》老师的分享。以下也是我的随堂笔记。

龙果学院 《Elasticsearch 顶尖高手系列 - 快速入门篇》

Elasticsearch顶尖高手系列-快速入门篇

大白话介绍Elasticsearch

什么是搜索?

垂直搜索(站内搜索)

  • 互联网的搜索:电商网站,招聘网站,新闻网站,app等。
  • IT系统的搜索:OA软件

搜索,就是在任何场景下,根据你想要得到的信息,根据关键字找到的相关信息。

如果用数据库搜索会怎么样?

慢、无法更精确的匹配、无法分词。

什么是全文检索,什么是Lucene

  • 全文检索:将所有结构化和非结构化的数据提取信息,创建索引,根据用户的查询请求,搜索创建的索引,返回结果。
  • 倒排索引:根据词的关键字找文档
  • Lucene,就是一个jar包,里面包含了封装好的各种建立倒排索引,以及进行搜索的代码,包括各种算法。我们使用 java 开发的时候,引入lucene jar,然后基于 lucene 的 api 进行开发就可以了。用 lucene,我们接可以去将已有的数据建立索引,lucene会在本地磁盘上面,给我们组织索引的数据结构。另外的话,我们也可以用lucene提供的一些功能和 api 来针对磁盘上的索引数据进行搜索。

什么是Elasticsearch?

What

Elasticsearch的功能、使用场景以及特点

Elasticsearch的功能

  1. 分布式的搜索引擎和数据分析引擎

  2. 全文搜索,结构化检索,数据分析

    • 结构化搜索:分类搜索 : sql where =
    • 全文搜索:内容搜索 :sql like
    • 数据分析:某分类下有多少个数 :sql group by
  3. 对海量数据进行近实时的处理

    分布式: ES自动可以将海量数据分散到多台服务器上去存储和检索

    海量数据的处理;分布式以后,就可以采用大量的服务器去吃存储和检索数据,自然而然就可以实现海量数 据的处理了。跟分布式/海量数据相反的,lucene,单机应用,只能在单台服务器上使用,最多只能处理单台服 务器的数据。

    近实时:在秒级别对数据进行搜索和分析

    Batch-processing: 花费n小时,离线批处理

Elasticsearch的使用场景

  • 维基百科
  • The Guardian (国外新闻网站)
  • Stack Overflow
  • GitHub 搜索上千亿行代码
  • 电商网站,检索商品
  • 日志数据分析,logstash采集日志,ES进行复杂的数据分析(ELK技术,elasticsearch+logstash+kibana)
  • 商品价格监控网站,用户设定某商品的价格阈值
  • BI系统,商业智能,Business Intelligence,分析某区域近三年的用户消费金额趋势以及用户群体的组成构成,产出相关的报表。ES执行数据分析和挖掘,Kibana进行数据可视化
  • 国内:站内搜索(电商、招聘、门户等等)、IT系统搜索(OA、CRM、ERP等等),数据分析

Elasticsearch的特点

  • 可以作为一个大型分布式集群(数百台服务器)技术,处理PB级数据,服务大公司;也可以运行在单机上,服务小公司
  • Elasticsearch 不是新技术,主要是将全文检索、数据分析以及分布式技术,合并在了一起,才形成了独一无二的ES;lucene (全文检索),商用的数据分析软件(也是有的),分布式数据库(mycat)
  • 对用户而言,是开箱即用的,非常简单,作为中小型的应用,直接3分钟部署ES,就可以作为生产环境的系统来使用了,数据量不大,操作不是太复杂
  • 数据库的功能面对很多领域是不够用的 (事务,还有各种联机事务性的操作)。比如全文检索;同义词处理,相关度排名;复杂数据分析,海量数据的近实时处理;Elasticsearch作为传统数据库的一个补充,提供了数据库所不能提供的很多功能

手工画图剖析Elasticsearch核心概念:NRT、索引、分片、副本等

lucene和elasticsearch的前世今生

lucene,最先进、功能最强大的搜索库,直接基于lucene开发,非常复杂,api复杂(实现一些简单的功能,写大量java代码),需要深入理解原理 (各种索引结构)

Elasticsearch, 基于lucene,隐藏复杂性,提供简单易用的restful、api接口、java api接口(还有其他语言的api接口)

  • 分布式文档存储引擎
  • 分布式搜索引擎和分析引擎
  • 分布式;支持PD级数据

开箱即用,优秀的默认参数,不需要任何额外设置,完全开源

失业程序员-陪老婆英国伦敦学习-写一个菜谱搜索引擎-compass-elasticsearch

elasticsearch的核心概念

  • Near Realtime (NRT),近实时,两个意思,从写入数据到数据可以被搜索到有一个小延迟(大概1秒);基于es执行搜索和分析可以达到秒级
  • Cluster:集群,包含多个节点,每个节点属于哪个集群是通过一个配置(集群名称,默认是elasticsearch)来决定的,对于中小型应用来说,刚开始一个集群就一个节点很正常
  • Node:节点,集群中的一个节点,节点也有一个名称(默认是随机分配的),节点名称很重要(在执行运维管理操作的时候),默认节点会去加入一个名称为“elasticserach”的集群,如果直接启动一堆节点,那么它们会自动组成一个elasticserach集群,当然一个节点也可以组成一个elasticsearch集群
  • Document:文档,es中的最小数据单元,一个document可以是一条客户数据,一条商品分类数据,一条订单数据,通常用JSON数据结构表示,每个index下的type中,都可以存储多个document。
  • Indexd:索引,包含一堆有相似结构的文档数据,比如可以有一个客户索引,商品分类索引,订单索引,索引有一个名称,一个index包含很多document,一个index就代表了一类类似的或者相同的document,比如说建立一个product index,商品索引,里面可能就存放了所有的商品数据,所有的商品document。
  • Type:类型,每个索引里面都可以有一个活多个type,type是idnex中的一个逻辑数据分类,一个type下的document,都有相同的field,比如博客系统,有一个索引,可以定义用户数据type,博客数据type,评论数据type。一个index可以放很多个type。
  • shard:单台机器无法存储大量数据,es可以将一个索引中的数据切分成多个shard,分布在多给服务器上存储。有了shard就可以横向扩展,存储更多数据,让搜索和分析等操作分布到多台服务器上去执行,提升吞吐量和性能,每个shard都是一个lucene index。
  • replica:任何一个服务器随时可能故障或宕机,此时shrad可能就会丢失,因此可以为每个shard创建多个replica副本。replica可以在shrad故障时提供备用服务,保证数据不丢失,多个replica还可以提升搜索操作的吞吐量和性能,primary shard(建立索引时一次设置,不能修改,默认5个),replica shard(随时修改数量,默认1个),默认每个索引10个shrad,5个primary shard。5个replica shard,最小的高可用配置,是两台服务器。

shard

Elasticsearch 核心概念 vs. 数据库核心概念

Elasticsearch 数据库
Document
Type
Index 数据库

使用Docker创建Elasticsearch+kibana服务

docker pull elasticsearch

docker run -d -p 9200:9200 -e ES_JAVA_OPTS="-Xms125m -Xmx125m" --name es_test docker.io/elasticsearch

ip:post访问即可。开箱即用。

docker pull kibana

docker run --name leon_kibana -p 5601:5601 -d -e ELASTICSEARCH_URL=http://ip:port kibana

我使用的是vm+centos 7 的虚拟环境

需要防火墙开启9200端口

firewall-cmd --zone=public --add-port=80/tcp --permanent

firewall-cmd --reload

指令操作参考

快速入门,文档CRUD

document的数据格式

面向文档的搜索分析引擎

  1. 应用系统的数据结构都是面向对象的,复杂的
  2. 对象数据存储到数据库中,只能拆解开来,变为扁平的多张表,每次查询的时候还得还原回对象格式,相当麻烦
  3. ES是面向文档的,文档中存储的数据结构,与面向对象的数据结构是一样的,基于这种文档数据结构,es可以提供复杂的索引,全文检索,分析聚合等功能。
  4. es的document用 josn数据格式来表达。

实验:电商网站商品管理案例

有一个电商网站,需要为其基于ES构建一个后台系统,提供一下功能:

  1. 对商品信息进行CRUD操作
  2. 执行简单的结构化查询
  3. 可以执行简单的全文检索,以及负载的phrase(短语)检索
  4. 对于全文检索的结果,可以进行高亮显示
  5. 对数据进行简单的聚合分析

简单的集群管理

  1. 快速检查集群的健康状况

    GET /_cat/health?v

    如何快速了解集群的健康状况?green、yellow、red

    green:每个索引的primary shard 和 reploca shard 都是active状态的

    yellow:每个索引的primary shard 都是active状态的,但是部分replica shard 不是active状态,处于不可用的状态

    red:不是所有索引的primary shard都是active状态,部分索引有数据丢失了

    为什么现在会处于一个yellow状态?

    我们单机启动了一个es进程,相当于只有一个node,现在es中有一个index,就是kibana自己内置建立的index。由于默认的配置是给每个index分配5个primary shrad 和5个 replica shrad,而且primary shard 和 replica shard 不能在同一个机器上(为了容错)。现在kibana自己建立的index是1个primary shard和1个replica shard。当前就一个node,所有只有1个primary shard被分配和启动,但是一个replica shard没有第二台机器去启动。

    进行一个小实验 ,此时只要启动第二个es进程,就会在es集群中有2个node,然后那1个replica shrad就会自动分配过去,然后cluster status 就会变成green状态。

    centos 7+dcoker 未顺利完成实验,TODO

    2019-06-05 参考官方文档done

  2. 快速查看集群有哪些索引?

    GET _cat/indicess?v

  3. 简单的索引操作

    • 创建索引:PUT /test_index?pretty
    • 删除索引:DELETE /test_index?pretty

商品的CRUD操作

  • 新增商品:新增文档,建立索引

    PUT /index/type/id

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    PUT /ecommerce/product/1 
    {
    "name": "gaoluejie yagao",
    "desc": "gaoxiao meibai",
    "price": 30,
    "producer": "gaolujie producer",
    "tags": ["meibai", "fangzhu"]
    }
    PUT /ecommerce/product/2
    {
    "name": "jiajieshi yagao",
    "desc": "youxiao fangzhu",
    "price": 25,
    "producer": "jiajieshi producer",
    "tags": ["fangzhu"]
    }
    PUT /ecommerce/product/3
    {
    "name": "zhonghua yagao",
    "desc": "caoben zhiwu",
    "price": 40,
    "producer": "zhonghua producer",
    "tags": ["qingxin"]
    }

    es会自动建立index和type,不需要提前创建,而且es默认会对document每个field都建立倒排索引,让其可以被搜索。

  • 查询商品:检索文档

    GET /index/type/id

    GET /ecommerce/product/1

  • 修改商品:替换文档

    1
    2
    3
    4
    5
    6
    7
    8
    PUT /ecommerce/product/1
    {
    "name": "gaoluejie yagao",
    "desc": "gaoxiao meibai",
    "price": 32,
    "producer": "gaolujie producer",
    "tags": ["meibai", "fangzhu"]
    }

    替换方式有一个坏处,必须带上所有的field才能进行信息修改。

  • 修改商品:更新文档

    1
    2
    3
    4
    5
    6
    POST /ecommer/product/1/_update
    {
    "doc":{
    "name": "jiaqiangban gaolujie yagao"
    }
    }
  • 删除商品:删除文档

    DELETE /ecommerce/product/1?pretty

留言

⬆︎TOP