Repository: nats-io/nats-server

Issue:
JetStream timestamp seek: make `GetSeqFromTime` O(log n) and fix nil-mid deletion edge case
### Observed behavior


### Summary
- Timestamp-based seeks used by JetStream consumers (e.g., `OptStartTime`) were slow due to linear scans:
  - Linear block selection across `fs.blks`.
  - Linear intra-block scan to find the first message with `ts >= t`.
- We prototyped an improvement that switches both steps to binary search, delivering large speedups (details below).
- While validating, we identified an edge case in the binary search when the probed mid sequence is deleted (nil). The current search may skip the true lower-bound when mid is nil and the correct answer lies to the left.

https://github.com/nats-io/nats-server/pull/7352



### Expected behavior

### Proposed fix for nil-mid in binary search
When `mid` is deleted (nil), avoid discarding half of the range blindly:
- Probe to the nearest extant message using store-level jumps:
  - Use `LoadNextMsg(_EMPTY_, false, mid, ...)` to jump forward to the next extant seq; ignore if beyond current block (`seq > lseq`).
  - If no forward extant exists, probe backward with `LoadPrevMsg(mid, ...)`; ignore if before the block (`seq < fseq`).
- Update bounds based on the extant message timestamp:
  - If forward extant exists and `ts >= targetTs`: set `result = seq`; `right = seq - 1`.
  - Else if forward extant exists and `ts < targetTs`: `left = seq + 1`.
  - Else if only backward extant exists: compare and update bounds similarly.
  - If neither exists within bounds, shrink toward the other side (segment has no extant messages).

This keeps common-case complexity ~O(log n), with occasional O(1) jumps for deleted mids.

### Compatibility
- No on-disk format changes.
- No API changes.
- Preserves lower-bound semantics: return first sequence with `ts >= target`.
- Existing consumer clamping and stream state logic remain unchanged.

### Additional notes
- The optimization helps filestore; memstore already has a more efficient time lookup.
- Follow-up (optional): consider an in-memory sparse timestamp index per block to reduce probe costs further for repeated seeks. This is not required for correctness and can be scoped separately.


### Server and client version
latest master

### Host environment

_No response_

### Steps to reproduce

_No response_

Discussion:

Solution patch:
diff --git a/server/filestore.go b/server/filestore.go
index 77499a6b..33e0737c 100644
--- a/server/filestore.go
+++ b/server/filestore.go
@@ -2560,7 +2560,6 @@ func copyMsgBlocks(src []*msgBlock) []*msgBlock {
 
 // GetSeqFromTime looks for the first sequence number that has
 // the message with >= timestamp.
-// FIXME(dlc) - inefficient, and dumb really. Make this better.
 func (fs *fileStore) GetSeqFromTime(t time.Time) uint64 {
 	fs.mu.RLock()
 	lastSeq := fs.state.LastSeq
@@ -2580,14 +2579,17 @@ func (fs *fileStore) GetSeqFromTime(t time.Time) uint64 {
 	lseq := atomic.LoadUint64(&mb.last.seq)
 
 	var smv StoreMsg
-
-	// Linear search, hence the dumb part..
 	ts := t.UnixNano()
-	for seq := fseq; seq <= lseq; seq++ {
-		sm, _, _ := mb.fetchMsgNoCopy(seq, &smv)
-		if sm != nil && sm.ts >= ts {
-			return sm.seq
-		}
+
+	// Because sort.Search expects range [0,off), we have to manually
+	// calculate the offset from the first sequence.
+	off := int(lseq - fseq + 1)
+	i := sort.Search(off, func(i int) bool {
+		sm, _, _ := mb.fetchMsgNoCopy(fseq+uint64(i), &smv)
+		return sm != nil && sm.ts >= ts
+	})
+	if i < off {
+		return fseq + uint64(i)
 	}
 	return 0
 }
@@ -6886,14 +6888,25 @@ func (fs *fileStore) selectMsgBlockForStart(minTime time.Time) *msgBlock {
 	fs.mu.RLock()
 	defer fs.mu.RUnlock()
 
-	t := minTime.UnixNano()
-	for _, mb := range fs.blks {
+	// Binary search for first block where last.ts >= t.
+	i, _ := slices.BinarySearchFunc(fs.blks, minTime.UnixNano(), func(mb *msgBlock, target int64) int {
 		mb.mu.RLock()
-		found := t <= mb.last.ts
+		last := mb.last.ts
 		mb.mu.RUnlock()
-		if found {
-			return mb
+		switch {
+		case last < target:
+			return -1
+		case last > target:
+			return 1
+		default:
+			return 0
 		}
+	})
+
+	// BinarySearchFunc returns an insertion point if not found.
+	// Either way, i is the index of the first mb where mb.last.ts >= t.
+	if i < len(fs.blks) {
+		return fs.blks[i]
 	}
 	return nil
 }



Test patch:
diff --git a/server/filestore_test.go b/server/filestore_test.go
index 5ae0881a..80b4ce5a 100644
--- a/server/filestore_test.go
+++ b/server/filestore_test.go
@@ -10534,3 +10534,55 @@ func TestFileStoreCorruptedNonOrderedSequences(t *testing.T) {
 		})
 	}
 }
+
+func BenchmarkFileStoreGetSeqFromTime(b *testing.B) {
+	fs, err := newFileStore(
+		FileStoreConfig{
+			StoreDir:  b.TempDir(),
+			BlockSize: 16,
+		},
+		StreamConfig{
+			Name:     "foo",
+			Subjects: []string{"foo.>"},
+			Storage:  FileStorage,
+		},
+	)
+	require_NoError(b, err)
+	defer fs.Stop()
+
+	for range 4096 {
+		_, _, err := fs.StoreMsg("foo.bar", nil, []byte{1, 2, 3, 4, 5}, 0)
+		require_NoError(b, err)
+	}
+
+	fs.mu.RLock()
+	fs.blks[0].mu.RLock()
+	fs.lmb.mu.RLock()
+	start := time.Unix(0, fs.blks[0].first.ts)
+	middle := time.Unix(0, fs.blks[0].first.ts+(fs.lmb.last.ts-fs.blks[0].first.ts)/2)
+	end := time.Unix(0, fs.lmb.last.ts)
+	fs.blks[0].mu.RUnlock()
+	fs.lmb.mu.RUnlock()
+	fs.mu.RUnlock()
+
+	b.Run("Start", func(b *testing.B) {
+		b.ReportAllocs()
+		for range b.N {
+			fs.GetSeqFromTime(start)
+		}
+	})
+
+	b.Run("Middle", func(b *testing.B) {
+		b.ReportAllocs()
+		for range b.N {
+			fs.GetSeqFromTime(middle)
+		}
+	})
+
+	b.Run("End", func(b *testing.B) {
+		b.ReportAllocs()
+		for range b.N {
+			fs.GetSeqFromTime(end)
+		}
+	})
+}