Line data Source code
1 : // Copyright 2020 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package tool
6 :
7 : import (
8 : "encoding/json"
9 : "fmt"
10 : "io"
11 : "log"
12 : "math"
13 : "sort"
14 :
15 : "github.com/cockroachdb/errors"
16 : "github.com/cockroachdb/pebble"
17 : "github.com/cockroachdb/pebble/internal/base"
18 : "github.com/cockroachdb/pebble/internal/manifest"
19 : "github.com/cockroachdb/pebble/record"
20 : "github.com/cockroachdb/pebble/sstable"
21 : "github.com/spf13/cobra"
22 : )
23 :
24 : //go:generate ./make_lsm_data.sh
25 :
26 : type lsmFileMetadata struct {
27 : Size uint64
28 : Smallest int // ID of smallest key
29 : Largest int // ID of largest key
30 : SmallestSeqNum uint64
31 : LargestSeqNum uint64
32 : }
33 :
34 : type lsmVersionEdit struct {
35 : // Reason for the edit: flushed, ingested, compacted, added.
36 : Reason string
37 : // Map from level to files added to the level.
38 : Added map[int][]base.FileNum `json:",omitempty"`
39 : // Map from level to files deleted from the level.
40 : Deleted map[int][]base.FileNum `json:",omitempty"`
41 : // L0 sublevels for any files with changed sublevels so far.
42 : Sublevels map[base.FileNum]int `json:",omitempty"`
43 : }
44 :
45 : type lsmKey struct {
46 : Pretty string
47 : SeqNum uint64
48 : Kind int
49 : }
50 :
51 : type lsmState struct {
52 : Manifest string
53 : Edits []lsmVersionEdit `json:",omitempty"`
54 : Files map[base.FileNum]lsmFileMetadata `json:",omitempty"`
55 : Keys []lsmKey `json:",omitempty"`
56 : StartEdit int64
57 : }
58 :
59 : type lsmT struct {
60 : Root *cobra.Command
61 :
62 : // Configuration.
63 : opts *pebble.Options
64 : comparers sstable.Comparers
65 :
66 : fmtKey keyFormatter
67 : embed bool
68 : pretty bool
69 : startEdit int64
70 : endEdit int64
71 : editCount int64
72 :
73 : cmp *base.Comparer
74 : state lsmState
75 : keyMap map[lsmKey]int
76 : }
77 :
78 1 : func newLSM(opts *pebble.Options, comparers sstable.Comparers) *lsmT {
79 1 : l := &lsmT{
80 1 : opts: opts,
81 1 : comparers: comparers,
82 1 : }
83 1 : l.fmtKey.mustSet("quoted")
84 1 :
85 1 : l.Root = &cobra.Command{
86 1 : Use: "lsm <manifest>",
87 1 : Short: "LSM visualization tool",
88 1 : Long: `
89 1 : Visualize the evolution of an LSM from the version edits in a MANIFEST.
90 1 :
91 1 : Given an input MANIFEST, output an HTML file containing a visualization showing
92 1 : the evolution of the LSM. Each version edit in the MANIFEST becomes a single
93 1 : step in the visualization. The 7 levels of the LSM are depicted with each
94 1 : sstable represented as a 1-pixel wide rectangle. The height of the rectangle is
95 1 : proportional to the size (in bytes) of the sstable. The sstables are displayed
96 1 : in the same order as they occur in the LSM. Note that the sstables from
97 1 : different levels are NOT aligned according to their start and end keys (doing so
98 1 : is also interesting, but it works against using the area of the rectangle to
99 1 : indicate size).
100 1 : `,
101 1 : Args: cobra.ExactArgs(1),
102 1 : RunE: l.runLSM,
103 1 : }
104 1 :
105 1 : l.Root.Flags().Var(&l.fmtKey, "key", "key formatter")
106 1 : l.Root.Flags().BoolVar(&l.embed, "embed", true, "embed javascript in HTML (disable for development)")
107 1 : l.Root.Flags().BoolVar(&l.pretty, "pretty", false, "pretty JSON output")
108 1 : l.Root.Flags().Int64Var(&l.startEdit, "start-edit", 0, "starting edit # to include in visualization")
109 1 : l.Root.Flags().Int64Var(&l.endEdit, "end-edit", math.MaxInt64, "ending edit # to include in visualization")
110 1 : l.Root.Flags().Int64Var(&l.editCount, "edit-count", math.MaxInt64, "count of edits to include in visualization")
111 1 : return l
112 1 : }
113 :
114 0 : func (l *lsmT) isFlagSet(name string) bool {
115 0 : return l.Root.Flags().Changed(name)
116 0 : }
117 :
118 0 : func (l *lsmT) validateFlags() error {
119 0 : if l.isFlagSet("edit-count") {
120 0 : if l.isFlagSet("start-edit") && l.isFlagSet("end-edit") {
121 0 : return errors.Errorf("edit-count cannot be provided with both start-edit and end-edit")
122 0 : } else if l.isFlagSet("end-edit") {
123 0 : return errors.Errorf("cannot use edit-count with end-edit, use start-edit and end-edit instead")
124 0 : }
125 : }
126 :
127 0 : if l.startEdit > l.endEdit {
128 0 : return errors.Errorf("start-edit cannot be after end-edit")
129 0 : }
130 :
131 0 : return nil
132 : }
133 :
134 0 : func (l *lsmT) runLSM(cmd *cobra.Command, args []string) error {
135 0 : err := l.validateFlags()
136 0 : if err != nil {
137 0 : return err
138 0 : }
139 :
140 0 : edits := l.readManifest(args[0])
141 0 : if edits == nil {
142 0 : return nil
143 0 : }
144 :
145 0 : if l.startEdit > 0 {
146 0 : edits, err = l.coalesceEdits(edits)
147 0 : if err != nil {
148 0 : return err
149 0 : }
150 : }
151 0 : if l.endEdit < int64(len(edits)) {
152 0 : edits = edits[:l.endEdit-l.startEdit+1]
153 0 : }
154 0 : if l.editCount < int64(len(edits)) {
155 0 : edits = edits[:l.editCount]
156 0 : }
157 :
158 0 : l.buildKeys(edits)
159 0 : err = l.buildEdits(edits)
160 0 : if err != nil {
161 0 : return err
162 0 : }
163 :
164 0 : w := l.Root.OutOrStdout()
165 0 :
166 0 : fmt.Fprintf(w, `<!DOCTYPE html>
167 0 : <html>
168 0 : <head>
169 0 : <meta charset="utf-8">
170 0 : <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
171 0 : `)
172 0 : if l.embed {
173 0 : fmt.Fprintf(w, "<style>%s</style>\n", lsmDataCSS)
174 0 : } else {
175 0 : fmt.Fprintf(w, "<link rel=\"stylesheet\" href=\"data/lsm.css\">\n")
176 0 : }
177 0 : fmt.Fprintf(w, "</head>\n<body>\n")
178 0 : if l.embed {
179 0 : fmt.Fprintf(w, "<script src=\"https://d3js.org/d3.v5.min.js\"></script>\n")
180 0 : } else {
181 0 : fmt.Fprintf(w, "<script src=\"data/d3.v5.min.js\"></script>\n")
182 0 : }
183 0 : fmt.Fprintf(w, "<script type=\"text/javascript\">\n")
184 0 : fmt.Fprintf(w, "data = %s\n", l.formatJSON(l.state))
185 0 : fmt.Fprintf(w, "</script>\n")
186 0 : if l.embed {
187 0 : fmt.Fprintf(w, "<script type=\"text/javascript\">%s</script>\n", lsmDataJS)
188 0 : } else {
189 0 : fmt.Fprintf(w, "<script src=\"data/lsm.js\"></script>\n")
190 0 : }
191 0 : fmt.Fprintf(w, "</body>\n</html>\n")
192 0 :
193 0 : return nil
194 : }
195 :
196 0 : func (l *lsmT) readManifest(path string) []*manifest.VersionEdit {
197 0 : f, err := l.opts.FS.Open(path)
198 0 : if err != nil {
199 0 : fmt.Fprintf(l.Root.OutOrStderr(), "%s\n", err)
200 0 : return nil
201 0 : }
202 0 : defer f.Close()
203 0 :
204 0 : l.state.Manifest = path
205 0 :
206 0 : var edits []*manifest.VersionEdit
207 0 : w := l.Root.OutOrStdout()
208 0 : rr := record.NewReader(f, 0 /* logNum */)
209 0 : for i := 0; ; i++ {
210 0 : r, err := rr.Next()
211 0 : if err != nil {
212 0 : if err != io.EOF {
213 0 : fmt.Fprintf(w, "%s\n", err)
214 0 : }
215 0 : break
216 : }
217 :
218 0 : ve := &manifest.VersionEdit{}
219 0 : err = ve.Decode(r)
220 0 : if err != nil {
221 0 : fmt.Fprintf(w, "%s\n", err)
222 0 : break
223 : }
224 0 : edits = append(edits, ve)
225 0 :
226 0 : if ve.ComparerName != "" {
227 0 : l.cmp = l.comparers[ve.ComparerName]
228 0 : if l.cmp == nil {
229 0 : fmt.Fprintf(w, "%d: unknown comparer %q\n", i, ve.ComparerName)
230 0 : return nil
231 0 : }
232 0 : l.fmtKey.setForComparer(ve.ComparerName, l.comparers)
233 0 : } else if l.cmp == nil {
234 0 : l.cmp = base.DefaultComparer
235 0 : }
236 : }
237 0 : return edits
238 : }
239 :
240 0 : func (l *lsmT) buildKeys(edits []*manifest.VersionEdit) {
241 0 : var keys []base.InternalKey
242 0 : for _, ve := range edits {
243 0 : for i := range ve.NewFiles {
244 0 : nf := &ve.NewFiles[i]
245 0 : keys = append(keys, nf.Meta.Smallest)
246 0 : keys = append(keys, nf.Meta.Largest)
247 0 : }
248 : }
249 :
250 0 : l.keyMap = make(map[lsmKey]int)
251 0 :
252 0 : sort.Slice(keys, func(i, j int) bool {
253 0 : return base.InternalCompare(l.cmp.Compare, keys[i], keys[j]) < 0
254 0 : })
255 :
256 0 : for i := range keys {
257 0 : k := &keys[i]
258 0 : if i > 0 && base.InternalCompare(l.cmp.Compare, keys[i-1], keys[i]) == 0 {
259 0 : continue
260 : }
261 0 : j := len(l.state.Keys)
262 0 : l.state.Keys = append(l.state.Keys, lsmKey{
263 0 : Pretty: fmt.Sprint(l.fmtKey.fn(k.UserKey)),
264 0 : SeqNum: k.SeqNum(),
265 0 : Kind: int(k.Kind()),
266 0 : })
267 0 : l.keyMap[lsmKey{string(k.UserKey), k.SeqNum(), int(k.Kind())}] = j
268 : }
269 : }
270 :
271 0 : func (l *lsmT) buildEdits(edits []*manifest.VersionEdit) error {
272 0 : l.state.Edits = nil
273 0 : l.state.StartEdit = l.startEdit
274 0 : l.state.Files = make(map[base.FileNum]lsmFileMetadata)
275 0 : var currentFiles [manifest.NumLevels][]*manifest.FileMetadata
276 0 :
277 0 : for _, ve := range edits {
278 0 : if len(ve.DeletedFiles) == 0 && len(ve.NewFiles) == 0 {
279 0 : continue
280 : }
281 :
282 0 : edit := lsmVersionEdit{
283 0 : Reason: l.reason(ve),
284 0 : Added: make(map[int][]base.FileNum),
285 0 : Deleted: make(map[int][]base.FileNum),
286 0 : }
287 0 :
288 0 : for j := range ve.NewFiles {
289 0 : nf := &ve.NewFiles[j]
290 0 : if _, ok := l.state.Files[nf.Meta.FileNum]; !ok {
291 0 : l.state.Files[nf.Meta.FileNum] = lsmFileMetadata{
292 0 : Size: nf.Meta.Size,
293 0 : Smallest: l.findKey(nf.Meta.Smallest),
294 0 : Largest: l.findKey(nf.Meta.Largest),
295 0 : SmallestSeqNum: nf.Meta.SmallestSeqNum,
296 0 : LargestSeqNum: nf.Meta.LargestSeqNum,
297 0 : }
298 0 : }
299 0 : edit.Added[nf.Level] = append(edit.Added[nf.Level], nf.Meta.FileNum)
300 0 : currentFiles[nf.Level] = append(currentFiles[nf.Level], nf.Meta)
301 : }
302 :
303 0 : for df := range ve.DeletedFiles {
304 0 : edit.Deleted[df.Level] = append(edit.Deleted[df.Level], df.FileNum)
305 0 : for j, f := range currentFiles[df.Level] {
306 0 : if f.FileNum == df.FileNum {
307 0 : copy(currentFiles[df.Level][j:], currentFiles[df.Level][j+1:])
308 0 : currentFiles[df.Level] = currentFiles[df.Level][:len(currentFiles[df.Level])-1]
309 0 : }
310 : }
311 : }
312 :
313 0 : v := manifest.NewVersion(l.cmp.Compare, l.fmtKey.fn, 0, currentFiles)
314 0 : edit.Sublevels = make(map[base.FileNum]int)
315 0 : for sublevel, files := range v.L0SublevelFiles {
316 0 : iter := files.Iter()
317 0 : for f := iter.First(); f != nil; f = iter.Next() {
318 0 : if len(l.state.Edits) > 0 {
319 0 : lastEdit := l.state.Edits[len(l.state.Edits)-1]
320 0 : if sublevel2, ok := lastEdit.Sublevels[f.FileNum]; ok && sublevel == sublevel2 {
321 0 : continue
322 : }
323 : }
324 0 : edit.Sublevels[f.FileNum] = sublevel
325 : }
326 : }
327 0 : l.state.Edits = append(l.state.Edits, edit)
328 : }
329 :
330 0 : if l.state.Edits == nil {
331 0 : return errors.Errorf("there are no edits in [start-edit, end-edit], which add or delete files")
332 0 : }
333 0 : return nil
334 : }
335 :
336 0 : func (l *lsmT) coalesceEdits(edits []*manifest.VersionEdit) ([]*manifest.VersionEdit, error) {
337 0 : if l.startEdit >= int64(len(edits)) {
338 0 : return nil, errors.Errorf("start-edit is more than the number of edits, %d", len(edits))
339 0 : }
340 :
341 0 : be := manifest.BulkVersionEdit{}
342 0 : be.AddedByFileNum = make(map[base.FileNum]*manifest.FileMetadata)
343 0 :
344 0 : // Coalesce all edits from [0, l.startEdit) into a BulkVersionEdit.
345 0 : for _, ve := range edits[:l.startEdit] {
346 0 : err := be.Accumulate(ve)
347 0 : if err != nil {
348 0 : return nil, err
349 0 : }
350 : }
351 :
352 0 : startingEdit := edits[l.startEdit]
353 0 : var beNewFiles []manifest.NewFileEntry
354 0 : beDeletedFiles := make(map[manifest.DeletedFileEntry]*manifest.FileMetadata)
355 0 :
356 0 : for level, deletedFiles := range be.Deleted {
357 0 : for _, file := range deletedFiles {
358 0 : dfe := manifest.DeletedFileEntry{
359 0 : Level: level,
360 0 : FileNum: file.FileNum,
361 0 : }
362 0 : beDeletedFiles[dfe] = file
363 0 : }
364 : }
365 :
366 : // Filter out added files that were also deleted in the BulkVersionEdit.
367 0 : for level, newFiles := range be.Added {
368 0 : for _, file := range newFiles {
369 0 : dfe := manifest.DeletedFileEntry{
370 0 : Level: level,
371 0 : FileNum: file.FileNum,
372 0 : }
373 0 :
374 0 : if _, ok := beDeletedFiles[dfe]; !ok {
375 0 : beNewFiles = append(beNewFiles, manifest.NewFileEntry{
376 0 : Level: level,
377 0 : Meta: file,
378 0 : })
379 0 : }
380 : }
381 : }
382 0 : startingEdit.NewFiles = append(beNewFiles, startingEdit.NewFiles...)
383 0 :
384 0 : edits = edits[l.startEdit:]
385 0 : return edits, nil
386 : }
387 :
388 0 : func (l *lsmT) findKey(key base.InternalKey) int {
389 0 : return l.keyMap[lsmKey{string(key.UserKey), key.SeqNum(), int(key.Kind())}]
390 0 : }
391 :
392 0 : func (l *lsmT) reason(ve *manifest.VersionEdit) string {
393 0 : if len(ve.DeletedFiles) > 0 {
394 0 : return "compacted"
395 0 : }
396 0 : if ve.MinUnflushedLogNum != 0 {
397 0 : return "flushed"
398 0 : }
399 0 : for i := range ve.NewFiles {
400 0 : nf := &ve.NewFiles[i]
401 0 : if nf.Meta.SmallestSeqNum == nf.Meta.LargestSeqNum {
402 0 : return "ingested"
403 0 : }
404 : }
405 0 : return "added"
406 : }
407 :
408 0 : func (l *lsmT) formatJSON(v interface{}) string {
409 0 : if l.pretty {
410 0 : return l.prettyJSON(v)
411 0 : }
412 0 : return l.uglyJSON(v)
413 : }
414 :
415 0 : func (l *lsmT) uglyJSON(v interface{}) string {
416 0 : data, err := json.Marshal(v)
417 0 : if err != nil {
418 0 : log.Fatal(err)
419 0 : }
420 0 : return string(data)
421 : }
422 :
423 0 : func (l *lsmT) prettyJSON(v interface{}) string {
424 0 : data, err := json.MarshalIndent(v, "", "\t")
425 0 : if err != nil {
426 0 : log.Fatal(err)
427 0 : }
428 0 : return string(data)
429 : }
|
