[pkg/stanza] - Performance improvements while comparing fingerprints in fileconsumer

[VihasMakwana]

Intuitively, the fastest way of doing this would be to drop the bytes completely and just store a hash and the length of the file prefix it was calculated from. Then we'd also skip having to base64 encode all of these fingerprints to be able to store them in JSON, which I suspect costs more CPU time than the actual matching.

Originally posted by @swiatekm-sumo in #29106 (comment)

I'm converting the above discussion to a new issue—more in the comments.

[github-actions]

Pinging code owners:

• pkg/stanza: @djaglowski

See Adding Labels via Comments if you do not have permissions to add labels yourself.

[VihasMakwana]

Summarizing @swiatekm-sumo 's proposal:

Comparing and storing hashes of the fingerprints seems to be more efficient than storing individual fingerprint bytes. Storing the whole fingerprint is an awkward solution to begin with in my opinion, but its primary value is that it's very simple.
You have a set of old readers from the previous cycle, and those readers have fingerprints with lengths {x, y, z}, ordered by size. So you calculate fingerprints for your new readers up to x, y, and z lengths respectively, and compare at each level. This may seem wasteful, but I think it'd be more performant in practice:

• Hashes are calculated iteratively byte-by-byte anyway, so you don't incur any cost for stopping at a particular length.
• Hashes are just int64s, so comparisons are very fast.
• In the vast majority of cases, the set of lengths will be very small. It's very rare to have a lot of files smaller than the fingerprint size.

Using the above solution + trie wouldn't make much sense. as we'd need to run multiple checks on the trie with different hashes.
IMO, only one of the above solutions can co-exist at one time i.e. (either trie+fingerprint or storing hashes of fingerprints in an array/map)
@djaglowski what are your thoughts?

[djaglowski]

I'm happy to see a competition of ideas here. The current tracking mechanism cannot possibly be the best, so I'm open to anything which improves upon the situation.

I think the right way to evaluate this is to clearly define the requirements. Then we only need validate correctness and compare performance.

Here's my best attempt. This incorporates the notion of "singleton files", which I believe is critical to properly hardening this package. This was loosely introduced in #27823 but has not yet been strictly enforced. Please call out if I've missed something.

1. Our identification mechanism for a file must be based solely on its contents. We may assume that files are append-only, but must be able to recognize a file which has had data appended to it.
2. At a high level, we need to be able to track a global set of files where no two items in the set represent the same file.
3. The global set of files must be subdivided into discrete subsets of files, where each subset represents a stage in our lifecycle of reading and remembering the file. (Roughly, "actively reading", "done reading but still open", "closed, but not forgotten", "closed, but not forgotten 2", etc) A file must not exist in two subsets simultaneously. (Though it may be removed from one and then immediately added to another.)
4. We must be able to add a file to a specific subset.
5. We must be able to retrieve a file from a specific subset, if present, knowing that if retrieved it is also removed from both the subset and the overall set. (e.g. a Get which returns nil if not found, otherwise, removes and returns the item)
6. We must be able to retrieve all values from a specific subset, effectively emptying it.
7. The identifying type for a file should be consistent across all subsets. (e.g. always fingerprint.Fingerprint or an equivalent)
8. The value of a file in a subset must be generic enough to allow either *reader.Metadata (for closed files) or *reader.Reader (for open files).

[djaglowski]

To illustrate what I mean by the above, with a simplified management struct, I think we should end up with something like the following:

type Tracker struct {
    readingFiles FileSet
    openFiles FileSet
    closedFiles []FileSet
}

// When opening a new file to determine its contents and whether to read
func (t Tracker) readFile(path string) {

    // respect max_concurrent_files
    if len(r.readingFiles) + len(r.openFiles) >= t.maxConcurrentFiles {
        t.closeOne() // maybe need to also track order in which files were added to set
    }

    id, handle := readID(path string) 
    if id == nil { // don't bother with empty files
        handle.Close()
        return
    }
    
    // first check if we're already reading it
    if f := t.readingFiles(id); f != nil {
        handle.Close()
        t.readingFiles.Add(f) // readd, since it was removed by Get
        return 
    }

    // next best a file that's still open
    if f := t.openFiles(id); f != nil {
        handle.Close()
        t.readingFiles.Add(f)
        return true
    }

    // if we remember it, we can pick up from a checkpoint
    for i := 0; i < len(t.closedFiles[i]); i++ {
        if md := t.closedFiles[i]; md != nil {
            f := reader.NewFromMetadata(md, handle)
            t.readingFiles.Add(f)
            return
        }
    }

    // No memory of this file
    f := reader.New(id, handle)
    t.readingFiles.Add(f)
    return
}

// When we've read to the end of a file
func (t Tracker) doneReading(id FileID) {
    f := t.readingFiles.Get(f.ID)
    t.openFiles.Add(id, f)
}

// When we need to close a file
func (t Tracker) closeFile(id FileID) {
    f := t.openFiles.Get(f.ID)
    md := f.Close()
    t.closedFiles.Add(id, md)
}

// When we reach the end of a poll cycle
func (t Tracker) forgetOldest() {
    // drop oldest, shift each set, instantiate new at [0]
}

[VihasMakwana]

I like the simplicity here. Thanks for clarifying!
The requirements make a lot of sense and I was thinking of comparing the two approaches mentioned above. Does it sound good by you?

[VihasMakwana]

@djaglowski I compared both approaches.

1. TRIE

• TRIE is only useful if we have a read-heavy system and write less than reads.
• In our case, the read-to-write ratio is 1:1 approximately as we will update the trie after every poll and read it during the poll.
• The time complexity for writing all files in Trie is O(fingerprint_size * max_concurrent_files).
• For comparing from trie, we spend O(fingerprint_size) time on average.
• Also, we need to consider the overhead in individual functions. (for eg. setting value, comparing nodes)

2. Current approach

• We append all the readers, so O(max_concurrent_files).
• For comparing, worst case isO(fingerprint_size * max_concurrent_files).
  • Bear in mind, in most cases, we stop early if we find a match or if we encounter a mismatching byte.
  • So comparison can be fairly quick.

The results are almost identical considering normal cases. TRIE sometimes falls short, because the writing complexity is always O(fingerprint_size * max_concurrent_files).
Whereas, in the current approach we have the advantage of stopping early so it outperforms TRIE sometimes.
TRIE outperforms the current scenario for extreme cases such as, the fingerprint is smaller and there's a mismatch at the last byte.
For average cases, the current scenario seems to be doing well.

[djaglowski]

Thanks for the analysis @VihasMakwana

[github-actions]

Pinging code owners for receiver/filelog: @djaglowski. See Adding Labels via Comments if you do not have permissions to add labels yourself.

[github-actions]

This issue has been inactive for 60 days. It will be closed in 60 days if there is no activity. To ping code owners by adding a component label, see Adding Labels via Comments, or if you are unsure of which component this issue relates to, please ping @open-telemetry/collector-contrib-triagers. If this issue is still relevant, please ping the code owners or leave a comment explaining why it is still relevant. Otherwise, please close it.

Pinging code owners:

• receiver/filelog: @djaglowski
• pkg/stanza: @djaglowski

See Adding Labels via Comments if you do not have permissions to add labels yourself.

[djaglowski]

Closing based on #31317 (comment).

If anyone else wants to make a PR with another implementation, please feel free to ping me and I'll reopen the issue. Otherwise, this is unplanned.