CodingTour —

ARTS #146

Algorithm

本周选择的算法题是：Validate Stack Sequences。

规则

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• All the elements of pushed are unique.
• popped.length == pushed.length
• popped is a permutation of pushed.

Solution

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        while pushed or popped:
            while stack and stack[-1] == popped[0]:
                stack.pop()
                popped.pop(0)
            if pushed:
                stack.append(pushed.pop(0))
            else:
                break
        return not stack

Review

Software Architecture Pitfalls: High Risk — Low Reward Designs

这篇文章主要描述了高风险、低回报系统的常见问题。

虽然每一个软件工程都是独一无二的，但风险往往是类似的：

• 当前架构正在做高风险的事情，比如：
  • 几乎没有其他人做过，如自己实现持久层的设计，而不是使用业内软件等
  • 引入的数据库、语言、框架等对团队是陌生的，此前无人使用
• 如果碰巧遇到了上面说的问题，而这些问题不解决系统将无法使用，这又会产生替换、重构、重写的风险
• 价值对用户来说微乎其微，比如第1点提到的技术“创新”对用户来说没有感知

感觉保持简单和统一是软件工程里永远难而正确的事情。

Tip

将内网前端的构建速度进一步从 7mins 降低到 20s：

• 设置 Jenkins 规则，不删除缓存
• 设置 --registry=https://registry.npm.taobao.org

Share

从一个奇怪的现象重新学习了 chrome 的缓存策略。

这个现象是：在 chrome 的多个 tabs 发送相同请求时，会出现请求排队的情况。一开始我觉得可能和后端的 session 实现有关，但看了日志后发现 nginx 收到请求时已经被 delay 了，所以问题出现在浏览器上。

网上也有类似的问题：

• Are calls to the SAME view synchronous?
• Same Browser Requests Serialization

不过这些资料更多的是描述现象，并没有解释为什么会出现这种情况，为此我简单做了个调研：

• 同时在 chrome、safari 里发送相同请求，不会出现排队
• 在 safari 的多个 tabs 发送相同请求，无论匿名模式是否开启，不会出现排队
• 在 chrome 里开启匿名模式，不会出现排队
• 在 chrome 里禁用缓存，也不会出现排队
• 在 chrome 里关闭匿名模式，则会出现排队

ps: 我部署了一个 sleep 5秒的服务，用于测试。

所以这还是和浏览器的缓存策略有关的，那么设置 no-cache/no-store 能不能解决问题呢？

从 no-cache 的定义上看：

If the no-cache directive does not specify a field-name, then a cache MUST NOT use the response to satisfy a subsequent request without successful revalidation with the origin server. This allows an origin server to prevent caching even by caches that have been configured to return stale responses to client requests.

If the no-cache directive does specify one or more field-names, then a cache MAY use the response to satisfy a subsequent request, subject to any other restrictions on caching. However, the specified field-name(s) MUST NOT be sent in the response to a subsequent request without successful revalidation with the origin server. This allows an origin server to prevent the re-use of certain header fields in a response, while still allowing caching of the rest of the response.

no-cache 并不要求 response 不能存储在缓存中，它只规定缓存的 response 必须在重新验证后才能作用于后续请求(subsequent)上，语义上等同于 must-revalidate, max-age=0。

而什么是后续请求则取决于浏览器，不同的浏览器引擎之间存在差异。

no-store：

Even when this directive is associated with a response, users might explicitly store such a response outside of the caching system (e.g., with a “Save As” dialog). History buffers MAY store such responses as part of their normal operation.

The purpose of this directive is to meet the stated requirements of certain users and service authors who are concerned about accidental releases of information via unanticipated accesses to cache data structures. While the use of this directive might improve privacy in some cases, we caution that it is NOT in any way a reliable or sufficient mechanism for ensuring privacy. In particular, malicious or compromised caches might not recognize or obey this directive, and communications networks might be vulnerable to eavesdropping.

相比 no-cache，no-store 是作用于所有请求的。

但无论是 no-cache 还是 no-store 都不能完全让浏览器禁用缓存，从 no-store 定义甚至可以看到 cache 和 history 的行为是不同的，no-cache、no-store 策略在 history 场景下并不会生效，而要做到这一步，仍然需要浏览器进行缓存，具体可以看 History Lists，这里就不展开了。

从开发者面板可以看到后续请求被 Stalled 了 4.27 秒：

这 4.27 秒又发生了什么呢，这就得从 Events 里找线索了：

1. 将 chrome 的网络日志通过 net-export 写入到本地文件
2. 用 netlog_viewer 分析 net-export 的输出文件

通过对 Events 的分析终于找到了问题原因：

net_error = -406 (ERR_CACHE_RACE) 就是导致了 Stalled 的元凶，这也解释了 4.27 秒是怎么来的，10420-(6148-1)=4273。

从 ERR_CACHE_RACE 字面量大致可以猜出是什么问题了，但为了搞明白 chrome 里究竟发生了什么，可以继续从源码里找答案：

int HttpCache::CreateEntry(const std::string& key,
                           ActiveEntry** entry,
                           Transaction* transaction) {
  if (FindActiveEntry(key)) {
    return ERR_CACHE_RACE;
  }
...

https://chromium.googlesource.com/chromium/src/+/refs/heads/main/net/http/http_cache.cc#839

线索指向了 ActiveEntry 和 active_entries_：

HttpCache::ActiveEntry* HttpCache::FindActiveEntry(const std::string& key) {
  auto it = active_entries_.find(key);
  return it != active_entries_.end() ? it->second.get() : nullptr;
}

https://chromium.googlesource.com/chromium/src/+/refs/heads/main/net/http/http_cache.cc#709

active_entries_ 是 ActiveEntriesMap 的实例。

想要理解 chrome 的行为，就得理解 http_cache 模块的设计：

• http_cache 依赖了 disk_cache
• http_cache 将 ActiveEntry 维护在 disk_cache 上
• http_cache + ActiveEntry 实现了缓存事务的概念
• http_cache 是数据访问层，决定了数据是从磁盘还是从网络获取
• http_cache 在实现上采用了多读单写，在任何时间对同一资源的网络请求只有一个

所以 http_cache 从设计上就是要等前一个请求完成(write)后才会开始下一个请求(read)，优点很明显，不会浪费带宽去获取相同的资源，而且绕过这个设计并不是好的选择，因为会引入一致性的问题；缺点谈不上，算是这个设计的 trade-off 吧。