Debian Codegraph @

cram/README

raw
1 CRAM encoding internals
2 =======================
3
4 A quick summary of functions involved.
5
6 The encoder works by accumulating a bunch of BAM records (via the
7 cram_put_bam_seq function), and at a certain point (eg counter of
8 records, or switching reference) the array of BAM records it turned
9 into a container, which in turn creates slices, holding CRAM
10 data-series in blocks. The function that turns an array of BAM
11 objects into the container is below.
12
13 cram_encode_container func:
14 Validate references MD5 against header, unless no_ref mode
15 If embed_ref <= 1, fetch ref
16 Switch to embed_ref=2 if failed
17
18 Foreach slice:
19 If embed_ref == 2
20 call cram_generate_reference
21 if failed switch to no_ref mode
22 Foreach sequence
23 call process_one_read to append BAM onto each data series (DS)
24 call cram_stats_add for each DS to gather metrics
25 call cram_encode_aux
26
27 # We now have cram DS, per slice
28 call cram_encoder_init, per DS (based on cram_stats_add data)
29
30 Foreach slice:
31 call cram_encode_slice to turn DS to blocks
32 call cram_compess_slice
33
34 call cram_encode_compression_header
35
36 Threading
37 ---------
38
39 CRAM can be multi-threaded, but this brings complications.
40
41 The above function is the main CPU user, so it is this bit which can
42 be executed in parallel from multiple threads. To understand this we
43 need to now look at how the primary loop works when writing a CRAM:
44
45 Encoding main thread:
46 repeatedly calls cram_put_bam_seq
47 calls cram_new_container on first time through to initialise
48 calls cram_next_container when current is full or we need to flush
49 calls cram_flush_container_mt to flush last container
50 pushes BAM object onto current container
51
52 If non-threaded, cram_flush_container_mt does:
53 call cram_flush_container
54 call cram_encode_container to go from BAM to CRAM data-series
55 call cram_flush_container2 (writes it out)
56
57 If threaded, cram_flush_container_mt does:
58 Main: Dispatch cram_flush_thread job
59 Thread: call cram_encode_container to go from BAM to CRAM data-series
60 Main: Call cram_flush_result to drain queue of encoded containers
61 Main: Call cram_flush_container2 (writes it out);
62
63
64
65 Decisions on when to create new containers, detection of sorted vs unsorted,
66 switching to multi-seq mode, etc occur at the main thread in
67 cram_put_bam_seq.
68
69 We can change our mind on container parameters at any point up until
70 the cram_encode_container call. At that point these parameters get
71 baked into a container compression header and all data-series
72 generated need to be in sync with the parameters.
73
74 It is possible that some parameter changes can get detected while
75 encoding the container, as it is there where we fetch references. Eg
76 the need to enable embedded reference or switch to non-ref mode.
77
78 While encoding a container, we can change the parameters for *this*
79 container, and we can also set the default parameter for subsequent
80 new parameters via the global cram fd to avoid spamming attempts to
81 load a reference which doesn't exist, but we cannot change other
82 containers that are being processed in parallel. They'll fend for
83 themselves.
84
85 References
86 ----------
87
88 To avoid spamming the reference servers, there is a shared cache of
89 references being currently used by all the worker threads (leading to
90 confusing terminology of reference-counting of references). So each
91 container fetches its section of reference, but the memory for that is
92 handled via its own layer.
93
94 The shared references and ref meta-data is held in cram_fd -> refs (a
95 refs_t pointer):
96
97 // References structure.
98 struct refs_t {
99 string_alloc_t *pool; // String pool for holding filenames and SN vals
100
101 khash_t(refs) *h_meta; // ref_entry*, index by name
102 ref_entry **ref_id; // ref_entry*, index by ID
103 int nref; // number of ref_entry
104
105 char *fn; // current file opened
106 BGZF *fp; // and the hFILE* to go with it.
107
108 int count; // how many cram_fd sharing this refs struct
109
110 pthread_mutex_t lock; // Mutex for multi-threaded updating
111 ref_entry *last; // Last queried sequence
112 int last_id; // Used in cram_ref_decr_locked to delay free
113 };
114
115 Within this, ref_entry is the per-reference information:
116
117 typedef struct ref_entry {
118 char *name;
119 char *fn;
120 int64_t length;
121 int64_t offset;
122 int bases_per_line;
123 int line_length;
124 int64_t count; // for shared references so we know to dealloc seq
125 char *seq;
126 mFILE *mf;
127 int is_md5; // Reference comes from a raw seq found by MD5
128 int validated_md5;
129 } ref_entry;
130
131 Sharing of references to track use between threads is via
132 cram_ref_incr* and cram_ref_decr* (which locked and unlocked
133 variants). We free a reference when the usage count hits zero. To
134 avoid spamming discard and reload in single-thread creation of a
135 pos-sorted CRAM, we keep track of the last reference in cram_fd and
136 delay discard by one loop iteration.
137
138 There are complexities here around whether the references come from a
139 single ref.fa file, are from a local MD5sum cache with one file per
140 reference (mmapped), or whether they're fetched from some remote
141 REF_PATH query such as the EBI. (This later case typically downloads
142 to a local md5 based ref-cache first and mmaps from there.)
143
144 The refs struct start off by being populated from the SAM header. We
145 have M5 tag and name known, maybe a filename, but length is 0 and seq
146 is NULL. This is done by cram_load_reference:
147
148 cram_load_reference (cram_fd, filename):
149 if filename non-NULL
150 call refs_load_fai
151 Populates ref_entry with filename, name, length, line-len, etc
152 sanitise_SQ_lines
153 If no refs loaded
154 call refs_from_header
155 populates ref_entry with name.
156 Sets length=0 as marker for not-yet-loaded
157
158 The main interface used from the code is cram_get_ref(). It takes a
159 reference ID, start and end coordinate and returns a pointer to the
160 relevant sub-sequence.
161
162 cram_get_ref:
163 r = fd->refs->ref_id[id]; // current ref
164 call cram_populate_ref if stored length is 0 (ie ref.fa set)
165 search REF_PATH / REF_CACHE
166 call bgzf_open if local_path
167 call open_path_mfile otherwise
168 copy to local REF_CACHE if required (eg remote fetch)
169
170 If start = 1 and end = ref-length
171 If ref seq unknown
172 call cram_ref_load to load entire ref and use that
173
174 If ref seq now known, return it
175
176 // Otherwise known via .fai or we've errored by now.
177 call load_ref_portion to return a sub-seq from index fasta
178
179 The encoder asks for the entire reference rather than a small portion
180 of it as we're usually encoding a large amount. The decoder may be
181 dealing with small range queries, so it only asks for the relevant
182 sub-section of reference as specified in the cram slice headers.
183
184
185 TODO
186 ====
187
188 - Multi-ref mode is enabled when we have too many small containers in
189 a row.
190
191 Instead of firing off new containers when we switch reference, we
192 could always make a new container after N records, separating off
193 M <= N to make the container such that all M are the same reference,
194 and shuffling any remaining N-M down as the start of the next.
195
196 This means we can detect how many new containers we would create,
197 and enable multi-ref mode straight away rather than keeping a recent
198 history of how many small containers we've emitted.
199
200 - The cache of references currently being used is a better place to
201 track the global embed-ref and non-ref logic. Better than cram_fd.
202 Cram_fd is a one-way change, as once we enable non-ref we'll stick
203 with it.
204
205 However if it was per-ref in the ref-cache then we'd probe and try
206 each reference once, and then all new containers for that ref would
207 honour the per-ref parameters. So a single missing reference in the
208 middle of a large file wouldn't change behaviour for all subsequence
209 references.
210
211 Optionally we could still do meta-analysis on how many references
212 are failing, and switch the global cram_fd params to avoid repeated
213 testing of reference availability if it's becoming obvious that none
214 of them are known.