主要观点：介绍了一种名为 Galloping Search 的算法，用于在未知上限的情况下搜索已排序的项目，类似于二分搜索但无需“高”值。作者在构建分布式日志时遇到问题，即 S3 限制导致难以找到最后插入的对象，通过并行在指数间隔搜索并结合二分搜索来解决，还提到了其他替代方案及自身采取的措施。
关键信息：

• Galloping Search 可在排序、无界列表中搜索指定输入值，分两阶段，先确定范围再二分搜索。
• 在 S3 构建分布式日志，连续添加顺序整数命名的文件，Writer 维护内存计数器。
• S3 限制：无获取最后插入项的 API，LIST API 不支持排序且昂贵，不能扫描大量文件。
• 解决方案为并行在指数间隔搜索，找到差距后二分搜索，再用 LIST API 获取对象。
• 替代方案有逆序存储、分区和分层搜索等。
• 自身做法：每 10k 或 50k 写入时在.metadata 文件中记录当前计数，搜索时从该文件计数器开始进行 Galloping Search，即使文件不存在该方法仍有效。
  重要细节：
• 用 S3 的条件写入“追加”并添加下一个序列号的新对象。
• 有间隙的日志可能导致灾难性后果，如 Writer 在间隙处添加对象并返回成功给客户端。
• s3-log 项目开源。