算法之LFU缓存算法

LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。

举个例子,缓存空间大小为3：

1. put(1,“a”)
2. put(2,“b”)
3. get(1)
4. get(2)
5. put(3,“c”)
6. put(4,“d”) // 此时LFU应该淘汰(3,“c”)

Maven依赖机制

Maven依赖传递是Maven的核心机制之一，它能够一定程度上简化Maven的依赖配置。

flowchart LR
    A -->|depend on|B
    B -->|depend on|C
    A -->|depend on|C

如上图所示，模块A依赖模块B，模块B依赖模块C。此时B是A的直接依赖，C是A的间接依赖。

Maven的依赖传递机制是指，不管Maven项目存在多少间接依赖，POM中都只需要定义其直接依赖，而不需要定义任何间接依赖。Maven 会动读取当前项目各个直接依赖的 POM，将那些必要的间接依赖以传递性依赖的形式引入到当前项目中。Maven 的依赖传递机制能够帮助用户一定程度上简化POM的配置。

基于 A、B、C 三者的依赖关系，根据 Maven 的依赖传递机制，我们只需要在模块 A 的 POM 中定义其直接依赖 B，在模块 B 的 POM 中定义其直接依赖 C，Maven会解析A的直接依赖 B 的POM，将间接依赖 C 以传递性依赖的形式引入到模块 A 中。通过这种依赖传递关系，可以使依赖关系树迅速增长到一个很大的量级，很有可能会出现依赖重复，依赖冲突等情况，Maven 针对这些情况提供了如下功能进行处理:

• 依赖关系传递
  • 可选依赖
  • 排除依赖
• 依赖关系范围
• 依赖关系管理

Clickhouses别名使用问题

clickhouse 在查询中使用别名时可能会有下面的问题¹。

1
2
3

$ SELECT avg(number) AS number, max(number) FROM numbers(10)

Aggregate function avg(number) is found inside another aggregate function in query.

If aliased expression contains aggregate function, alias should not be resolved inside another aggregate function.
If alias name clashes with the column name, the substitution of this alias should be cancelled.

原因是clickhouse的别名如果和某个列名相同，就会有上面的异常。可以通过添加下面了配置处理上述问题².

1
2

SELECT avg(number) AS number, max(number) FROM numbers(10)
settings prefer_column_name_to_alias  = 1;

但是这个配置引入了新的问题³.

Prefer alias for ORDER BY after GROUP BY in case of set prefer_column_name_to_alias=1;
Clickhouse version 21.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

$ SELECT
    max(number) AS number,
    sum(number) AS sum
FROM numbers(100)
ORDER BY number ASC

Query id: 058b2cb1-7ea6-44de-b6a8-662ac4d949a8


0 rows in set. Elapsed: 0.002 sec.

Received exception from server (version 21.6.1):
Code: 184. DB::Exception: Received from localhost:9000. DB::Exception: Aggregate function max(number) is found inside another aggregate function in query: While processing max(number) AS number.

$ set prefer_column_name_to_alias=1;

$ SELECT
    max(number) AS number,
    sum(number) AS sum
FROM numbers(100)
ORDER BY number ASC

Query id: f8ca2417-9bba-42c6-9f12-42987a26e75d


0 rows in set. Elapsed: 0.004 sec.

Received exception from server (version 21.6.1):
Code: 215. DB::Exception: Received from localhost:9000. DB::Exception: Column `number` is not under aggregate function and not in GROUP BY: While processing number ASC.

clickhouse 社区又提出了新的pr⁴处理上述问题:

Add more options to prefer_column_name_to_alias setting. This is for #24237

1. set prefer_column_name_to_alias=1 --> prefer column over alias in all sub clauses;
2. set prefer_column_name_to_alias=2 --> prefer column over alias in all sub clauses before and include group by;
3. set prefer_column_name_to_alias=3 --> prefer column over alias in all sub clauses before group by;

参考

• [1] Clickhouse.issue_9715

• [2] Clickhouse.pull_22044

• [3] Clickhouse.issue_24237

• [4] Clickhouse.pull_24391

maven打包带上时间戳

maven的包名可以通过finalName配置。

1
2
3

<build>
    <finalName> ${project.artifactId}-${project.version}</finalName>
</build>

如果想在包名上增加时间戳，可以通过在finalName中添加属性maven.build.timestamp.

1
2
3

<build>
    <finalName> ${project.artifactId}-${maven.build.timestamp}</finalName>
</build>

maven.build.timestamp的格式是通过maven.build.timestamp.format参数设置的。

1
2
3

<properties>
    <maven.build.timestamp.format>yyyyMMddHHmmss</maven.build.timestamp.format>
</properties>

时区问题

maven自带时间组件时区是只能使用UTC，要使用正确的时间，需要另一个插件的帮助。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

