## 4 Design and Implementation
### High-Level Design
Otherwise, if the metadata persistence fails, the record is discarded. In Figure 3, the last four bits of the hash function's result play a critical role in determining the segment and bucket for record insertion. These bits serve as directory entries, allocated to segments by the hashing scheme. The metadata provides additional information to specify the exact bucket for record storage. Further details regarding the metadata are described in the subsequent section. **Metadata:** The metadata section in each bucket holds crucial information, such as the bucket's status, lock state, and overflow indicators, enabling fast access to the bucket. This valuable information, as shown in Figure 3, is essential for performing various operations. In the implementation, the metadata occupies 32 bytes of the total bucket size, as required for conducting the experiment. **Locking (lock)**: Locking ensures that a process remains in memory and imposes restrictions on access to a resource or bucket when multiple threads are executing. In real  
Figure 3: Overall architecture of bucket and segment structure for scalable hashing scheme. OFRB: overflow records address byte; OB: overflow bit; MC: membership counter; OC: overflow counter. time environments, it is crucial to guarantee the locking of a process in memory to minimize latency for data access, instruction fetches, buffer passing, and other operations. It serves the purpose of enforcing mutual exclusion and concurrency control. In the proposed scheme, the lock indicator is a metadata component that stores locking information for writer threads. Writer threads are required to acquire the lock by setting the lock bit to 1 before writing to the bucket, ensuring consistency. Once the first thread releases the lock and sets the lock bit back to 0, other threads can attempt to access the same bucket again. **State**: The state parameter is a Boolean flag that determines whether the system has been shut down properly. In certain scenarios, the hashing scheme may be left in an inconsistent state due to unexpected events such as power failure. When a process completes its operation on a bucket, it updates the state to 0, indicating that the flag is correct. When other threads access the same bucket, they check the state parameter. If the state is set to 1, it signifies that the prior process did not close the system correctly. In such cases, the data should be discarded or a recovery process should be initiated to restore consistency. **Overflow bit (OB)**: The overflow bit is a Boolean indicator used to determine the status of a bucket during insertion. It helps to identify whether the bucket is full or not. **Overflow records address byte (OFRB)**: In ESH, OFRB is used to store the address of a neighboring bucket where records are moved when the initial bucket becomes full. Instead of immediately triggering segment splitting or directory doubling, the scheme checks for available space in neighboring buckets within the same segment. By storing the record in a neighboring bucket, the OFRB holds the address of the bucket to which the record has been moved. This allows for easier search operations as it indicates the address of the bucket holding the record. **Overflow counter (OC)**: In ESH, OC is used to differentiate between records that are originally handed to a specific bucket and those that have been moved from neighboring buckets due to overflow. This differentiation is important to avoid confusion during search operations. When searching for records, the overflow counter indicates whether there are additional records stored in neighboring buckets that were moved due to overflow from the original bucket. If the overflow counter indicates that there are more records in the neighboring buckets, the search operation continues by reading the address stored in the OFRB to continue searching within the same segment.