Skip to content

Commit 561428c

Browse files
Added block cache with pre-loading of the data in the background thread. (#1178)
* Added BackgroundBlockCache --------- Co-authored-by: Martin Durant <[email protected]>
1 parent 35da646 commit 561428c

3 files changed

Lines changed: 284 additions & 0 deletions

File tree

‎docs/source/api.rst‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -234,6 +234,7 @@ Read Buffering
234234
fsspec.caching.MMapCache
235235
fsspec.caching.ReadAheadCache
236236
fsspec.caching.FirstChunkCache
237+
fsspec.caching.BackgroundBlockCache
237238

238239
.. autoclass:: fsspec.caching.BlockCache
239240
:members:
@@ -250,6 +251,9 @@ Read Buffering
250251
.. autoclass:: fsspec.caching.FirstChunkCache
251252
:members:
252253

254+
.. autoclass:: fsspec.caching.BackgroundBlockCache
255+
:members:
256+
253257
Utilities
254258
---------
255259

‎fsspec/caching.py‎

Lines changed: 256 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,12 @@
1+
import collections
12
import functools
23
import io
34
import logging
45
import math
56
import os
7+
import threading
68
import warnings
9+
from concurrent.futures import ThreadPoolExecutor
710

811
logger = logging.getLogger("fsspec")
912

@@ -508,6 +511,258 @@ def _fetch(self, start, stop):
508511
return out + super()._fetch(start, stop)
509512

510513

514+
class UpdatableLRU:
515+
"""
516+
Custom implementation of LRU cache that allows updating keys
517+
518+
Used by BackgroudBlockCache
519+
"""
520+
521+
CacheInfo = collections.namedtuple(
522+
"CacheInfo", ["hits", "misses", "maxsize", "currsize"]
523+
)
524+
525+
def __init__(self, func, max_size=128):
526+
self._cache = collections.OrderedDict()
527+
self._func = func
528+
self._max_size = max_size
529+
self._hits = 0
530+
self._misses = 0
531+
self._lock = threading.Lock()
532+
533+
def __call__(self, *args):
534+
with self._lock:
535+
if args in self._cache:
536+
self._cache.move_to_end(args)
537+
self._hits += 1
538+
return self._cache[args]
539+
540+
result = self._func(*args)
541+
542+
with self._lock:
543+
self._cache[args] = result
544+
self._misses += 1
545+
if len(self._cache) > self._max_size:
546+
self._cache.popitem(last=False)
547+
548+
return result
549+
550+
def is_key_cached(self, *args):
551+
with self._lock:
552+
return args in self._cache
553+
554+
def add_key(self, result, *args):
555+
with self._lock:
556+
self._cache[args] = result
557+
if len(self._cache) > self._max_size:
558+
self._cache.popitem(last=False)
559+
560+
def cache_info(self):
561+
with self._lock:
562+
return self.CacheInfo(
563+
maxsize=self._max_size,
564+
currsize=len(self._cache),
565+
hits=self._hits,
566+
misses=self._misses,
567+
)
568+
569+
570+
class BackgroundBlockCache(BaseCache):
571+
"""
572+
Cache holding memory as a set of blocks with pre-loading of
573+
the next block in the background.
574+
575+
Requests are only ever made ``blocksize`` at a time, and are
576+
stored in an LRU cache. The least recently accessed block is
577+
discarded when more than ``maxblocks`` are stored. If the
578+
next block is not in cache, it is loaded in a separate thread
579+
in non-blocking way.
580+
581+
Parameters
582+
----------
583+
blocksize : int
584+
The number of bytes to store in each block.
585+
Requests are only ever made for ``blocksize``, so this
586+
should balance the overhead of making a request against
587+
the granularity of the blocks.
588+
fetcher : Callable
589+
size : int
590+
The total size of the file being cached.
591+
maxblocks : int
592+
The maximum number of blocks to cache for. The maximum memory
593+
use for this cache is then ``blocksize * maxblocks``.
594+
"""
595+
596+
name = "background"
597+
598+
def __init__(self, blocksize, fetcher, size, maxblocks=32):
599+
super().__init__(blocksize, fetcher, size)
600+
self.nblocks = math.ceil(size / blocksize)
601+
self.maxblocks = maxblocks
602+
self._fetch_block_cached = UpdatableLRU(self._fetch_block, maxblocks)
603+
604+
self._thread_executor = ThreadPoolExecutor(max_workers=1)
605+
self._fetch_future_block_number = None
606+
self._fetch_future = None
607+
self._fetch_future_lock = threading.Lock()
608+
609+
def __repr__(self):
610+
return "<BackgroundBlockCache blocksize={}, size={}, nblocks={}>".format(
611+
self.blocksize, self.size, self.nblocks
612+
)
613+
614+
def cache_info(self):
615+
"""
616+
The statistics on the block cache.
617+
618+
Returns
619+
-------
620+
NamedTuple
621+
Returned directly from the LRU Cache used internally.
622+
"""
623+
return self._fetch_block_cached.cache_info()
624+
625+
def __getstate__(self):
626+
state = self.__dict__
627+
del state["_fetch_block_cached"]
628+
del state["_thread_executor"]
629+
del state["_fetch_future_block_number"]
630+
del state["_fetch_future"]
631+
del state["_fetch_future_lock"]
632+
return state
633+
634+
def __setstate__(self, state):
635+
self.__dict__.update(state)
636+
self._fetch_block_cached = UpdatableLRU(self._fetch_block, state["maxblocks"])
637+
self._thread_executor = ThreadPoolExecutor(max_workers=1)
638+
self._fetch_future_block_number = None
639+
self._fetch_future = None
640+
self._fetch_future_lock = threading.Lock()
641+
642+
def _fetch(self, start, end):
643+
if start is None:
644+
start = 0
645+
if end is None:
646+
end = self.size
647+
if start >= self.size or start >= end:
648+
return b""
649+
650+
# byte position -> block numbers
651+
start_block_number = start // self.blocksize
652+
end_block_number = end // self.blocksize
653+
654+
fetch_future_block_number = None
655+
fetch_future = None
656+
with self._fetch_future_lock:
657+
# Background thread is running. Check we we can or must join it.
658+
if self._fetch_future is not None:
659+
if self._fetch_future.done():
660+
logger.info("BlockCache joined background fetch without waiting.")
661+
self._fetch_block_cached.add_key(
662+
self._fetch_future.result(), self._fetch_future_block_number
663+
)
664+
else:
665+
# Must join if we need the block for the current fetch
666+
must_join = bool(
667+
start_block_number
668+
<= self._fetch_future_block_number
669+
<= end_block_number
670+
)
671+
if must_join:
672+
# Copy to the local variables to release lock
673+
# before waiting for result
674+
fetch_future_block_number = self._fetch_future_block_number
675+
fetch_future = self._fetch_future
676+
677+
# Cleanup the fetch variables. Either done or have a local copy.
678+
self._fetch_future_block_number = None
679+
self._fetch_future = None
680+
681+
# Need to wait for the future for the current read
682+
if fetch_future is not None:
683+
logger.info("BlockCache waiting for background fetch.")
684+
# Wait until result and put it in cache
685+
self._fetch_block_cached.add_key(
686+
fetch_future.result(), fetch_future_block_number
687+
)
688+
689+
# these are cached, so safe to do multiple calls for the same start and end.
690+
for block_number in range(start_block_number, end_block_number + 1):
691+
self._fetch_block_cached(block_number)
692+
693+
# fetch next block in the background if nothing is running in the background,
694+
# the block is within file and it is not already cached
695+
end_block_plus_1 = end_block_number + 1
696+
with self._fetch_future_lock:
697+
if (
698+
self._fetch_future is None
699+
and end_block_plus_1 <= self.nblocks
700+
and not self._fetch_block_cached.is_key_cached(end_block_plus_1)
701+
):
702+
self._fetch_future_block_number = end_block_plus_1
703+
self._fetch_future = self._thread_executor.submit(
704+
self._fetch_block, end_block_plus_1, "async"
705+
)
706+
707+
return self._read_cache(
708+
start,
709+
end,
710+
start_block_number=start_block_number,
711+
end_block_number=end_block_number,
712+
)
713+
714+
def _fetch_block(self, block_number, log_info="sync"):
715+
"""
716+
Fetch the block of data for `block_number`.
717+
"""
718+
if block_number > self.nblocks:
719+
raise ValueError(
720+
"'block_number={}' is greater than the number of blocks ({})".format(
721+
block_number, self.nblocks
722+
)
723+
)
724+
725+
start = block_number * self.blocksize
726+
end = start + self.blocksize
727+
logger.info("BlockCache fetching block (%s) %d", log_info, block_number)
728+
block_contents = super()._fetch(start, end)
729+
return block_contents
730+
731+
def _read_cache(self, start, end, start_block_number, end_block_number):
732+
"""
733+
Read from our block cache.
734+
735+
Parameters
736+
----------
737+
start, end : int
738+
The start and end byte positions.
739+
start_block_number, end_block_number : int
740+
The start and end block numbers.
741+
"""
742+
start_pos = start % self.blocksize
743+
end_pos = end % self.blocksize
744+
745+
if start_block_number == end_block_number:
746+
block = self._fetch_block_cached(start_block_number)
747+
return block[start_pos:end_pos]
748+
749+
else:
750+
# read from the initial
751+
out = []
752+
out.append(self._fetch_block_cached(start_block_number)[start_pos:])
753+
754+
# intermediate blocks
755+
# Note: it'd be nice to combine these into one big request. However
756+
# that doesn't play nicely with our LRU cache.
757+
for block_number in range(start_block_number + 1, end_block_number):
758+
out.append(self._fetch_block_cached(block_number))
759+
760+
# final block
761+
out.append(self._fetch_block_cached(end_block_number)[:end_pos])
762+
763+
return b"".join(out)
764+
765+
511766
caches = {
512767
"none": BaseCache,
513768
None: BaseCache,
@@ -518,4 +773,5 @@ def _fetch(self, start, stop):
518773
"first": FirstChunkCache,
519774
"all": AllBytes,
520775
"parts": KnownPartsOfAFile,
776+
"background": BackgroundBlockCache,
521777
}

‎fsspec/tests/test_caches.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -114,3 +114,27 @@ def test_known(sort, strict):
114114
else:
115115
# Over-read will be zero-padded
116116
assert c._fetch(25, 35) == b"2" * 5 + b"\x00" * 5
117+
118+
119+
def test_background(server, monkeypatch):
120+
import threading
121+
import time
122+
123+
import fsspec
124+
125+
head = {"head_ok": "true", "head_give_length": "true"}
126+
urla = server + "/index/realfile"
127+
h = fsspec.filesystem("http", headers=head)
128+
thread_ids = {threading.current_thread().ident}
129+
f = h.open(urla, block_size=5, cache_type="background")
130+
orig = f.cache._fetch_block
131+
132+
def wrapped(*a, **kw):
133+
thread_ids.add(threading.current_thread().ident)
134+
return orig(*a, **kw)
135+
136+
f.cache._fetch_block = wrapped
137+
assert len(thread_ids) == 1
138+
f.read(1)
139+
time.sleep(0.1) # second block is loading
140+
assert len(thread_ids) == 2

0 commit comments

Comments
 (0)