<build>
    <!-- 要将maven.build.timestamp替换成build.time，因为要使用buildnubmer-maven-plugin组件中声明的时间串。-->
    <finalName>${project.artifactId}-${build.time}</finalName>
    <plugins>
        <plugin>
            <groupId>org.codehaus.mojo</groupId>
            <artifactId>build-helper-maven-plugin</artifactId>
            <version>3.2.0</version>
            <executions>
                <execution>
                    <id>timestamp-property</id>
                    <goals>
                        <goal>timestamp-property</goal>
                    </goals>
                    <configuration>
                        <name>build.time</name>
                        <pattern>yyyyMMddHHmm</pattern>
                        <locale>zh_CN</locale>
                        <timeZone>GMT+8</timeZone>
                    </configuration>
                </execution>
            </executions>
        </plugin>
    </plugins>
</build>

web安全之XSS漏洞

Cross-Site Scripting（跨站脚本攻击）简称 XSS，是一种代码注入攻击。攻击者通过在目标网站上注入恶意脚本，使之在用户的浏览器上运行。利用这些恶意脚本，攻击者可获取用户的敏感信息如 Cookie、SessionID 等，进而危害数据安全。为了和 CSS 区分，这里把攻击的第一个字母改成了 X，于是叫做 XSS。XSS 的本质是：恶意代码未经过滤，与网站正常的代码混在一起；浏览器无法分辨哪些脚本是可信的，导致恶意脚本被执行。

而由于直接在用户的终端执行，恶意代码能够直接获取用户的信息，或者利用这些信息冒充用户向网站发起攻击者定义的请求。在部分情况下，由于输入的限制，注入的恶意脚本比较短。但可以通过引入外部的脚本，并由浏览器执行，来完成比较复杂的攻击策略。

Java异常丢失堆栈信息

在排查线上问题的时候，发现日志中只有java.lang.NullPointerException: null，没有打印出日志堆栈。第一反应是log.error()用错了方法。

1
2
3

void error(String msg);
void error(String format, Object... arguments);
void error(String msg, Throwable t);

在打印异常的时候建议使用 void error(String msg, Throwable t)这个方法。

如果想使用void error(String format, Object... arguments)这个方法，需要注意2点:

1. slf4j的版本要大于或等于1.6.0.
2. 使用占位符时，不要带上Exception。

1
2
3
4
5
6

String s = "Hello world";
try {
  Integer i = Integer.valueOf(s);
} catch (NumberFormatException e) {
  logger.error("Failed to format {}", s, e);
}

仔细检查了代码，发现并不是这个问题引起的。

AntlrV4的内存泄漏问题

在使用antlr生成的语法解析器处理多个文件后，JVM 最终会产生内存不足异常,PredictionContextCache中的hashMap和DFA数组_decisionToDFA会不断增长。因为 PredictionContextCache和_decisionToDFA在生成Parser和Lexer中是类共享的。

1
2
3
4
5
6

public class XXXParser extends Parser {
	protected static final DFA[] _decisionToDFA;
	protected static final PredictionContextCache _sharedContextCache =
		new PredictionContextCache();
  // ...
}

What Every Programmer Should Know About Computer 002

上一篇我们介绍了早期计算机和现代计算机构成位的不同硬件，计算机最底层的抽象“从硬件层抽象出二进制值”，以及二进制值的简单计算(和对应的门电路)。这一篇文章，将介绍一些更复杂的门电路(Gate Combinations )。

复杂门电路的重要设计思想：Design small circuits to be used in a bigger circuit。

What Every Programmer Should Know About Computer 001

本文的目的是快速了解计算机系统。文章标题模仿了《What Every Programmer Should Know About Memory》

Lightweight Asynchronous Snapshots for Distributed Dataflows

本篇是论文的中文简单翻译

概述

分布式有状态的流处理允许在云上部署和执行大规模的流数据计算，并且要求低延迟和高吞吐。这种模式一个比较大的挑战，就是其容错能力，能够应对潜在的 failure。现有的方案都是依赖周期性地全局状态的快照做失败恢复。 这些方法有两个主要的缺点:

1. 通常会停止分布式计算，影响流的摄入(为了获得全局的一致性状态，需要停止流处理程序，直到快照的完成)。
2. 快照的内容包含传输过程中所有的内容，这导致快照的大小过大。

本篇论文中提出了一个适用于现代数据流执行引擎，并最大限度减少空间需求的轻量级算法 Asynchronous Barrier Snapshot（ABS）。ABS在无环的拓扑结构中只对有状态的operator进行快照，对于有环的执行拓扑只保存最小化的record日志。在Apache Flink（一个支持有状态的分布式流处理分析引擎）中实现了ABS。通过评估表明，这种算法对程序执行没有很重的影响，并且保持了线性的可扩展性，在频繁的快照情况下也表现良好。

关键词: 容错，分布式计算，流处理，数据流，云计算，状态管理