Snowflake OA面经、VO面经,Snowflake 实习上岸 Snowflake | OA | All Questions | Summer Internship 2023

今年的第一个系统面试告负,拖了一个多星期终于静下心来准备写下面试的经历,一方面失败总是难以接受,另一方面,这次的面试对自己仿佛也有了更新的认识。长期在当前职位的react而不是think,也仿佛导致了必然的结果。

Snowflake的面试官都是属于人狠话不多类型,上来直接丢题,对你的背景毫不感兴趣。题目是设计Key-Value Store with global versioning and time travel。听到Global Key-Value Store,我从Design Data-Intensive Application书里学来的东西直接short circuit了我的大脑,按着pattern就一点一点开始设计Key Value Store,直接完全忽略了global versioning 和 time travel的requirement,导致最后压根都涉及到time travel,完全纠结在make the basic work。

Redesign

应该从data出手,想想in-memory和single db如何handle,以及对performance的需求,然后延展到distributed system.

比如这里的核心需求是global versioning,那么所有的历史数据都必须得存下来。同时有time travel的需求,那么timestamp也必须得被存下来。

那么最简单的一个table schema就可以变成:

create_snapshot_table.sql
CREATE TABLE IF NOT EXISTS snapshots (
snapshot_id SERIAL PRIMARY KEY,
key VARCHAR NOT NULL,
value VARCHAR NOT NULL,
created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
);
CREATE INDEX IF NOT EXISTS idx_snapshots_key ON snapshots (key);
CREATE INDEX IF NOT EXISTS idx_snapshots_created_at ON snapshots (created_at);

每个put request会append一个row,每一个row number都是snapshot id。

这个本质上跟SSTable一样,只不过不涉及到底层的文件存储,这些都被postgres 的api abstract掉了。

这样put和get包括ss和timetravel的handling就是简单的SQL.

Read Performance — Scaling

最后整个db对每个entry的query P50大概在1.7ms 左右,server response time P50大概在9ms左右。

这些都是可以通过砸更多机器保证的。

进一步的提升那么只能通过cache,可以达到sub-ms 的read速度 (100ns),或者干脆在client端cache,从而完全不需要network request。

Write Performance — Snapshot id

对Snapshot id的操作有几种选择。

  1. 使用db的auto increment
  2. 读current ss然后写入ss+1,利用unique index constraint on primary key去guarantee consistency

2 显然是没法scale的,在很多concurrent write发生的时候,大家都会争夺current ss id,然后只有一个可以成功, 其他所有都要retry。

1会快很多。

每个write还是生成一个snapshot id (uuidv4),根据snapshot id找到timestamp,然后用timestamp往前搜索。

这样就enable sharding,同时可以用Cassandra之流。

Read会慢一些,因为timestamp的sort会span across multiple database shard。

但是write也可以horizontal scale了。

Idea 4: Batch Snapshot Id Update

每个Write都先进入一个Event Queue,然后Worker进行batch snapshot update,这样write没法立刻得到Snapshot id。不符合需求。

Failure Handling

Request -> Coordinator (API Service) -> Persistence (Postgres)

  • When write is received, but Coordinator crashed, write is lost
  • other failures? if postgres is down, cannot read/write, add cache so we can still support read

Reference

https://github.com/Noeyfan/system-design/tree/master/key-value-store

Leave a Reply

Your email address will not be published. Required fields are marked *