Appendix G

List of Algorithms

14 min read

This appendix lists all 188 “Algorithm” boxes of the book in chapter order. Each box comes with an explanation, pseudocode, complexity, a worked numeric example and at least one figure. The “Source” column names the file and function the algorithm was extracted from and checked against. The page column links to the box itself.

#	Algorithm	Source in code	Chapter
1	Probability of losing a PG when three OSDs fail at the same time	`Exact computation on the CRUSH mapping with osdmaptool; default mon_target_pg_per_osd = 200 from src/common/options/mgr.yaml.in`	1
2	Time to restore redundancy, bottlenecked by the busiest target	`Mapping before and after osdmaptool --mark-out 0; real limits: osd_max_backfills, the mClock profile (chapter 21) and the network`	1
3	Building an image id and the names of its objects (format 2)	`src/librbd/Utils.cc :: generate_image_id; src/include/rbd_types.h (prefixes); src/cls/rbd/cls_rbd.cc :: dir_add_image`	2
4	Pruning a discard and choosing its operation	`src/librbd/io/ImageRequest.cc :: ImageDiscardRequest::prune_object_extents; src/librbd/io/ObjectRequest.h :: ObjectDiscardRequest; src/librbd/ImageCtx.cc (skip_partial_discard)`	2
5	Counting the space used in rbd du	`src/tools/rbd/action/DiskUsage.cc :: get_image_disk_usage (diff_iterate2 with whole_object = !exact); src/librbd/api/DiffIterate.cc`	2
6	Mapping an image range to RADOS objects (striping)	`src/osdc/Striper.cc :: Striper::file_to_extents; src/librbd/ImageCtx.cc :: ImageCtx::init_layout`	3
7	Size and states of the object map	`src/include/rbd/object_map_types.h; src/librbd/ObjectMap.cc :: ObjectMap::is_compatible; src/cls/rbd/cls_rbd_types.h :: MAX_OBJECT_MAP_OBJECT_COUNT; src/librbd/io/ObjectRequest.cc :: AbstractObjectWriteRequest; src/librbd/object_map/SnapshotCreateRequest.cc :: update_object_map`	3
8	Computing a diff from object maps	`src/librbd/object_map/DiffRequest.cc :: DiffRequest::handle_load_object_map`	3
9	The TokenBucketThrottle token bucket for rbd_qos_*	`src/common/Throttle.cc :: TokenBucketThrottle::set_limit, tokens_this_tick, add_tokens, Bucket::put, Bucket::get; src/librbd/io/QosImageDispatch.cc`	3
10	Mapping an object key to a bucket index shard	`src/rgw/services/svc_bi_rados.h :: RGWSI_BucketIndex_RADOS::bucket_shard_index; src/rgw/driver/rados/rgw_tools.h :: rgw_shards_mod; src/common/ceph_hash.cc :: ceph_str_hash_linux`	4
11	Computing the preferred number of shards	`src/rgw/driver/rados/rgw_reshard.cc :: RGWBucketReshard::calculate_preferred_shards, nearest_prime`	4
12	Number of entries requested from each shard in an ordered ListObjects	`src/rgw/driver/rados/rgw_rados.cc :: RGWRados::calc_ordered_bucket_list_per_shard, cls_bucket_list_ordered`	4
13	The layout of an S3 object in RADOS	`src/rgw/rgw_obj_manifest.cc :: RGWObjManifest::get_implicit_location; src/rgw/driver/rados/rgw_putobj_processor.cc :: AtomicObjectProcessor::prepare; src/rgw/driver/rados/rgw_obj_manifest.cc :: RGWObjManifest::generator::create_begin`	4
14	Choosing the datalog shard for a bucket shard	`src/rgw/driver/rados/rgw_datalog.cc :: RGWDataChangesLog::choose_oid`	5
15	Adding a datalog entry with the window and renew	`src/rgw/driver/rados/rgw_datalog.cc :: RGWDataChangesLog::add_entry, renew_entries, renew_run`	5
16	Choosing the mdlog shard for a metadata change	`src/rgw/driver/rados/rgw_sal_rados.cc (hash_key = section + ":" + key); src/rgw/driver/rados/rgw_metadata.cc :: rgw_shard_name, RGWMetadataLog::add_entry`	5
17	Trimming the datalog based on the lowest stable marker	`src/rgw/driver/rados/rgw_trim_datalog.cc :: DataLogTrimCR, take_min_markers, get_stable_marker`	5
18	Mapping a file byte to a RADOS object in the data pool	`src/osdc/Striper.cc :: Striper::file_to_extents; src/include/object.cc :: file_object_t::c_str; src/mds/InoTable.cc :: InoTable::reset_state`	6
19	Choosing the dirfrag for a dentry	`src/mds/CInode.cc :: InodeStoreBase::hash_dentry_name, pick_dirfrag; src/include/frag.h :: fragtree_t::operator[]; src/include/ceph_frag.h`	6
20	The split and merge decision for a dirfrag	`src/mds/MDBalancer.cc :: MDBalancer::hit_dir, maybe_fragment, queue_split; src/mds/CDir.cc :: CDir::should_split, should_split_fast, should_merge`	6
21	DecayCounter and the "hot" threshold	`src/common/DecayCounter.cc :: DecayCounter::decay; src/common/DecayCounter.h :: DecayRate`	6
22	The MON's decision to mark an OSD down	`src/mon/OSDMonitor.cc :: OSDMonitor::check_failure, get_grace_time, is_failure_stale`	7
23	Updating laggy_probability and laggy_interval	`src/mon/OSDMonitor.cc :: OSDMonitor::prepare_boot, grace_interval_threshold_exceeded, set_default_laggy_params`	7
24	Automatic marking out	`src/mon/OSDMonitor.cc :: OSDMonitor::tick (down_pending_out), can_mark_out; src/osd/OSDMap.cc :: containing_subtree_is_down`	7
25	Estimating a pool's usable space	`src/mon/PGMap.cc :: PGMap::get_rule_avail, dump_object_stat_sum; src/osd/OSDMap.cc :: pool_raw_used_rate`	7
26	Counting movement by comparing two mappings	`osdmaptool --test-map-pgs-dump before and after the change; bucket_straw2_choose and crush_choose_firstn in src/crush/mapper.c`	8
27	Classifying movements after a reweight	`crushtool --reweight-item (also updates the parents' weights); the same A and B comparison`	8
28	Password validation in the Dashboard	`src/pybind/mgr/dashboard/services/access_control.py :: PasswordPolicy.check_all, check_password_complexity, check_if_sequential_characters, check_if_repetitive_characters; src/pybind/mgr/dashboard/settings.py :: PWD_POLICY_*`	9
29	Checking scope and permission for each endpoint	`src/pybind/mgr/dashboard/services/auth/auth.py :: AuthManagerTool._check_authorization, JwtManager.gen_token, JwtManager.get_user; src/pybind/mgr/dashboard/services/access_control.py :: User.authorize, Role.authorize; src/pybind/mgr/dashboard/controllers/_rest_controller.py :: _permission_map`	9
30	Counting failed login attempts and disabling	`src/pybind/mgr/dashboard/controllers/auth.py :: Auth.create; src/pybind/mgr/dashboard/services/access_control.py :: AccessControlDB.increment_attempt, reset_attempt, get_attempt`	9
31	Measuring stats staleness	`measurement; mgr_stats_period in src/common/options/mgr.yaml.in`	9
32	The cost of each query in terms of PG count	`measurement; mgr_command('pg dump') and mon_command('status')`	9
33	Validating osd bench parameters	`src/osd/OSD.cc :: OSDBenchTest::precheck, OSDBenchTest::run_test (v21.2.0 and main); in v20.2.0 the same logic is in OSD::run_osd_bench_test`	10
34	The boot test and storing osd_mclock_max_capacity_iops	`src/osd/OSD.cc :: OSD::maybe_override_max_osd_capacity_for_qos`	10
35	Turning an mClock profile into byte reservations and limits	`src/common/mclock_common.cc :: MclockConfig::set_from_config, ClientRegistry::update_from_profile, MclockConfig::calc_scaled_cost; src/common/mclock_common.h :: HIGH_CLIENT_OPS, BALANCED, HIGH_RECOVERY_OPS (v21.2.0)`	10
36	The closed loop of rados bench and Little's law	`rados bench (src/common/obj_bencher.cc); L = X · R`	10
37	Placing daemons on hosts	`src/pybind/mgr/cephadm/schedule.py :: HostAssignment.place, get_candidates`	11
38	The DB/WAL slot size on the fast device	`src/ceph-volume/ceph_volume/devices/lvm/batch.py :: Batch.fast_allocations, get_physical_fast_allocs`	11
39	The upgrade order in cephadm	`src/pybind/mgr/cephadm/utils.py :: CEPH_UPGRADE_ORDER; src/pybind/mgr/cephadm/upgrade.py :: CephadmUpgrade._do_upgrade, _to_upgrade`	11
40	Maximising the ok-to-stop set	`src/mgr/DaemonServer.cc :: DaemonServer::_maximize_ok_to_stop_set, _check_offlines_pgs`	11
41	Accepting or rejecting a compressed blob	`src/os/bluestore/BlueStore.cc :: BlueStore::_do_alloc_write (want_len, result_len)`	12
42	The space allocated for an object	`src/os/bluestore/BlueStore.cc (min_alloc_size recorded in the superblock at mkfs); defaults bluestore_min_alloc_size_{hdd,ssd} = 4K in main`	12
43	Target level sizes with the default options	`src/common/options/global.yaml.in :: bluestore_rocksdb_options (max_bytes_for_level_base = 1 GiB, max_bytes_for_level_multiplier = 8)`	12
44	Reed-Solomon with a Vandermonde matrix in ISA (technique=reed_sol_van)	`src/erasure-code/isa/ErasureCodeIsa.cc :: ErasureCodeIsaDefault::prepare, isa_encode, isa_decode; ISA-L ec_base.c :: gf_gen_rs_matrix`	13
45	Checking whether the Vandermonde matrix is MDS	`src/erasure-code/isa/ErasureCodeIsa.cc :: ErasureCodeIsaDefault::parse (m > 4, or m = 4 and k > 21 ← cauchy)`	13
46	Parity-delta writes in FastEC	`src/erasure-code/isa/ErasureCodeIsa.cc :: encode_delta, apply_delta (ec_encode_data_update); src/osd/ECTransaction.cc (do_parity_delta_write)`	13
47	The read volume for rebuilding one chunk	`src/erasure-code/clay/ErasureCodeClay.cc :: parse (q = d − k + 1, t = (k+m+nu)/q, sub_chunk_no = qᵗ); src/erasure-code/lrc`	13
48	Budget calculation and the dual throttle	`src/osdc/Objecter.cc :: Objecter::calc_op_budget, _throttle_op; src/common/Throttle.h :: Throttle::_should_wait`	14
49	Throughput cap of one Objecter instance	`src/osdc/Objecter.cc :: _throttle_op (with the defaults of objecter_inflight_ops and objecter_inflight_op_bytes)`	14
50	Linger pings and watch expiry in the OSD	`src/osdc/Objecter.cc :: Objecter::tick, _send_linger_ping; src/osd/PrimaryLogPG.cc (CEPH_OSD_WATCH_OP_WATCH); src/osd/Watch.cc`	14
51	Determining the effective notify timeout	`src/librados/IoCtxImpl.cc :: IoCtxImpl::notify, aio_notify; src/osd/PrimaryLogPG.cc (CEPH_OSD_OP_NOTIFY)`	14
52	Checking the RD/WR flags before and after running a class method	`src/osd/osd_op_util.cc :: OpInfo::set_from_op (the CEPH_OSD_OP_CALL branch); src/osd/ClassHandler.cc :: ClassHandler::open_class, _get_class, in_class_list; src/osd/PrimaryLogPG.cc :: PrimaryLogPG::do_osd_ops`	15
53	Acquiring, renewing and expiring a lock in cls_lock	`src/cls/lock/cls_lock.cc :: lock_obj, read_lock; src/cls/lock/cls_lock_types.h :: LOCK_FLAG_MAY_RENEW, LOCK_FLAG_MUST_RENEW`	15
54	Paging in cls_cxx_map_get_vals	`src/osd/objclass.cc :: cls_cxx_map_get_vals; src/osd/PrimaryLogPG.cc :: do_osd_ops (CEPH_OSD_OP_OMAPGETVALS)`	15
55	Atomic increment with a class method	`src/cls/numops/cls_numops.cc :: add (cls_cxx_map_get_val, then cls_cxx_map_set_val); serialization by the PG lock in PrimaryLogPG`	15
56	The break-even point of processing next to the data	`measurement; clslua_read, clslua_stat and eval_json in src/cls/lua/cls_lua.cc`	15
57	Size of the Bloom filter in a HitSet	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::hit_set_create; src/osd/BloomHitSet.h :: BloomHitSet`	16
58	The grade table and object temperature	`src/osd/osd_types.h :: pg_pool_t::calc_grade_table, get_grade; src/osd/PrimaryLogPG.cc :: agent_estimate_temp, agent_maybe_evict; src/common/histogram.h :: pow2_hist_t::get_position_micro`	16
59	Computing evict_effort	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::agent_choose_mode`	16
60	Mapping a bucket to a lifecycle shard, and the workers' traversal	`src/rgw/rgw_lc.cc :: get_lc_index, get_bucket_lc_key, random_sequence, RGWLC::process; src/common/ceph_hash.cc :: ceph_str_hash_linux`	16
61	Computing expiry with rounding to midnight	`src/rgw/rgw_lc.cc :: obj_has_expired; src/include/utime.h :: utime_t::round_to_day`	16
62	Extra DB capacity in use_some_extra	`src/os/bluestore/BlueFS.h :: RocksDBBlueFSVolumeSelector (constructor, get_extra_level, get_hint_by_dir); src/os/bluestore/BlueStore.cc :: BlueStore::_open_bluefs (building the vselector)`	16
63	Choosing the authoritative info in peering	`src/osd/PeeringState.cc :: PeeringState::calculate_maxles_and_minlua, PeeringState::find_best_info`	17
64	Counting and reporting slow operations with exponential back-off	`src/common/TrackedOp.cc :: OpTracker::with_slow_ops_in_flight, OpTracker::check_ops_in_flight, visit_ops_in_flight`	17
65	Randomizing the time of shallow and deep scrubs	`src/osd/scrubber/scrub_job.cc :: ScrubJob::adjust_shallow_schedule, ScrubJob::adjust_deep_schedule, ScrubJob::guaranteed_offset; src/osd/scrubber/pg_scrubber.cc :: PgScrubber::populate_config_params`	17
66	Counting PG states during an event	`ceph pg dump pgs_brief (PGMap in the mgr); the state string from pg_state_string in src/osd/osd_types.cc`	17
67	The effect of losing k hosts before the OSDs are marked out	`up mapping from osdmaptool --test-map-pgs-dump; the min_size criterion in PeeringState (chapter 17)`	17
68	Updating the connection score in ConnectionTracker	`src/mon/ConnectionTracker.cc :: report_live_connection, report_dead_connection, get_total_connection_score; src/mon/Elector.cc :: ping_check, dead_ping`	18
69	Comparing proposals in ElectionLogic	`src/mon/ElectionLogic.cc :: connectivity_election_score, propose_connectivity_handler`	18
70	SimplePolicy: mapping and moving images	`src/tools/rbd_mirror/image_map/SimplePolicy.cc :: calc_images_per_instance, do_shuffle_add_instances, do_map; src/tools/rbd_mirror/image_map/Policy.cc :: can_shuffle_image; src/tools/rbd_mirror/ImageMap.cc :: schedule_rebalance_task`	18
71	Three-pass pg_autoscaler (up to v20.2.0)	`src/pybind/mgr/pg_autoscaler/module.py :: PgAutoscaler._calc_final_pg_target, nearest_power_of_two (tag v20.2.0)`	19
72	Optimal PG rounding with dynamic programming	`src/pybind/mgr/pg_autoscaler/module.py :: PgAutoscaler._find_optimal_pg_distribution, _calculate_final_pool_pg_target, get_dynamic_threshold, PoolGroup.update (tag v21.2.0)`	19
73	Weighted deviation and bal_score in calc_pg_upmaps	`src/osd/OSDMap.cc :: OSDMap::calc_pg_upmaps, calc_deviations, fill_overfull_underfull`	19
74	The balancer's path in upmap mode	`src/osd/OSDMap.cc :: calc_pg_upmaps; src/pybind/mgr/balancer/module.py; the same code in osdmaptool --upmap`	19
75	The pg_num and pgp_num controller in the mgr	`src/mgr/DaemonServer.cc :: adjust_pgs; the options target_max_misplaced_ratio = 0.05 (global.yaml.in) and mgr_max_pg_num_change = 128 (mgr.yaml.in)`	19
76	Mapping a value to a bucket in PerfHistogram	`src/common/perf_histogram.cc :: PerfHistogramCommon::get_bucket_for_axis, get_axis_bucket_ranges; src/osd/osd_perf_counters.cc :: op_hist_x_axis_config, op_hist_y_axis_config`	20
77	Metric cache and the stale policy	`src/pybind/mgr/prometheus/module.py :: MetricCollectionThread.collect, Module.config_notify, Root.metrics`	20
78	Detecting flapping with rate on a gauge	`monitoring/ceph-mixin/prometheus_alerts.yml :: CephOSDFlapping`	20
79	Deviation of each OSD's PG count from the device class average	`monitoring/ceph-mixin/prometheus_alerts.yml :: CephPGImbalance`	20
80	Predicting pool fill-up with linear regression	`monitoring/ceph-mixin/prometheus_alerts.yml :: CephPoolGrowthWarning; Prometheus :: predict_linear`	20
81	Choosing the OSDShard for a request	`src/osd/OSD.cc :: OSD::ShardedOpWQ::_enqueue, OSD::get_num_op_shards; src/osd/osd_types.h :: spg_t::hash_to_shard`	21
82	Automatic tuning of osd_memory_target	`src/pybind/mgr/cephadm/autotune.py :: MemoryAutotuner.tune; src/pybind/mgr/cephadm/serve.py :: CephadmServe._autotune_host_memory`	21
83	Splitting a write and the deferred decision in the classic path	`src/os/bluestore/BlueStore.cc :: BlueStore::_do_write_data, _do_write_big, _do_alloc_write`	21
84	Tagging and selecting requests in dmClock	`src/dmclock/src/dmclock_server.h :: RequestTag::RequestTag, tag_calc, PriorityQueueBase::do_next_request, reduce_reservation_tags; src/osd/scheduler/mClockScheduler.h`	21
85	Extracting each stage's time from dump_historic_ops	`TrackedOp::mark_event and OpRequest::mark_flag_point (src/common/TrackedOp.cc, src/osd/OpRequest.h); ReplicatedBackend::submit_transaction and do_repop_reply`	22
86	libaio batch submission with exponential backoff	`src/blk/aio/aio.cc :: aio_queue_t::submit_batch`	23
87	io_uring submission and reaping with two locks and epoll	`src/blk/kernel/io_uring.cc :: ioring_queue_t::submit_batch, ioring_queue, ioring_get_cqe, get_next_completed`	23
88	Exponential growth of append space	`src/common/buffer.cc :: buffer::list::append(const char*, unsigned), refill_append_space`	23
89	crc32c of zeros with jump matrices	`src/common/crc32c.cc :: ceph_crc32c_zeros, create_turbo_table (the crc_turbo_table[32][32] table)`	23
90	Adjusting a cached crc to a new seed	`src/common/buffer.cc :: buffer::list::crc32c; include/buffer_raw.h :: raw::get_crc, set_crc`	23
91	Choosing a range in AvlAllocator	`src/os/bluestore/AvlAllocator.cc :: AvlAllocator::_allocate, _pick_block_after, _pick_block_fits`	24
92	Computing fragmentation_rating	`src/os/bluestore/Allocator.cc :: Allocator::get_fragmentation_score`	24
93	AVL memory cap and moving ranges to bitmap	`src/os/bluestore/AvlAllocator.h :: AvlAllocator::_try_insert_range; src/os/bluestore/HybridAllocator_impl.h :: HybridAllocatorBase::allocate, _spillover_range`	24
94	Decoding and verifying the label	`bluestore_bdev_label_t::encode/decode in src/os/bluestore/bluestore_types.cc; _write_bdev_label with bl.crc32c(-1) in BlueStore.cc`	24
95	Insert and search in a skiplist	`rocksdb/memtable/inlineskiplist.h :: InlineSkipList::RandomHeight, FindGreaterOrEqual, Insert`	25
96	Forming a write group	`rocksdb/db/write_thread.cc :: WriteThread::JoinBatchGroup, EnterAsBatchGroupLeader, ExitAsBatchGroupLeader`	25
97	Splitting a WAL record into 32K blocks	`rocksdb/db/log_writer.cc :: log::Writer::AddRecord, EmitPhysicalRecord; db/log_format.h`	25
98	Key delta encoding and Seek within a block	`rocksdb/table/block_based/block_builder.cc :: BlockBuilder::AddWithLastKeyImpl, Finish; table/block_based/block.cc :: DataBlockIter::SeekImpl (BinarySeek); util/coding.h :: EncodeVarint32`	25
99	Cache-line-local Bloom	`rocksdb/util/bloom_impl.h :: FastLocalBloomImpl::ChooseNumProbes, AddHash, HashMayMatchPrepared; BloomMath::CacheLocalFpRate`	25
100	Computing level targets and the compaction score	`rocksdb/db/version_set.cc :: VersionStorageInfo::CalculateBaseBytes, ComputeCompactionScore, MaxInputLevel`	25
101	On-wire length of an msgr2.1 frame	`src/msg/async/frames_v2.h :: FrameAssembler::get_preamble_onwire_len, get_segment_onwire_len, get_epilogue_onwire_len, get_frame_onwire_len`	26
102	Nonce management in AES-128-GCM	`src/msg/async/crypto_onwire.cc :: rxtx_t::create_handler_pair, AES128GCM_OnWireTxHandler::reset_tx_handler, AES128GCM_OnWireRxHandler::reset_rx_handler`	26
103	The Worker event loop	`src/msg/async/Event.cc :: EventCenter::process_events, dispatch_event_external, wakeup; src/msg/async/Stack.cc :: NetworkStack::add_thread`	26
104	Distributing connections across Workers	`src/msg/async/Stack.cc :: NetworkStack::get_worker; Stack.h :: Worker::release_worker; AsyncConnection.cc :: AsyncConnection::_stop`	26
105	Resending and discarding messages after a reconnect	`src/msg/async/ProtocolV2.cc :: ProtocolV2::requeue_sent, discard_requeued_up_to, handle_reconnect_ok`	26
106	Multiplication with log/exp tables	`isa-l/erasure_code/ec_base.c :: gf_mul, gf_inv`	27
107	Vector multiplication with a nibble table (split-table)	`isa-l/erasure_code/ec_base.c :: gf_vect_mul_init_base, ec_init_tables_base and the assembly versions gf_*vect_dot_prod_avx2.asm`	27
108	Generating the ISA-L encoding matrix	`isa-l/erasure_code/ec_base.c :: gf_gen_rs_matrix, gf_gen_cauchy1_matrix; src/erasure-code/isa/ErasureCodeIsa.cc :: ErasureCodeIsaDefault::parse, prepare`	27
109	decode with Gauss-Jordan elimination in GF(2⁸)	`isa-l/erasure_code/ec_base.c :: gf_invert_matrix; src/erasure-code/isa/ErasureCodeIsa.cc :: ErasureCodeIsaDefault::isa_decode`	27
110	Parity update with a delta	`src/erasure-code/isa/ErasureCodeIsa.cc :: ErasureCodeIsaDefault::encode_delta, apply_delta; isa-l :: ec_encode_data_update`	27
111	Generating mapping and layers in LRC	`src/erasure-code/lrc/ErasureCodeLrc.cc :: ErasureCodeLrc::parse_kml`	27
112	Choosing the repair sub-chunks in Clay	`src/erasure-code/clay/ErasureCodeClay.cc :: ErasureCodeClay::parse, get_repair_subchunks, get_repair_sub_chunk_count`	27
113	Choosing in a uniform bucket with an incremental permutation	`src/crush/mapper.c :: bucket_perm_choose, bucket_uniform_choose`	28
114	Choosing in a list bucket	`src/crush/mapper.c :: bucket_list_choose`	28
115	Choosing in a tree bucket	`src/crush/mapper.c :: bucket_tree_choose; src/crush/builder.c :: crush_make_tree_bucket`	28
116	Greedy upmap selection with a score test	`src/osd/OSDMap.cc :: OSDMap::calc_pg_upmaps, calc_deviations, fill_overfull_underfull, try_pg_upmap, find_best_remap`	28
117	Multi-step descent with retry (MSR)	`src/crush/mapper.c :: crush_msr_do_rule, crush_msr_choose, crush_msr_descend, crush_msr_get_retry_value`	28
118	Splitting and merging extents in the striper	`net/ceph/striper.c :: ceph_file_to_extents, ceph_calc_file_object_mapping, lookup_last`	29
119	calc_target and the resend decision	`net/ceph/osd_client.c :: calc_target, target_should_be_paused, ceph_osds_changed; net/ceph/osdmap.c :: ceph_pg_is_split`	29
120	handle_timeout and handle_osds_timeout	`net/ceph/osd_client.c :: handle_timeout, handle_osds_timeout, send_linger_ping; include/linux/ceph/libceph.h (defaults)`	29
121	Acquiring the exclusive lock and pushing aside a dead owner	`drivers/block/rbd.c :: rbd_acquire_lock, rbd_try_acquire_lock, rbd_try_lock, find_watcher, rbd_request_lock`	29
122	Encoding and displaying caps	`fs/ceph/caps.c :: ceph_cap_string, gcap_string; include/linux/ceph/ceph_fs.h (CEPH_CAP_S, CEPH_CAP_G)`	29
123	Cooperative scheduling in the Seastar reactor	`seastar: reactor::run (used in src/crimson/osd/main.cc and the crimson_reactor_* options)`	30
124	Choosing the least-loaded core for a new PG	`src/crimson/osd/pg_map.cc :: PGShardMapping::get_or_create_pg_mapping`	30
125	Batching records in RecordSubmitter	`src/crimson/os/seastore/journal/record_submitter.cc :: RecordSubmitter::submit / flush_current_batch`	30
126	Choosing a segment to reclaim (greedy / cost-benefit / benefit)	`src/crimson/os/seastore/async_cleaner.cc :: SegmentCleaner::calc_gc_benefit_cost, get_next_reclaim_segment`	30
127	Detecting completion with the Phase Tag (walking the CQ)	`linux: drivers/nvme/host/pci.c :: nvme_poll_cq, nvme_cqe_pending, nvme_update_cq_head`	31
128	I/O splitting and DMA buffer allocation in NVMEDevice	`src/blk/spdk/NVMEDevice.cc :: write_split, make_read_tasks, SharedDriverQueueData::alloc_buf_from_pool`	31
129	Little's law for the required queue depth	`a queueing-theory result; in the code: max_queue_depth = io_queue_size − 1 in SharedDriverQueueData`	31
130	Choosing the replacement gateway (least loaded, with location priority)	`src/mon/NVMeofGwMap.cc :: NVMeofGwMap::find_failover_candidate, find_failover_gw_logic`	31
131	Randomized scrub scheduling (uniform for shallow, truncated normal for deep)	`src/osd/scrubber/scrub_job.cc :: ScrubJob::adjust_shallow_schedule, adjust_deep_schedule`	32
132	Choosing the chunk range, shrinking after preemption	`src/osd/scrubber/pg_scrubber.cc :: PgScrubber::select_range; preemption_data_t::adjust_left in pg_scrubber.h`	32
133	Choosing the authoritative copy in scrub	`src/osd/scrubber/scrub_backend.cc :: ScrubBackend::select_auth_object, possible_auth_shard`	32
134	Computing the recovery and backfill priority	`src/osd/PeeringState.cc :: get_recovery_priority, get_backfill_priority, clamp_recovery_priority`	32
135	Priority-based reservation grants with preemption	`src/common/AsyncReserver.h :: AsyncReserver::do_queues, preempt_one`	32
136	Choosing async recovery targets by cost	`src/osd/PeeringState.cc :: PeeringState::choose_async_recovery_replicated`	32
137	backfill as a merge-join over sorted hobjects	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::recover_backfill, scan_range, prep_backfill_object_push`	32
138	Mapping a PG to an op-queue shard	`src/osd/osd_types.h :: spg_t::hash_to_shard; src/osd/OSD.cc :: OSD::enqueue_op`	33
139	The sharded mempool counter	`src/common/mempool.cc :: get_num_shards, pick_a_shard_int; include/mempool.h :: pool_allocator::allocate`	33
140	Tuning the cache budget with feedback from the heap (tune_memory)	`src/common/PriorityCache.cc :: PriorityCache::Manager::tune_memory`	33
141	Dividing memory among caches in priority order with a weighted fair share	`src/common/PriorityCache.cc :: Manager::balance, balance_priority; BlueStore.h :: MempoolCache::request_cache_bytes`	33
142	Choosing the NUMA node for the OSD	`src/osd/OSD.cc :: OSD::set_numa_affinity`	33
143	The pg log length budget per PG	`OSDService::get_target_pg_log_entries in src/osd/OSD.cc; trimming in PeeringState::calc_trim_to with osd_pg_log_trim_min = 100`	33
144	Comparing two hobject_t values and the bitwise key	`src/common/hobject.cc :: cmp(const hobject_t&, const hobject_t&); src/common/hobject.h :: hobject_t::_reverse_bits, get_bitwise_key_u32`	34
145	Choosing the shard for an op	`src/osd/OSD.cc :: OSD::enqueue_op, OSD::ShardedOpWQ::_enqueue; src/osd/osd_types.h :: spg_t::hash_to_shard`	34
146	The op admission gates on the primary	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::do_request, do_op_impl`	34
147	Detecting duplicate requests with the pg log and dups	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::check_in_progress_op; src/osd/PGLog.h :: IndexedLog::get_request`	34
148	Setting version and user_version and building the log entry	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::execute_ctx, prepare_transaction, finish_ctx`	34
149	The key names of log and dup entries	`src/osd/osd_types.cc :: eversion_t::get_key_name, pg_log_dup_t::get_key_name; src/osd/osd_types.h :: infover_key, fastinfo_key`	34
150	Recording a past interval and determining maybe_went_rw	`src/osd/osd_types.cc :: PastIntervals::is_new_interval, PastIntervals::check_new_interval`	35
151	Building the prior set and detecting a down PG	`src/osd/osd_types.h :: PastIntervals::PriorSet::PriorSet; src/osd/osd_types.cc :: PastIntervals::iterate_mayberw_back_to`	35
152	merge_log: merging the authoritative log into the local log	`src/osd/PGLog.cc :: PGLog::merge_log, PGLog::rewind_divergent_log`	35
153	The five cases for handling an object's divergent entries	`src/osd/PGLog.h :: PGLog::_merge_object_divergent_entries`	35
154	The target log length and computing trim_to	`src/osd/OSD.cc :: OSDService::get_target_pg_log_entries; src/osd/PeeringState.cc :: PeeringState::calc_trim_to`	35
155	The recovery order in one round of start_recovery_ops	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::start_recovery_ops, recover_primary, recover_replicas, recover_backfill`	35
156	Comparing backfill intervals	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::recover_backfill, scan_range_primary, scan_range_replica`	35
157	make_writeable: creating a clone before the first write after a snapshot	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::make_writeable, _make_clone`	36
158	Mapping a snapid to a clone on read	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::find_object_context`	36
159	Trimming a clone for a deleted snap	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::trim_object; src/osd/SnapMapper.cc :: SnapMapper::get_next_objects_to_trim`	36
160	The watch lifecycle and notify completion	`src/osd/Watch.cc :: Watch::connect, Watch::got_ping, Notify::maybe_complete_notify, Notify::do_timeout`	36
161	Running a cls method inside the op transaction	`src/osd/PrimaryLogPG.cc :: PrimaryLogPG::do_osd_ops (case CEPH_OSD_OP_CALL); src/osd/ClassHandler.cc; src/osd/objclass.cc :: cls_cxx_*`	36
162	Mapping an image offset to (object, offset within the object)	`src/osdc/Striper.cc :: Striper::file_to_extents`	37
163	Computing each object's change state between two snapshots	`src/librbd/object_map/DiffRequest.cc :: DiffRequest::handle_load_object_map`	37
164	A write passing through the dispatch chain	`src/librbd/io/ImageDispatcher.cc; src/librbd/io/ObjectDispatcher.cc; src/librbd/io/ImageRequest.cc :: ImageWriteRequest; src/librbd/io/ObjectRequest.cc :: ObjectWriteRequest`	38
165	copyup: filling a clone object from the parent before the first write	`src/librbd/io/ObjectRequest.cc :: AbstractObjectWriteRequest::compute_parent_info, send_write, handle_write_object; src/librbd/io/CopyupRequest.cc; src/cls/rbd/cls_rbd.cc :: copyup`	38
166	Acquiring exclusive-lock and breaking a dead owner's lock	`src/librbd/ManagedLock.cc; src/librbd/managed_lock/AcquireRequest.cc, BreakRequest.cc, Utils.cc :: encode_lock_cookie; src/librbd/ExclusiveLock.cc`	38
167	The writearound layer	`src/librbd/cache/WriteAroundObjectDispatch.cc :: dispatch_io, block_overlapping_io, flush`	38
168	The token bucket in librbd QoS	`src/common/Throttle.cc :: TokenBucketThrottle::add_tokens, get; src/librbd/io/QosImageDispatch.cc`	38
169	Appending an event to the journal and choosing the object	`src/journal/JournalRecorder.cc :: JournalRecorder::append, get_object; src/journal/Entry.cc :: Entry::encode`	39
170	Writing with journaling: event first, then data	`src/librbd/Journal.cc :: append_write_event, append_io_event, commit_io_event; src/librbd/journal/ObjectDispatch.cc`	39
171	Replaying journal events in rbd-mirror	`src/tools/rbd_mirror/image_replayer/journal/Replayer.cc; EventPreprocessor.cc; src/librbd/journal/Replay.cc`	39
172	One replay round in snapshot mode	`src/tools/rbd_mirror/image_replayer/snapshot/Replayer.cc :: scan_local_mirror_snapshots, scan_remote_mirror_snapshots, copy_snapshots, create_non_primary_snapshot, copy_image, update_non_primary_snapshot, unlink_peer`	39
173	Leader election and assigning images to instances	`src/tools/rbd_mirror/LeaderWatcher.cc, InstanceWatcher.cc, ImageMap.cc, image_map/SimplePolicy.cc`	39
174	prepare and complete in the bucket index	`src/cls/rgw/cls_rgw.cc :: rgw_bucket_prepare_op, rgw_bucket_complete_op, rgw_dir_suggest_changes; src/rgw/driver/rados/rgw_rados.cc :: RGWRados::Bucket::UpdateIndex`	40
175	link_olh: adding a version and setting the current version	`src/cls/rgw/cls_rgw.cc :: rgw_bucket_link_olh; src/rgw/driver/rados/rgw_rados.cc :: RGWRados::set_olh, apply_olh_log`	40
176	Setting the head, chunk and stripe sizes for a PUT	`src/rgw/driver/rados/rgw_putobj_processor.cc :: AtomicObjectProcessor::prepare; src/rgw/rgw_obj_manifest.cc :: set_trivial_rule`	40
177	Multipart upload: init, part and complete	`src/rgw/driver/rados/rgw_sal_rados.cc :: RadosMultipartUpload::init, complete; src/rgw/driver/rados/rgw_putobj_processor.cc :: MultipartObjectProcessor::complete; src/rgw/rgw_multi.h`	40
178	The processing pipeline of a request	`src/rgw/rgw_process.cc :: process_request, rgw_process_authenticated; src/rgw/rgw_asio_frontend.cc`	41
179	Checking an AWS SigV4 signature	`src/rgw/rgw_auth_s3.cc :: get_v4_canonical_headers, get_v4_string_to_sign, get_v4_signing_key, get_v4_signature; src/rgw/rgw_auth_s3.h :: RGW_AUTH_GRACE`	41
180	Data flow in PUT and GET	`src/rgw/driver/rados/rgw_putobj_processor.cc; src/rgw/rgw_op.cc :: RGWPutObj::execute, RGWGetObj::execute; src/rgw/driver/rados/rgw_rados.cc :: get_obj_iterate`	41
181	Checking bucket and user quotas	`src/rgw/rgw_quota.cc :: RGWQuotaHandlerImpl::check_quota, RGWQuotaInfoDefApplier, RGWQuotaInfoRawApplier; src/rgw/rgw_common.h :: rgw_rounded_objsize`	41
182	A token bucket in each RGW	`src/rgw/rgw_ratelimit.h :: RateLimiterEntry; src/rgw/rgw_process.cc`	41
183	The gc queue and its processing	`src/rgw/driver/rados/rgw_gc.cc :: RGWGC::tag_index, send_chain, process; src/cls/rgw_gc`	41
184	Scheduling and running lifecycle	`src/rgw/rgw_lc.cc :: get_lc_index, RGWLC::process, bucket_lc_process, LCOpAction_*; src/rgw/rgw_lc.h`	41
185	Committing a period	`src/rgw/rgw_zone.cc :: commit_period; src/rgw/rgw_period.cc`	42
186	Incremental sync of a datalog shard	`src/rgw/driver/rados/rgw_data_sync.cc :: RGWDataSyncShardCR, RGWDataIncSyncShardCR, RGWDataSyncSingleEntryCR, RGWDataFullSyncShardCR`	42
187	Syncing a bucket shard and an object	`src/rgw/driver/rados/rgw_data_sync.cc :: RGWSyncBucketCR, RGWBucketFullSyncCR, RGWBucketShardIncrementalSyncCR, RGWObjFetchCR; src/rgw/driver/rados/rgw_rados.cc :: fetch_remote_obj, obj_time_weight`	42
188	metadata sync from the master zone	`src/rgw/driver/rados/rgw_sync.cc :: RGWMetaSyncCR, RGWMetaSyncShardCR, RGWMetaSyncSingleEntryCR`	42

List of Algorithms

My reading

Bookmarks