Replies: 2 comments 4 replies
-
|
I almost forgot the main issue that motivated this entire development plan!! 🙂 Critical Performance Issue: Cache Validation Overhead1. The Problem: Current Cache Rendered Ineffective by Excessive ValidationThe directory cache implementation has a fundamental flaw that essentially breaks its intended purpose. Every cache lookup performs a stat() system call to validate the cached entry, defeating the benefit of having a cache. Current Implementation// From current etc/afpd/dircache.c - showing the problem
struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
{
struct dir key;
struct stat st;
hnode_t *hn;
// ... cache lookup code ...
if (cdir) {
// PROBLEM: This stat() happens on EVERY cache hit!
if (ostat(cfrombstr(cdir->d_fullpath), &st, vol_syml_opt(vol)) != 0) {
LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {missing:\"%s\"}",
ntohl(cnid), cfrombstr(cdir->d_fullpath));
(void)dir_remove(vol, cdir);
dircache_stat.expunged++;
return NULL;
}
// PROBLEM: Validation happens EVERY time, negating cache benefits!
if ((cdir->dcache_ctime != st.st_ctime) || (cdir->dcache_ino != st.st_ino)) {
LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {modified:\"%s\"}",
ntohl(cnid), cfrombstr(cdir->d_u_name));
(void)dir_remove(vol, cdir);
dircache_stat.expunged++;
return NULL;
}
dircache_stat.hits++;
}
return cdir;
}Impact: The current cache implementation provides minimal benefit—it only saves object reconstruction, but the expensive stat() I/O still occurs on every access. 2. Recommended Solution: Intelligent Probabilistic ValidationImplement a multi-layered optimization strategy that dramatically reduces stat() calls while maintaining data consistency. Core Strategy Components
3. Key Code Examples: Problem and SolutionThe Fix: Probabilistic Validation// New validation strategy
static unsigned long validation_counter = 0;
static unsigned int dircache_validation_freq = DEFAULT_DIRCACHE_VALIDATION_FREQ; // Default: 5
static int should_validate_cache_entry(void)
{
validation_counter++;
/* Validate every Nth access to detect external changes */
if (dircache_validation_freq == 0) {
return 1; /* Always validate if freq is 0 (invalid config) */
}
return (validation_counter % dircache_validation_freq == 0);
}
// Modified lookup function with optimization
struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
{
// ... cache lookup ...
if (cdir) {
// Files found when expecting directories are always invalid
if (cdir->d_flags & DIRF_ISFILE) {
LOG(log_debug, logtype_afpd,
"dircache(cnid:%u): {not a directory:\"%s\"}",
ntohl(cnid), cfrombstr(cdir->d_u_name));
(void)dir_remove(vol, cdir);
dircache_stat.expunged++;
return NULL;
}
/*
* OPTIMIZATION: Skip validation most of the time.
* Internal netatalk operations invalidate cache explicitly.
* Periodic validation catches external filesystem changes.
*/
if (should_validate_cache_entry()) {
/* Check if file still exists */
if (ostat(cfrombstr(cdir->d_fullpath), &st, vol_syml_opt(vol)) != 0) {
LOG(log_debug, logtype_afpd,
"dircache(cnid:%u): {missing:\"%s\"}",
ntohl(cnid), cfrombstr(cdir->d_fullpath));
(void)dir_remove(vol, cdir);
dircache_stat.expunged++;
return NULL;
}
/* Smart validation: distinguish meaningful changes */
if (cache_entry_externally_modified(cdir, &st)) {
LOG(log_debug, logtype_afpd,
"dircache(cnid:%u): {externally modified:\"%s\"}",
ntohl(cnid), cfrombstr(cdir->d_u_name));
(void)dir_remove(vol, cdir);
dircache_stat.expunged++;
return NULL;
}
}
// Most cache hits now avoid the stat() call entirely!
dircache_stat.hits++;
}
return cdir;
}4. Detailed Optimization Components4.1 Probabilistic ValidationConcept: Validate cached entries only periodically, not on every access.
4.2 Intelligent Change Detectionstatic int cache_entry_externally_modified(struct dir *cdir, const struct stat *st)
{
AFP_ASSERT(cdir);
AFP_ASSERT(st);
/* Inode number changed means file was deleted and recreated */
if (cdir->dcache_ino != st->st_ino) {
LOG(log_debug, logtype_afpd,
"dircache: inode changed for \"%s\" (%llu -> %llu)",
cfrombstr(cdir->d_u_name),
(unsigned long long)cdir->dcache_ino,
(unsigned long long)st->st_ino);
return 1; // Invalidate
}
/* No ctime change means no external modification */
if (cdir->dcache_ctime == st->st_ctime) {
return 0; // Still valid
}
/* Files: any ctime change is significant */
if (cdir->d_flags & DIRF_ISFILE) {
LOG(log_debug, logtype_afpd,
"dircache: file ctime changed for \"%s\"",
cfrombstr(cdir->d_u_name));
return 1; // Invalidate
}
/*
* Directories: ctime changes for multiple reasons:
* 1. Content changes (files added/removed) - should invalidate
* 2. Metadata changes (permissions, xattrs) - should NOT invalidate
* 3. Subdirectory changes - should NOT invalidate parent
*
* Heuristic: Recent, small ctime changes are likely metadata-only.
*/
time_t now = time(NULL);
time_t ctime_age = now - st->st_ctime;
time_t ctime_delta = st->st_ctime - cdir->dcache_ctime;
if (ctime_age <= dircache_metadata_window &&
ctime_delta <= dircache_metadata_threshold) {
/*
* Recent, small change - likely metadata update.
* Update cached ctime to prevent repeated checks and continue.
*/
LOG(log_debug, logtype_afpd,
"dircache: metadata-only change detected for \"%s\", updating cached ctime",
cfrombstr(cdir->d_u_name));
cdir->dcache_ctime = st->st_ctime;
return 0; // Keep cached
}
/* Significant change - assume content modification */
LOG(log_debug, logtype_afpd,
"dircache: significant change detected for \"%s\" (age=%lds, delta=%lds)",
cfrombstr(cdir->d_u_name), (long)ctime_age, (long)ctime_delta);
return 1; // Invalidate
}4.3 Time-based Heuristics for Directory ModificationsDirectories require special handling because their ctime changes for many reasons that don't affect cached data:
4.4 New Configuration Parameters// From include/atalk/globals.h
#define DEFAULT_DIRCACHE_VALIDATION_FREQ 5 /* Validate every Nth access */
#define DEFAULT_DIRCACHE_METADATA_WINDOW 300 /* Metadata change window (seconds) */
#define DEFAULT_DIRCACHE_METADATA_THRESHOLD 60 /* Metadata change threshold (seconds) */Configuration in [Global]
# How often to validate cached entries (1 = every access, 10 = every 10th access)
dircache validation freq = 5
# Time window for distinguishing metadata-only changes (seconds)
dircache metadata window = 300
# Maximum ctime delta to consider as metadata-only change (seconds)
dircache metadata threshold = 604.5 Performance GainsImprovements already validated using proposed default settings with proof-of-concept stash (motivating this entire development plan):
Configurable profiles:
5. Critical Design PrinciplesInternal vs External Change HandlingInternal Netatalk Operations:
External Changes:
Different Handling for Files vs DirectoriesFiles (Strict):
Directories (Smart Heuristics):
Implementation ImpactThis optimization transforms the directory cache from a minimal-benefit component into a high-performance acceleration layer:
The implementation maintains full backward compatibility through configuration options while providing substantial performance improvements for modern deployments. |
Beta Was this translation helpful? Give feedback.
-
|
A few comments after skimming through this! The overall approach seems sound to me. I think it will be key to establish a current performance baseline and then validate the new behavior in an empirical fashion. Have you thought about how to simulate organic usage scenarios? You can only get so long with invariant tests. I'm a fan of fuzz testing! And speaking of testing: love the idea of doing unit testing. The one C unit testing library I have hands-on experience with is libcheck. Do you have other suggestions? Agreed that multi-threaded optimization is a very low priority right now, since netatalk isn't currently a threaded application. Sections 6 and 7 have overlapping migration plans – which one is you aiming for right now? |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Hi team, I have prepared a development plan for dircache.c which I would like peer review?
Comprehensive Performance Analysis of dircache.c
Executive Summary
The dircache.c file implements a directory cache system for AFP (Apple Filing Protocol) with three main index structures: a hash table for DID lookups, a hash table for name lookups, and an LRU queue. While the implementation is functional, there are several significant performance bottlenecks and opportunities for optimization.
Current Implementation Analysis
1. Data Structure Performance
Hash Tables
LRU Queue
2. Critical Performance Bottlenecks
2.1 Hash Function Quality
Note: The current implementation already uses FNV-1a hashing (dircache.c lines 128-145), which is a good hash function. The main remaining issues are:
2.2 Linear Search in Hash Buckets
Problems:
2.3 Memory Allocation Patterns
Problems:
2.4 String Operations
Problems:
3. Algorithmic Complexity Analysis
4. Memory Usage Analysis
Current Memory Overhead
Performance Improvement Recommendations
1. Immediate Optimizations (High Impact, Low Risk)
1.1 Enhance Existing Performance Metrics (Do First)
Current Implementation (dircache.c lines 117-125, 618-630):
Current Emission Method:
LOG()macro to the AFP daemon logRecommended Enhancements:
Implementation Notes:
dircache_statstructure1.2 Verify Hash Function Effectiveness
Note: The current implementation already uses FNV-1a (dircache.c lines 128-145).
1.3 Add Memory Pool for Directory Entries
1.4 Implement Bloom Filter for Negative Lookups
2. Medium-Term Optimizations (Moderate Impact, Moderate Risk)
2.1 Replace Hash Table with Robin Hood Hashing
2.2 Implement Adaptive Resizing
2.3 Add Fast Path for Recent Lookups
3. Advanced Optimizations (High Impact, Higher Risk)
3.1 Lock-Free Data Structures (for multi-threaded scenarios) - This is questionable, adding mainly for discussion
3.2 SIMD Optimizations for Batch Operations
3.3 Hierarchical Caching
4. Configuration and Tuning Recommendations
4.1 Make Cache Parameters Configurable
5. Memory Optimization Strategies
5.1 Reduce Memory Fragmentation
5.2 Improve Cache Locality
5.3 Compressed Storage for Names
6. Adaptive Replacement Cache (ARC) Analysis and Implementation
ARC reference paper ARC.pdf
6.1 Overview of ARC Algorithm
The Adaptive Replacement Cache (ARC) algorithm, developed by IBM Research (Megiddo and Modha, 2003), represents a significant advancement over traditional LRU caching. ARC provides a self-tuning, scan-resistant cache replacement policy that automatically adapts to varying workload patterns without requiring manual tuning.
Key Advantages Over Current LRU Implementation:
6.2 ARC Algorithm Fundamentals
ARC maintains four lists to track both cached and recently evicted entries:
The algorithm dynamically adjusts the target size
pfor T1, with T2 getting the remainingc - pentries, wherecis the total cache size.6.3 Detailed ARC Implementation Design for dircache
6.3.1 Core Data Structures
6.3.2 Core ARC Operations
6.4 Performance Analysis and Projections
6.4.1 Expected Performance Improvements
Based on empirical studies and the specific characteristics of AFP directory access patterns:
6.4.2 Memory Overhead Analysis
6.5 Implementation Strategy
Phase 1: Preparation (Week 1)
Phase 2: Core Implementation (Weeks 2-3)
Phase 3: Integration (Week 4)
Phase 4: Optimization (Week 5)
6.6 Configuration and Tuning
6.7 Monitoring and Observability
6.8 Testing and Validation
6.8.1 Unit Tests
6.8.2 Performance Benchmarks
6.9 Scalability for Large Memory Systems
Current Limitations
The current implementation has a hard limit (anything laarger and the cache becomes too inefficent to be useful) of
MAX_POSSIBLE_DIRCACHE_SIZE = 131072entries (dircache.h line 24), which translates to approximately:This is inadequate for modern systems with abundant memory.
ARC Scalability Recommendations
Benefits of Large ARC Caches
Scaling Considerations
Hash Table Sizing: Must scale with cache size
Ghost List Management: Ghost lists should be capped
Memory Pressure Handling:
Performance at Scale:
Recommended Configuration
Memory/Performance Trade-off Analysis
For a file server with 1 million files and 100,000 directories:
Conclusion: For systems with adequate memory (>8GB), configuring ARC caches of 256K-1M entries provides performance improvements for more of the working set with modest memory usage (45-180MB). The ARC algorithm's self-tuning nature makes it particularly effective at these scales, automatically adapting to workload patterns.
6.11 Example Implementation Comparison
7. Implementation Roadmap
7.1 Phased Implementation Approach
Based on the comprehensive analysis, the recommended implementation follows a data-driven approach:
Phase 0 - Measurement Foundation (3-5 days)
Phase 1 - Quick Wins (1-2 weeks)
Phase 2 - ARC Preparation (2-3 weeks)
Phase 3 - ARC Implementation (3-4 weeks)
Phase 4 - Production Rollout (2-3 weeks)
7.2 Expected Benefits
The ARC implementation will provide:
7.3 Risk Mitigation
7.4 Final Recommendation
The implementation of ARC for the dircache represents a significant but worthwhile investment. The expected performance improvements, particularly for scan-heavy workloads common in AFP operations, justify the implementation effort. The self-tuning nature of ARC will also reduce operational overhead and improve system reliability.
8. Implementation Priority Matrix
9. Benchmark Recommendations
Key Metrics to Track
Suggested Benchmark Scenarios
10. Code Quality Improvements
10.1 Add Consistent Error Handling
10.2 Improve Logging and Debugging
10.3 Add Invariant Checking
11. Testing Recommendations
Unit Tests Needed
Performance Tests
12. Final Conclusion
The current dircache implementation already includes several optimizations:
Building on this foundation, the highest priority improvements should be:
These changes can improve performance by 2-5x for typical workloads while maintaining backward compatibility. The ARC implementation specifically offers the most significant long-term benefits through its self-tuning capabilities and superior handling of diverse access patterns.
Appendix: ARC Implementation Example
This comprehensive analysis presents a clear roadmap for improving the dircache implementation, from immediate quick wins to advanced adaptive caching strategies. The recommended approach balances performance gains with implementation complexity, ensuring each optimization delivers measurable value while maintaining system stability.
The key insight is that significant optimizations are already present (FNV-1a hashing, batch eviction, basic metrics), but there remains substantial room for improvement through enhanced measurement, memory pooling, and ultimately the implementation of the ARC algorithm for adaptive caching behavior.
Beta Was this translation helpful? Give feedback.
All reactions