1
#pragma once
2
 
3
#include <kj/filesystem.h>
4
#include <kj/map.h>
5
 
6
namespace workerd::server {
7
 
8
using kj::uint;
9
 
10
// Implements an index, stored on disk, which maps leaves of a tree to small integers in a stable
11
// way.
12
//
13
// Specifically, this is used to assign numeric IDs to facets of Durable Objects. Each Durable
14
// Object is potentially composed of a tree of "facets". One facet -- with ID zero -- serves as
15
// the root facet. All other facets have a parent facet and a name. Names are unique among facets
16
// with the same parent, but not globally. Each facet is assigned a numeric ID the first time it is
17
// seen. These IDs are assigned sequentially.
18
//
19
// We assume that the total number of facets created for a single Durable Object over its entire
20
// lifetime will never be very large. Therefore, it is reasonable to store the entire tree index
21
// in memory, loaded in its entirely at startup. Because of this, entries can simply be stored in
22
// order by ID (starting with ID 1, since no entry is needed for the root). We also assume that
23
// it's never necessary to delete an entry -- while a facet itself can be deleted, if a new facet
24
// is created with the same name, it should use the same ID. Therefore, the index file can be
25
// append-only, modified only when a never-before-seen facet is created.
26
//
27
// The facet index file therefore uses a very simple format. The index is simply a sequence of
28
// entries, where each entry is composed of:
29
// * A 2-byte integer specifying the parent ID.
30
// * A 2-byte integer specifying the length of the name. Note this cannot be zero.
31
// * The bytes of the name itself (not including any NUL terminator).
32
//
33
// Note that the format implicitly limits a Durable Object to have no more than 65536 facets in
34
// its entire lifetime. An attempt to exceed this limit will throw an exception. If this ever comes
35
// up in practice, we probably need to rethink the format -- not just the size of the integers, but
36
// the entire design, as it is not designed for so many facets.
37
//
38
// Notice that the index file's design is such that updating the file strictly at append operation.
39
// This avoids the need for a write-ahead log on updates. It is still possible, in the event of
40
// a power failure during an update, that the tail of the index will be corrupted. This is OK,
41
// becaues that tail could not have been relied upon yet. When reading the file, if a nonsensical
42
// entry is seen (parent ID out-of-range, name overrunning the end of the file, empty name, or
43
// duplicate entry), the remainder of the file from that point can simply be ignored. In the
44
// unlikely event that corrupted entries by coincidence appear to be valid, no harm is done -- this
45
// only has the effect of assigning IDs to names that will never actually be used.
46
//
47
// The index file is prefixed with the 8-byte magic number 0xc4cdce5bc5b0ef57. All integers
48
// (including the magic number) are in host byte order (which is little-endian on all supported
49
// platforms).
50
class FacetTreeIndex {
51
 public:
52
  // Construct the index, reading the given file to populate the initial index, and then arranging
53
  // to append new entries to the file as needed.
54
  FacetTreeIndex(kj::Own<const kj::File> file);
55
 
56
  // Gets the ID for the given facet, assigning it if needed.
57
  uint getId(uint parent, kj::StringPtr name);
58
 
59
  // For each child of the given parent ID, call the callback.
60
  template <typename Func>
61
  void forEachChild(uint parentId, Func&& callback) {
62
    for (auto& child: entries.range(EntryPtr{parentId, nullptr}, EntryPtr{parentId + 1, nullptr})) {
63
      KJ_IASSERT(child.parent == parentId);
64
      uint childId = 1 + (&child - entries.begin());
65
      callback(childId, child.name);
66
    }
67
  }
68
 
69
 private:
70
  kj::Own<const kj::File> file;
71
 
72
  // Offset at which to write the next entry. Typically points to the end of the file (except when
73
  // a corrupted tail was detected).
74
  uint offset = 0;
75
 
76
  struct EntryPtr;
77
 
78
  struct Entry {
79
    uint parent;
80
    kj::String name;
81
 
82
    bool operator==(const Entry& other) const = default;
83
    bool operator<(const Entry& other) const {
84
      if (parent < other.parent) return true;
85
      if (parent > other.parent) return false;
86
      return name < other.name;
87
    }
88
    bool operator<(const EntryPtr& other) const {
89
      if (parent < other.parent) return true;
90
      if (parent > other.parent) return false;
91
      return name < other.name;
92
    }
93
  };
94
 
95
  struct EntryPtr {
96
    uint parent;
97
    kj::StringPtr name;
98
 
99
    bool operator==(const Entry& other) const {
100
      return parent == other.parent && name == other.name;
101
    }
102
  };
103
 
104
  // All entries. Note that there's no need to store the ID of each entry since they are strictly
105
  // ordered with no erasures. kj::TreeSet is based on kj::Table which maintains the original
106
  // insertion order (as long as no erasures occur), so the index of any entry can be computed
107
  // by subtracting `entries.begin()` from its pointer. (Add 1 to the index to get the ID, since
108
  // the root is ID zero.)
109
  kj::TreeSet<Entry> entries;
110
 
111
  // Next ID that will be assigned. Off-by-one due to root not being in the set.
112
  inline uint nextId() {
113
    return entries.size() + 1;
114
  }
115
 
116
  static constexpr uint64_t MAGIC_NUMBER = 0xc4cdce5bc5b0ef57;
117
  static constexpr uint MAX_ID = static_cast<uint16_t>(kj::maxValue);
118
 
119
  struct EntryHeader {
120
    uint16_t parentId;
121
    uint16_t nameLength;
122
  };
123
};
124
 
125
}  // namespace workerd::server