Skip to content

Commit a1c3d57

Browse files
ManMansonpitrou
andauthored
ARROW-17306: [C++] Provide an optimized GetFileInfoGenerator specialization for LocalFileSystem (#13796)
Introduce a specialization of `GetFileInfoGenerator` in the `LocalFileSystem` class. This implementation tries to improves performance by hiding latencies at two levels: 1. Child directories can be readahead so that listing directories entries from disk can be achieved in parallel with other work; 2. Directory entries can be `stat`'ed and yielded in chunks so that the `FileInfoGenerator` consumer can start receiving entries before a large directory is fully processed. Both mechanisms can be tuned using dedicated parameters in `LocalFileSystemOptions`. Signed-off-by: Pavel Solodovnikov <[email protected]> Co-Authored-by: Igor Seliverstov <[email protected]> Lead-authored-by: Pavel Solodovnikov <[email protected]> Co-authored-by: Antoine Pitrou <[email protected]> Signed-off-by: Antoine Pitrou <[email protected]>
1 parent bc52f9f commit a1c3d57

6 files changed

Lines changed: 499 additions & 3 deletions

File tree

‎cpp/src/arrow/filesystem/CMakeLists.txt‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,16 @@ add_arrow_test(filesystem-test
2828
EXTRA_LABELS
2929
filesystem)
3030

31+
if(ARROW_BUILD_BENCHMARKS)
32+
add_arrow_benchmark(localfs_benchmark
33+
PREFIX
34+
"arrow-filesystem"
35+
SOURCES
36+
localfs_benchmark.cc
37+
STATIC_LINK_LIBS
38+
${ARROW_BENCHMARK_LINK_LIBS})
39+
endif()
40+
3141
if(ARROW_GCS)
3242
add_arrow_test(gcsfs_test
3343
EXTRA_LABELS

‎cpp/src/arrow/filesystem/localfs.cc‎

Lines changed: 242 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717

1818
#include <chrono>
1919
#include <cstring>
20+
#include <memory>
2021
#include <sstream>
2122
#include <utility>
2223

@@ -29,12 +30,15 @@
2930
#include <sys/stat.h>
3031
#endif
3132

33+
#include "arrow/filesystem/filesystem.h"
3234
#include "arrow/filesystem/localfs.h"
3335
#include "arrow/filesystem/path_util.h"
36+
#include "arrow/filesystem/type_fwd.h"
3437
#include "arrow/filesystem/util_internal.h"
3538
#include "arrow/io/file.h"
39+
#include "arrow/io/type_fwd.h"
40+
#include "arrow/util/async_generator.h"
3641
#include "arrow/util/io_util.h"
37-
#include "arrow/util/logging.h"
3842
#include "arrow/util/uri.h"
3943
#include "arrow/util/windows_fixup.h"
4044

@@ -243,7 +247,8 @@ LocalFileSystemOptions LocalFileSystemOptions::Defaults() {
243247
}
244248

245249
bool LocalFileSystemOptions::Equals(const LocalFileSystemOptions& other) const {
246-
return use_mmap == other.use_mmap;
250+
return use_mmap == other.use_mmap && directory_readahead == other.directory_readahead &&
251+
file_info_batch_size == other.file_info_batch_size;
247252
}
248253

249254
Result<LocalFileSystemOptions> LocalFileSystemOptions::FromUri(
@@ -309,6 +314,241 @@ Result<std::vector<FileInfo>> LocalFileSystem::GetFileInfo(const FileSelector& s
309314
return results;
310315
}
311316

317+
namespace {
318+
319+
/// Workhorse for streaming async implementation of `GetFileInfo`
320+
/// (`GetFileInfoGenerator`).
321+
///
322+
/// There are two variants of async discovery functions suported:
323+
/// 1. `DiscoverDirectoryFiles`, which parallelizes traversal of individual directories
324+
/// so that each directory results are yielded as a separate `FileInfoGenerator` via
325+
/// an underlying `DiscoveryImplIterator`, which delivers items in chunks (default size
326+
/// is 1K items).
327+
/// 2. `DiscoverDirectoriesFlattened`, which forwards execution to the
328+
/// `DiscoverDirectoryFiles`, with the difference that the results from individual
329+
/// sub-directory iterators are merged into the single FileInfoGenerator stream.
330+
///
331+
/// The implementation makes use of additional attributes in `LocalFileSystemOptions`,
332+
/// such as `directory_readahead`, which can be used to tune algorithm
333+
/// behavior and adjust how many directories can be processed in parallel.
334+
/// This option is disabled by default, so that individual directories are processed
335+
/// in serial manner via `MakeConcatenatedGenerator` under the hood.
336+
class AsyncStatSelector {
337+
public:
338+
using FileInfoGeneratorProducer = PushGenerator<FileInfoGenerator>::Producer;
339+
340+
/// Discovery state, which is shared among all `DiscoveryImplGenerator`:s,
341+
/// spawned by a single discovery operation (`DiscoverDirectoryFiles()`).
342+
///
343+
/// The sole purpose of this struct is to handle automatic closing the
344+
/// producer side of the resulting `FileInfoGenerator`. I.e. the producer
345+
/// is kept alive until all discovery iterators are exhausted, in which case
346+
/// `producer.Close()` is called automatically when ref-count for the state
347+
/// reaches zero (which is equivalent to finishing the file discovery
348+
/// process).
349+
struct DiscoveryState {
350+
FileInfoGeneratorProducer producer;
351+
352+
explicit DiscoveryState(FileInfoGeneratorProducer p) : producer(std::move(p)) {}
353+
~DiscoveryState() { producer.Close(); }
354+
};
355+
356+
/// The main procedure to start async streaming discovery using a given `FileSelector`.
357+
///
358+
/// The result is a two-level generator, i.e. "generator of FileInfoGenerator:s",
359+
/// where each individual generator represents an FileInfo item stream from coming an
360+
/// individual sub-directory under the selector's `base_dir`.
361+
static Result<AsyncGenerator<FileInfoGenerator>> DiscoverDirectoryFiles(
362+
FileSelector selector, LocalFileSystemOptions fs_opts,
363+
const io::IOContext& io_context) {
364+
PushGenerator<FileInfoGenerator> file_gen;
365+
366+
ARROW_ASSIGN_OR_RAISE(
367+
auto base_dir, arrow::internal::PlatformFilename::FromString(selector.base_dir));
368+
ARROW_RETURN_NOT_OK(DoDiscovery(std::move(base_dir), 0, std::move(selector),
369+
std::make_shared<DiscoveryState>(file_gen.producer()),
370+
io_context, fs_opts.file_info_batch_size));
371+
372+
return file_gen;
373+
}
374+
375+
/// Version of `DiscoverDirectoryFiles` which flattens the stream of generators
376+
/// into a single FileInfoGenerator stream.
377+
/// Makes use of `LocalFileSystemOptions::directory_readahead` to determine how much
378+
/// readahead should happen.
379+
static arrow::Result<FileInfoGenerator> DiscoverDirectoriesFlattened(
380+
FileSelector selector, LocalFileSystemOptions fs_opts,
381+
const io::IOContext& io_context) {
382+
int32_t dir_readahead = fs_opts.directory_readahead;
383+
ARROW_ASSIGN_OR_RAISE(
384+
auto part_gen,
385+
DiscoverDirectoryFiles(std::move(selector), std::move(fs_opts), io_context));
386+
return dir_readahead > 1
387+
? MakeSequencedMergedGenerator(std::move(part_gen), dir_readahead)
388+
: MakeConcatenatedGenerator(std::move(part_gen));
389+
}
390+
391+
private:
392+
/// The class, which implements iterator interface to traverse a given
393+
/// directory at the fixed nesting depth, and possibly recurses into
394+
/// sub-directories (if specified by the selector), spawning more
395+
/// `DiscoveryImplIterators`, which feed their data into a single producer.
396+
class DiscoveryImplIterator {
397+
const PlatformFilename dir_fn_;
398+
const int32_t nesting_depth_;
399+
const FileSelector selector_;
400+
const uint32_t file_info_batch_size_;
401+
402+
const io::IOContext& io_context_;
403+
std::shared_ptr<DiscoveryState> discovery_state_;
404+
FileInfoVector current_chunk_;
405+
std::vector<PlatformFilename> child_fns_;
406+
size_t idx_ = 0;
407+
bool initialized_ = false;
408+
409+
public:
410+
DiscoveryImplIterator(PlatformFilename dir_fn, int32_t nesting_depth,
411+
FileSelector selector,
412+
std::shared_ptr<DiscoveryState> discovery_state,
413+
const io::IOContext& io_context, uint32_t file_info_batch_size)
414+
: dir_fn_(std::move(dir_fn)),
415+
nesting_depth_(nesting_depth),
416+
selector_(std::move(selector)),
417+
file_info_batch_size_(file_info_batch_size),
418+
io_context_(io_context),
419+
discovery_state_(std::move(discovery_state)) {}
420+
421+
/// Pre-initialize the iterator by listing directory contents and caching
422+
/// in the current instance.
423+
Status Initialize() {
424+
auto result = arrow::internal::ListDir(dir_fn_);
425+
if (!result.ok()) {
426+
auto status = result.status();
427+
if (selector_.allow_not_found && status.IsIOError()) {
428+
ARROW_ASSIGN_OR_RAISE(bool exists, FileExists(dir_fn_));
429+
if (!exists) {
430+
return Status::OK();
431+
}
432+
}
433+
return status;
434+
}
435+
child_fns_ = result.MoveValueUnsafe();
436+
437+
const size_t dirent_count = child_fns_.size();
438+
current_chunk_.reserve(dirent_count >= file_info_batch_size_ ? file_info_batch_size_
439+
: dirent_count);
440+
441+
initialized_ = true;
442+
return Status::OK();
443+
}
444+
445+
Result<FileInfoVector> Next() {
446+
if (!initialized_) {
447+
auto init = Initialize();
448+
if (!init.ok()) {
449+
return Finish(init);
450+
}
451+
}
452+
while (idx_ < child_fns_.size()) {
453+
auto full_fn = dir_fn_.Join(child_fns_[idx_++]);
454+
auto res = StatFile(full_fn.ToNative());
455+
if (!res.ok()) {
456+
return Finish(res.status());
457+
}
458+
459+
auto info = res.MoveValueUnsafe();
460+
461+
// Try to recurse into subdirectories, if needed.
462+
if (info.type() == FileType::Directory &&
463+
nesting_depth_ < selector_.max_recursion && selector_.recursive) {
464+
auto status = DoDiscovery(std::move(full_fn), nesting_depth_ + 1, selector_,
465+
discovery_state_, io_context_, file_info_batch_size_);
466+
if (!status.ok()) {
467+
return Finish(status);
468+
}
469+
}
470+
// Everything is ok. Add the item to the current chunk of data.
471+
current_chunk_.emplace_back(std::move(info));
472+
// Keep `current_chunk_` as large, as `batch_size_`.
473+
// Otherwise, yield the complete chunk to the caller.
474+
if (current_chunk_.size() == file_info_batch_size_) {
475+
FileInfoVector yield_vec = std::move(current_chunk_);
476+
const size_t items_left = child_fns_.size() - idx_;
477+
current_chunk_.reserve(
478+
items_left >= file_info_batch_size_ ? file_info_batch_size_ : items_left);
479+
return yield_vec;
480+
}
481+
} // while (idx_ < child_fns_.size())
482+
483+
// Flush out remaining items
484+
if (!current_chunk_.empty()) {
485+
return std::move(current_chunk_);
486+
}
487+
return Finish();
488+
}
489+
490+
private:
491+
/// Release reference to shared discovery state and return iteration end
492+
/// marker to indicate that this iterator is exhausted.
493+
Result<FileInfoVector> Finish(Status status = Status::OK()) {
494+
discovery_state_.reset();
495+
ARROW_RETURN_NOT_OK(status);
496+
return IterationEnd<FileInfoVector>();
497+
}
498+
};
499+
500+
/// Create an instance of `DiscoveryImplIterator` under the hood for the
501+
/// specified directory, wrap it in the `BackgroundGenerator` and feed
502+
/// the results to the main producer queue.
503+
///
504+
/// Each `DiscoveryImplIterator` maintains a reference to `DiscoveryState`,
505+
/// which simply wraps the producer to keep it alive for the lifetime
506+
/// of this iterator. When all references to `DiscoveryState` are invalidated,
507+
/// the producer is closed automatically.
508+
static Status DoDiscovery(const PlatformFilename& dir_fn, int32_t nesting_depth,
509+
FileSelector selector,
510+
std::shared_ptr<DiscoveryState> discovery_state,
511+
const io::IOContext& io_context,
512+
int32_t file_info_batch_size) {
513+
ARROW_RETURN_IF(discovery_state->producer.is_closed(),
514+
arrow::Status::Cancelled("Discovery cancelled"));
515+
516+
// Note, that here we use `MakeTransferredGenerator()` with the same
517+
// target executor (io executor) as the current iterator is running on.
518+
//
519+
// This is done on purpose, since typically the user of
520+
// `GetFileInfoGenerator()` would want to perform some more IO on the
521+
// produced results (e.g. read the files, examine metadata etc.).
522+
// So, it is preferable to execute the attached continuations on the same
523+
// executor, which belongs to the IO thread pool.
524+
ARROW_ASSIGN_OR_RAISE(
525+
auto gen,
526+
MakeBackgroundGenerator(Iterator<FileInfoVector>(DiscoveryImplIterator(
527+
std::move(dir_fn), nesting_depth, std::move(selector),
528+
discovery_state, io_context, file_info_batch_size)),
529+
io_context.executor()));
530+
gen = MakeTransferredGenerator(std::move(gen), io_context.executor());
531+
ARROW_RETURN_IF(!discovery_state->producer.Push(std::move(gen)),
532+
arrow::Status::Cancelled("Discovery cancelled"));
533+
return arrow::Status::OK();
534+
}
535+
};
536+
537+
} // anonymous namespace
538+
539+
FileInfoGenerator LocalFileSystem::GetFileInfoGenerator(const FileSelector& select) {
540+
auto path_status = ValidatePath(select.base_dir);
541+
if (!path_status.ok()) {
542+
return MakeFailingGenerator<FileInfoVector>(path_status);
543+
}
544+
auto fileinfo_gen =
545+
AsyncStatSelector::DiscoverDirectoriesFlattened(select, options(), io_context_);
546+
if (!fileinfo_gen.ok()) {
547+
return MakeFailingGenerator<FileInfoVector>(fileinfo_gen.status());
548+
}
549+
return fileinfo_gen.MoveValueUnsafe();
550+
}
551+
312552
Status LocalFileSystem::CreateDir(const std::string& path, bool recursive) {
313553
RETURN_NOT_OK(ValidatePath(path));
314554
ARROW_ASSIGN_OR_RAISE(auto fn, PlatformFilename::FromString(path));

‎cpp/src/arrow/filesystem/localfs.h‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,10 +34,29 @@ namespace fs {
3434

3535
/// Options for the LocalFileSystem implementation.
3636
struct ARROW_EXPORT LocalFileSystemOptions {
37+
static constexpr int32_t kDefaultDirectoryReadahead = 16;
38+
static constexpr int32_t kDefaultFileInfoBatchSize = 1000;
39+
3740
/// Whether OpenInputStream and OpenInputFile return a mmap'ed file,
3841
/// or a regular one.
3942
bool use_mmap = false;
4043

44+
/// Options related to `GetFileInfoGenerator` interface.
45+
46+
/// EXPERIMENTAL: The maximum number of directories processed in parallel
47+
/// by `GetFileInfoGenerator`.
48+
int32_t directory_readahead = kDefaultDirectoryReadahead;
49+
50+
/// EXPERIMENTAL: The maximum number of entries aggregated into each
51+
/// FileInfoVector chunk by `GetFileInfoGenerator`.
52+
///
53+
/// Since each FileInfo entry needs a separate `stat` system call, a
54+
/// directory with a very large number of files may take a lot of time to
55+
/// process entirely. By generating a FileInfoVector after this chunk
56+
/// size is reached, we ensure FileInfo entries can start being consumed
57+
/// from the FileInfoGenerator with less initial latency.
58+
int32_t file_info_batch_size = kDefaultFileInfoBatchSize;
59+
4160
/// \brief Initialize with defaults
4261
static LocalFileSystemOptions Defaults();
4362

@@ -73,6 +92,7 @@ class ARROW_EXPORT LocalFileSystem : public FileSystem {
7392
/// \endcond
7493
Result<FileInfo> GetFileInfo(const std::string& path) override;
7594
Result<std::vector<FileInfo>> GetFileInfo(const FileSelector& select) override;
95+
FileInfoGenerator GetFileInfoGenerator(const FileSelector& select) override;
7696

7797
Status CreateDir(const std::string& path, bool recursive = true) override;
7898

0 commit comments

Comments
 (0)