Make messages with identical timestamps sortable by ULID #6711
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
/rebase |
github-actions
bot
force-pushed
the
ulid-sorted-messages
branch
from
27d71fd
to
6d52c07
Compare
mpfz0r
force-pushed
the
ulid-sorted-messages
branch
from
6d52c07
to
ae39533
Compare
bernd
previously requested changes
Dec 13, 2019
graylog2-server/src/main/java/org/graylog2/shared/buffers/processors/MessageULIDGenerator.java
Outdated
Show resolved
Hide resolved
graylog2-server/src/main/java/org/graylog2/shared/buffers/processors/MessageULIDGenerator.java
Outdated
Show resolved
Hide resolved
graylog2-server/src/main/resources/org/graylog2/plugin/journal/raw_message.proto
Show resolved
Hide resolved
graylog2-server/src/main/resources/org/graylog2/plugin/journal/raw_message.proto
Show resolved
Hide resolved
graylog2-server/src/main/java/org/graylog2/shared/buffers/processors/MessageULIDGenerator.java
Outdated
Show resolved
Hide resolved
graylog2-server/src/main/java/org/graylog2/plugin/inputs/MessageInput.java
Outdated
Show resolved
Hide resolved
mpfz0r
commented
Dec 30, 2019
|
Checking for an existing "gl2_message_id" and using the message timestamp is done in #7290. |
mpfz0r
force-pushed
the
ulid-sorted-messages
branch
from
7b3e148
to
751dec0
Compare
|
@mpfz0r Does this implementation still work when a non-local message journal implementation (e.g., Kafka) is used? This just crossed my mind. |
It does. I had the same thought at first, but only my first iteration depended on the journal 😅 |
patrickmann
reviewed
Nov 7, 2022
graylog2-server/src/main/java/org/graylog2/shared/buffers/processors/MessageULIDGenerator.java
Outdated
Show resolved
Hide resolved
patrickmann
approved these changes
Nov 7, 2022
The ULID format is composed of a 48 bit timestamp followed by 80 bits of randomness. Use the first 16 bits of the random field to embed a sequence number for each message. If a batch of messages was received with identical timestamps (the same millisecond), the original receive order is kept by the encoded sequence number which directly follows the timestamp.
Introduce a seqence number on each input which gets incremented and embedded in every received message. This allows sorting to work without depending on a KafkaJournal. Regenerate the protobuf class JournalMessages so it can pass the sequence number from a RawMessage to a Message. Don't overwrite already existing GL2_MESSAGE_IDs. They might already be set if we are receiving messages from a Graylog forwarder.
Every message should have a gl2_message_id now
This enables us to sort by gl2_message_id, even if the field does not exist. This might be the case with older indices, restored from archives.
This test should not be using the default index template
Multiple forwarders can run the same input, that's why we need to differentiate them in the cache.
This allows us to sort on older indices that might not have that field yet. https://www.elastic.co/guide/en/elasticsearch/reference/7.17/sort-search-results.html#_ignoring_unmapped_fields
thll
requested changes
Nov 29, 2022
graylog2-server/src/main/java/org/graylog2/shared/buffers/processors/MessageULIDGenerator.java
Outdated
Show resolved
Hide resolved
...ensearch2/src/main/java/org/graylog/storage/opensearch2/views/searchtypes/OSMessageList.java
Outdated
Show resolved
Hide resolved
Also add some tests
This is simpler and probably leads to less log messages.
thll
approved these changes
Nov 30, 2022
bernd
pushed a commit
that referenced
this pull request
Dec 9, 2022
* Make messages with identical timestamps sortable by ULID The ULID format is composed of a 48 bit timestamp followed by 80 bits of randomness. Use the first 16 bits of the random field to embed a sequence number for each message. If a batch of messages was received with identical timestamps (the same millisecond), the original receive order is kept by the encoded sequence number which directly follows the timestamp. * Add license * Use a MessageInput sequenceNr instead of journalOffset Introduce a seqence number on each input which gets incremented and embedded in every received message. This allows sorting to work without depending on a KafkaJournal. Regenerate the protobuf class JournalMessages so it can pass the sequence number from a RawMessage to a Message. Don't overwrite already existing GL2_MESSAGE_IDs. They might already be set if we are receiving messages from a Graylog forwarder. * final some variables * Fix review comments * Use protoc 2.5.0 instead of 3.0.0 * Handle sequenceNr wrap and exceptions * update license * better log messages; bump offset gap * increase cache size * Cleanup and fix test * Fix some comments and add changelog * Bump OFFSET_GAP to 5000 and rename a few constants With an OFFSET_GAP of 5000, I couldn't reproduce negative sequence numbers anymore. It's a tradeoff, but ordering only 60535 messages for the same timestamp is reasonable. * improve java doc * Always add gl2_message_id as a second sort order, if sorting by timestamp is requested. * Don't assume that sort list is mutable * Fix BackendStartupIT test Every message should have a gl2_message_id now * Clarify when gl2_message_id might not be empty * Add a index mapping for gl2_message_id This enables us to sort by gl2_message_id, even if the field does not exist. This might be the case with older indices, restored from archives. * Fix IndexMappingTest * fix FieldTypePollerIT * Fix FieldAliasForEvents IT This test should not be using the default index template * Handle Messages with sequenceNr that are received from Forwarders * Include the nodeId into the sequenceNr lookup cache Multiple forwarders can run the same input, that's why we need to differentiate them in the cache. * Provide unmapped_type for gl2_message_id sort This allows us to sort on older indices that might not have that field yet. https://www.elastic.co/guide/en/elasticsearch/reference/7.17/sort-search-results.html#_ignoring_unmapped_fields * Only add gl2_message_id sort if not already present Also add some tests * Simply reset the sequenceNrCache in case we exceed the ULID limit This is simpler and probably leads to less log messages. * Improve log message
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The ULID format in the
gl2_message_idfield is composed of a 48 bit timestamp followed by 80 bitsof randomness.
Use the first 16 bits of the random field to embed a sequence number
for each message.
If a batch of messages was received with identical timestamps
(the same millisecond), the original receive order is kept by the
encoded sequence number which directly follows the timestamp.
This allows us to sort messages by
gl2_message_idwhich should have the correct originalorder in most cases.
CAVEATS
This is a best effort approach to a complicated problem. It's not a silver bullet.
Here are reasons why the
gl2_message_idsort order might not always be correct:The sequence number is generated per node and input.
This means that sorting will not work if an input is load balanced over multiple nodes.
There is only space for
60535messages with the same timestamp and input.Also, there is a small chance that, if too many batches of messages with the same timestamp and input get processed
in parallel, the sort order might be wrong.
Performance Impact
Running a benchmark, which ingests 8 million messages.
Four parallel curl loops send batches of
5000messages with identical timestamps.Without this change, this takes
3m 19sWith this change:
3m 25sWhich means approx 40k msg/sec and no measurable performance impact.
Fixes #2741