Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Allow overriding LogIdList::load_log_ids by providing the information directly from the state machine or log reader #1261

Closed
schreter opened this issue Oct 31, 2024 · 5 comments · Fixed by #1264
Closed

Allow overriding LogIdList::load_log_ids by providing the information directly from the state machine or log reader #1261

schreter opened this issue Oct 31, 2024 · 5 comments · Fixed by #1264
Assignees
@drmingdrmer

Comments

@schreter
Copy link
Collaborator

Currently, when openraft starts, it scans the entire log with random accesses to find key log IDs where the leader changed. However, this information may be already available in other state machine metadata (as it is in our case), so it can be provided to openraft by the state machine implementation, greatly reducing the effort finding key log IDs.

My suggestion is to add a trait method to provide key log IDs and default-implement it with the current search algorithm. If the implementation of the state machine has a better way to provide key log IDs, then it can override the method and provide them directly.
@github-actions GitHub Actions
Copy link

👋 Thanks for opening this issue!

Get help or engage by:

  • /help : to print help messages.
  • /assignme : to assign this issue to you.

@drmingdrmer
Copy link
Member

Why is such key-log-id metadata stored in state machine? shouldn't be part of the Raft log?

Does your state machine provide the complete key-log-id or just the applied log-ids? If there are some logs that are not in state machine, Openraft still needs several other rounds of RaftLogStorage access to locate these key log ids.

@schreter
Copy link
Collaborator Author

schreter commented Nov 5, 2024

Why is such key-log-id metadata stored in state machine? shouldn't be part of the Raft log?

For us, the state machine includes log storage. So the two openraft interfaces are effectively backed by the same implementation. But yes, logically, it's part of the log.

Does your state machine provide the complete key-log-id or just the applied log-ids?

All log IDs which were logged, also not applied. Key log IDs are part of log segment management (and stored in log segment metadata). So we can quickly reconstruct the entire set of key log IDs (leader changes) from this metadata w/o loading the log proper.

@drmingdrmer
Copy link
Member

For us, the state machine includes log storage. So the two openraft interfaces are effectively backed by the same implementation. But yes, logically, it's part of the log.

So, it could be another RaftLogStorage API to return all of the key log id.

@schreter
Copy link
Collaborator Author

schreter commented Nov 5, 2024

So, it could be another RaftLogStorage API to return all of the key log id.

Yes. Sorry for the confusion.

@drmingdrmer drmingdrmer self-assigned this Nov 8, 2024
drmingdrmer added a commit to drmingdrmer/openraft that referenced this issue Nov 8, 2024
@drmingdrmer
Feature: Retrieve Key Log IDs via RaftLogReader::get_key_log_ids()
c593b8e 
Key log IDs represent the first log IDs proposed by each Leader. These
IDs enable Openraft to efficiently access log IDs at each index with
a succinct storage.

Previously, key log IDs were obtained using a binary-search-like
algorithm through `RaftLogReader`. This commit introduces the
`RaftLogReader::get_key_log_ids()` method, allowing implementations to
directly return a list of key log IDs if the `RaftLogStorage` can
provide them.

For backward compatibility, a default implementation using the original
binary-search method is provided. No application changes are required
when upgrading to this version.

Tests verifying the implementation are included in
`openraft::testing::log::suite::Suite`.

- Fixes: databendlabs#1261
@drmingdrmer drmingdrmer mentioned this issue Nov 8, 2024
Merged
drmingdrmer added a commit to drmingdrmer/openraft that referenced this issue Nov 8, 2024
@drmingdrmer
Feature: Retrieve Key Log IDs via RaftLogReader::get_key_log_ids()
57930ea 
Key log IDs represent the first log IDs proposed by each Leader. These
IDs enable Openraft to efficiently access log IDs at each index with
a succinct storage.

Previously, key log IDs were obtained using a binary-search-like
algorithm through `RaftLogReader`. This commit introduces the
`RaftLogReader::get_key_log_ids()` method, allowing implementations to
directly return a list of key log IDs if the `RaftLogStorage` can
provide them.

For backward compatibility, a default implementation using the original
binary-search method is provided. No application changes are required
when upgrading to this version.

Tests verifying the implementation are included in
`openraft::testing::log::suite::Suite`.

- Fixes: databendlabs#1261
drmingdrmer added a commit to drmingdrmer/openraft that referenced this issue Nov 8, 2024
@drmingdrmer
Feature: Retrieve Key Log IDs via RaftLogReader::get_key_log_ids()
f778ec6 
Key log IDs represent the first log IDs proposed by each Leader. These
IDs enable Openraft to efficiently access log IDs at each index with
a succinct storage.

Previously, key log IDs were obtained using a binary-search-like
algorithm through `RaftLogReader`. This commit introduces the
`RaftLogReader::get_key_log_ids()` method, allowing implementations to
directly return a list of key log IDs if the `RaftLogStorage` can
provide them.

For backward compatibility, a default implementation using the original
binary-search method is provided. No application changes are required
when upgrading to this version.

Tests verifying the implementation are included in
`openraft::testing::log::suite::Suite`.

- Fixes: databendlabs#1261
drmingdrmer added a commit to drmingdrmer/openraft that referenced this issue Nov 8, 2024
@drmingdrmer
Feature: Retrieve Key Log IDs via RaftLogReader::get_key_log_ids()
2e02fc1 
Key log IDs represent the first log IDs proposed by each Leader. These
IDs enable Openraft to efficiently access log IDs at each index with
a succinct storage.

Previously, key log IDs were obtained using a binary-search-like
algorithm through `RaftLogReader`. This commit introduces the
`RaftLogReader::get_key_log_ids()` method, allowing implementations to
directly return a list of key log IDs if the `RaftLogStorage` can
provide them.

For backward compatibility, a default implementation using the original
binary-search method is provided. No application changes are required
when upgrading to this version.

Tests verifying the implementation are included in
`openraft::testing::log::suite::Suite`.

- Fixes: databendlabs#1261
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@drmingdrmer drmingdrmer

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Feature: Retrieve Key Log IDs via RaftLogReader::get_key_log_ids() drmingdrmer/openraft
2 participants
@drmingdrmer @schreter